Polish notation

Polish notation (PN), also called Normal Polish Notation (NPN), prefix notation, Łukasiewicz notation, or Warsaw Normal Form, is (in computer science and mathematical logic) a parenthesis-free notation for formulas or expressions in general, in which the operator is written before its operands:

Operator Operand1 Operand2 ... OperandN

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 Polish notation as a compact and bracket-free notation for propositional logic. As junctors (or connectives) he uses N for negation, K for conjunction, A for disjunction, C for conditional, and E for biconditional. He uses lower case letters as sentence letters which stand for any statements. From these, statements such as Np ("it is not the case that p") or Cpq ("if p, then q") can be composed.

Łukasiewicz himself points out that while his notation is the most compact and the first linearly written bracket-free notation, it is not the first bracket-free notation ever. The credit for freeing logic from the parenthesis goes to Gottlob Frege with his Begriffsschriftnotation, published as early as 1879.

Besides a niche in logic, Polish notation has a firm 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

respectively

Function name Argument1 Argument2 ... ArgumentN

In the field of mathematics, most functions are written in Polish notation, e.g. sine (" ") or logarithm (" "). An exception to this are two-digit operations such as basic arithmetic. Here an infix notation is common, where the operator is written between its arguments ("operands") (" " instead of " "). Infix notations also dominate propositional logic today, mostly variants of the early Peano-Russell notation.

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 usual infix notation, the following term requires several parentheses:

(4 + 9) : (17 + 2)

With the prefix notation, on the other hand, none:

: + 4 9 + 17 2

Analogously, the statement

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

for the shorter

CCpCqrCCpqCpr

Application

Besides the function notation in mathematics, where in many cases the function name precedes its arguments (e. g., "sin 30" or "lg 10"), and a niche position in logic, where Polish notation is still used by some authors today, this notation is currently most prominent in computer science. Thus, 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 parentheses (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 Polish notation because of its proximity to lambda calculus and the associated function notation. The advantage of the absence of parentheses is lost in Lisp, however, firstly because operators cannot be clearly distinguished from operands in the context there (variables, functions as operands) and secondly because the significance of an operator (i.e. the number of its operands) is not unique. The solution chosen in Lisp, to put an opening parenthesis before the operator and a closing parenthesis after its last operands, is called the "Cambridge variant of Polish notation".

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