Polnische Notation

Polnische Notation (PN), auch Normale Polnische Notation (NPN),^[1] Präfixnotation, Łukasiewicz-Notation oder Warschauer Normalform^[2] genannt, ist (in der Informatik und mathematischen Logik) eine klammerfreie Schreibweise für Formeln bzw. allgemein für Ausdrücke, bei der der Operator vor seinen Operanden geschrieben wird:

Operator Operand1 Operand2 … OperandN

Die polnische Notation verdankt ihren Namen dem polnischen Mathematiker Jan Łukasiewicz, der sie in den 1920er-Jahren entwickelte (eine genauere Datierung ist wohl nicht möglich^[3]). Łukasiewicz stellte die polnische Notation als kompakte und klammerfreie Schreibweise für die Aussagenlogik vor. Als Junktoren (bzw. Konnektive) verwendet er N für die Negation, K für die Konjunktion, A für die Disjunktion, C für das Konditional und E für das Bikonditional. Als Satzbuchstaben, die für beliebige Aussagen stehen, verwendet er Kleinbuchstaben. Daraus lassen sich Aussagen wie Np („es ist nicht der Fall, dass p“) oder Cpq („Wenn p, dann q“) zusammensetzen.

Łukasiewicz weist selbst darauf hin,^[4] dass seine Schreibweise zwar die kompakteste und die erste linear geschriebene klammerfreie Schreibweise ist, aber nicht die erste klammerfreie Schreibweise überhaupt. Das Verdienst, die Logik von der Klammer befreit zu haben, kommt Gottlob Frege mit seiner bereits 1879 veröffentlichten Begriffsschriftnotation zu.

Neben einer Nische in der Logik hat die polnische Notation heute vor allem bei Programmiersprachen einen festen Platz. Hier ist der Operator ein Befehlswort (z. B. Mnemonic in der Assemblersprache) oder die Bezeichnung der gewünschten Funktion und sind die Operanden die zugehörigen Parameter bzw. Funktionsargumente:

Befehlswort Parameter1 Parameter2 … ParameterN

bzw.

Funktionsbezeichnung Argument1 Argument2 … ArgumentN

Im Bereich der Mathematik werden in der üblichen Schreibweise die meisten Funktionen in polnischer Notation angeschrieben, z. B. Sinus („${\displaystyle \sin 30}$“) oder Logarithmus („${\displaystyle \ln 10}$“). Eine Ausnahme bilden zweistellige Verknüpfungen wie z. B. die Grundrechenarten. Hier ist eine Infix-Schreibweise üblich, bei der der Operator zwischen seine Argumente („Operanden“) geschrieben wird („${\displaystyle a+b}$“ statt „${\displaystyle {+}\;a\;b}$“). Auch in der Aussagenlogik dominieren heute Infix-Notationen, meist Varianten der frühen Peano-Russell-Notation.

Die Addition der Zahlen 21 und 43 wird in der Präfixnotation folgendermaßen dargestellt:

+ 21 43

Die Aussage „P → Q“ wird in polnischer Notation wie folgt geschrieben:

Cpq

In der gewohnten Infix-Notation benötigt der folgende Term mehrere Klammern:

(4 + 9) : (17 + 2)

Mit der Präfixnotation hingegen keine:

: + 4 9 + 17 2

Analog wird die Aussage

(P → (Q → R)) → ((P → Q) → (P → R))

zum kürzeren

CCpCqrCCpqCpr

Neben der Funktionsschreibweise in der Mathematik, bei der in vielen Fällen der Funktionsname seinen Argumenten vorangeht (z. B. „sin 30“ oder „lg 10“), und einer Nischenposition in der Logik, in der auch heute noch von manchen Autoren polnische Notation verwendet wird, ist diese Schreibweise derzeit am prominentesten in der Informatik vertreten. So verwenden die meisten Kommandozeileninterpreter polnische Notation (z. B. „dir *.doc“ oder „ls -a /“).

In Analogie zum mathematischen Gebrauch werden in den meisten Programmiersprachen mathematische Funktionen bzw. generell Funktionsaufrufe in polnischer Notation geschrieben, dann allerdings meist mit zusätzlicher Klammerung (z. B. „sin(30)“ oder „exp(log(10))“). Programmiersprachen mit polnischer Notation sind APL, Assembler, Tcl und Lisp. Letztere wird (wie ihre Dialekte, z. B. Scheme) wegen ihrer Nähe zum Lambda-Kalkül und der damit verbundenen Funktionsschreibweise zu den Anwendungen der polnischen Notation gezählt. Der Vorteil der Klammerfreiheit geht in Lisp allerdings verloren, weil dort erstens Operatoren im Kontext nicht eindeutig von Operanden unterschieden werden können (Variablen, Funktionen als Operanden) und weil zweitens die Stelligkeit eines Operators (d. h. die Anzahl seiner Operanden) nicht eindeutig ist. Die in Lisp gewählte Lösung, eine öffnende Klammer vor den Operator und eine schließende Klammer nach seinen letzten Operanden zu setzen, wird „Cambridge-Variante der Polnischen Notation“ genannt.^[5]

Die polnische Notation (und noch mehr die umgekehrte polnische Notation, siehe unten) eignet sich gut dazu, auf einfache Weise maschinell ausgewertet zu werden. Vor allem in der Anfangszeit der elektronischen Datenverarbeitung wurde diese Schreibweise daher gerne als intermediäres Produkt von Compilern und Interpretern erzeugt bzw. verwendet, um die weitere Verarbeitung einer in benutzerfreundlicherer Schreibweise vorliegenden Eingabe für die Rechenanlage zu vereinfachen.^[6]

Die umgekehrte polnische Notation, kurz UPN, ist eine Variante der polnischen Notation, bei der die Operatoren nicht vor, sondern nach ihren Argumenten geschrieben werden. Entsprechend wird die UPN Postfixnotation oder auch umgekehrte Präfixnotation, selten auch Schinlop-Notation genannt.

Sie findet bei den Taschenrechnern der Firma Hewlett-Packard und stapelbasierten Rechenprogrammen wie dc und bc, sowie bei stapelbasierten Programmiersprachen wie Forth und PostScript Verwendung, blieb aber weitestgehend auf diese beschränkt.

• Currying als Anwendungsbeispiel polnischer Notation
• Polnische Mathematikerschule

• Jan Łukasiewicz: Selected Works. Hrsg.: Ludwik Borkowski (= Studies in logic and the foundations of mathematics. Nr. 54). North-Holland Publishing Company / Polish Scientific Publishers, Amsterdam / Warschau 1970, ISBN 0-7204-2252-3 (englisch). 
• Charles L. Hamblin: Translation to and from Polish notation. In: The Computer Journal. Band 5, Nr. 3, Oktober 1962, S. 210–213, doi:10.1093/comjnl/5.3.210 (englisch, comjnl.oxfordjournals.org [PDF]). 

1. ↑ Günter Jorke, Bernhard Lampe, Norbert Wengel: Arithmetische Algorithmen der Mikrorechentechnik. 1. Auflage. VEB Verlag Technik, Berlin 1989, ISBN 3-341-00515-3, EAN:9783341005156, MPN:5539165 (google.de). 
2. ↑ Bauer, Goos: Informatik, Eine einführende Übersicht. Band 1. Springer-Verlag, Berlin 1982, S. 224. 
3. ↑ „Die ältesten Texte in den ‚Selected Works‘, in denen [Łukasiewicz] polnische Notation verwendet, datieren relativ spät, sind aber Präsentationen vorangehender Arbeiten, die ‚in the course of the years 1920–1930‘ (Seite 131) stattgefunden haben, also auch keine genauere Zeitangabe geben.“ (Ch. Gottschall: Logische Notationen und deren Verarbeitung auf elektronischen Rechenanlagen aus theoretischer, praktischer und historischer Sicht (Diplomarbeit), Wien: 2005, Seite 88).
4. ↑ „On the history of the logic of propositions“, abgedruckt in: Łukasiewicz 1970, Seite 207 ff.
5. ↑ Michael L. Scott: Programming Language Pragmatics. 4. Auflage. Morgan Kaufmann, Elsevier, Amsterdam / Boston 2015, ISBN 978-0-12-410409-9, S. 225 (amerikanisches Englisch).  Zur Erklärung der Bezeichnung heißt es dort: „Lisp-like parenthesized syntax was first employed (for noncomputational purposes) by philosopher W. V. Quine of Harvard University (Cambridge, MA).“
6. ↑ Charles L. Hamblin: Translation to and from Polish notation. In: The Computer Journal. Band 5, Nr. 3, Oktober 1962, S. 210–213, doi:10.1093/comjnl/5.3.210 (englisch, comjnl.oxfordjournals.org [PDF]).