Re: Lisp compilers (long)

[from Stanley Shebs <harvard!seismo!utah-cs.UTAH-CS!utah-cs!shebs@bbnccv.ARPA>]


> [in response to Darryl Richman's note on Lisp compiling]


As far as I know, there are no books devoted to Lisp compilation. Part of
the reason is that production-quality Lisp compilers tend to look a lot
like those for other languages. One still has to do dataflow analysis,
register allocation, peephole optimization, and so forth. The major
differences are that there is no lexical analyzer or parser (not quite
true, but close enough) and that much much more optimization stages
need be done to get credible output. Type inference is a must, although
many Lisp implementations have gotten away without it by providing all
kinds of language crocks. One should not forget, either, that the
Lisp runtime system is at least as important as the compiler in
determining performance, and so a book on compilation should be
a book on runtime systems also. (I might write it when I finish
my thesis! :-) )


I found the new dragon book a bit of a disappointment w.r.t. Lisp,
but it does have a new chapter on type checking which includes Milner's
type inference system used in ML (ML can be thought of as a strongly
typed Lisp). Not all of the ideas extend well to the majority of Lisps
which are weakly typed, and need declarations to help the type inferencer
along.


If you want to find out lots about Lisp compilation issues, you've got
to hit the literature - fortunately, it's not widely scattered! The
compiler construction conferences have a few Lisp papers each time,
also there are some in the biennial ACM Lisp and Functional Programming
conferences. John Allen's "Anatomy of Lisp" (McGraw-Hill, 1978) has
a simple compiler in Chap. 6, although the descriptive style is a bit
idiosyncratic (I recommend not trying to understand every gritty bit
that comes earlier in the book). Abelson and Sussman's "Structure
and Interpretation of Computer Programs" (MIT Press, 1985) also has
material in Section 5.3 ff., but it's aimed more at low-level undergrads.
I highly recommend Guy Steele's MS thesis "RABBIT: A Compiler for
SCHEME" (MIT AI-TR-474, May 1978) as a case study. He talks about
many issues specific to Lisp compilation, and includes the full source
listing of RABBIT, about 3500 lines of code. There is a good paper
by Griss & Hearn in a 1979 (I think) Software Practice & Experience,
which describes a "Portable Lisp Compiler". It achieves portability
by generating code for an Abstract Lisp Machine (which looks suspiciously
like a DEC-20), which is then translated to a specific machine's
instructions.


I should mention at this point that looking for the words "Lisp" and
"compilation" together in a title is not very reliable; much research
is directed at "functional languages", of which Lisp is the Fortran-like
member. I've already mentioned ML and Scheme; work on SASL, HOPE, FP,
and other languages can also be usefully applied in the design of Lisp
compilers.


stan shebs
--------

Return to the comp.compilers page.
Search the comp.compilers archives again.