[plt-scheme] Books on Lisp interpreter implementation in C?

From: David Van Horn (dvanhorn at ccs.neu.edu)
Date: Wed Nov 5 19:09:41 EST 2008

Grant Rettke wrote:
> Any recommended books on Lisp interpreter implementation in C?

Grant,

What are you looking to get out of such a book?  We can make better 
recommendations based on that info.

Here is my guess on what you're asking: how can does one implement the 
interpreter for a higher-order (maybe garbage-collected, maybe 
tail-recursive) language (like Scheme) in a first-order (maybe 
explicitly memory-managed, maybe non-tail-recursive) language (like C)?

If this is the question, what you are looking for is a reference on 
"abstract machines".  An abstract machine is just an interpreter which 
is 1) first-order, and where 2) all calls are tail calls.  It is easy to 
implement such an abstract machine in a language like C.

If you're interested in abstract machines, see Felleisen and Flatt's 
monograph.  I can't remember if that book deals with implementing 
garbage collection, but Krishnamurthi's PLAI is a great reference on the 
topic.  Finally, I'll mention that you can from a higher-order 
functional evaluator to an abstract machine via standard tools in the 
functional programmer's toolkit: CPS and defunctionalization.  For this 
you want to see Danvy's invited ICFP talk from this year.

David


Posted on the users mailing list.