- SECD: about
- Part I and Part Ia describe high-level, formal definition of a SECD machine;
- Part II discusses low-level details of SECD implementation in C;
- Part III (TODO): how to compile a Scheme subset into SECD code.
What are these posts about
Perhaps, a lot of people studying functional programming languages write their own simplistic Lisp interpreter. First of all, it’s quite easy with a modern functional language: parsing is primitive, the runtime maps straightforwardly to a favorite language’s runtime, etc.
Writing it in C is a more complicated task, since garbage collection and nitty-gritty details of implementation are up to you all of a sudden. I went crazy when I thought about endless
conses created with every operation. I don’t want to say that writing a Lisp runtime in C is fundamentally complex, but it’s still true that it’s quite hard to implement something you haven’t quite grokked yet.
I am fond of Haskell and GHC’s functioning often strikes like magic of waving terms into complex pattern that are reduced into normal forms at run time. In order to understand that, I started to study compiler theory. A classic book for understanding functional programming is Functional programming: Application and Implementation by Peter Henderson. Although it may seem very old (published in 1980) it’s still a good and clear introduction into functional way of thinking. When I came across SECD machine description I was amused by its simplicity and how easy is to encode it in a low-level language and how easy is to map a decent functional language into it at the same time (let’s forget about types for a while, we’re just studying). So I started to write my little SECD interpreter in C.
My little Scheme-to-SECD compiler
So I wrote a simple SECD interpreter in C and a self-hosting Scheme-to-SECD compiler in subset of Scheme. The code may be found here.