The Concepts and Confusions of Prefix, Infix, Postfix and Fully
Functional Notations
Xah Lee, 2006-03-15
[This articles explains away the confusion of common terms for
notation systems used in computer languages: prefix, infix, postfix,
algebraic, functional. These notation's relation to the concept of
operators. These are explained using examples from LISP, Mathematica,
and imperative languages. Then, it discuss some problems of purely
nested notation.]
In LISP languages, they use a notation like “(+ 1 2)” to mean “1+2”.
Likewise, they write “(if test this that)” to mean “if (test) {this}
else {that}”. LISP codes are all of the form “(a b c ...)”, where the
a b c themselves may also be of that form. There is a wide
misunderstanding that this notation being “prefix notation”. In this
article, i'll give some general overview of the meanings of Algebraic
Notation and prefix, infix, postfix notations, and explain how LISP
notation is a Functional Notation and is not a so-called prefix
notation or algebraic notation.
The math notation we encounter in school, such as “1+2”, is called
Infix Algebraic Notation. Algebraic notations have the concept of
operators, meaning, symbols placed around arguments. In algebraic
infix 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 is 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 postfix notation known as Polish Notation, there needs
not to have the concept of Operator Precedence. For example, the infix
notation “(3+(2*5))>7” is written as “3 2 5 * + 7 >”, where the
operation simply evaluates from left to right. Similarly, for a prefix
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 “prefix, postfix, infix” are notions in
algebraic notations only. Because in Full Functional Notation, there
are no operators, therefore no positioning to talk about. A Function's
arguments are simply explicitly 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 its syntax syntactical
remains the same. 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 (aka “head”) is placed in
outside and in front of the argument enclosure symbols.
The reason for the misconception that lisp notations are “prefix” is
because the “head” appears as the first element in the enclosed
parenthesis. Such use of the term “prefix” is a confusion engenderer
because the significance of the term lies in algebraic notation
systems that involves the concept of operators.
A side note: the terminology “Algebraic” Notation is a misnomer. It
seems to imply that such notations have something to do with the
branch of math called algebra while other notation systems do not. The
reason the name Algebraic Notation is used because when the science of
algebra was young, around 1700s mathematicians are dealing with
equations using symbols like “+ × =” written out similar to the way we
use them today. This is before the activities of systematic
investigation into notation systems as necessitated in the studies of
logic in 1800s or computer languages in 1900s. So, when notation
systems are actually invented, the conventional way of infixing “+ ×
=” became known as algebraic because that's what people think of when
seeing them.
--------
This post is part of a 3-part exposition:
“The Concepts and Confusions of Prefix, Infix, Postfix and Fully
Functional Notations”,
“Prefix, Infix, Postfix notations in Mathematica”,
“How Purely Nested Notation Limits The Language's Utility”,
available at:
http://xahlee.org/UnixResource_dir/writ/notations.html
Xah
[EMAIL PROTECTED]
∑ http://xahlee.org/
--
http://mail.python.org/mailman/listinfo/python-list
