Mon Jan 25 16:04:13 CET 2010

Indulge yourself: Scheme literature

From [1]:

  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

  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.

More here: http://www.reddit.com/r/programming/comments/9220o/ask_proggit_recommender_a_compsci_paper_for_me_to/

[1] http://news.ycombinator.com/item?id=835020
[2] http://news.ycombinator.com/item?id=834175