Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Posting-Version: Notesfiles $Revision: 1.6.2.16 $; site ima.UUCP Path: utzoo!decvax!cca!ima!compilers From: compilers@ima.UUCP Newsgroups: mod.compilers Subject: Re: Lisp compilers (long) Message-ID: <136300022@ima.UUCP> Date: Mon, 6-Jan-86 22:13:00 EST Article-I.D.: ima.136300022 Posted: Mon Jan 6 22:13:00 1986 Date-Received: Wed, 8-Jan-86 02:44:15 EST Lines: 55 Approved: compilers@ima.uucp Nf-ID: #N:ima:136300022:000:3008 Nf-From: ima!compilers Jan 6 22:13:00 1986 [from Stanley Shebs ] > [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 --------