Scheme - Reflections on a classic Lisp Paper

Author

Reflections on a classic Lisp Paper

Ray Dillinger

2006-07-04, 6:09 pm

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.

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.

In it, he briefly explained all three systems (as they were
understood at the time) and then made comparisons of their
advantages and di

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

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

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.

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. In modern dialects, where all
macroexpansion is pushed to the compilation phase, there
is no remaining choice and this is no longer an
advantage.

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.

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.

4) A cited di

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

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.

William D Clinger

2006-07-04, 6:09 pm

The following paper nails down one of the more important
things to understand about FEXPRs:

Mitchell Wand. The Theory of Fexprs is Trivial.
Higher-Order and Symbolic Computation 10(3),
May 1998, pages 189-199.

Abstract: We provide a very simple model of a reflective
facility based on the pure lambda-calculus, and we show
that its theory of contextual equivalence is trivial: two
terms in the language are contextually equivalent iff
they are alpha-congruent.

Will

Pascal Costanza

2006-07-08, 7:59 am

Ray Dillinger wrote:
>
> Reflections on a classic Lisp Paper
>

You should definitely read about 3-Lisp. The paper "Control-related
meta-level facilities in LISP" by Jim des Rivieres gives an excellent
overview. It's published in the book "Meta-Level Architectures and
Reflection" by Patti Maes and Daniele Nardi. It's hard to find, but
definitely worth the effort.

Pascal

--
3rd European Lisp Workshop
July 3 - Nantes, France - co-located with ECOOP 2006
http://lisp-ecoop06.bknr.net/

shriram@gmail.com

2006-07-09, 9:59 pm

Ray Dillinger wrote:

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

I encourage people interested in the above point to look at John
Shutt's work, which addresses this quite elegantly:

http://web.cs.wpi.edu/~jshutt/kernel.html

Shriram

Sponsored Links