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 calling it “prefix notation” is misleading and misconception at a fundamental level.
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”, not “((3+2)*5)>7”, because the operator “*” has a higher stickness than the operator “+”, and “+” has a higher stickness than the “>” operator. 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 the above example is written as: “(> (+ 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 matching delimiters.
The reason for the misconception that lisp notation is “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.
2000-02-21, 2007-05
[In the following essay, I discuss prefix, infix, postfix notations and Mathematica's syntax for them.]
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 interpret source code linearly, the logic of their lexical structure is necessarily hierarchical (i.e. tree). The lisp's notation, is the most effective in visually showing the logic of the syntax. This is because, a function and its arguments, are simply laid out inside a matching delimiter. 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 the same how math are written traditionally.
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(pointA,pointB)” is a function that returns a function f, such that “f(graphicsData)” will reflect the “graphicsData” along a line passing “pointA” and “pointB”. In lisp, we would write “((Reflection pointA pointB) graphicsData)”. In Mathematica, we would write “Reflection[pointA,pointB][graphicsData]”. In lisp's version, the visual nesting corresponds to the logics of the evaluation. In the Mathematica's form, the visual nesting is now broken.
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.
A prefix notation in Mathematica is represented as “f@arg”. (A prefix notation in this context limits it to uses for functions on only one argument) For example: “f@a@b@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@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 are other 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)”.
Note: it can also make the source code harder to read if the notations are mixed up unreasonably or intentionally as in obfuscated code.
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, “expr1 ? expr2 : expr3”, “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) 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. 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.
2007-05-03
There is a common complain by programers about lisp's notation, of nested parenthesis, being unnatural or difficult to read. Long time lisp programers, often counter, that it is a matter of conditioning, and or blaming the use of “inferior” text editors that are not designed to display nested notations. In the following, i describe how lisp notation is actually a problem, in several levels.
(1) Some 99% of programers are not used to the nested parenthesis syntax. This is a practical problem. On this aspect along, lisp's syntax can be considered a problem.
(2) Arguably, the pure nested syntax is not natural for human to read. Long time lispers may disagree on this point.
(3) Most importantly, a pure nested syntax discourages frequent or advanced use of function sequencing or compositions. This aspect is the most devastating.
The first issue, that most programers are not comfortable with nested notation, is well known. It is not a technical issue. Whether it is considered a problem of the lisp language is a matter of philosophical disposition.
The second issue, about nested parenthesis not being natural for human to read, may be debatable. I do think, that deep nesting is a problem to the programer. Here's a example of 2 blocks of code that are syntactically equivalent in the Mathematica language:
vectorAngle[{a1_, a2_}] := Module[{x, y},
{x, y} = {a1, a2}/Sqrt[a1^2 + a2^2] // N;
If[x == 0, If[Sign@y === 1, π/2, -π/2],
If[y == 0, If[Sign@x === 1, 0, π],
If[Sign@y === 1, ArcCos@x, 2 π - ArcCos@x]
]
]
]
SetDelayed[vectorAngle[List[Pattern[a1,Blank[]],Pattern[a2,Blank[]]]],
Module[List[x,y],
CompoundExpression[
Set[List[x,y],
N[Times[List[a1,a2],
Power[Sqrt[Plus[Power[a1,2],Power[a2,2]]],-1]]]],
If[Equal[x,0],
If[SameQ[Sign[y],1],Times[π,Power[2,-1]],
Times[Times[-1,π],Power[2,-1]]],
If[Equal[y,0],If[SameQ[Sign[x],1],0,π],
If[SameQ[Sign[y],1],ArcCos[x],
Plus[Times[2,π],Times[-1,ArcCos[x]]]]]]]]]
In the latter, it uses a full nested form (called FullForm in Mathematica). This form is isomorphic to lisp's nested parenthesis syntax, token for token (i.e. lisp's “(f a b)” is Mathematica's “f[a,b]”). As you can see, this form, by the sheer number of nested brackets, is in practice problematic to read and type. In Mathematica, nobody really program using this syntax. (The FullForm syntax is there, for the same reason of language design principle shared with lisp of “consistency and simplicity”, or the commonly touted lisp advantage of “data is program; program is data”.)
The following shows the same code with tokens transformed into the lisp style.
(SetDelayed (vectorAngle (list (Pattern a1 (Blank)) (Pattern a2 (Blank)))) (let (list x y) (progn (setq (list x y) (N (* (list a1 a2) (exp (sqrt (+ (exp a1 2) (exp a2 2))) -1)))) (if (eq x 0) (if (equal (signum y) 1) (* π (exp 2 -1)) (* (* -1 π) (exp 2 -1))) (if (eq y 0) (if (equal (signum x) 1) 0 π) (if (equal (signum y) 1) (acos x) (+ (* 2 π) (* -1 (acos x)))))))))
Note: The steps to transform the sample Mathematica code in FullForm to lisp's sexp is done by these operations (for those curious):
The third issue, about how nested syntax seriously discourages frequent or advanced use of inline function sequencing on the fly, is the most important and I'll give further explanation below.
One practical way to see how this is so, is by considering unix's shell syntax. You all know, how convenient and powerful is the unix's pipes. Here are some practical example: “ls -al | grep xyz”, or “cat a b c | grep xyz | sort | uniq”.
Now suppose, we get rid of the unix's pipe notation, instead, replace it with a pure functional notation: e.g. (uniq (sort (grep xyz (cat a b c)))), or enrich it with a composition function and a pure function construct (aka lambda), so this example can be written as: ((composition uniq sort (lambda (x) (grep xyz x))) (cat a b c)).
You see, how this change, although syntactically equivalent to the pipe “|” (or semantically equivalent in the example using function compositions), but due to the cumbersome nesting of parenthesis, will force a change in the nature of the language by the code programer produces. Namely, the frequency of inline sequencing of functions on the fly will probably be reduced, instead, there will be more code that define functions with temp variables and apply it just once as with traditional languages.
A language's syntax or notation system, has major impact on what kind of code or style or thinking pattern on the language's users. This is a well-known fact for those acquainted with the history of math notations.
The sequential notation “f@g@h@x”, or “x//h//g//f”, or unixy “x|h|g|f”, are far more convenient and easier to decipher, than “(f (g (h x)))” or “((composition f g h) x)”. In actual code, any of the f, g, h might be a complex pure function (aka lambda constructs, full of parenthesis themselves).
Lisp, by sticking with a almost uniform nested parenthesis notation, it immediately reduces the pattern of sequencing functions, simply because the syntax does not readily lend the programer to it as in the unix's “x|h|g|f”. For programers who are aware of the coding pattern of sequencing functions, now either need to think in terms of a separate “composition” construct, and or subject to the much problematic typing and deciphering of nested parenthesis. (in practice, it's mostly done by writing the inline functions as a auxiliary function definitions on their own, then another code block sequence them together.)
(Note: Lisp's sexp is actually not that pure. It has ad hoc syntax equivalents such as the “quote” construct “ '(a b c) ”, and also “`”, “#”, “,@” constructs, precisely for the purpose of reducing parenthesis and increasing readability. Scheme's coming standard the R6RS ↗, even proposes the introduction of [] and {} and few other syntax sugars to break the uniformity of nested parenthesis for legibility. Mathematica's FullForm, is actually a version of unadulterated nested notation as can be.)
Related essays:
Page created: 2006-03. © 2006 by Xah Lee.