The Concepts and Confusions of Pre-fix, In-fix, Post-fix and Fully
Functional Notations

Xah Lee, 2006-03-15

Let me summarize: The LISP notation, is a functional notation, and is
not a so-called pre-fix notation or algebraic notation.

Algebraic notations have the concept of operators, meaning, symbols
placed around arguments. In algebraic in-fix notation, different
symbols have different stickiness levels defined for them. e.g. “3
+2*5>7” means “(3+(2*5))>7”. The stickiness of operator symbols
are normally called “Operator Precedence”. It is done by giving a
order specification for the symbols, or equivalently, give each
symbol a integer index, so that for example if we have
“a⊗b⊙c”, we can unambiguously understand it to mean one of
“(a⊗b)⊙c” or “a⊗(b⊙c)”.

In a algebraic post-fix notation known as Polish Notation, there
needs not to have the concept of Operator Precedence. For example,
the in-fix notation “(3+(2*5))>7” is written as “3 2 5 * + 7
>”, where the operation simply evaluates from left to right.
Similarly, for a pre-fix notation syntax, the evaluation goes from
right to left, as in “> 7 + * 5 2 3”.

While functional notations, do not employ the concept of Operators,
because there is no operators. Everything is a syntactically a
“function”, written as f(a,b,c...). For example, the same
expression above is written as “>( +(3, *(2,5)), 7)” or
“greaterThan( plus(3, times(2,5)), 7)”.

For lisps in particular, their fully functional notation is
historically termed sexp (short for S-Expression, where S stands for
Symbolic). It is sometimes known as Fully Parenthesized Notation. For
example, in lisp it would be (f a b c ...). In the above example it
is: “(> (+ 3 (* 2 5)) 7)”.

The common concepts of “pre-fix, post-fix, in-fix” are notions in
algebraic notations only. Because in Full Functional Notation, there
is no concept for the positioning of the operator among its operands.
A Function's arguments are simply explictly written out inside a pair
of enclosing delimiters.

Another way to see that lisp notation are not “pre” anything, is
by realizing that the “head” f in (f a b c) can be defined to be
placed anywhere. e.g. (a b c f) or even (a f b c), and it's still not
pre- or in- or post- anything. For example, in the language
Mathematica, f(a b c) would be written as f[a,b,c] where the argument
enclosure symbols is the square bracket instead of parenthesis, and
argument separator is comma instead of space, and the function symbol
(or head) is placed in outside and in front of the argument enclosure
symbols.

The reason for the misconception that lisp notations are “pre-fix”
is because the head appears before the enclosed arguments. Such use
of the term “pre-fix” is a confusion engenderer because the
significance of the term lies in Algebraic notation systems.

2000-02-21

The common name for the lisp way is Fully Parenthesized Notation.
This syntax is the most straightforward to represent a tree, but it's
not the only choice. For example, one could have Fully Parenthesized
Notation by simply moving the semantics of the first element to the
last. You write (arg1 arg2 ... f) instead of the usual (f arg1 arg2).

Like wise, you can essentially move f anywhere and still make sense.
In Mathematica, they put the f in front of the paren, and use square
brackets instead. e.g. f[a,b,c], Sin[3], Map[f,list] ... etc. The f
in front of parent makes better conventional sense until f is itself
a list which then we'll see things like f[a,b][c, g[3,h]] etc. It's
worse when there are arbitrary nesting of heads.

A pre-fix notation in Mathematica is represented as “f@arg”.
Essentially, a pre-fix notation in this context limits it to uses for
function that has only one argument. More example: “f@a@b@c” is
equivalent to “f[a[b[c]]]” or in lispy “(f (a (b c)))”. A post-
fix notation is similar. In Mathematica it is, e.g. “c//b//a//f”.
For example “List[1,2,3]//Sin” is syntactically equivalent to
“Sin[List[1,2,3]]” or “Sin@List[1,2,3]”. (and they are
semantically equivalent to “Map[Sin, List[1,2,3]]” in Mathematica)
For in-fix notation, the function symbol is placed between its
arguments. In Mathematica, the generic form for in-fix notation is by
sandwiching the tilde symbol around the function name. e.g. “Join
[List[1,2],List[3,4]]” can be written as “List[1,2] ~Join~ List
[3,4]”.

In general, when we say C is a in-fix notation language, we don't
mean it's strictly in-fix but the situation is one-size-fits-all for
convenience. Things like “i++”, “++i”, “for(;;)”, 0x123,
“sprint(...%s...,...)”, ... are syntax whimsies. (that is, a ad
hoc syntax soup)

In Mathematica for example, there is quite a lot syntax sugars beside
the above mentioned systimatic constructs. For instance, Plus[a,b,c]
can be written as “a+b+c”, “Plus[a+b,c]”, “Plus[Plus
[a,b],c]”, or “(a+b)~Plus~c”.

The gist being that certain functions such as Plus is assigned a
special symbol '+' with a particular syntax form to emulate the
irregular and inefficient but nevertheless well-understood
conventional notation. For another example: Times[a,b] can be also
written as “a*b” or just “a b”. Mathematica also have C
language's convention of “i++”, “++i”, “i+=1” for examples.

As a side note, the Perl mongers are proud of their slogan of There
Are More Than One Way To Do It in their gazillion ad hoc syntax
sugars but unaware that in functional languages (such as Mathematica,
Haskell, Lisp) that there are consistent and generalized constructs
that can generate far far more syntax variations than the ad hoc
prefixed Perl both in theory AND in practice. (in lisps, their power
syntax variation comes in the guise of macros.) And, more
importantly, Perlers clamor about Perl's “expressiveness” more or
less on the useless syntax level but don't realize that semantic
expressibility is what's really important.

----
This post is archived at:
http://xahlee.org/UnixResource_dir/writ/notations.html


☄