This page is referenced from LostInaSeaofParentheses
, which contains discussion on this topic. Please preserve this page, since it is a historic artifact brought in from UseNet
, and not a "live" Wiki.
Wonderful! The best explanation I've seen of this issue. -- DanielKnapp
From: firstname.lastname@example.org (Kaz Kylheku)
Subject: Re: java or c++ as first language
Date: 29 Jan 2003 10:43:27 -0800
Jerry Coffin <email@example.com> wrote in message news:<MPG.18a0a466b245c2f998976f@news>...
> In article <firstname.lastname@example.org>,
> email@example.com says...
> > That syntax serves as a barrier between the language and the programmer,
> ...or not. Compare:
> LISP: (+ x ( * y z))
> C++: x + y * z;
> and the difference is pretty obvious to most people.
However, the similarity is not pretty obvious to most people, which is
the point. The two expressions have the same *inner* syntax. That
difference which is obvious is the surface syntax, or read syntax.
If you say ``syntax'' to a Lisp programmer, she understands that to be
the tree structure. The parentheses, or InfixNotation
or whatever are
just the read syntax.
You can write an abstract syntax tree for the C++ notation like this:
Okay, now traverse it in preorder notation, printing the parent first,
then the children, recursively, and place a parenthesis before each
parent and after its last child:
(+ x (* y z))
> Even experienced
> LISP programmers have to stop and think about things to figure out even
> a moderately complex mathematical expression.
Are you an experienced Lisp programmer? I'm mildly experienced and I
don't have any problems.
> By contrast, almost any
> reasonably intelligent 12 year-old can read the second without really
> having to try at all.
s which mimic mathematics work well only when the
nesting level is not too deep, and the whole thing is written on one
line. There is no satisfactory way to break infix notations across
Moreover, there are issues of precedence. That twelve-year-old has
gone through several years of hard-wiring to parse multiplication at a
higher precedence to addition. But throw in some unfamiliar operators,
and he is stuck. You can always parse the *structure* of Lisp even if
you don't know the meaning of the utterance due to unfamiliar symbols.
Lastly, there are only so many infix operators. When those run out,
languages with infix expression syntax switch to function call
Lisp's notation is basically same thing as function call notations, but
with the superfluous commas removed, and the parenthesis moved to the
left of the function designator to properly enclose the entire call,
so that (f x y z) is analogous to f(x, y, z).
A properly formatted prefix notation can always be read as a sideways
tree, similar to the layout of a GUI tree control:
(and (or (not x)
(not (or (and z
Taking out the parentheses and adding some connecting line segments we
and +-- or +-- not --- x
| +-- not --- y
+-- not --- or +-- and +-- z
| | |
| | +-- w
| +-- and +-- s
| +-- t
+-- or +-- a
See? Same physical arrangement of symbols as the Lisp expression. You
can see a sideways tree in the canonically formatted parenthesized
notation. Moreover, you can mentally ``fold'' portions of the tree
that you are momentarily not interested in it, like closing the nodes
of a GUI tree control. Also note how the above resembles a logic gate
diagram, albeit with the propagation going right to left. Why do
digital circuit designers draw pictures rather than spew infix
You can't easily see a tree in the InfixNotation
. When it's written
all on one line, it's a kind of downward-flattening projection of the
leaves of the syntax tree, which you have to mentally unfold, possibly
disambiguating by applying rules of precedence, if parentheses have
been removed. There is no satisfactory way to split infix expressions
into multiple lines such that a tree structure is apparent.
Here it is:
(((not x) or (not y)) and (not ((z and w) or (s and t))) and (a or b))
I have not included associativity parentheses to show the left-right
grouping of the and operator. This is clearly hard to read, and so we
would like to break it into multiple lines. The question is how? Let's
((not x) or (not y))
and (not ((z and w) or (s and t))
and (a or b)
But the first AND clause doesn't line up with the other two. There is
no obvious tree structure. How about moving the operators to the
((not x) or (not y)) and
(not ((z and w) or (s and t))) and
(a or b)
then apply recursively:
((not x) or
(not y)) and
(not ((z and w) or
(s and t)) and
(a or b)
Or maybe write the infix operators on separate lines?
((not x) or (not y))
(not ((z and w) or (s and t)))
(a or b)
Hmm. Recurse into constituents:
(not ((z and w)
(s and t)))
(a or b)
Mathematics actually has a far richer notation than infix; a two
dimensional one. Only the infix part of it survives into the algebraic
expression syntaxes of [programming languages]
. Also, mathematicians
invent specialized operators and shorthands for which allow them to
concisely express the idea of some branch of thought. It's a kind of
macro-processing, like in Lisp.