Part Ia. SECD: a high-level description

---

Contents

• SECD: about
• Part I and Part Ia describe high-level, formal definition of a SECD machine;
• Part II discusses low-level details of SECD C implementation;
• Part III (TODO): how to compile a Scheme subset into SECD code.

---

Things are getting dirty: putting functional in the SECD

Now we’re starting the most interesting part, adding functions into the functional virtual machine. First of all, a function is usually tied to its environment: a pair of function definition (arguments and body) and the environment it has been created in is called closure. So don’t be afraid of this semantic rules for opcode LDF (the newly made closure is underlined):

• (s, e, LDF.(args body).c, d) => (((args body).e).s, e, c, d)

I want to stress that the environment is paired with the function definition on the stack, producing a closure (args body).e, which may be saved, used as an argument to another function (thus bound to a symbol), and so on.

The closure on top of the stack may be called using opcode AP:

• (((argnames body).e').argvals.s, e, AP.c, d)
=> ( (), new-frame(argnames, argvals).e', body, s.e.c.d)

Part I. SECD: a high-level description

---

Contents

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

---

Part I: What is a SECD machine?

Formally, it is just a tuple of four lists with some set of rigidly defined operations on it. The SECD semantics describes a stack-based virtual machine which is designed to run pure functions. As seen by a computer scientist: one of first denotational semantics for a pure functional language, where operations are transitions between possible machine states.

The components of the tuple are named (unsurprisingly):

SECD: about

---

Contents

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