What I find fascinating is that Lisp, commonly perceived as too high level to be practical, is actually at its core (in its original implementations!) an incredibly low level language.
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.
