Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ucbvax!hplabs!otter!sfk
From: sfk@otter.hpl.hp.com (Stephen Knight)
Newsgroups: comp.lang.lisp
Subject: Re: Re: Code as data (replies to comments).
Message-ID: <1350021@otter.hpl.hp.com>
Date: 11 Jun 89 14:21:52 GMT
References: <1057@syma.sussex.ac.uk>
Organization: Hewlett-Packard Laboratories, Bristol, UK.
Lines: 254

A few quick replies to these interesting comments followed by a longer
exposition of my crazy ideas.

> It's a very important benefit of Lisp that there is no distinction
> between "built-in operators" and "user-defined functions". 

Of course.  But this does not imply prefix syntax (cf. Prolog for counter
example.)  The point I was trying to make was that Lisp has made unsatisfying
compromises, and I gave an arithmetic expression as an example.  Other
languages do not make this compromise and do not seem to suffer any penalty.

> Meanwhile, Lisp also has the
> advantage that nobody has to learn a bunch of arbitrary "precedence
> rules"; everything just works in the obvious way.

At the expense of inflexible and rather odd-looking expressions.  Again, I was
trying to establish the notion that a compromise has taken place.  I would 
certainly agree that the over-use of infix syntax is poor style.

>>    Outside the Lisp
>>    community, the syntax is widely considered to be a laughing matter.  
> 
> It's gratifying to see that this conversation is being kept on a
> rational, intellectual plane.

Maybe you feel the remark was tactless but that's life as I see it,
sorry.  I *promise* that I was not trying to create a slanging match.  I
was only trying to show by dramatic contrast that Lispers are very insular in
their views on the weaknesses of Lisp.  The fact that people scoff at
Lisp's syntax signifies that a real compromise of readability has taken
place.  I appeal to your honesty.  Haven't you noticed people scoffing
at Lisp purely because of its syntax?  I think that's a silly reason to
reject a most interesting language.  I want to accept it as a valid criticism
and propose a route to a better language.

> In just about all the cases you listed, there's nothing "very
> strange"; these things are simply different from what you are familiar
> with. 

Hmm.  I must have structured this a bit poorly.  The idea was to show that
Lisp's syntax is not compatible with the claim that code reflects data.
The example of '#( ... )' was intended to provoke the observation that
the choice of '#(' is completely arbitrary and therefore Lisp has a concrete
syntax, at least in this instance.  The sucession of examples was intended
to hammer this point home.  These observations were meant to lead to this
relatively obvious point.  Lisp has slowly but surely over the years acquired
a concrete syntax whose relationship with the underlying parser tree is
less and less direct.  Given this, I think a better compromise would be to
separate concrete and abstract syntax entirely, in the manner of modern
programming languages.

> One of the unusual design criteria of Lisp is that people often
> use it to create their own embedded languages, and this little
> decision makes it a bit more convenient for some of them.

There are other languages which do this, too.  They don't have prefix syntax.
Furthermore, the introduction of syntax is not an obvious problem in this
regard.

>>    Why are atoms quoted with a single quote at the start?
> 
> Everything is quoted with a single quote at the start, not only
> "atoms".  There's no need for a close quote; it would be entirely
> redundant.

At the risk of seeming ludicrous for discussing trivia in depth, there is
a quite serious point lurking here.

It should be clear that there is an implicit closer for an open quote --
namely the token boundary.  If the atom being quoted contains a token
boundary in its text it needs quoting in a more conventional manner with
string-like quotes.  As this is only an occasional requirement, Lisp has
a second quoting convention rather than only one.  (It has at least
three, of course.)

The absurdity is that a quote is chosen for the implicit close convention and
a vertical bar for the open-close convention.  The point here is that, for a
beginner, Lisp is dominated by bracket-pairs which must be matched exactly.
But almost immediately, the beginner is confronted with a quote (a close
quote, in fact) that doesn't need opening.  The impression of arbitrary rules
and poor choices is established almost immediately.

             -- OK, So what's the alternative(s) --

Rather than raising any more hackles, I'd like to propose my 'vision'
of Lisp with Pascal-like syntax, and an introduction route that hopefully
wouldn't have too many Lisp hackers hanging themselves in the morning.  
In case you haven't guessed, much of this vision derives from Prolog.  (I'm
not a great Prolog fan, by the way, so don't bother knocking it :-))

The two key ideas are to clean up the parse-tree representation of Lisp by
making the forms regular and to divorce concrete from abstract syntax.  A
corollary is that by having a clear intermediate form it becomes relatively
easy to begin defining multiple standard syntaxes -- one syntax being
s-expression like, the other Pascal-like, and perhaps others can be 
considered that also have merit.

Firstly, I suggest representing the parse-tree in s-expression format with
the head of each s-expression being one of a fixed set of atoms denoting
special forms.  Thus where one would have written
    (f E1 ... En)
the 'raw' syntax requires
    (APPLY f E1 ... En)
All and *only* literals would be quoted.  Thus where one would have written
    (f 'a 'b 7)
one now has
    (APPLY f (QUOTE a) (QUOTE b) (QUOTE 7))
[So far, this should be familiar to anyone who has bumped into Lispkit Lisp.]  
It is a matter of taste, whether to go to the next stage and insist that
even variables are tagged with an appropriate atom.
    (APPLY (VAR f) (QUOTE a) (QUOTE b) (QUOTE 7))
As you can see, the correspondance between form and function has been made
excruciatingly obvious.  

Next, one makes EVAL work on this new format -- only one gives it a sensible
name such as 'raw-eval' so that you don't ordinarily fall over it.  The old
eval has to do a little bit more work to massage s-expressions into the
required form.

The vital stage is that Lisp is then defined in terms of this canonical
form.  The alternative syntaxes are going to be defined in terms of READ
functions (parsers) that generate s-expressions in this format.  This will
imply the need for two types of READ -- one that reads in a literal and
one that reads in a program.  Of course, the former is no more than a 
component of the latter.

The 'visionary' stage (which I freely admit is no more than a fantasy) is
then to restructure Lisp standards to accomodate the idea of multiple
syntaxes.  This means separating the standard into two levels, the lower
level defines Lisp in terms of the canonical form, the upper level(s) define
readers for the various syntaxes together with a technique for integrating
the reader into the Lisp interpreter.  (Actually, I imagine this is no more
that ensuring that the 'raw' interpreter takes a parser as a parameter +
the requirement for a notion of current-parser + parser associated with a 
package.  That's easy.)

This would then open the field for standardisation of new syntaxes.  All
the committee would have to do is ensure that it was compatible with the
lower-level of the standard, convince 1 million Lisp programmers that it's
totally brilliant, and a new look is born !:-)  Needless to say, the first
and original syntax will be there, in all its glorious technicolor.  So this
should satisfy Lispers who want to stick with the current concrete syntax.

Of course, I think that *all* languages should be defined this way, not 
just Lisp.  The recent difficulties that the Prolog standardisation group
had with respect to syntax could, I think, have been largely eliminated
by constructing the standard in this manner.  

                -- And what's the payoff? --

Well, what kind of look would I give Lisp?  As I have tried to show that
Lisp's syntax is outdated and wrong-headed, I suppose I ought to put my
own ideas up for demolition.  I won't say I didn't ask for it....

Concepts:
* I admire the philosophy of languages, such as Ada and Pop11, which have
  explicit opening and closing pairs for their major syntactic constructs.
  They also have plenty of padding words, such as 'then', 'else', 'do',
  which improve local readability.
* I also enjoy the use of infix syntax for operators such as assignment,
  arithmetic, boolean operators, and a few other conventional cases.  Although
  user-definable syntax is attractive from the viewpoint of orthogonality
  of syntax, my experience is that it needs strict limiting to be acceptable.
  So I would limit user-defined operators to be of a single precedence level
  and enforce bracketing where there is potential ambiguity.
* If the language is intended for functional programming then I prefer
  function application to be denoted by expression juxtaposition.  This 
  doesn't work so well in Lisp because functions can take multiple
  arguments.  So for this purpose, I think that the standard prefix form
  that is familiar from mathematics and languages such as FORTRAN and Pascal
  is appropriate.
* In imperative languages, it's a good idea to permit each expression
  context to contain a sequence of expression (separated by the ubiquitous
  semicolon (which is optional at the end of sequences)) and to allow
  declarations.
* There are many occasions when monadic operators look best in postfix
  format.  I would borrow the postfix '.' of (C, Pascal, Ada, Pop11,...)
  for this.
* I think it is a point of good syntax design for the formal parameter list
  to mirror the actual parameter list.  Thus I prefer DEFINE to DEFUN.
* The list syntax of Prolog is admirable because it elegantly integrates
  bracketing with list appending without the need for quoting (as in Lisp
  and Pop11) and *also* works in a functional context, unlike other Prologian
  ideas.

Examples:
When these points are taken together, you get a language which looks 
something like this.  Here is 'append' written in this style.

define append( x, y ) as
    if x = [] then
        y
    else
        [ x.head | append( x.tail, y ) ]
    endif
enddefine

(   If you wanted to be cute you could write,
        define append( x, y ) as [|x |y] enddefine
    but that's because append is built into the syntax.  It's just like
    writing
        (defun append( x y ) `( ,@x ,@y ))
    but who'd be so gross?
)

The next example is defining 'reverse'.  I'd do it like this.

define fold( op, seed, list ) as
    if list = [] then
        seed
    else
        fold( op, op( list.head, seed ), list.tail )
    endif
enddefine

define reverse( list ) as
    fold( cons, [], list )
enddefine

And if I suspected the compiler was too stupid to optimise 'fold' into 
an iterative format, I'd write the following, where -> is assignment from
left to right.

define fold( op, seed, list ) -> seed as
    for i in list do
        op( i, seed ) -> seed
    endfor
enddefine

I think that I would follow Pop11 in using a left to write assignment for 
two reasons.  Firstly, it suggests that the expression is evaluated before
the target (and I would insist that that was true).  Secondly, it means that
the formal parameter line can echo the actual call and still put the name
of the function being defined first.  Otherwise I'd have to have written
    define seed := fold( op, seed, list ) as ...
which is OK but less attractive to my eyes.  The for loop construct is picked
out of Pop11, too, of course.  Unlike Pop11, I assume in the example, that 
the loop variable is automatically declared locally to the for loop -- as in
Ada and Algol68, for example.  In addition, the loop variable would be
protected from assignment, as in Algol68, which can be syntactically enforced.

So, these are my crazy ideas.  I think they give Lisp a new and attractive
look, borrow from modern languages the best, and leave the dross behind.
The language is still Lisp, of course, which is the beauty of the thing.

Ah well, time for the flames, I suppose ....

Steve Knight
HP Labs, Bristol
June 11th 1989
---------------------------------------------------------------------------
The views expressed above are not necessarily those of my employers or even
my friends, I am sad to say.  But I am working on it.
---------------------------------------------------------------------------