Polish notation

( Abbreviated PN, also prefix notation or Łukasiewicz notation) Polish notation (in the computer science and mathematical logic) a clamp -free notation for formulas, or in general terms, in which the operator is written before its operands:

Operator Operand1 Operand2 ... OperandN

The Polish Notation owes its name to the Polish mathematician January Łukasiewicz, who developed it in the 1920s ( a more precise dating probably not possible ). Łukasiewicz introduced the Polish notation as before and compact clamp- free notation for the propositional logic. As connectives (or connectives ) he used for negation N, K for conjunction, A for disjunction, C for the conditional and E for the biconditional. As a set of letters that stand for arbitrary propositions, it uses lowercase. From this, statements such as Np ( " it is not the case that p" ) or Cpq ( "If p, then q" ) put together.

Łukasiewicz has himself pointed out that his writing is indeed the most compact and the first clip free linear -written notation, but not the first clip free writing ever. The merit of having freed the logic of the bracket, Gottlob Frege comes to his 1879 published Begriffsschrift notation.

In addition to a niche in the logic of the Polish notation has a firm place today especially in computer languages. Here the operator is a command word (eg mnemonic in assembler language) or the name of the desired function, and are the operands the associated parameter or function arguments:

Or

Function name Argument1 arg2 ... argumentN

In the field of mathematics most of the functions in Polish notation, in the usual notation written, eg Sine ( "sin 30") or logarithm ( "ln 10"). There are also two digit shortcuts such as the basic arithmetic operations. Here is an infix notation is common, in which the operator between its arguments ( "Address ") is written ( "a b " instead of " ab "). Also in logic today dominate infix notations, mostly variants of the early Peano - Russell notation.

Examples

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

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

In the usual infix notation, the following term requires multiple brackets:

With the other hand, no prefix notation:

Similarly, the statement in Peano - Russell notation ( P → (Q → R) ) → ( (P → Q) → (P → R) )

For shorter

Application

In addition to the functional notation in mathematics, where in many cases the function name its arguments precedes (eg "sin 30" or "lg 10") and a niche position in the logic used in the still Polish by some authors notation is, this notation is currently represented most prominently in computer science. So most command line interpreter using Polish notation (eg " dir *. Doc" or " ls -a / ").

In analogy to the mathematical use mathematical functions and function calls are generally written in Polish notation in most programming languages ​​, but then usually with additional brackets (eg, "sin ( 30 )" or " exp (log ( 10) )"). Programming languages ​​with Polish notation are APL, Tcl and Lisp. The latter is (like their dialects, such as Scheme) because of their proximity to the lambda calculus and the associated functional notation counted among the applications of the Polish notation. The advantage of the clamp freedom is in Lisp lost, however, because there firstly operators in the context can not be clearly distinguished from operands ( variables, functions as operands ) and secondly because the arity of an operator (ie the number of its operands ) is clearly not. To put the chosen solution in Lisp, an open parenthesis before the operator and a closing parenthesis after its last operand, Cambridge variant of Polish notation is called.

The Polish Notation ( and even more the Reverse Polish Notation, see below) is well suited to be evaluated by machine easily. Especially in the early days of electronic data processing, this notation was therefore often produced as an intermediate product of compilers and interpreters or used to facilitate the further processing of a present in user-friendly notation input for the computer system. (see References: Hamblin 1962)

Reverse Polish Notation

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