Friday, July 31, 2015

Building a Lisp Interpreter from Scratch -- Part 14: Full Monty Compiler

Well, I finally got around to implementing a full monty compiler for pLisp. I say 'full monty' because this version attempts to completely do away with the interpreter; now an expression passed to the REPL will be compiled to a native function plus the objects that represent the free variables in the expression (aka a closure) and then executed.

I still haven't worked out all the wrinkles, specifically how to handle macros, but considering that macros are pretty much identical to regular functions (as evidenced by the identical interpreter code that handles both), this should not be too difficult.

The full monty compiler does its job in phases:
  1. Macro expansion
  2. Assignment conversion
  3. Translation to intermediate pLisp
  4. Renaming transformation
  5. Simplification of the intermediate pLisp
  6. CPS transformation
  7. Closure conversion transformation
  8. Lift transformation
Each of these phases is a separate post in itself, so I'll dive into them in the coming weeks. Discerning readers will notice that these phases seem to be incomplete (i.e. no register allocation, mucking around with type information, and so on). The reason for this is two-fold: a) we're not compiling to assembly or machine code, but are targeting C (letting the Tiny C Compiler handle things from this point onward), thereby obviating the need to dive into things like register allocation and b) pLisp is dynamically typed, with no attempt made to infer types and type correctness at compile-time.

Right now the compiler is written in pLisp itself (everybody raise your hands and say 'Code is Data'), and produces code in a Lisp dialect I've dubbed 'pLisp_IL_Lift', which is then executed by a toy interpreter in pLisp to verify the correctness of the compilation. The plan is to produce a hand-written version of this compiler in C and use this version (v1) during business-as-usual (one can even produce the C version of the compiler by running v1 on the compiler pLisp source to produce v2 -- we can then proudly proclaim that the pLisp compiler is written in pLisp itself, but let me not get ahead of myself).

P.S. Tip of the hat to Design Concepts in Programming Languages for nearly all of the underlying theory.