The Concepts and Confusions of Prefix, Infix, Postfix and Fully Functional Notations

[Xah Lee]

Prefix, Infix, Postfix notations in Mathematica

2000-02-21, 2007-05

[In the following essay, I discuss prefix, infix, postfix notations
and Mathematica's syntax for them. The full HTML formatted article is
available at:
http://xahlee.org/UnixResource_dir/writ/notations.html
]

THE HEAD OF EXPRESSIONS

Lisp's nested parenthesis syntax is a Functional Notation. It has the
general form of “(f a b ...)” where any of the symbols inside the
matching parenthesis may again be that form. For example, here's a
typical code from Emacs Lisp.

; Recursively apply (f x i), where i is the ith element in the list
li.
; For example, (fold f x '(1 2)) computes (f (f x 1) 2)
(defun fold (f x li)
  (let ((li2 li) (ele) (x2 x))
    (while (setq ele (pop li2))
      (setq x2 (funcall f x2 ele))
    )
    x2
  )
)

Vast majority of computer languages, interpret source code in a one-
dimensional, linear nature. Namely, from left to right, line by line,
as in written text. (Examples of computer languages's source code that
are not linear in nature, are spread sheets, cellular automata,
graphical programing languages) For languages that interprets source
code linearly, the logics of their syntax necessarily have a
hierarchical structure (i.e. tree). The lisp's notation, is the most
effective in visually showing the logics of the syntax. This is
because, a function and its arguments, are simply laid out inside a
parenthesis. The level of nesting corresponds to the “precedence” in
evaluating the expression.

The first element inside the matching parenthesis, is called the
“head” of the expression. For example, in “(f a b)”, the “f” is the
head. The head is a function, and the rest of the symbols inside the
matching parenthesis are its arguments.

The head of lisp's notation needs not to be defined as the first
element inside the parenthesis. For example, we can define the “head”
to be the last element inside the parenthesis. So, we write “(arg1
arg2 ... f)” instead of the usual “(f arg1 arg2 ...)” and its
syntactical analysis remains unchanged. Like wise, you can move the
head outside of the parenthesis.

In Mathematica, the head is placed in front of the parenthesis, and
square brackets are used instead of parenthesis for the enclosing
delimiter. For example, lisp's “(f a b c)” is syntactically equivalent
to Mathematica's “f[a,b,c]”. Other examples: “(sin θ)” vs “Sin[θ]”,
“(map f list)” vs “Map[f,list]”. Placing the head in front of the
matching bracket makes the notation more familiar, because it is a
conventional math notation.

However, there is a disadvantage in moving the head of a expression
from inside the matching bracket to outside. Namely: The nesting of
the matching delimiters, no longer corresponds to the logics of the
syntax, when the head is itself a compound expression.

For example, suppose Reflection(vectorV,pointP) is function that
returns a function f, such that f(graphicsData) will reflect the
graphicsData along a line passing pointP and parallel to vectorV. In
lisp, we would write “((Reflection vectorV pointP) graphicsData)”. In
Mathematica, we would write “Reflection[vectorV,pointP]
[graphicsData]”. In lisp's version, the nesting corresponds to the
logics of the evaluation. In the Mathematica's form, that is no longer
so.

For another example, suppose Deriv is a function that takes a function
f and returns a function g (the derivative of f), and we want to apply
g to a variable x. In lisp, we would write “((Deriv f) x)”. In
Mathematica, we would write “Deriv[f][x]”. In lisp's version, the
nesting corresponds to the logics of the evaluation. In the
Mathematica's form, the logics of the evaluation no longer corresponds
to the nesting level, because now the head is outside of the enclosing
delimiters, so the head of expressions no longer nests.

PREFIX, POSTFIX, INFIX

A prefix notation in Mathematica is represented as “f at arg”.
Essentially, a prefix notation in this context limits it to uses for
functions on only one argument. For example: “f at a@b at c” is equivalent
to “f[a[b[c]]]” or in lispy “(f (a (b c)))”. Mathematica also offers a
postfix notation using the operator “//”. For example, “c//b//a//f” is
syntactically equivalent to “f[a[b[c]]]”. (unix's pipe “|” syntax, is
a form of postfix notation. e.g. “c | b | a | f”).

For example, “Sin[List[1,2,3]]” can be written in postfix as
“List[1,2,3]//Sin”, or prefix “Sin at List[1,2,3]”. (by the way, they are
semantically equivalent to “Map[Sin, List[1,2,3]]” in Mathematica) For
infix notation, the function symbol is placed between its arguments.
In Mathematica, the generic form for infix notation is by sandwiching
the tilde symbol around the function name. e.g.
“Join[List[1,2],List[3,4]]” is syntactically equivalent to “List[1,2]
~Join~ List[3,4]”.

In Mathematica, there is quite a lot syntax variations beside the
above mentioned systematic constructs. For example, 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”. “List[a,b,c]” can be written as “{a,b,c}”, and
“Map[f,List[a,b,c]]” can be written as “f /@ {a,b,c}”.

The gist being that certain functions are given a special syntactical
construct to emulate the irregular and inefficient but nevertheless
well-understood conventional notations. Also, it reduces the use of
deep nesting that is difficult to type and manage. For example, the
“Plus” function is given a operator “+”, so that Plus[3,4] can be
written with the more familiar “3+4”. The “List” function is given a
syntax construct of “{}”, so that, List[3,4] can be more easily
written as “{3,4}”. The boolean “And” function is given the operator
“&&”, so that And[a,b] can be written with the more familiar and
convenient “a && b”. Combining all these types of syntax variations,
it can make the source code easier to read than a purely nested
structure. For example, common math expressions such as “3+2*5>7”
don't have to be written as “Greater[Plus[3,Times[2,5]],7]” or the
lispy “(> (+ 3 (* 2 5)) 7)”.
C and Perl

When we say that C is a infix notation language, the term “infix
notation” is used loosely for convenience of description. C and other
language's syntaxes derived from it (e.g. C++, Java, Perl,
Javascript...) are not based on a notation system, but takes the
approach of a ad hoc syntax soup. Things like “i++”, “++i”, “for(;;)
{}”, “while(){}”, 0x123, “sprint(...%s...,...)”, ... are syntax
whimsies.

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 more syntax variations than the ad hoc
inflexible Perl both in theory AND in practice. (in lisp, its power of
syntax variation comes in the guise of macros.) And, more importantly,
Perlers clamor about Perl's “expressiveness” more or less on the
syntax level but don't realize that semantic expressibility is far
more important.

  Xah
  xah at xahlee.org
∑ http://xahlee.org/