Polish notation

Polish notation ( PN ), also known as normal Polish notation ( NPN ), prefix notation , Łukasiewicz notation or Warsaw normal form , is (in computer science and mathematical logic ) a notation in brackets for formulas or in general for expressions in which the operator is in front of his Operands are written:

Operator Operand1 Operand2… OperandN

The Polish notation owes its name to the Polish mathematician Jan Łukasiewicz , who developed it in the 1920s (a more precise dating is probably not possible). Łukasiewicz introduced the Polish notation as a compact and bracket-free notation for propositional logic . As junctors (or connectives) he used Nfor the negation , Kthe conjunction , Afor disjunction , Cfor the conditional and Efor the biconditional . He uses lowercase letters as sentence letters that stand for any statement. From this statements like Np(“it is not the case that p”) or Cpq(“if p, then q”) can be put together.

Łukasiewicz himself points out that his spelling is the most compact and the first linear spelling without brackets, but not the first without brackets at all. The merit of having freed logic from the brackets goes to Gottlob Frege with his conceptual notation published in 1879 .

In addition to a niche in logic, the Polish notation has a permanent place today, especially in programming languages . Here the operator is a command word (e.g. mnemonic in assembly language ) or the designation of the desired function and the operands are the associated parameters or function arguments:

Command word Parameter1 Parameter2… ParameterN

or.

Function name Argument1 Argument2… ArgumentN

In the field of mathematics, most functions are written in Polish notation in the usual notation, e.g. B. Sine (" ") or logarithm (" "). Two- digit links such as B. the basic arithmetic operations . An infix notation is common here, in which the operator is written between its arguments (“operands”) (“ ” instead of “ ”). In propositional logic, too, infix notations dominate today, mostly variants of the early Peano-Russell notation . ${\ displaystyle \ sin 30}$ ${\ displaystyle \ ln 10}$ ${\ displaystyle a + b}$ ${\ displaystyle {+} \; a \; b}$

Examples

The addition of the numbers 21 and 43 is represented in the prefix notation as follows:

+ 21 43

The statement "P → Q" is written in Polish notation as follows:

Cpq

In the familiar Infix notation, the following term requires several brackets:

(4 + 9) : (17 + 2)

With the prefix notation, however, none:

: + 4 9 + 17 2

The statement is analogous

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

for the shorter one

CCpCqrCCpqCpr

application

In addition to the functional notation in mathematics, in which the function name precedes its arguments in many cases (e.g. "sin 30" or "lg 10") and a niche position in logic, in which some authors still use Polish notation today is, this spelling is currently most prominently represented in computer science . Most command line interpreters use Polish notation (e.g. " dir *.doc" or " ls -a /").

In analogy to mathematical usage, in most programming languages mathematical functions or generally function calls are written in Polish notation, but then usually with additional brackets (e.g. "sin (30)" or "exp (log (10))"). Programming languages with Polish notation are APL , Assembler , Tcl and Lisp . The latter (like its dialects, e.g. Scheme ) is counted among the applications of the Polish notation because of its proximity to the lambda calculus and the associated functional notation. The advantage of freedom from parentheses is lost in Lisp, however, because firstly, operators cannot be clearly differentiated from operands in context (variables, functions as operands) and secondly because the arity of an operator (i.e. the number of its operands) is not unambiguous. The solution chosen in Lisp, to put an opening bracket in front of the operator and a closing bracket after its last operand, is called the "Cambridge variant of Polish notation".

The Polish notation (and even more so the reverse Polish notation, see below) is well suited to be evaluated easily by machine. Especially in the early days of electronic data processing, this notation was therefore often created or used as an intermediate product by compilers and interpreters in order to simplify the further processing of an input in a more user-friendly notation for the computer system.

Reverse Polish notation

The reverse Polish notation, UPN for short, is a variant of the Polish notation in which the operators are not written before, but after their arguments. Accordingly, the UPN postfix notation or reverse prefix notation, rarely also called Schinlop notation.

It is used in the pocket calculators from Hewlett-Packard as well as in the Forth and PostScript programming languages , but was largely limited to these.

literature

Jan Łukasiewicz : Selected Works . Ed .: Ludwik Borkowski (= Studies in logic and the foundations of mathematics . No. 54 ). North-Holland Publishing Company / Polish Scientific Publishers, Amsterdam / Warsaw 1970, ISBN 0-7204-2252-3 .
Charles L. Hamblin : Translation to and from Polish notation . In: The Computer Journal . tape 5 , no. 3 , 1962, pp. 210-213 , doi : 10.1093 / comjnl / 5.3.210 ( PDF ).

Individual evidence

↑ Günter Jorke, Bernhard Lampe, Norbert Wengel: Arithmetic Algorithms of Micro Computing Technology , 1st edition, VEB Verlag Technik , Berlin 1989, ISBN 3341005153 , EAN: 9783341005156, MPN: 5539165.

^ Bauer, Goos: Informatik, An introductory overview , Volume 1. Springer-Verlag, Berlin 1982, p. 224.

↑ "The oldest texts in the 'Selected Works', in which [Łukasiewicz] uses Polish notation, date relatively late, but are presentations of previous works that took place 'in the course of the years 1920–1930' (page 131), so do not give a more precise time. ”(Ch. Gottschall: Logical notations and their processing on electronic computers from a theoretical, practical and historical point of view (diploma thesis), Vienna: 2005, page 88).

^ "On the history of the logic of propositions", printed in: Łukasiewicz 1970 , page 207 ff.

^ Michael L. Scott: Programming Language Pragmatics . 4th edition. Morgan Kaufmann, Elsevier, Amsterdam / Boston 2015, ISBN 978-0-12-410409-9 , pp. 225 (American English). To explain the name it says: "Lisp-like parenthesized syntax was first employed (for noncomputational purposes) by philosopher WV Quine of Harvard University (Cambridge, MA)."

^ Charles L. Hamblin : Translation to and from Polish notation . In: The Computer Journal . tape 5 , no. 3 , 1962, pp. 210-213 , doi : 10.1093 / comjnl / 5.3.210 ( PDF ).

[Jorke_1989-1] Günter Jorke, Bernhard Lampe, Norbert Wengel: Arithmetic Algorithms of Micro Computing Technology , 1st edition, VEB Verlag Technik , Berlin 1989, ISBN 3341005153 , EAN: 9783341005156, MPN: 5539165.

[Bauer_1982-2] Bauer, Goos: Informatik, An introductory overview , Volume 1. Springer-Verlag, Berlin 1982, p. 224.

[3] "The oldest texts in the 'Selected Works', in which [Łukasiewicz] uses Polish notation, date relatively late, but are presentations of previous works that took place 'in the course of the years 1920–1930' (page 131), so do not give a more precise time. ”(Ch. Gottschall: Logical notations and their processing on electronic computers from a theoretical, practical and historical point of view (diploma thesis), Vienna: 2005, page 88).

[4] "On the history of the logic of propositions", printed in: Łukasiewicz 1970 , page 207 ff.

[5] Michael L. Scott: Programming Language Pragmatics . 4th edition. Morgan Kaufmann, Elsevier, Amsterdam / Boston 2015, ISBN 978-0-12-410409-9 , pp. 225 (American English). To explain the name it says: "Lisp-like parenthesized syntax was first employed (for noncomputational purposes) by philosopher WV Quine of Harvard University (Cambridge, MA)."

[6] Charles L. Hamblin : Translation to and from Polish notation . In: The Computer Journal . tape 5 , no. 3 , 1962, pp. 210-213 , doi : 10.1093 / comjnl / 5.3.210 ( PDF ).