Lisp Parentheses Use Net Article

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: kaz@ashi.footprints.net (Kaz Kylheku)
 Newsgroups: comp.lang.c++
 Subject: Re: java or c++ as first language
 Date: 29 Jan 2003 10:43:27 -0800
 Message-ID: <cf333042.0301291043.1b4e32aa@posting.google.com>

 Jerry Coffin <jcoffin@taeus.com> wrote in message news:<MPG.18a0a466b245c2f998976f@news>...
 > In article <cf333042.0301281206.1e3fd920@posting.google.com>, 
 > kaz@ashi.footprints.net says...
 > > That syntax serves as a barrier between the language and the programmer,
 > 
 > ...or not.  Compare:
 > 
 > LISP: (+ x ( * y z))
 > to:
 > 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:

   +
  x  *
    y z

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

Aha!

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

InfixNotations 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 multiple lines.

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 notations.

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 y))
       (not (or (and z
                     w)
                (and s
                     t))
       (or a
           b))

Taking out the parentheses and adding some connecting line segments we get:

   and +-- or  +-- not --- x
       |       |
       |       +-- not --- y
       |
       +-- not --- or  +-- and +-- z
       |               |       |
       |               |       +-- w
       |               |
       |               +-- and +-- s
       |                       |
       |                       +-- t
       +-- or  +-- a
               |
               +-- b

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 expressions?

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 try:

  ((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 right?

  ((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))
  and
  (not ((z and w) or (s and t)))
  and
  (a or b)

Hmm. Recurse into constituents:

  ((not x)
    or
   (not y))
  and
   (not ((z and w)
         or
         (s and t)))
  and
  (a or b)

Forget it!

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.