SECD: about


  • 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.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s