Python interpreter for Peter Landin's SECD abstract machine.
Clone or download
Carlo Hamalainen
Carlo Hamalainen Script for running doctests.
Latest commit 6e956f2 Apr 12, 2013

README.md

pysecd

Python interpreter for the SECD abstract machine defined by Peter Landin.

I followed the presentation of the SECD machine given by Peter M. Kogge in his book The Architecture of Symbolic Computers (1991, McGraw Hill). I wrote this interpreter as a learning exercise, so the code should not be taken as a definitive statement on how the SECD machine operates. The trickiest opcodes to implement were DUM and RAP, for defining recursive closures.

To aid debugging I wrote a small wrapper for pydot, so that the memory structures can be visualised. For example the list [1, 2, 3] is stored as:

small list

A nonterminal cell has three parts: its address, the car value, and the cdr value. Nonterminal cells have two parts: the address and the integer value. For convenience opcodes (ADD, LD, LDF, etc) are stored as strings so that when we draw the graph we can see opcodes instead of integers. For examle the program

[LDC, [3, 4], LDF, [LD, [1, 2], LD, [1, 1], ADD, RTN], AP, WRITEI, STOP,]

corresponds to the following graph in memory:

sample program

On Debian-like systems, install pydot with this command:

sudo apt-get install python-pydot

Further reading

I only read Kogge's presentation of the SECD machine, so I really ought to invest some time in getting through these:

TODO

  • Test pysecd against one of the other implementations listed above.
  • Implement garbage collection (Chapter 8 of Kogge's book).