Re: Reflections on a classic Lisp Paper

[ Replying to comp.lang.lisp only.
http://www.nhplace.com/kent/PFAQ/cross-posting.html ]

Ray Dillinger <bear@xxxxxxxxx> writes:

Reflections on a classic Lisp Paper

Note: if you're only interested in Modern Common Lisp or
Scheme, skip this article. It deals with history and the
semantics of constructs which no longer appear in modern
lisp dialects.

Apropos the Fourth of July, on which I'm posting this, that remark is
like saying if you're interested only in the future of the nation, don't
go see the movie 1776 today.

(Btw, if you've never seen it, that's on my list of top ten movies of all
time, not even just top ten musicals, which it is. Quite an awesome movie,
and it speaks to tomorrow as much as today because it talks about recurrent
issues and about how decisions are made and the fact that decisions are
made by individual people with individual fears, frailties, passions,
obsessions, diseases, shady interests, and so on. Without giving away the
climax, the story offered [I don't even know if it's true, but it somewhat
doesn't matter] of how the last vote was acquired is a lesson to all of us
about political reality.)

I don't know that everyone should read my 1980 paper. But I do know that
the set of them who should it not limited to those "only interested in
Modern Common Lisp" unless you pejoratively mean "only those who value the
latest and greatest and think that a new release of anything means the
rest of eternity has been obsoleted". But I don't think those describe the
same sets.

I care desperately about the present and future of the US, and I find
documents like the Federalist papers directly relevant because they inform
me of pitfalls that were avoided and of things that tried and failed and so on.

Note: Crossposted to CLS and CLL. Please remember how
easy it is to be polite to one another.

In 1980, Kent Pitman (and if you're reading this, Hi)
published a paper entitled, 'Special Forms In Lisp', which
explored three different mechanisms for producing
user-defined special forms - Macros, Fexprs, and Nlambda.

Incidentally, just to establish my position here, it wasn't me that "caused"
these changes so much as that acted as scribe in summarizing a mood of
a lot of people. I came to the conclusions in the paper by surveying a whole
community, who was of very similar mind. What got the paper note was that
it summarized a mood of the times, sort of like Gorbechev was said to have
more summarized the political mood of the USSR at the time than having
single-handedly brought down ccommunism. (Not to blow the importance
of my paper or of Lisp out of context by grandiose comparisons, but just
to make an easy-to-understand metaphor.) Some things are just due and the
person who first says them is sometimes credited but is not always the real
cause.

In it, he briefly explained all three systems (as they were
understood at the time) and then made comparisons of their
advantages and disadvantages, concluding that macros were
really all a Lisp dialect needed.

You can read his paper online at
http://www.nhplace.com/kent/Papers/Special-Forms.html .

Having read Pitman's paper, it is my contention that:

1) Modern Common-Lisp style macros are not as clearly good
relative to other mechanisms as the rather different macros
he was writing about were, in that several advantages claimed
for the old formulation of macros do not apply to the new
formulations.

Such as...? I'm not being defensive here, just curious.
Claims like this do require evidence though.

2) Modern compilation techniques have extended what were
once advantages obtaining only to macros to callable
functions, potentially including fexprs and nlambda's.

Again, I find it hard to make sense of this or evaluate its
truth value without examples.

3) Fexprs in particular, retaining their acknowledged
advantages of applicability and first-class status at
runtime, can be made drastically better than the fexprs this
paper talked about by handling environments explicitly.

This is a possible but somewhat difficult claim to make. In order to
make it fully, there are probably some things you have to do which you
overlook here. In particular, you pretty much must count in the
positive effect of being able to do universal quantification across
all special forms, which was the result of the CL decision to follow
up on my paper's thesis and to limit special forms to a fixed set.
This allows the writing of portable code-walkers, and even though no
one has done that, I don't think it's impossible in CL--I just think
it's hard. I have one somewhere that I wrote, for example, and it
worked pretty well. But the point is that the ways it fell down were
over environment access (which you presuppose here) not due to
impenetrability of fixed special forms. Once you open the space to new
creation, people can't have code-walkers, even if the environment problem
is fixed, unless you create a protocol for understanding and code-walking
new special forms. And I'm not sure that's possible without a general
purpose AI description language to fully describe the effect of the
new special form, or without a reflective formal semantics that can be
dynamically understood and processed by codewalkers to assure that
appropriate semantics are maintained. (And the problem there may well
be that once you can do that, it's possible that you've reduced the language
from a fixed set of special forms to some other fixed space dictated by
the semantics and that all you're offering is new syntax--which is all
that macros do. I don't know this for sure--I'd have to read up on
denotational semantics to find out--but it's a "point of due diligence"
I wouldn't let pass before declaring success if I were you).

My arguments of these points are thus:

1) The Macros he was talking about in this paper were
run-time macros rather than compile-time macros. He
cites the ability to use the macro evaluation to alter
the text of the macro form into a non-macro form (expand
once, run many times) or not as the user requires as an
advantage of Macros.

Yes, we found through later experimentation that this wasn't very interesting
computationally and mostly addressed short-term small address space concerns
and so we got rid of the "memoization" kind of macros in CL. No one complained
until now. You need examples to put teeth in your remarks. Claims of this
sort are effectively assertions that there are expressions that cannot be
rewritten properly and efficiently without what you propose, and if you offer
no such challenge expressions, your argument is weak.

In modern dialects, where all
macroexpansion is pushed to the compilation phase, there
is no remaining choice and this is no longer an
advantage.

I don't think those that were involved in this change would define it this
way. I think they'd mostly say that twe did two rounds of simplification:
one to remove fexprs and another to remove self-modifying macros since both
seemed to add little power and mostly the opportunity to let users confuse
themselves. Your claim that this was ill-advised requires examples.
But certainly it's wrong to suggest that the "round two" changes as I've
alled them here were done by people oblivious to the motivation of "round one",
and so saying "Lisp has changed so much that we should revamp it" is like
saying "I decided to repaint my house and then I also repainted the trim
on the house in a matching color, so I therefore have changed the house so
much I should go back and reconsider the original change". I think these
changes were similarly motivated: to keep users from being caught in complex
code-analysis halting problems, and I think they succeeded. A claim that
they should be re-armed with foot-pointing weapons because users have gotten
smarter and less spazz-prone requires some elaboration.

2) The cited advantages of macros include inline expansion
for named abstractions, not available at that time with
function calls (including normal as well as fexpr and
nlambda calls). Modern compilers do function inlining
just fine, so this is also no longer an advantage for
macros.

3) The cited advantages of macros include the macroexpansion
being in the same lexical contour as local non-special
variables and therefore having the ability to provide
scope rules that other types of definitions cannot. But:

First, that very ability to capture local variables is
now widely regarded as "breaking hygiene" and gives
rise to a nest of smallish semantic problems, not
really formalized at the time the paper was published.

Second, Lispers have been dealing or refusing to deal
with this nest of smallish semantic problems for
years, and have pretty much spec'd out good methods of
enforcing hygiene when and where it's needed. Many of
these methods (including the very simple one of
getting a local variable bound to the lexical
environment of the call site and using eval with that
environment explicitly when a capture is intended) are
equally applicable to fexprs and nlambdas.

I think you are underestimating the degree to which you might thwart
the ability to compile.

In Maclisp, I think some special forms were not compilable or not fully
compilable because the compiler just couldn't do it. Nowadays, we
have special forms that we can compile, but if you re-open it to users
doing arbitrary things, you may or may not be able to still compile them.
The burden is on you to show that even when a change, all uses of
even user-defined special forms can be compiled... not on to show you've
been held back by a concern that they might not be.

Third, the exact formulation of fexprs and nlambdas
implemented in the systems of 1980 is not the only
possible formulation. There is no inherent problem
with a fexpr or nlambda form that gets a local
variable bound to the lexical environment of the call
site when it's called. Such fexpr's or nlambda's
would then have the same ability as macros to do
things in the local scope of the call site, without
the risk of unintentional capture.

Some of what compilers do is to prove by exhaustive analysis that various
effects cannot happen, too. If you create a situation where there is a
proliferation of operators with the potential to do changes that the compiler
cannot know, such proofs can break. The burden is again on you to show
they weill not.

4) A cited disadvantage of both Fexprs and Macros is the
need for declaration in the compiler. A Fexpr
declaration would alert the system to suppress argument
evaluation prior to the function call, whereas if a macro
definition does not precede its call site the call is
compiled as a function call to an as-yet-undefined
function.

First, modules have greatly diminished the
inconvenience of having calls resolve to declarations
in nearly-arbitrary orders.

Second, an alternate semantics for function calls
wherein _all_ arguments are evaluated under the
control of the called functions rather than before the
call would completely eliminate the need for fexpr
declarations.

And would make compiler optimization hard.

Third, there is no formulation I can think of that
would entirely eliminate the need for macro
definitions visible when the macro call site is
compiled.

I can't even figure out what the relevance of your point is on this last.

In any case, I await the version of this with lots of worked examples.

The only languages I know of that do this kind of thing have no compiler.
I don't regard that as a proof that they can't have one. But it doesn't
give me confidence that semantics like this leads to good compilers.

.

Relevant Pages

  • Re: Problem with the lambda form
    ... common lisp. ... With CL macros you can have any embedded language expanding to lisp ... but the embedded language can't have a language feature that CL ... Code compiled by the compiler wants to call standard ...
    (comp.lang.lisp)
  • Re: What c++, and most other languages dont have, but c# does
    ... Macros are simply user-defined hooks in the ... compiler, which are written as Lisp functions. ... only far more fragile and coarse-grained than a Lisp image. ...
    (comp.lang.lisp)
  • Re: optimizer macro
    ... lisp, but i think the question makes sense here so ... All such rules will be language specific, ... will make code faster without having to implement a full compiler. ... This is why CL allows compilers to implement some macros as ...
    (comp.lang.lisp)
  • Re: Reflections on a classic Lisp Paper
    ... relative to other mechanisms as the rather different macros ... of a functioning fexpr-based lisp. ... Fexprs is that they're applicable and have first-class runtime ... the rest of their design decisions. ...
    (comp.lang.lisp)
  • Re: Cpp Considered Harmful
    ... > However, in either case, assertions are invaluable in making certain ... because we now have our own cpp ... > macros, we can use several different compilers and have our system ... > built into the compiler. ...
    (comp.lang.cpp)