also known as Reverse Polish Notation
), is a notational system where the operation/function follows the arguments. For example, "1 2 add" would be postfix notation for adding the numbers 1 and 2.
Most programming languages use either prefix notation ("add(1, 2)" or "(add 1 2)") or infix notation ("1 add 2" or "1 + 2"). Prefix and infix are more familiar to most people, as they are the standard notations used for arithmetic and algebra. Many people wonder why anyone would use this "weird" postfix notation.
The answer is that it is useful, especially for programming, because it clearly shows the order in which operations are performed, and because it disambiguates operator groupings. For example, look at this postfix expression:
1 2 + 3 * 6 + 2 3 + /
This means "take 1 and 2, add them, take 3 and multiply, take 6 and add, take 2 and 3, add them, and divide". In contrast, the equivalent expression in InfixNotation
(((1 + 2) * 3) + 6) / (2 + 3)
This may seem more familiar, but note the need for parentheses to control the order of evaluation. The prefix notation would be
(/ (+ (* (+ 1 2) 3) 6) (+ 2 3))
which you to read "inside-out" to evaluate.
It isn't all roses, however: for example, in the expression above, you have to remember all arguments left for "future operations": for example, for the last operation ("divide"), it is at least as cumbersome to find out just what is to be divided as it is to read the prefix expressions. Postfix notation also really only makes sense for languages where operations are not first-class; and so, is ill suited for most FunctionalProgrammingLanguage
- Not really. You either pass references to functions as parameters (execution tokens in ForthLanguage, with the same "tick" operator as LispLanguage) or add syntax for code blocks as in JoyLanguage. Joy is in fact a very regular and elegant functional language.
In programming languages that use postfix notation, the order of operations is clear. For example,
getWindow topLeft x
means "call getWindow
, then call topLeft
with that result, then call x
with that result". The prefix notation would be
(x (topLeft (getWindow)))
which is "inside-out and backwards" in comparison to the actual order of operations.
The most difficult thing in functional prefix notation is that, usually the arguments are evaluated before the function, but arguments to the left are evaluated before arguments to the right. So you actually end reading some parts of the expression from left to right, and some from right to left.
Some programming languages, such as ForthLanguage
, are designed to use postfix notation. Such languages generally use a stack to hold arguments and intermediate results. So, for example, "1 2 + 3 *" is evaluated as "push 1 to the stack; push 2 to the stack; pop two items from the stack, add them, and push the result (3) to the stack; push 3 to the stack; pop two items from the stack, multiply them, and push the result (9) to the stack". Such an evaluator is very easy to implement, and very easy to extend with additional operations.
Many other programming languages support similar notations. For example, "getWindow topLeft x" could be a SmalltalkLanguage
expression, where getWindow
returns an object, topLeft
is a message sent to it, and x
is a message sent to the result of that operation.
In many languages, a similar expression could be represented as "getWindow().topLeft().x()" or "getWindow()->topLeft()->x()". Here, "." or "->" are infix operators, but if you ignore them and look only at the function calls, you get something similar to a postfix expression. The point here is that postfix is not really unnatural; programmers think this way all the time. Postfix only becomes difficult for people to read when the stack is used to store a value "under" some evaluation.
This is not an attempt to convert the world to postfix, nor to convince anyone that prefix and infix notations are "bad". It simply demonstrates why some people like to use postfix for some purposes.
The prefix notation doesn't require parentheses if the number of arguments are known. Then you can write the postfix expression
1 2 + 3 * 6 + 2 3 + /
as the prefix expression
/ + * + 1 2 3 6 + 2 3
. Both of these are tree-traversals (preorder vs. postorder), but both of them depend on the number of arguments being known, as well as the fact that the leaf nodes have numbers on them while the non-leaf nodes have operators on them.
* 6 2 3
Postfix notation still has the advantage that it reflects the order in which operations are performed.
The main difference is that postfix doesn't require parsing in the sense that the prefix notation does. In postfix notation, the number of arguments for a given operator (word) needs only be known to that word -- no additional layer of look-ahead is required -- the elements are executed as they are encountered.
Consider print + * 3 2 1
and the gymnastics required to evaluate it:
- print -- Print what? Well, hold that thought (somewhere) ...
- + (add) -- Add what? Well, hold that thought ...
- * (mul) -- Multiply what? Well, hold that thought ...
- 3 -- Ahha! An argument value! Well, hold that for a moment ...
- 2 -- Another arg value -- wait, I need another one ...
- 1 -- Ok, got that last one, let's dance ...
- retrieve the 3 and 2, do the 3 x 2 operation, store the result
- retrieve the 1 and the last result, do the 1 + 6 operation, store the result
- format and print the "7"
And the icky part is that you need some mechanism to tell print
how many arguments to expect in the expression that follows.
As opposed to 3 2 * 1 + print
which goes like this:
- 3 is a number, push 3
- 2 is a number, push 2
- * is a word --> pop two numbers and multiply, push result (6)
- 1 is a number, push 1
- + is a word --> pop two numbers and add, push result (7)
- print is a word --> pop a number, format and print.
Now, optimizing compilers can pretty much make all of this moot, but what's not moot is that I can read and evaluate a progression of RPN expressions without getting lost, whereas, without brackets of some kind, other notations are more of an adventure.
Not really. Optimizing compilers can't rearrange the order of functions that return values, only atomic numbers. The reason is side-effects: "10 + getSalary() + getBonus()" could yield a different result than "getBonus() + getSalary() + 10" since the methods could be dependent upon the sequencing of shared (global) state.
Further, because the RPN notation more closely models what the machine has to do to accomplish the task, interactive testing and analysis is easier.
And magically, because of the lack of look-ahead parsing overhead, the whole thing tends to fit in really small spaces. I have to admit that, though I make my living as an InfixNotation
coder with occasional excursions into raw AssemblyLanguage
, I'm a big fan of PostfixNotation
Another consequence of extensible RPN is readable stuff like this:
conveyor signal until
right arm full extend
right hand open
10 seconds wait
right hand close
right arm 5 degrees raise
right arm 15 degrees rotate
right arm 5 degrees lower
right hand open
right arm return
The prefix notation can also be evaluated with a stack, but the stack has to be able to contain partial subexpressions. When each subexpression is completed, you must evaluate it and push its result back into the input (or at least pretend to). The evaluator produces the result of * 3 2 slightly sooner than you think, like this:
It might be amusing to write a Scheme program to do this. If you want to see a Scheme macro that converts infix to postfix, there's one on DefineSyntax.
- print -- has 1 arg -- push "print __"
- + -- has 2 args -- push "+ __ __"
- * -- has 2 args -- push "* __ __"
- 3 -- is an arg -- pop "* __ __" and produce "* 3 __", which is incomplete, so push it
- 2 -- is an arg -- pop "* 3 __" and produce "* 3 2", complete, evaluate to get 6, prepend to front of input
- 6 -- is an arg -- pop "+ __ __" and produce "+ 6 __", which is incomplete, so push it
- 1 -- is an arg -- pop "+ 6 __" and produce "+ 6 1", complete, evaluate to get 7, prepend to front of input
- 7 -- is an arg -- pop "print __" and produce "print 7", complete, evaluate, no result
- stack and input are now empty
is a lovely postfix FunctionalProgrammingLanguage
. -- ThomasColthurst
this is also known as ConcatenativeCombinators?
also qualify as PostfixNotation
? also known as CollectsAndSelects?
. -- zuzu