Can anybody give me a reference to techniques of Lisp compiler
construction?
I'm particularly interested on compilers that are written in lisp (the
majority?). How do these compilers deviate from "usual" compilers
(dragon-book style)?
A document that shows how the design process for such a beast was made
would be great. More points if it describes not only the
parsing/compiling pass but also the optimizing pass.
Thanks.
h9
On Fri, Oct 17, 2003 at 01:22:10PM -0700, Hal Niner wrote:
> Can anybody give me a reference to techniques of Lisp compiler
> construction?
>
> I'm particularly interested on compilers that are written in lisp (the
> majority?). How do these compilers deviate from "usual" compilers
> (dragon-book style)?
There is no particular reason for a Lisp compiler to significantly
differ in overall construction. Obviously, the semantics of the
language are going to entail quite a few differences from a compiler for
a statically-typed C-like language.
For one thing, except for values only used in forms subject to static
analysis (such as within a closure), the representation of objects needs
to carry type information.
Another issue is the need to support indefinite extent variables caught
in closures; unless it can be shown that a variable is never used after
the function has completed, the variable must be allocated in such a way
that it is still available later on, such as on the heap with GC to
clean it up.
Lisp compilers also tend to cater to programmers who prefer an
interactive incremental compiler; this complicates the loading of the
generated code. There are several approaches here: CMUCL has its own
assembler, whereas ECLS uses dynamic library functions to load object
files outputted from gcc. It also means that the compiler is part of a
larger environment, which is yet another issue in itself.
There are certain Smalltalk and Self compilers which, IIRC, keep track
of method definitions and can dynamically inline or uninline method
calls as needed, as the code changes. This would be applicable to Lisp
too, though I do not know of any Lisp compiler which does it.
> A document that shows how the design process for such a beast was made
> would be great. More points if it describes not only the
> parsing/compiling pass but also the optimizing pass.
You can take a look at the sources and internals documents for the
``Python'' compiler used in CMUCL and SBCL. It is a highly regarded
optimizing compiler that does extensive type-inferencing and tries to
use efficient representation of Lisp data when possible.
Two things I've noticed about the backend of Python, things which makes
it unusual, is that it uses a notion of Virtual OPerations for the
second internal representation; where these VOPs are somewhat like
high-level macro assembler instructions. Each VOP generally translates
into a block of several actual machine instructions. And when it comes
time to emit machine code (into a CL vector, btw), there is a loop
through all the VOPs and each in turn calls functions which take the
assembly instruction template of the VOP and translate it into machine
code which is then inserted into the vector (along with certain
annotations). The vector is then adjusted and labels are resolved. One
consequence of this is that there is no obvious place to put a peephole
optimizer stage (though the generated code is pretty decent, anyhow).
I have been told, by sources much more knowledgable than I am, that this
sort of design is fairly unusual in compiler construction. I imagine
that the reason for it is simply a choice that was made back in the late
80s, but if you find other reasons for it I would be interested to know.
_Lisp in Small Pieces_ and the older _Anatomy of Lisp_ are two books
often suggested as recommended reading, so I will pass that along.
However, many of the issues surrounding Lisp optimization are not really
that unique to Lisp (anymore, at least), so a good general compiler
design book like _Advanced Compiler Design & Implementation_ will be
useful too.
http://www.cons.org/cmucl and http://sbcl.sf.net/ are for CMUCL and SBCL
respectively.
--
; Matthew Danish <·······@andrew.cmu.edu>
; OpenPGP public key: C24B6010 on keyring.debian.org
; Signed or encrypted mail welcome.
; "There is no dark side of the moon really; matter of fact, it's all dark."
Also, Peter Norvig's _Paradigms of AI Programming_ has a nice chapter
where he develops a Scheme compiler, as well as being a good book in
general on CL programming.
--
; Matthew Danish <·······@andrew.cmu.edu>
; OpenPGP public key: C24B6010 on keyring.debian.org
; Signed or encrypted mail welcome.
; "There is no dark side of the moon really; matter of fact, it's all dark."
In article <····························@posting.google.com>,
Hal Niner <····@cyberspace.org> wrote:
>Can anybody give me a reference to techniques of Lisp compiler
>construction?
In the 70's, David Moon wrote a paper on the design of the ITS Maclisp
compiler, and Bernie Greenberg wrote a paper about the design of the
Multics Maclisp compiler. Try googling to see if either of these is
online.
In the 80's there were ACM Lisp & Functional Programming conferences every
other year, and there must have been some compiler design papers presented
at them.
>I'm particularly interested on compilers that are written in lisp (the
>majority?). How do these compilers deviate from "usual" compilers
>(dragon-book style)?
Much of the dragon book is about lexing and parsing. Lisp compilers that
are written in Lisp don't have to do too much fancy parsing. The Lisp
reader takes care of lexical analysis and parsing of lists. Most operators
with complex syntax are macros, so the compiler doesn't have to worry about
them (it calls the macro function, and then operates on the result).
Code generation and optimization of Lisp isn't too much different from
other languages.
--
Barry Margolin, ··············@level3.com
Level(3), Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
Hal Niner wrote:
> Can anybody give me a reference to techniques of Lisp compiler
> construction?
>
> I'm particularly interested on compilers that are written in lisp (the
> majority?). How do these compilers deviate from "usual" compilers
> (dragon-book style)?
>
> A document that shows how the design process for such a beast was made
> would be great. More points if it describes not only the
> parsing/compiling pass but also the optimizing pass.
Christian Queinnec's book is excellent:
<http://www-spi.lip6.fr/~queinnec/WWW/LiSP.html>
There is also chapter five of SICP
<http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-35.html#%_sec_5.5>
If you are interested in papers on writing compilers then take a look
at the references at readscheme.org:
<http://library.readscheme.org/page8.html>
--
Jens Axel S�gaard
"Jens Axel S�gaard" <······@jasoegaard.dk> wrote in message
······························@dread12.news.tele.dk...
> Hal Niner wrote:
> > Can anybody give me a reference to techniques of Lisp compiler
> > construction?
> >
> > I'm particularly interested on compilers that are written in lisp (the
> > majority?). How do these compilers deviate from "usual" compilers
> > (dragon-book style)?
> >
> > A document that shows how the design process for such a beast was made
> > would be great. More points if it describes not only the
> > parsing/compiling pass but also the optimizing pass.
>
> Christian Queinnec's book is excellent:
>
> <http://www-spi.lip6.fr/~queinnec/WWW/LiSP.html>
>
Lisp In Small Pieces is totally the best single book on this subject,
without question.
You can literally write a compiler from it, and I know people who
have used the book to get initial compilers working from which
they do further research.