www lispmeister.com

About

A life with Lisp blog

index | rss2.0 | atom

Author

Products

Order Succesful Lisp directly from bookfix.com


Order Successful Lisp by David B. Lamkins at amazon.de
German Shop: Lisp t-shirt
US Shop: JohnMcCarthy Lisp tshirt

Categories

Links

del.icio.us/lispmeister
bookfix.com
medigist.de
Successful Lisp
lemonodor.com
Foresight Institute
Lawrence Lessig
nanobot
Bill Clementson
FuturePundit
Planet Lisp
Nanotechnology Now
Nanodot.org
Unvollstaendigkeit

Archives

Calendar

Creative Commons License
hacker emblem blosxom

2004/05/07

Dave Moon: S-expressions are a bad idea

Paul Graham has a summary of all the suggestions he received for his ARC project. Dave Moon commented extensively on S-expressions, objects and the ARC syntax.(via Tayssir John Gabbour in comp.lang.lisp)
I want to comment on your use of S-expressions, based on what I learned 
in my couple of years researching Lisp hygienic macro ideas and working 
on Dylan macros.  Summary: I learned that S-expressions are a bad idea.  
There are three different things wrong with them, none of which have 
anything to do with surface syntax.  Having as a convenient abbreviation 
a surface syntax different from the program representation that macros 
work on is a fine thing to do.


[1] The (function . arguments) notation is not extensible.  In other 
words, there isn't any place to attach additional annotations if some 
should be required.  20 years ago it was noticed that there is no place 
to attach a pointer back to the original source code, for use by a 
debugger.  That's just one example.  This is easily patched by changing 
the notation to (annotation function . arguments), where annotation is a 
property list, but this is a bit awkward for macro writers.  The next 
point suggests a better fix.

[2] Representing code as linked lists of conses and symbols does not lead 
to the fastest compilation speed.  More generally, why should the 
language specification dictate the internal representation to be used by 
the compiler?  That's just crazy!  When S-expressions were invented in 
the 1950s the idea of separating interface from implementation was not 
yet understood.  The representation used by macros (and by anyone else 
who wants to bypass the surface syntax) should be defined as just an 
interface, and the implementation underlying it should be up to the 
compiler.  The interface includes constructing expressions, extracting 
parts of expressions, and testing expressions against patterns.  The 
challenge is to keep the interface as simple as the interface of 
S-expressions; I think that is doable, for example you could have 
backquote that looks exactly as in Common Lisp, but returns an 
<expression> rather than a <cons>.  Once the interface is separated from 
the implementation, the interface and implementation both become 
extensible, which solves the problem of adding annotations.

So you don't get confused, I am not saying that Dylan macros provide a 
good model of such an interface (in fact that part of Dylan macros was 
never done), nor that Dylan macros necessarily have any ideas you should 
copy.  I'm just talking about what I learned from the Dylan macros 
experience.  Actually if you succeed in your goals it should be 
straightforward for a user to add Dylan-like macros to Arc without 
changing anything in Arc.

Maybe someday I can explain to you the representation of programs I used 
in the Dylan compiler I wrote (never finished) after I left Apple.  It 
has some clever ideas so that it is efficient in terms of consing and the 
same representation can be used in all levels of the compiler from the 
surface syntax parser down to the machine code generator.  I'd have to 
retrieve the code from backup first.

[3] Symbols are not the right representation of identifiers.  This 
becomes obvious as soon as you try to design a good hygienic macro 
system.  This is really another case of failing to separate interface 
from implementation.  A symbol can be a convenient abbreviation, but in 
general an identifier needs to be a combination of a name and a lexical 
context.  Because of macros, the structure of lexical contexts is not 
simple block-structured nesting: an identifier can be referenced from a 
place in the code where it is not visible by name.  Also an identifier 
can be created that doesn't have a name, or equivalently isn't visible 
anywhere just by name, only by insertion into code by a macro.

So I think you should have an internal Arc-expression representation for 
programs, and a surface syntax which is more compact and legible, but 
Arc-expressions should not be specified to be made out of conses, 
symbols, and literals.  Arc-expressions should be defined only by an 
interface, which should be open (i.e. new interfaces can be added that 
apply to the same objects).  The implementation should be up to the 
compiler writer and there should be room for experimentation and 
evolution.  Interesting question: is there a surface syntax for 
Arc-expressions different from the abbreviated surface syntax, and if so, 
what is it?

Other unrelated comments:

"Here are a couple ideas:
x.y and x:y for (x y) and (x 'y) respectively."

Do you mean x.y stands for (y x)?  Oh, I see, you have field names as 
indices rather than accessors, so you actually meant x.y stands for (x 
'y).

As for x:y, I think what Dylan borrowed from Smalltalk is the right 
answer, thus x: stands for (quote x).  Colon as a postfix lexical 
"operator" works surprisingly well.

"local variables can be created implicitly by assigning them a value. If 
you do an assignment to a variable that doesn't already exist, you 
thereby create a lexical variable that lasts for the rest of the block."

This is a really bad idea, because inserting a block of code that 
includes a local variable declaration into a context where a variable 
with that name already is visible changes the declaration into an 
assignment!  Or if you fix that by making an assignment at the front of a 
block always do a local declaration instead of an assignment, then when 
you put code at the front of a block you have to remember to stick an 
"onion" in front of that code if there is any chance that the code being 
inserted could be an assignment.

Weird context-dependent interpretation of expressions like that makes a 
language harder to use, both for programmers and for macros.  It's one of 
the problems with C, don't put it into Arc too.

I'm not saying that you need to use Common Lisp's let for local 
declarations.  One possibility would be to use = for declaration, := for 
assignment, and == for equality.  Another would be to use = for all 
three, but with a prefix set for assignment and let for declaration.  
Other possibilities abound.

But then later you introduce a let macro, so I don't know what you really 
think about local declaration.

"Making macros first-class objects may wreak havoc with compilation."

That depends entirely on whether it is permissible to write functions 
that return macros as values and permissible to pass macros as arguments 
to functions that are not locally defined (or directly visible fn 
expressions), or whether all macros are directly visible at compile-time 
as initial values of variables.  I think you should limit the language to 
what you know how to implement, so the macro special-form should only be 
allowed in places where its complete flow is visible at compile time and 
should never be allowed to materialize as a run-time object.  You need a 
different way to create a macro object that exists in the run-time in 
which macros run, the compile-time run-time.  You need to define 
precisely "flow visible at compile time," possibly being very restrictive 
and only allowing what we really know is needed, namely a macro special 
form can be used in function position, as an argument in a function call 
where the function is a fn special form, in the initial value of a global 
constant (not variable!), and nowhere else.  This is tricky but tractable 
I think.

"strings work like lists"

does rplaca [probably (= (car x) y] work on strings?  What about rplacd?

"Overload by using a fn as a name."

I think you need to rethink this way of defining methods, it has a lot of 
problems.
CONS vs Pattern-matching - posted by Faré - 2004/5/7 15:17:08
I wrote my pattern-matcher http://www.cliki.net/fare-matcher specifically so that I could match source code forms in macros without ever having to know about CONS CAR and CDR. However, you still have to use lists when dealing with variable-length parameter lists - but that's ok.


Leave a comment...

 
Name:
URL/Email: [http://... or mailto:you@wherever] (optional)
Title: (optional)
Comments:
Save my Name and URL/Email for next time

Trackback

TrackBack ping me at:

http://lispmeister.com/blog/lisp-news/moon-on-s-expressions.trackback