gateley@m2.csc.ti.com (John Gateley) (02/25/90)
Thanks to all who responded to my query about postfix being better than
prefix. After thinking about it, I concluded that postfix and prefix are
equivalent: that is, if you have any prefix notation for a language,
there is a postfix notation for the language and it has the same
drawbacks/advantages of the prefix language. My personal preference
is for prefix, but this is purely religous.
First, I would like to try and disprove the claim that postfix is
easier to parse than prefix. Consider the following prefix if
expression.
(if (if (foo arg1)
(bar arg2)
(baz arg3))
(bum arg4)
(boo arg5))
In postfix this would be:
arg1 foo arg2 bar arg3 baz if arg4 bum arg5 boo if
The semantics of the prefix evaluates (baz arg2) ONLY if (foo arg1)
returns a true value, so in order to properly parse the postfix
expression, you have to do some lookahead to determine if the expression
is an IF expression. What this means is that you have to parse it as
follows:
read arg1
read foo
read arg2
read bar
read arg3
read baz
read if
At this point, if we hadn't read an IF, and an IF were the longest
special form in our language, we would go ahead and emit standard code
for the three applications. Since we did read an IF, we still don't emit
anything.
read arg4
read bum
read arg5
read boo
read if.
Now, we have reached the end of the program, and it is only because of
that that we can emit code! Note that if you use grouping, then the
postfix version is just as easy to parse as the prefix version.
Second, I would like to try and disprove the claim that postfix needs no
grouping operator (or show that if it is true, then the corresponding
prefix notation also needs no grouping operator).
Consider the prefix expression:
(+ a b c (* d e f) g h i)
Trying to convert this into plain postfix gives:
a b c d e f * g h i +
If you look at this, there is no way to tell if "a" is an argument of
"*" or of "+"! So, we use a grouping operator for postfix:
a b c (d e f) * g h i +
This is a correct version, but actually takes advantage of the fact that
we are at "top level". If this were a nested expression, then we would
have to write:
(a b c (d e f) * g h i) +
Guess what: we nested the grouping operator (just like in the equivalent
prefix expression). This happens of course because of allowing any
number of arguments to be taken. If you restrict the language to
operators which only accept fixed number of arguments, then there is no
grouping needed, but there is no grouping needed for the prefix version
either. Consider:
a b + c * e f + *
This can be represented in prefix without grouping as:
* * + a b c + f e
Presto, no grouping needed here either.
Some people mentioned a variation of postfix notation that had optional
arguments AFTER the operator. (To me, this notation is not true
postfix). Still there are some problems with this approach: consider the
postfix expression:
arg1 arg2 operator opt1 opt2 "x"
Suppose operator takes three optional arguments, then the above is a
complete program, and returns an answer. But suppose that operator only
takes two: then the answer is different: it is the operator "x" applied
to whatever answer is returned by the first operator. This seems to
require that the language be interpreted instead of compiled (hint, what
if x were IF). It is an interesting idea, but I am not sure whether the
interpretation requirement is worth the extra expressive power.
Using postfix with first class functions also seems a bit bizarre to me.
First of all, you need an "apply" operator:
(foo (lambda (x) (+ x 1))) ; calling foo with a single argument which is
; a function that adds 1 to its argument.
Naively writing postfix:
<lambda (x) (+ x 1)> foo
doesn't make sense: both foo and the lambda term are the same kind of
object: a function. There is no indicator that the lambda term is an
argument instead of an "operator". (If you think that you can just wait
til the function has enough arguments, this doesn't work: replace the
lambda term with one that accepts 0 arguments). Instead, you need to
write:
<lambda (x) (+ x 1)> foo <apply>
where <apply> is the operator that says: apply my last argument to
whatever else is on the stack (modulo grouping of course :^). In Lisp
style prefix notation, the grouping operator also happens to be the
apply operator as well, so this works okay for prefix (and postfix with
grouping).
John
gateley@m2.csc.ti.com