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

[xahlee at gmail.com]

How Purely Nested Notation Limits The Language's Utility

[The full HTML formatted article is available at:
http://xahlee.org/UnixResource_dir/writ/notations.html
]

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 at y === 1, π/2, -π/2],
      If[y == 0, If[Sign at x === 1, 0, π],
        If[Sign at y === 1, ArcCos at x, 2 π - ArcCos at 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 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 (λ), 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 nested syntax, 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 at g@h at 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.

(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.)

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