Polish notation

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

Polish notation (PN), also known as normal Polish notation (NPN),[1] Łukasiewicz notation, Warsaw notation, Polish prefix notation or simply prefix notation, is a mathematical notation in which operators precede their operands, in contrast to 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,[2] who invented Polish notation in 1924.[3][4]

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

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 terms of prefix notation (and others use postfix notation).

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.[6] Heinrich Behmann, editor in 1924 of the article of Moses Schönfinkel[7] already had the idea of eliminating parentheses in logic formulas.

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.[8]

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.[9] He then goes on to cite, as an example, a 1930 paper he wrote with Alfred Tarski on the sentential calculus.[10]

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

Explanation[edit]

The expression for adding the numbers 1 and 2 is written in Polish notation as + 1 2 (pre-fix), rather than as 1 + 2 (in-fix). 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

(5 − 6) × 7

can be written in Polish notation as

× (− 5 6) 7

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 thereof is unambiguous, and brackets within the prefix expression are unnecessary. As such, the above expression can be further simplified to

× − 5 6 7

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

5 − (6 × 7)

or removing them

5 − 6 × 7

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

− 5 × 6 7.

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, ÷ 10 5, with 10 left to 5, has the meaning of 10 ÷ 5 (read as "divide 10 by 5"), or - 7 6, with 7 left to 6, has the meaning of 7 - 6 (read as "subtract from 7 the operand 6").

Prefix evaluation algorithm[edit]

Prefix notation is especially popular with stack-based operations due to its innate ability to easily distinguish order of operations without the need for parentheses. To evaluate order of operations under prefix notation, one does not even need to memorize an operational hierarchy, as with infix notation. Instead, one looks directly to the notation to discover which operator to evaluate first. Reading an expression from left to right, one first looks for an operator and proceeds to look for two operands. If another operator is found before two operands are found, then the old operator is placed aside until this new operator is resolved. This process iterates until an operator is resolved, which must happen eventually, as there must be one more operand than there are operators in a complete statement. Once resolved, the operator and the two operands are replaced with a new operand. Because one operator and two operands are removed and one operand is added, there is a net loss of one operator and one operand, which still leaves an expression with N operators and N + 1 operands, thus allowing the iterative process to continue. This is the general theory behind using stacks in programming languages to evaluate a statement in prefix notation, although there are various algorithms that manipulate the process. Once analyzed, a statement in prefix notation becomes less intimidating to the human mind as it allows some separation from convention with added convenience.

  • Here is an algorithm for evaluating prefix expressions using a stack (under this algorithm the expression is processed from left to right):
for each token in the prefix expression:
  if token is an operator:
    push token onto the operator stack
    pending_operand ← False
  else if token is an operand:
    operand ← token
    if pending_operand is True:
      while the operand stack is not empty:
        operand_1 ← pop from the operand stack
        operator ← pop from the operator stack
        operand ← evaluate operator with operand_1 and operand
    push operand onto the operand stack
    pending_operand ← True
result ← pop from the operand stack
  • Here is another algorithm for evaluating prefix expressions using a stack (under this algorithm the expression is processed from right to left):
for each token in the reversed prefix expression:
  if token is an operator:
    operand_1 ← pop from the stack
    operand_2 ← pop from the stack
    result ← evaluate token with operand_1 and operand_2
    push result back onto the stack
  else if token is an operand:
    push token onto the stack
result ← pop from the stack

Example[edit]

The infix expression ((15 ÷ (7 − (1 + 1))) × 3) − (2 + (1 + 1)) can be written like this in Polish notation:

− × ÷ 15 − 7 + 1 1 3 + 2 + 1 1
  • Evaluating this prefix expression with the above left-to-right algorithm yields:
− × ÷ 15 − 7 + 1 1 3 + 2 + 1 1 =
− × ÷ 15 − 7 2     3 + 2 + 1 1 =
− × ÷ 15 5         3 + 2 + 1 1 =
− × 3              3 + 2 + 1 1 =
− 9                  + 2 + 1 1 =
− 9                  + 2 2     =
− 9                  4         =
5

The following table shows the state of the operator and operand stack at each stage of the above left-to-right algorithm:

Token Type Operator Stack Operand Stack Pending Operand Actions
Operator False Push onto operator stack.
× Operator − × False Push onto operator stack.
÷ Operator − × ÷ False Push onto operator stack.
15 Operand − × ÷ 15 True Push onto operand stack.
Operator − × ÷ − 15 False Push onto operator stack.
7 Operator − × ÷ − 15 7 True Push onto operand stack.
+ Operator − × ÷ − + 15 7 False Push onto operator stack.
1 Operand − × ÷ − + 15 7 1 True Push onto operand stack.
1 Operand − × 3 True Loop while the operand stack is not empty.
  • Pop from operand stack (1) and operator stack (+), calculate (1 + 1 = 2).
  • Pop from operand stack (7) and operator stack (−), calculate (7 − 2 = 5).
  • Pop from operand stack (15) and operator stack (÷), calculate (15 ÷ 5 = 3).

Push result (3) onto operand stack.

3 Operand 9 True Loop while the operand stack is not empty.
  • Pop from operand stack (3) and operator stack (×), calculate (3 × 3 = 9).

Push result (9) onto operand stack.

+ Operator − + 9 False Push onto operator stack.
2 Operand − + 9 2 True Push onto operand stack.
+ Operator − + + 9 2 False Push onto operator stack.
1 Operand − + + 9 2 1 True Push onto operand stack.
1 Operand 5 True Loop while the operand stack is not empty.
  • Pop from operand stack (1) and operator stack (+), calculate (1 + 1 = 2).
  • Pop from operand stack (2) and operator stack (+), calculate (2 + 2 = 4).
  • Pop from operand stack (9) and operator stack (-), calculate (9 − 4 = 5).

Push result (5) onto operand stack.

  • Evaluating this prefix expression with the above right-to-left algorithm yields:
− × ÷ 15 − 7 + 1 1 3 + 2 + 1 1 =
− × ÷ 15 − 7 + 1 1 3 + 2 2     =
− × ÷ 15 − 7 + 1 1 3 4         =
− × ÷ 15 − 7 2     3 4         =
− × ÷ 15 5         3 4         =
− × 3              3 4         =
9                  4         =
5

The following table shows the state of the operand stack at each stage of the above right-to-left algorithm:

Token Type Stack Actions
1 Operand 1 Push onto stack.
1 Operand 1 1 Push onto stack.
+ Operator 2 Pop from stack twice (1, 1), calculate (1 + 1 = 2) and push onto stack.
2 Operand 2 2 Push onto stack.
+ Operator 4 Pop from stack twice (2, 2), calculate (2 + 2 = 4) and push onto stack.
3 Operand 4 3 Push onto stack.
1 Operand 4 3 1 Push onto stack.
1 Operand 4 3 1 1 Push onto stack.
+ Operator 4 3 2 Pop from stack twice (1, 1), calculate (1 + 1 = 2) and push onto stack.
7 Operand 4 3 2 7 Push onto stack.
Operator 4 3 5 Pop from stack twice (7, 2), calculate (7 − 2 = 5) and push onto stack.
15 Operand 4 3 5 15 Push onto stack.
÷ Operator 4 3 3 Pop from stack twice (15, 5), calculate (15 ÷ 5 = 3) and push onto stack.
× Operator 4 9 Pop from stack twice (3, 3), calculate (3 × 3 = 9) and push onto stack.
Operator 5 Pop from stack twice (9, 4), calculate (9 − 4 = 5) and push onto stack.

Polish notation for logic[edit]

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

Concept Conventional
notation
Polish
notation
Polish
term
Negation negacja
Conjunction koniunkcja
Disjunction alternatywa
Material conditional implikacja
Biconditional ekwiwalencja
Falsum fałsz
Sheffer stroke dysjunkcja
Possibility możliwość
Necessity konieczność
Universal quantifier kwantyfikator ogólny
Existential quantifier kwantyfikator szczegółowy

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

Bocheński introduced an incompatible system of Polish notation that names all 16 binary connectives of classical propositional logic.[13]

Implementations[edit]

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[14] programming language uses Polish notation for arithmetic operations and program construction.

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.[15] At a lower level, postfix operators are used by some stack machines such as the Burroughs large systems.

See also[edit]

References[edit]

  1. ^ Jorke, Günter; Lampe, Bernhard; Wengel, Norbert (1989). Arithmetische Algorithmen der Mikrorechentechnik [Arithmetic algorithms in microcomputers] (in German) (1 ed.). Berlin, Germany: VEB Verlag Technik. ISBN 3341005153. EAN 9783341005156. MPN 5539165. License 201.370/4/89. Retrieved 2015-12-01. 
  2. ^ Łukasiewicz, Jan (1957). Aristotle's Syllogistic from the Standpoint of Modern Formal Logic. Oxford University Press.  (Reprinted by Garland Publishing in 1987. ISBN 0-8240-6924-2)
  3. ^ Hamblin, Charles Leonard (1962). "Translation to and from Polish notation" (PDF). Computer Journal. 5 (3): 210–213. doi:10.1093/comjnl/5.3.210. 
  4. ^ Ball, John A. (1978). Algorithms for RPN calculators (1 ed.). Cambridge, Massachusetts, USA: Wiley-Interscience, John Wiley & Sons, Inc. ISBN 0-471-03070-8. 
  5. ^ Main, Michael (2006). Data structures and other objects using Java (3rd ed.). Pearson PLC Addison-Wesley. p. 334. ISBN 978-0-321-37525-4. 
  6. ^ Pogorzelski, Henry A., "Reviewed work(s): Remarks on Nicod's Axiom and on "Generalizing Deduction" by Jan Łukasiewicz; Jerzy Słupecki; Państwowe Wydawnictwo Naukowe", The Journal of Symbolic Logic, Vol. 30, No. 3 (September 1965), pp. 376–377. The original paper by Łukasiewicz was published in Warsaw in 1961 in a volume edited by Jerzy Słupecki.
  7. ^ "Über die Bausteine der mathematischen Logik", Mathematische Annalen 92, pages 305-316. Translated by Stefan Bauer-Mengelberg as "On the building blocks of mathematical logic" in Jean van Heijenoort, 1967. A Source Book in Mathematical Logic, 1879-1931. Harvard University Press: 355-66.
  8. ^ Church, Alonzo (1944). Introduction to Mathematical Logic. Princeton, New Jersey, USA: Princeton University Press. p. 38. […] Worthy of remark is the parenthesis-free notation of Jan Łukasiewicz. In this the letters N, A, C, E, K are used in the roles of negation, disjunction, implication, equivalence, conjunction respectively. […] 
  9. ^ Łukasiewicz, (1951) Aristotle's Syllogistic from the Standpoint of Modern Formal Logic, Chapter IV "Aristotle's System in Symbolic Form" (section on "Explanation of the Symbolism"), p. 78 and on.
  10. ^ Łukasiewicz, Jan; Tarski, Alfred, "Untersuchungen über den Aussagenkalkül" ["Investigations into the sentential calculus"], Comptes Rendus des Séances de la Société des Sciences et des Lettres de Varsovie, Vol. 23 (1930) Cl. III, pp. 31–32.
  11. ^ Martínez Nava, Xóchitl (2011-06-01), "Mhy bib I fail logic? Dyslexia in the teaching of logic", in Blackburn, Patrick; van Ditmarsch, Hans; Manzano, Maria; Soler-Toscano, Fernando, Tools for Teaching Logic: Third International Congress, TICTTL 2011, Salamanca, Spain, June 1-4, 2011, Proceedings, Lecture Notes in Artificial Intelligence, 6680, Springer Nature, pp. 162–169, doi:10.1007/978-3-642-21350-2_19, ISBN 9783642213496, […] Polish or prefix notation has come to disuse given the difficulty that using it implies. […] 
  12. ^ Craig, Edward (1998), Routledge Encyclopedia of Philosophy, Volume 8, Taylor & Francis, p. 496, ISBN 9780415073103 .
  13. ^ Bocheński, Józef Maria (1959). A Precis of Mathematical Logic, translated by Otto Bird from the French and German editions, D. Reidel: Dordrecht, Holland.
  14. ^ https://code.google.com/p/ambi/
  15. ^ "HP calculators | HP 35s RPN Mode" (PDF). Hewlett-Packard. 

Further reading[edit]

  • Łukasiewicz, Jan (1957). Aristotle's Syllogistic from the Standpoint of Modern Formal Logic. Oxford University Press. 
  • Łukasiewicz, Jan (1930). Philosophische Bemerkungen zu mehrwertigen Systemen des Aussagenkalküls [Philosophical Remarks on Many-Valued Systems of Propositional Logics]. Comptes Rendus des Séances de la Société des Sciences et des Lettres de Varsovie (in German). 23. pp. 51–77.  Translated by H. Weber in Storrs McCall, Polish Logic 1920-1939, Clarendon Press: Oxford (1967).