Secd: A silly implementation of the SECD machine | Hacker News Reader

Secd: A silly implementation of the SECD machine

github.com

43 pointsluu8 comments

Might be of interest: the ocaml interpreter runs on some kind of ZINC machine iirc, which is implemented here: https://github.com/ocaml/ocaml/blob/trunk/runtime/interp.c

I took an architecture course with Dr Kogge (author of the book the SECD machine is described in) and chose Erlang for building an SECD machine emulator, because Erlang's pattern-matching syntax for defining functions perfectly matched (if you'll excuse the pun) with "axiomatic semantics".

edit: correction, the SECD emulator was for another class, I had taken Dr Kogge's architecture class beforehand

for instance, the basic 0-ary operations are:

  eval({S,E,[],D}) -> {S,E,[],D};
  
  % Stack Operations:
  % 
  % NIL    s e (NIL.c) d        ->  (nil.s) e c d
  % LDC    s e (LDC x.c) d      ->  (x.s) e c d
  % LD     s e (LD (i.j).c) d   ->  (locate((i.j),e).s) e c d
  
  eval({S,E,[nil | C],D}) -> 
      debug(enter,eval_nil,[{S,E,[nil|C],D}]),
      Z = eval({[ [] | S ],E,C,D}),
      debug(exit,[],Z), Z;
  eval({S,E,[ldc, X | C],D}) -> 
      debug(enter,eval_ldc,[{S,E,[ldc,X|C],D}]),
      Z = eval({ [X | S],E,C,D}),
      debug(exit,[],Z), Z;
  eval({S,E,[ld, [I|J] | C],D}) -> 
      debug(enter,eval_ld,[{S,E,[ld,[I|J]|C],D}]),
      Z = eval({[locate([I|J],E)|S],E,C,D}),
      debug(exit,[],Z), Z;

I've actually recently read "FUNCTIONAL PROGRAMMING: Application and Implementation", by Peter Henderson from 1980, which contains a description of the SECD machine and a compiler for a simple purely-functional Lisp dialect called Lispkit.

This <https://github.com/carld/lispkit> looks like a good repo if you want to know more, although I'm not related to it in any way.

I can't say how it compares the book by Kogge mentioned in this post since I haven't read that, but I can say I think it's an excellent book and worth reading if you're interested in this kind of thing.

(2012)

Also, I can't figure out what makes it silly?

This VM basically maps the SECD machine, directly to the underlying Clojure environment, which being Lisp, is very close to begin with. (Since SECD was first intended to implement languages like Lisp.)

So, I suppose perhaps silly in the same way that the one page Lisp definitions written in Lisp are a bit silly. They presume that you already have garbage-collected Lisp-like cells, for example. And even if you have that, you still can't really use it as a practical programming language.

Consider how it evaluates a variable in an environment: https://github.com/zachallaun/secd/blob/master/src/secd/mach... It's the simplest, and worst, solution -- iterate over the linked list from the start until you find the value you want. Performance degrades exponentially the more variables you have. In a more "serious" interpreter or compiler, you'd want to do a transform at some point, and slip in the value directly, if possible. And if not, you want to call out to a fast lookup method, like a hash table or balanced tree.

> iterate over the linked list from the start until you find the value you want

I know right, you would want to use two threads to iterate in both directions and capture the element for the current scope for faster iterations!

In practice, that lookup technique might not be an issue at all.

A mis-autocorrect from simple. The GitHub page has the word in the project title correctly as “simple”.

The Architecture of Symbolic Computers is one of my favourite computer science texts ever.

Reply on news.ycombinator.com