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 itto 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 of where one places the “operator” or function. There is

always just a single position given with explicitly enclosed arguments.

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

“pre-fix” has no signifance in Full Functional Notation systems and

can only engender confusion in the Algebraic Pre-fix Notation systems

where the term has significance.

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 in the following ways: “(a+b)+c” or “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 expression is what's really

important.

----

This post is archived at:

http://xahlee.org/UnixResource_dir/writ/notations.html

Xah

xa*@xahlee.org

∑ http://xahlee.org/