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”, iscalled

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 itto 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 notionsin

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

xa*@xahlee.org

∑ http://xahlee.org/