Jakie jest znaczenie odwrotnej notacji polskiej?

21

Uczę informatyki dla 18-latków. Po wyjaśnieniu im odwrotnej notacji polskiej zapytano, dlaczego udział w publicznym egzaminie jest wystarczająco ważny. Wyjaśniłem historyczne znaczenie kalkulatorów z lat 70., ale tak naprawdę nie rozwiązało to problemu. Istnieją też praktyczne i teoretyczne zastosowania RPN.

Matt Scott
źródło
3
Programuję od prawie dziesięciu lat i ukończyłem studia magisterskie w CS, ale nie sądzę, żebym kiedykolwiek widział lub używał odwrotnego polerowania w jakimkolwiek poważnym kontekście. Czy jesteś pewien, że ma to znaczenie, zwłaszcza w przypadku nauczania uczniów?
Raphael
Oto implementacja silnika wyrażeń regularnych, który używa notacji postfiksowej: swtch.com/~rsc/regexp/regexp1.html#thompson . Ken Thompson wykorzystał go również w swojej pierwszej implementacji. Jest to również popularna technika oceny wyrażeń w czasie wykonywania (jeśli budujesz kompilator).
saadtaame
W RPN możesz zapisać dowolne wyrażenie bez użycia nawiasów.
Seg Fault
3
Artykuł w Wikipedii na temat RPN obejmuje wiele dziedzin. Teksty logiczne czasami odnoszą się do notacji polskiej (ponieważ nie zawiera nawiasów), kiedy wyjaśniają, co można pominąć w dowodach jako czysty „cukier syntaktyczny”. RPN jest jednak ważny ze względu na bliski związek ze stosami. Zrozumienie stosów jest ważne dla interaktywnego debugowania, ponieważ słynny „ślad” jest zwykle tylko zrzutem stosu. Czysto funkcjonalne języki wciąż mają trudności z oferowaniem czegoś podobnego do zrzutu stosu do debugowania, nawet jeśli miałyby do zaoferowania znacznie bardziej szczegółowe informacje (gdyby mogły to reprezentować).
Thomas Klimpel,
Muszę częściowo wycofać mój poprzedni komentarz. I nie widział ktoś use post-fix notacji drzew string-nora. Czytanie było okropne, ale łatwe do kodowania. Dlatego w bardzo szczególnych przypadkach użycia RP może być przydatne, ale nie jestem pewien, czy dotyczy to edukacji (ogólnie). Można go użyć, aby pokazać, że składnia nie jest naprawiona, tak myślę.
Raphael

Odpowiedzi:

9

Użyłem RPN kilka razy do szybkiego prototypowania, np. Programów, które muszą czytać i interpretować wyrażenia matematyczne dostarczone przez użytkownika.

Podczas gdy zwykła notacja matematyczna wymagałaby przynajmniej parsera rekurencyjnego (nawiasy klamrowe, kolejność operatorów itp.), Parser RPN jest w zasadzie stosem z switchinstrukcją podobną. Wydaje mi się, że to połączenie prostoty i ekspresyjnej mocy sprawiło, że HP początkowo z niej skorzystał.

Jest to jednak zazwyczaj w celu szybkiego prototypowania i dla wygody. Nigdy nie zakładałbym, że użytkownik może zrozumieć lub chce zrozumieć RPN.

Pedro
źródło
8

Aby rozwinąć poprzednie odpowiedzi / komentarze: nie zapominaj, że RPN żyje i jest w świetnej formie ... w rzeczywistości jest obecnie używany na maszynach stosowych, takich jak wirtualna maszyna Java.

Z Wikipedii: „... maszyna stosu implementuje stos z rejestrami. Operandy jednostki logicznej arytmetycznej (ALU) są zawsze dwoma górnymi rejestrami stosu, a wynik z ALU jest przechowywany w górnym rejestrze stosu „Maszyna stosu” zwykle odnosi się do komputerów, które używają stosu Last-First-First-Out do przechowywania krótkotrwałych wartości tymczasowych podczas wykonywania indywidualnych instrukcji programu. Zestaw instrukcji wykonuje większość akcji ALU z operacjami postfiks ( odwrotna notacja polska ) , które działa tylko na stosie wyrażeń, a nie na rejestrach danych lub głównych komórkach pamięci ... ”

Te zalety / wady takiego podejścia są również opisane w artykule Wikipedia .

Vor
źródło
Hm, patrząc na kod bajtowy, nie widzisz RPN per se; oczywiście instrukcje pojawiają się w kolejności „po naprawie”, ale nie wygląda to na RPN w arytmetyce, a jej powód jest raczej jasny. Rejestracja maszyn musi przebiegać w ten sam sposób: załadować wartości, a następnie połączyć.
Raphael
5

Dalej i PostScript (a zatem PDF, który IIRC zaczął jako kodowanie binarne podzbioru PostScript), są bardziej znanymi językami postfiksowymi niż jeden kieszonkowy kalkulator HP.

Jest to również stosunkowo powszechny wybór jako reprezentacja pośrednia w prostych kompilatorach.

Prostsza maszyna wirtualna zwykle ma również język maszynowy z postfiksem.

AProgrammer
źródło
Nawiasem mówiąc, wyrażenie „prostsza maszyna wirtualna” obejmuje maszynę JVM. Co ciekawe w RPN, jest to najprostsza użyteczna maszyna stosowa. Maszyny do układania w stosy są naprawdę interesujące, użyteczne i odpowiednie.
pseudonim
4

W odniesieniu do kalkulatorów: Zobacz Co to jest RPN?

  • Korzyści: RPN oszczędza czas i naciśnięcia klawiszy. Podczas wykonywania obliczeń unikasz używania i śledzenia nawiasów. Proces ten jest podobny do sposobu, w jaki nauczyłeś się matematyki na papierze.

  • Możesz zobaczyć wyniki pośrednie podczas wykonywania obliczeń, a nie tylko odpowiedź na końcu. Jest to niezwykle pomocne w nauce logiki. Nauczyciele matematyki używają tej funkcji do lepszego zrozumienia matematyki przez uczniów.

  • Wynik pośredni pozwala użytkownikowi łatwiej sprawdzić odpowiedź i poprawić błędy. Łatwiej jest śledzić strumień obliczeń. Użytkownik określa priorytet operatorów.

  • RPN jest logiczne, ponieważ użytkownik najpierw podaje numer, a następnie mówi, co z nim zrobić.

Guy Coder
źródło
3

Jak sama nazwa wskazuje, odwrotna notacja polska lub bezpośrednia notacja polska to notacje. Są one składnią do reprezentowania czegoś i faktycznie efektywną składnią, jeśli weźmie się pod uwagę wymagania dotyczące pamięci. Reprezentują one drzewa ukorzenione, którymi mogą być formuły, abstrakcyjne drzewa składniowe (AST) i inne rodzaje bytów, które każdy ma prawo konstytucyjne uważać za absolutnie bezużyteczne.

Czasami trzeba przechowywać takie byty w aktach. Na przykład istnieją systemy, które mogą edytować lub przekształcać programy jako AST i mogą wymagać przechowywania takich reprezentacji. Formularz polski jest wygodny. Ma ograniczoną czytelność dla ludzi, szczególnie dla dużych drzew, ale jest bardzo wygodną reprezentacją dla maszyn.

Innym aspektem jest to, że uważam, że badanie drzew i ich podstawowych zastosowań i reprezentacji, a także powiązanych urządzeń (stosów), jest pedagogicznie użyteczne jako wprowadzenie do przyszłych badań bardziej zaawansowanych pojęć (składnia, parsowanie, logika, językoznawstwo) , ...).

Ma również tę zaletę, że jest koncepcyjnie raczej prosty i łatwy do eksperymentowania na papierze. Jest to również dobra okazja do omówienia składni i faktu, że składnia jest reprezentacją, i że reprezentacje mogą się różnić, jednocześnie reprezentując to samo, i że można zastosować różne reprezentacje w zależności od potrzeby, którą należy spełnić (optymalizacja przestrzeni, łatwa modyfikacja, czytelność człowieka, czytelność komputera, ...).

Ale jestem zaskoczony, że to pytanie i jego odpowiedzi rozważają tylko RPN i żadne nie bierze pod uwagę bezpośredniego zapisu polskiego.

To z pewnością wspaniałe, o co pytają studenci. Ale odpowiedź na takie pytanie zawsze ma różnorodne aspekty. Czy jest to przydatne dla samej wiedzy? Myślę, że to jest. Czy jest to przydatne jako ćwiczenie pedagogiczne? Myślę, że tak, ale to zależy w dużej mierze od docelowej publiczności i tylko nauczyciel może ocenić, co jest w stanie zrozumieć. Czy warto rozumieć niektóre kwestie pojęciowe? Myślę, że tak, ale znowu zależy to od oceny nauczyciela, jakie pojęcia można wyjaśnić ich uczniom.

Babou
źródło
2

Twój uczeń miał absolutną rację. Odwrotna notacja polska nie jest na tyle znacząca w informatyce, że warto poświęcić na nią bardzo ograniczony czas zajęć. Zamiast tego istnieje wiele innych wspaniałych pomysłów koncepcyjnych, których mógłbyś się nauczyć, z głębokimi pomysłami intelektualnymi: stabilne małżeństwo, cięcie ciasta, przekątna i nierozstrzygalność problemu zatrzymania, dowody interaktywne i dowody zerowej wiedzy itp. Tak, wszystkie z nich można udostępnić 18-latkom.

I mam nadzieję, że chwaliłeś swojego ucznia za to, że był wystarczająco odważny, by zadać pytanie! Musieli postawić się na półce, aby poruszyć ten problem. Mówi dobrze dla twojego stylu nauczania, że ​​czuli się swobodnie zadając ci to pytanie.

DW
źródło
1
Nauczanie w języku polskim nie zajmuje prawie czasu. Ważna jest również linearyzacja standardowych struktur, takich jak drzewa, biorąc pod uwagę, że pamięć masowa jest często sekwencyjna, a nie losowa. Możesz także chcieć przechowywać je skutecznie lub dowiedzieć się, jak je odzyskać w całości lub w części. Łączy drzewa, chodzenie po drzewach, osadzone struktury i odpychanie. Abstradowo mówi, jak wykonać kodowanie Gödela dla danych. W porównaniu z ogromną stratą czasu i energii reprezentowanej przez parsowanie LR i LL oraz innymi niepotrzebnymi technologiami, powiedziałbym nawet, że czas poświęcony na zapisywanie w języku polskim jest czasem dobrze spędzonym.
babou
„niewystarczająco znaczący w informatyce” - niesamowicie wyrażony
Dmitri Zaitsev
1

Odwrotna notacja polska była dobrym narzędziem w mojej edukacji do zrozumienia parsowania drzew i ogólnie struktur danych drzew. Jest to również przydatne, jeśli ktoś ma jakiekolwiek zainteresowanie programowaniem w dowolnej rodzinie języków Lisp (Clojure, emacs-lisp, schemat itp.).

użytkownik21796
źródło
Dlaczego Lisp i Schemat? Są pełne nawiasów.
babou