Notacja polska pozwala zapisywać działania bez nawiasów
Jan Łukasiewicz wprowadził w 1924 roku zapis logiczny nazywany dziś notacją polską. Zamiast umieszczać operator między argumentami, jak w zwykłym „A + B”, stawia się go przed nimi. Dzięki temu poprawnie zbudowane wyrażenie może być jednoznaczne bez nawiasów: sama kolejność symboli mówi, co jest argumentem którego operatora. Pomysł powstał dla logiki formalnej, ale później podobne sposoby zapisu okazały się wygodne także w informatyce. Odwrócona notacja polska, w której operator stoi po argumentach, zdobyła sławę dzięki kalkulatorom i maszynom stosowym — jest jednak późniejszą odmianą, a nie dokładnie tym samym zapisem Łukasiewicza.
Skąd bierze się problem z nawiasami
W zwykłej notacji operator umieszczamy pomiędzy argumentami. Zapis „a + b × c” wymaga reguł pierwszeństwa, a przy bardziej złożonych wyrażeniach także nawiasów. W logice formalnej, gdzie formuły mogą mieć wiele poziomów zagnieżdżenia, nawiasów robi się szczególnie dużo. Łukasiewicz szukał sposobu, by struktura formuły wynikała z samego ciągu symboli. Rozwiązaniem było przeniesienie operatora przed jego argumenty i ustalenie liczby argumentów, które każdy operator pobiera.
Jak działa zapis prefiksowy
Dla prostego działania dwuargumentowego można pomyśleć o zapisie „+ 2 3” zamiast „2 + 3”. Jeżeli chcemy dodać 2 do iloczynu 3 i 4, zapis prefiksowy można przedstawić jako „+ 2 × 3 4”. Czytając od początku, wiemy, że plus potrzebuje dwóch argumentów: pierwszym jest 2, drugim całe wyrażenie rozpoczynające się od znaku mnożenia. Nie trzeba dodatkowo zaznaczać nawiasami, że mnożenie tworzy wewnętrzny fragment. W formalnej logice Łukasiewicz używał własnych symboli operatorów, ale zasada jest właśnie taka.
Dlaczego komputerom podoba się taka regularność
Komputer nie potrzebuje notacji „ładnej dla oka”; potrzebuje struktury, którą da się jednoznacznie przetworzyć. Prefiksowe i postfiksowe formy zapisu są atrakcyjne, bo w określonych warunkach eliminują konieczność przechowywania informacji o nawiasach i priorytetach operatorów. Można je łatwo interpretować rekurencyjnie albo przy pomocy stosu. To nie znaczy, że wszystkie języki programowania używają notacji polskiej, lecz pokazuje, dlaczego pomysł z logiki formalnej znalazł naturalne pokrewieństwo z późniejszym przetwarzaniem wyrażeń przez maszyny.
Notacja polska a odwrotna notacja polska
Warto rozróżnić dwa terminy. Oryginalna notacja Łukasiewicza jest prefiksowa: operator pojawia się przed argumentami. W odwrotnej notacji polskiej, czyli RPN, operator pojawia się po nich, np. „2 3 +”. RPN szczególnie dobrze współpracuje ze stosem: liczby odkłada się na stos, a operator pobiera potrzebne wartości i odkłada wynik. Ta odmiana stała się znana m.in. dzięki kalkulatorom firmy Hewlett-Packard. Jest potomkiem tej samej idei jednoznacznego zapisu, ale historycznie nie należy jej utożsamiać z oryginalną notacją z 1924 roku.
Mały wynalazek, duża lekcja
Stanford Encyclopedia of Philosophy podkreśla, że notacja polska była tylko niewielką częścią dorobku Łukasiewicza w porównaniu z jego pracami nad logiką. Mimo to świetnie pokazuje, jak zmiana sposobu zapisu może zmienić sposób rozwiązywania problemu. Nawiasy nie zostały „zakazane”; stały się zbędne, bo informację o strukturze przeniesiono w inne miejsce. To ten rodzaj pomysłu, który wygląda banalnie dopiero po jego poznaniu.
Dlaczego jednoznaczność jest cenna
W matematyce i programowaniu wiele błędów bierze się nie z trudnego rachunku, lecz z niejednoznacznej interpretacji struktury. Standardowy zapis radzi sobie z tym przez nawiasy oraz konwencje pierwszeństwa działań. Notacja prefiksowa eliminuje potrzebę takich konwencji: każdy operator ma znaną liczbę argumentów, więc parser może odtworzyć drzewo wyrażenia wyłącznie z kolejności symboli. To drobny przykład szerszej zasady informatycznej — dobry format danych potrafi sprawić, że pewna klasa błędów składniowych po prostu przestaje być możliwa.