Implementing Lisp

I'm interested in a sketch of the accumulated wisdom about ImplementingLisp.

Here are some specific questions I've wondered about:

-- TomStambaugh

Here is an attempt at describing a basic blueprint for a Lisp interpreter. It is not the only way to structure the system, but it seems to be a simple way for a hobbyist implementation.

There is a 323 line implementation of this blueprint, with no GarbageCollection and very little error checking, at http://www.sonoma.edu/users/l/luvisi/sl3.c

GarbageCollection:

List structured memory: Environment handling:
Lookup
Find the value of a symbol in an environment.
Extension
Create a new environment given an old environment, some symbols, and their new values.

Input/Output:
read
RecursiveDescentParser for reading in EssExpressions.
print
Simple recursive procedure to print out EssExpressions.

Evaluator (EvalApply):
eval
Evaluate a form. Looks up symbols. Handles special forms. For applications, delegates evaluation of subforms to evlis and delegates the actual application to apply.
apply
Unwraps user defined procedures, adjusting environment appropriately and delegates evaluation of body to begin. Applies primitives in an implementation dependant manner.
evlis
Takes a list of forms. Evaluates each one (using eval) and returns a list of the results.
begin
Takes a list of forms. Evaluates each one (using eval) and returns the result of the last evaluation.

Interface:
ReadEvalPrintLoop
Evaluates (print (eval (read))) over and over so that the user (probably you) can type in Lisp expressions and see what they evaluate to.

If you are writing your LispLanguage interpreter in LispLanguage itself, you get the GarbageCollection, the list structured memory, and the I/O for free. This is called a MetaCircularEvaluator. There is a partial MetaCircularEvaluator in WhyLisp. StructureAndInterpretationOfComputerPrograms has a good discussion of this process, as does "The Art Of The Interpreter" (see below).

If you are using something like CeeLanguage for your implementation, you can start by implementing just the list structured memory, read, and print. Then run (print (read)) in a loop. The other parts can then be added to the working system incrementally.

If you are happy without TailCallOptimization or FirstClassContinuations (ContinuationExplanation, ContinuationImplementation), then you can just go ahead and write the evaluator recursively as described above.

If you want TailCallOptimization, then you will either need to tail call optimize the interpreter or represent the control stack explicitly. If you write a MetaCircularEvaluator in SchemeLanguage, you're most of the way there. In a language like CeeLanguage or CommonLisp which has GoTo, the interpreter can be tail call optimized by inlining begin() and apply() into eval(), and replacing eval()'s tail recursive calls with assignments and GoTos that target the beginning of the function. ParadigmsOfArtificialIntelligenceProgramming explains how to do this, and there is an example in C at http://www.sonoma.edu/users/l/luvisi/sl5.c

If you want FirstClassContinuations, then you have a few options:

Implementing FirstClassContinuations is probably not worth the effort for your first crack at an evaluator.

Some books that may be of interest:

LISP 1.5 Programmer's Manual
This is the grandaddy of all Lisp books. It describes the implementation of LispOnePointFive, one of the first full featured Lisp implementations. Available for free online from http://www.softwarepreservation.org/projects/LISP/book
StructureAndInterpretationOfComputerPrograms
Contains a thorough treatment of a MetaCircularEvaluator, a description of translating Lisp code into instructions for a register machine (aka a normal computer), and a good discussion of implementing list structured memory. Brief treatment of GarbageCollection. Weak on I/O. Available free online from http://mitpress.mit.edu/sicp/full-text/book/book.html
LispInSmallPieces
Includes multiple interpreters and two compilers (one to ByteCode, and one to CeeLanguage) for SchemeLanguage. Weak on GarbageCollection, I/O, and the implementation of list structured memory.
ParadigmsOfArtificialIntelligenceProgramming
Includes a SchemeLanguage interpreter and compiler. The compiler targets a virtual machine which is also implemented. Weak on GarbageCollection, I/O, and the implementation of list structured memory.
AnatomyOfLisp?
Out of print. Decent treatment of all aspects of a Lisp system. Discusses implementation techniques for older features that are not often present in current Lisp systems, such as DynamicBinding and computed gotos in the "program feature".
GarbageCollectionBook
Garbage Collection -- Algorithms for Automatic Dynamic Memory Management, by Richard Jones and Rafael Lins. ISBN 0471941484 . Strong on GarbageCollection (heh heh). Discussion of implementing list structured memory, and particularly latent typing, is woven through the book.
EssentialsOfProgrammingLanguages
Develops interpreters and a compiler for a language that has SchemeLanguage like semantics but a more conventional syntax. Good coverage of ContinuationPassingStyle and how to implement dynamic-wind. Decent coverage of input. Weak on GarbageCollection, output, and the implementation of list structured memory.
FunctionalProgrammingApplicationAndImplementation?
by Peter Henderson. Has a good description of the SECD machine (see below), including an outline of a VirtualMachine implementation in a PascalLanguage like PseudoCode, a compiler (written in LispKit Lisp) that compiles his LispKit Lisp to the SECD VirtualMachine, and a little bit on I/O, list structured memory and GarbageCollection. Unfortunately, the only mention I've found of TailCallOptimization is in an exercise 6.6 on page 196 where it asks the student to explain how "AP RTN" is redundant and how to fix it. The dialect which it implements is a little bit weird. For example, the scheme code "(letrec ((fact (lambda (n) (if (= n 0) 1 (* n (fact (- n 1))))))) fact)" would look like "(letrec fact (fact lambda (n) (if (= n 0) 1 (* n (fact (- n 1))))))".
LispaPortableImplementation
S. Hekmatpour,1989

Some web sites of interest:
http://library.readscheme.org/page8.html
Lots of links to many good papers worth reading.
http://www.schemers.org/
Links to many implementations of SchemeLanguage. The most popular dialect of LispLanguage to write subsets of, and to implement LispLanguage subsets in.
http://www.iro.umontreal.ca/~boucherd/mslug/meetings/20041020/minutes-en.html
Has a nice video on a simple Scheme to C compiler based on Closure and CPS conversion. This is nice to see in conjunction with Queinnec's LispInSmallPieces and the Lambda Papers.

Some papers of interest:
http://www.schemers.org/Documents/Standards/R5RS/
The current SchemeLanguage standard.
An Interpreter for Extended Lambda Calculus ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-349.pdf
The original SchemeLanguage paper.
The Art of the Interpreter or the Modularity Complex (Parts Zero, One, and Two) ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-453.pdf
This paper includes many small interpreters and examines how different changes impact the usability of the language.
Representing Type Information in Dynamically Typed Languages ftp://ftp.cs.indiana.edu/pub/scheme-repository/doc/pubs/typeinfo.ps.gz
How to keep track of what things are of what type. Useful in implementing list structured memory.
An Introduction to Scheme and its Implementation ftp://ftp.cs.utexas.edu/pub/garbage/cs345/schintro-v14/schintro_toc.html
Just what the title says.
Definitional Interpreters for Higher-Order Programming Languages http://www.brics.dk/~hosc/local/HOSC-11-4-pp363-397.pdf
This paper has a fairly thorough discussion of how to implement things like FirstClassFunctions and FirstClassContinuations in an interpreter when the language you are writing the interpreter in does not support those features.

Implementations (open-source)

Google for "SECD machine" for one possible implementation. Also look for LispKit, using which I implemented a variant of the LispLanguage in a weekend.

Lispkit:

LispKit is an implementation of a Lisp like PurelyFunctional language with LazyEvaluation based on the SECD machine. A reference implementation of the VirtualMachine is written in Pascal, and the compiler and many other utilities are written in LispKit Lisp.

DougMerritt wrote: In no particular order, open source Lisps I have lying around my hard disk after searching for such in 2003:

I have a similar list of Scheme implementations but now I'm all tired out from editing the above. -- dm

Scheme open source implementations (also see SchemeImplementations)

Some of the above links are taken from sometimes-stale package documentation and may be broken links, but nonetheless, only software that was available somewhere on the net as of Dec 2003 is listed, even if I neglected to keep a note of its new location after I searched it out and downloaded it. In particular it is common for older software to be found only in the AI repository.

Also see http://library.readscheme.org/page8.html for a bibliography with links to papers discussing "Compiler Technology/Implementation Techniques and Optimization" for the SchemeLanguage.

Discussion moved to ImplementingLispDiscussion

CategoryLisp

EditText of this page (last edited March 9, 2011) or FindPage with title or text search