Reverse Polish notation

Programmable pocket calculator HP-41CX from the 1980s with a conspicuous, extra- wide Enter key for UPN input. Characteristically, the bracket keys typical of conventional pocket calculators ( )and the equality key are missing at the same time =.

The reverse Polish notation ( UPN ) or reverse Polish notation English reverse Polish notation ( RPN for short ), also called postfix notation , is a notation or input logic derived from the Polish notation for the use of operations. In the reverse Polish notation, the operands are first written down or entered and then the operator to be used on them .

More widespread the UPN found only by the calculator of the manufacturer Hewlett-Packard . Whose computers have a most strikingly large Enterkey for the missing clip button ( , )and the equals key = . There is also no conventional delete key to initiate the calculation, as results that are no longer required are automatically pushed from the stack during the calculations . A modified delete key is used to eliminate typing errors. Many of the larger Hewlett-Packard calculators, such as the HP-48 series, support an object-oriented modification and extension of UPN / RPN called RPL (for Reverse Polish LISP ), which is based on the same basic principles, but in some details so far deviates that input sequences must be adapted.

principle

A flowchart showing how to use a UPN calculator to perform a multi-number, multi-operation calculation

In computer science , the UPN is of interest because it is a stack-based allows execution: operands are placed on the stack while reading, an operator gets the number of operands from the stack (Stack), which corresponds to its arity, and stores the result of Operation back on the stack. In the end, the result of the term is on top of the stack. This is why the UPN forms the basis for batch-based programming languages ​​such as Forth , RPL , PostScript or the instruction list in the PLC area. Another name is the null address machine because there are no explicit memory addresses involved.

Example: 3 and 4 are to be added. The operands are then 3 and 4, the operator is "+":

In school the notation learned is the (sequentially organizing) infix notation "3 + 4". In the reverse Polish notation, however, “3 4 +” is written (there is a space between 3 and 4 so that the sequence of numbers can be distinguished from the number 34).

Another example (in infix notation): "(3 + 4) × 5". With the UPN, the brackets can be omitted, all operations (here “+” and “×”) work with the two upper elements of the stack . The example in UPN is then: "3 4 + 5 ×" (first the expression in brackets "3 4 +" is calculated, then the resulting number 7 is multiplied by 5).

A similar principle can also be found in German and other natural languages ​​( SOV languages ), called scrambling : In infinitives and subordinate clauses of German, first all additions ( arguments ) of a verb are mentioned one after the other, and at the end the verb that corresponds to an operator resembles because it connects the additions to one sentence:

• Wash the laundry with soap.
• Mix the flour with the eggs in a bowl
• when someone takes away the dog's food.

Linguistically, the differences between the infix notation "(3 + 4) × 5" and the UPN "3 4 + 5 ×" can be illustrated as follows:

• Instead of “3 plus 4, times 5” you say “add 3 and 4 and multiply by 5”.

In the case of non- commutative operations, the order is identical in both spellings.

For operators with only one operand, UPN is also very common in (pocket) computers that otherwise work with the infix notation. Examples of this are the trigonometric or logarithmic functions that are entered in most pocket calculators in the form 2 5 lnor 2 5 sin(the operator “ln” or “sin” is entered after the operand “25”).

The shunting yard algorithm can be used to convert between the spellings .

advantages

The HP-12C UPN Financial Calculator has been in production since 1981 to date.

The advantage of UPN over algebraic notation (infix notation) is often discussed among users.

The most noticeable advantage of the UPN is that it generally requires fewer keystrokes. For example, to do the calculation (1 + 2) × (3 + 4) , you have to press twelve keys in algebraic mode:

( 1 + 2 ) × ( 3 + 4 ) =

In many implementations, the key sequence can still be optimized; Strictly speaking, this is not an "algebraic approach":

1 + 2 = × ( 3 + 4 =

Only nine keystrokes are required in UPN mode:

1 Enter 2 + 3 Enter 4 + ×

There are three fewer keys to press than in algebraic mode; With more complex invoices, the savings are correspondingly greater.

Another advantage of the UPN is that the calculation is always carried out step-by-step and with visible intermediate results; the data can therefore be further processed gradually. However, many algebraic pocket calculators also show intermediate results as far as possible, for example )the value of the current expression in brackets when the key is pressed .

The availability of intermediate results not only makes it easier to check the entries and to identify errors, but also allows, in connection with the interchanging operations available with UPN within the stack, to simply store each intermediate result without the need for separate storage registers and to process them later . In particular, the frequently occurring case that an operand is needed again immediately - such as in the calculation (a − b) / b - can be calculated without entering or storing b again; UPN computers have a LASTX register for this, which automatically saves the last operand.

The programming of a UPN computer usually follows the manual entry of a calculation, which is very user-friendly, especially for frequent short arithmetic tasks, because no special programming language has to be learned. In algebraic pocket calculators, the programming model often (but not always) deviates from manual formula entry.

disadvantage

The main disadvantage of the UPN is the fact that it is often not familiar from everyday life or school and therefore has to be learned first; In addition, the advantages are only noticeable when used more intensively and especially when working with complex formulas. Getting used to one of the two notations can make it difficult to deal with the other.

implementation

In classic UPN computers, four stack levels are used, which at Hewlett-Packard are designated with X (display value), Y, Z and T. Initial implementations with only two (Sinclair pocket calculators) or three registers (X, Y and Z) had proven impractical. There were also implementations with five registers (Heathkit OC-1401). More recently, there have also been free implementations with eight stack levels (X, Y, Z, T, A, B, C, D) (WP 31S and WP 34S). Current implementations of the HP pocket calculators from the HP 48 series have no limit in the number of stack levels (only limited by the memory). This means that the naming conventions, in particular for registers Z, T, etc., are no longer required. For the sake of keyboard labeling and for easier understanding, however, the first two stack levels on these computers are also designated as Y and X (even if they are no longer programmatically addressed in this way). The almost complete elimination of the stack level limitation has the advantage that even more complex calculations can be entered clearly and intermediate results can be saved, but also the disadvantage that the stack has to be deleted with a key combination in order to remove old results.

Another register L (LASTX) automatically saves the last value of X. In addition, an exchange of X and Y (important for non-commutative operations) and a cyclic exchange of all stack registers ( roll down , the value of X gets to T) , the value from Y to X, etc.). In better equipped computers, the reverse cyclical exchange ( roll up ) and later (in the HP-41 ) the storage and recall of stack registers as required is possible.

Register T has a special function. Operations that have more than one argument move the stack “down” and the value of T is copied, which can be very beneficial for continued computing. Early implementations cleared T clears on pop on some machines , which turned out to be less practical. There were also models (such as the HP-35 ) that required T as a buffer for complex operations and overwrite its contents. On computers that support RPL, the depth of the stack is only limited by the available memory space. With the HP Prime , it is limited to 128 stack levels. As a result, the special function of the T register outlined above is also omitted there.

Another special feature concerns the function of the ENTER key, which on Hewlett-Packard computers that implement the classic UPN ( Classical RPN in English-speaking countries) automatically duplicates the content of the X register in the Y register under certain conditions, which is the case with UPN computers from other manufacturers and also with RPL computers does not happen. All newer Hewlett-Packard computers with UPN support that do not emulate one of the classic models also deviate from the classic UPN input logic in this regard and instead work like RPL in this regard. This variant also requires slight adjustments in the command sequence in programs and is often referred to colloquially as Entry RPN (input UPN) in English-speaking countries .

In the past, especially in the early days of electronic pocket calculators, a major advantage of the UPN was that it could be implemented with less hardware. Practice shows that relatively complex mathematical calculations can be carried out with a stack of just four entries. In contrast, an algebraic pocket calculator must have its own register for each level in brackets and generally for each intermediate result (" dot before line calculation ") that it is supposed to process; in practice, algebraic calculators have been made with up to twelve operand registers to store up to eleven incomplete operations. With the performance of today's electronic circuitry, this theoretical advantage of the UPN is no longer technically significant, and modern UPN pocket calculators are now equipped with more than four stack registers and additional storage registers.

Algorithms

Conversion from infix notation to UPN

Arithmetic expression as a term tree ${\displaystyle 23\cdot 2-4}$

An arithmetic expression in infix notation can be converted directly into the UPN character by character with the shunting yard algorithm (German: 'Rangierbahnhof' algorithm).

When displaying an expression in infix notation as a term tree, the UPN corresponds to the output of the node labels in a postorder traversal .

Example:

Infix notation: ${\displaystyle 23\cdot 2-4}$

Post order traversal:

   postorder(23*2-4)
-> postorder(23*2); postorder(4); print(-);
-> postorder(23); postorder(2); print(*); postorder(4); print(-);
-> print(23); print(2); print(*); print(4); print(-)

Postfix notation (UPN): ${\displaystyle 23\;2\cdot 4\;-}$

Definition: Analogous to a postorder traversal, the UPN can be formally defined recursively by converting an infix expression:

1. If the infix expression is an operand, then in UPN. ${\displaystyle e}$ ${\displaystyle e}$
2. When the infix expression of the form is present, then its UPN is by defined, wherein respectively the UPN of or refer to. ${\displaystyle e_{1}\theta e_{2}}$ ${\displaystyle e_{1}'e_{2}'\theta }$ ${\displaystyle e_{1}'}$ ${\displaystyle e_{2}'}$ ${\displaystyle e_{1}}$ ${\displaystyle e_{2}}$
3. If an infix has the form , then its UPN, where the UPN of denotes. ${\displaystyle (e)}$ ${\displaystyle e'}$ ${\displaystyle e'}$ ${\displaystyle e}$

application

Converting an infix term to UPN is an important part of building a compiler .

evaluation

An expression in UPN is evaluated by reading it from left to right, with operands placed on a stack . If a -digit operator is read, elements are removed from the stack, the operator is applied to them and the result is returned to the stack. At the end of the processing, the total result of the calculation is on the stack. The following pseudocode specifies this algorithm: ${\displaystyle x}$ ${\displaystyle x}$

compute_rpn(input)
  stack_init
  foreach (o in input)
     switch o
       isnumber
         push o
       isbinoperator
         right = pop
         left = pop
         t = compute(left, o, right)
         push t
  return pop

The order in which the operands are removed from the stack is not arbitrary. It follows directly from the definition of the conversion of infix expressions into the UPN. With non- commutative operators, an incorrect operand sequence can lead to an incorrect result.

Example: ${\displaystyle 23\;2\cdot 4\;-}$

           stack : []
o = 23     stack : [23]
o = 2      stack : [23,2]
o = *
right = 2  stack : [23]
left = 23  stack : []
t = 46     stack : [46]
o = 4      stack : [46,4]
o = -
right = 4  stack : [46]
left = 46  stack : []
t = 42     stack : [42]

Models

Compared to purely algebraic pocket calculators, there are only a few pocket calculator models that also or exclusively support UPN; the only established manufacturer that produces a large number of UPN-enabled devices is Hewlett-Packard . With the exception of the pure UPN pocket calculator HP-12C, which has been available since 1981, and some purely algebraic devices in the lower price range, the HP pocket calculators that came onto the market at the beginning of 2007, such as the HP-50g and the HP Prime, support both input notations.

The Russian company Semico from Novosibirsk is currently also offering pocket and desk calculators with UPN input, but only with a Cyrillic keyboard. Since 2012, the Swiss company SwissMicros has also been manufacturing a range of different UPN computers, which are mainly based on models from HP.

The Calc calculator integrated in Emacs optionally uses the reverse Polish notation. On the shell of almost every Unix system, the computer dc is available, which is also based on the reverse Polish notation. The macOS computer can also optionally be used in UPN mode, although an incorrect implementation of the stack in earlier versions restricted usability. The stack has been correctly implemented here since macOS 10.12 (Sierra) at the latest.

In addition, a number of programs that emulate UPN computers or use UPN are offered, especially in the open source , free and shareware areas.

Some BASIC dialects (especially on HP computers) have used the UPN form to represent the bytecode internally. These computers translated the entered program lines (and arithmetic expressions) into UPN and stored them in memory. During the runtime, the expressions could be processed with maximum efficiency, since no arithmetic conversions or priorities had to be carried out. In particular, the HP 70 and 80 series computers were able to achieve high processing speeds despite the low clock frequency.

history

The Polish notation (also prefix notation or Łukasiewicz 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 .

Ł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 .

The same effect of the absence of parentheses is achieved if the operator is not in front of the operand but after it. This variant of the Polish notation, known as "reverse Polish notation", was probably also seen by Łukasiewicz. However, the reverse Polish notation was explicitly addressed and used in practice by the Australian philosopher Charles Hamblin in the 1950s .

Individual evidence

1. ↑ Günter Jorke, Bernhard Lampe, Norbert Wengel: Arithmetic algorithms of micro computing technology. Edition 1, VEB Verlag Technik, Berlin 1989 ISBN 3-341-00515-3 ( books.google.de ).
2. ↑ mk.semico.ru
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' (p. 131) also 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, p. 88).
4. ^ On the history of the logic of propositions. In: Łukasiewicz: Selected Works. 1970.

literature

• Donald Knuth : The Art of Computer Programming , Volume 1: Fundamental Algorithms . 3. Edition. Addison-Wesley, 1997, ISBN 0-201-89683-4 , pp. 338 .
• Alfred V. Aho , Jeffrey D. Ullman : The Theory of Parsing, Translation, and Compiling, Vol. 1, Parsing . 1st edition. Prentice Hall, 1972, ISBN 0-13-914556-7 , pp. 214 .
• 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 ).

Web links

• An introduction to reverse Polish notation at HP
• Postfix Notation - mini lecture (English)
• Using the RPN at HP (English)
• Is it Really a Pathetic Name? Lecture at the HP Handheld Conference on, 22. – 23. Sept. 2012 in Nashville (English)