Prefix Notation

Polish notation (PN), also known as normal Polish notation (NPN), Łukasiewicz notation, Warsaw notation, Polish prefix notation or simply prefix notation, is a mathematical notation in which operators ''precede'' their operands, in contrast to the more common infix notation, in which operators are placed ''between'' operands, as well as reverse Polish notation (RPN), in which operators ''follow'' their operands. It does not need any parentheses as long as each operator has a fixed number of operands. The description "Polish" refers to the nationality of logician Jan Łukasiewicz, who invented Polish notation in 1924.

The term ''Polish notation'' is sometimes taken (as the opposite of ''infix notation'') to also include reverse Polish notation.

When Polish notation is used as a syntax for mathematical expressions by programming language interpreters, it is readily parsed into abstract syntax trees and can, in fact, define a one-to-one representation for the same. Because of this, Lisp ( see below) and related programming languages define their entire syntax in prefix notation (and others use postfix notation).

History

A quotation from a paper by Jan Łukasiewicz, ''Remarks on Nicod's Axiom and on "Generalizing Deduction"'', page 180, states how the notation was invented:

I came upon the idea of a parenthesis-free notation in 1924. I used that notation for the first time in my article Łukasiewicz(1), p. 610, footnote.

The reference cited by Łukasiewicz is apparently a lithographed report in Polish. The referring paper by Łukasiewicz ''Remarks on Nicod's Axiom and on "Generalizing Deduction"'' was reviewed by Henry A. Pogorzelski in the ''Journal of Symbolic Logic'' in 1965. Heinrich Behmann, editor in 1924 of the article of Moses Schönfinkel, already had the idea of eliminating parentheses in logic formulas. In one of his papers Łukasiewicz stated that his notation is the most compact and the first linearly written parentheses-free notation, but not the first one as Gottlob Frege proposed his parentheses-free Begriffsschrift notation in 1879 already.

Alonzo Church mentions this notation in his classic book on mathematical logic as worthy of remark in notational systems even contrasted to Alfred Whitehead and Bertrand Russell's logical notational exposition and work in Principia Mathematica.

In Łukasiewicz's 1951 book, ''Aristotle's Syllogistic from the Standpoint of Modern Formal Logic'', he mentions that the principle of his notation was to write the functors before the arguments to avoid brackets and that he had employed his notation in his logical papers since 1929. He then goes on to cite, as an example, a 1930 paper he wrote with Alfred Tarski on the sentential calculus.

While no longer used much in logic, Polish notation has since found a place in computer science.

Explanation

The expression for adding the numbers 1 and 2 is written in Polish notation as (prefix), rather than as (infix). In more complex expressions, the operators still precede their operands, but the operands may themselves be expressions including again operators and their operands. For instance, the expression that would be written in conventional infix notation as

can be written in Polish notation as

Assuming a given arity of all involved operators (here the "−" denotes the binary operation of subtraction, not the unary function of sign-change), any well-formed prefix representation is unambiguous, and brackets within the prefix expression are unnecessary. As such, the above expression can be further simplified to

The processing of the product is deferred until its two operands are available (i.e., 5 minus 6, and 7). As with ''any'' notation, the innermost expressions are evaluated first, but in Polish notation this "innermost-ness" can be conveyed by the sequence of operators and operands rather than by bracketing.

In the conventional infix notation, parentheses are required to override the standard precedence rules, since, referring to the above example, moving them

or removing them

changes the meaning and the result of the expression. This version is written in Polish notation as

When dealing with non-commutative operations, like division or subtraction, it is necessary to coordinate the sequential arrangement of the operands with the definition of how the operator takes its arguments, i.e., from left to right. For example, , with 10 to the left of 5, has the meaning of 10 ÷ 5 (read as "divide 10 by 5"), or , with 7 left to 6, has the meaning of 7 − 6 (read as "subtract from 7 the operand 6").

Evaluation algorithm

Prefix/postfix notation is especially popular for its innate ability to express the intended order of operations without the need for parentheses and other precedence rules, as are usually employed with infix notation. Instead, the notation uniquely indicates which operator to evaluate first. The operators are assumed to have a fixed arity each, and all necessary operands are assumed to be explicitly given. A valid prefix expression always starts with an operator and ends with an operand. Evaluation can either proceed from left to right, or in the opposite direction. Starting at the left, the input string, consisting of tokens denoting operators or operands, is pushed token for token on a stack, until the top entries of the stack contain the number of operands that fits to the top most operator (immediately beneath). This group of tokens at the stacktop (the last stacked operator and the according number of operands) is replaced by the result of executing the operator on these/this operand(s). Then the processing of the input continues in this manner. The rightmost operand in a valid prefix expression thus empties the stack, except for the result of evaluating the whole expression. When starting at the right, the pushing of tokens is performed similarly, just the evaluation is triggered by an operator, finding the appropriate number of operands that fits its arity already at the stacktop. Now the leftmost token of a valid prefix expression must be an operator, fitting to the number of operands in the stack, which again yields the result. As can be seen from the description, a push-down store with no capability of arbitrary stack inspection suffices to implement this parsing.

The above sketched stack manipulation works—with mirrored input—also for expressions in reverse Polish notation.

Polish notation for logic

The table below shows the core of Jan Łukasiewicz's notation for sentential logic. Some letters in the Polish notation table stand for particular words in Polish, as shown:

Note that the quantifiers ranged over propositional values in Łukasiewicz's work on many-valued logics.

Bocheński introduced a system of Polish notation that names all 16 binary connectives of classical propositional logic. For classical propositional logic, it is a compatible extension of the notation of Łukasiewicz. But the notations are incompatible in the sense that Bocheński uses L and M (for nonimplication and converse nonimplication) in propositional logic and Łukasiewicz uses L and M in modal logic.

Implementations

Prefix notation has seen wide application in Lisp S-expressions, where the brackets are required since the operators in the language are themselves data (first-class functions). Lisp functions may also be variadic. The Tcl programming language, much like Lisp also uses Polish notation through the mathop library. The Ambi programming language uses Polish notation for arithmetic operations and program construction. LDAP filter syntax uses Polish prefix notation.

Postfix notation is used in many stack-oriented programming languages like PostScript and Forth. CoffeeScript syntax also allows functions to be called using prefix notation, while still supporting the unary postfix syntax common in other languages.

The number of return values of an expression equals the difference between the number of operands in an expression and the total arity of the operators minus the total number of return values of the operators.

Polish notation, usually in postfix form, is the chosen notation of certain calculators, notably from Hewlett-Packard. At a lower level, postfix operators are used by some stack machines such as the Burroughs large systems.

See also

* Reverse Polish notation (RPN)
* Function application
* Lambda calculus
* Currying
* Lisp (programming language)
** S-expression
* Polish School of Mathematics
* Hungarian notation
* Verb–subject–object (VSO)
* Verb–object–subject (VOS)
* Head-directionality parameter
* WFF 'N PROOF

References

Further reading

* Translated by H. Weber in Storrs McCall, ''Polish Logic 1920–1939'', Clarendon Press: Oxford (1967).
*

(77 pages)
* (11 pages) (NB. Published in .)
* (11 pages)

External links

*

{{DEFAULTSORT:Polish Notation
Mathematical notation
Polish inventions
Science and technology in Poland
Operators (programming)
Logical expressions