Really? One of the only things about Lisp and other functional languages that strive to be pure that trips me up is that I could not guess how to write a compiler for one, and especially with ample lazy evaluation I'm really not sure what the execution of a program would end up being in terms of the stream of instructions going through the CPU. When it comes to imperative coding, I at least have a fairly good idea, but with LISP I haven't the slightest idea. Does it create stack frames and do calls when recursing or does it simple 'emulate' it through maintaining its own stack? I could tell you what it's doing in terms of lambda calculus, or what it would be doing on the CPU if I had to write a Lisp 'emulator'... but what the actual Lisp runtime is doing, I've no idea!
There are a bunch of books which explain how to write Lisp compilers. There are a bunch of different strategies.
> Does it create stack frames and do calls when recursing
That's what a typical Lisp might do. It might also change the stack frame and just jump to a function...
It's also relatively easy to check out, since Common Lisp has a built-in disassembler. One can take an implementation, compile a function and see the generated code. Just call the function DISASSEMBLE with a function object...
If you're interested, The Structure and Interpretation of Computer Programming winds up writing a Scheme interpreter in Scheme.
This is part of a proud and surprisingly long-standing tradition. The first Lisp interpreter was originally written in Lisp by one person, and then hand translated into assembly by another. This came as a surprise to the rest of the lab who had intended to work on an actual implementation in a year or two. You know, some time after they came up with a real syntax for it.
