Hacker Newsnew | comments | show | ask | jobs | submit login

Indulge yourself:


The must reads are Keny Dybvig's thesis, "Three Implementations of Scheme". The original lambda papers can wait until you read the Orbit paper, an optimizing compiler for T by Kranz, Rees et al.

The Lisp implementation bibliography pretty much runs through PL research like a vein. Some of the stuff you must read for Lisp are typically in "books"; Christian Quinnec's Lisp in Small Pieces is the most important work, but you will need a good foundation in denotational semantics (you can get by with the one chapter in the little book by Nielson and Nielson, "Semantics with Applications: A Formal Introduction".

Somewhere in there you will brush against various compilation methods and IRs for the lambda calculus, most importantly continuation passing style. Most semantics text introduce lambda calculus and its three rules, but none go in depth into this like the tall green book by Andrew Appel, "Compiling with Continuations", a good chunk of which can be read in Appel's other papers. Appel's work is MLish in nature, but don't let that stop you; most optimizing Lisp compilers are MLish down underneath anyway. CMUCL does very good type inference but gets short of implementing a full Hindley-Milner. Felleisen et al's "The Essence of Compiling with Continuations" might also come handy, though it's heavy on the theory. Andrew Kennedy continues the saga with "Compiling with Continuations Continued", this time CPS gives way to A-Normal Form, another IR. He describes the techniques used by a compiler targeting .NET.

Most compiling "meat" can be found in the bits-and-bytes type papers. Wilson's GC bibliography "Uniprocessor Garbage Collection Techniques" is a must, it should have been called "What Every Programmer Should Know About Garbage Collection". Not to be confused with Richard Jones' "the Garbage Collection Bibliography". Boehm's "Garbage Collection in an Uncooperative Environment" is sheer hacking bravado, perhaps second only to "Pointer Swizzling at Page Fault Time", which should introduce you to memory management for disk-based heaps (i.e. object stores) among other things.

Your start in hacking runtimes will probably be David Gudeman's "Representing Type Information in Dynamically Typed Languages"; this is where you learn how stuff looks inside the computer when you no longer need to malloc and free. A previous hacking of a Pascal dialect prepared me for this wonderful paper.

Implementations of runtimes are documented by Appel, for SML/NJ, Robert MacLaclahn's "Design of CMU Common Lisp" (also perhaps Scott Fahlman's CMU report on CMUCL's precursor, "Internal Design of Spice Lisp", but that confused the crap out of me as I don't know the machine architecture they're talking about.) You will also enjoy the Smalltalk research starting with L. Peter Deutsch's first optimizing Smalltalk compiler, documented in "Efficient Implementation of Smalltalk-80", follow the Smalltalk lineage btw, all they way up to David Ungar's "The Design and Evaluation of a High Performance Smalltalk System" making sure NOT to ignore Self and its literature, also spearheaded by Ungar (Start your Smalltalk hacking career with Timothy Budd's "A Little Smalltalk", should take you about a weekend and will absolutely prepare you for dynamic languages; a similar system is described by Griswold and Griswold, compiler, intermediate representation and VM, but that one is for ICON.)

Dynamic type inference and type-checking (TYPEP and SUBTYPEP, CLASS-OF, INSTANCE-OF, etc) you can learn a good chunk of how CLOS should look like to the runtime system from Justin Graver's "Type-Checking and Type-Inference for Object Oriented Programming Languages". He scratches the surface, and you should supplement this with a selection from Smalltalk and Self, though neither will prepare you for multiple-dispatch, for that peer into Stanley Lippman's "Inside the C++ Object System".

I have deliberately avoided "classics" on Lisp, compiler construction, optimization, and other stuff. None of the books and papers I have recommended are as popular as SICP, PAIP, or AMOP. Or even the popular PL books, like EoPL, van Roy and Haridi, both of which you should read by the way, but they're stuff that you need to read and understand to be able to implement a practical Lisp implementation, or at least satisfy your curiosity.

Applications are open for YC Winter 2016

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact