5 ms·

Secd: A silly implementation of the SECD machine

43 points by luu 3y ago

detrites 3y ago
(2012) Also, I can't figure out what makes it silly?
- retrac 3y ago
  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/machine.clj#L11 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.
  - sitkack 3y ago
    > 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.
- kisper 3y ago
  A mis-autocorrect from simple. The GitHub page has the word in the project title correctly as “simple”.
qubex 3y ago
The Architecture of Symbolic Computers is one of my favourite computer science texts ever.
philsnow 3y ago
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;
Penyngton 3y ago
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 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.
lapinot 3y ago
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 https://github.com/ocaml/ocaml/blob/trunk/runtime/interp.c

43 points by luu 3y ago

detrites 3y ago

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

retrac 3y ago
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/machine.clj#L11 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.
- sitkack 3y ago
  > 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.
kisper 3y ago
A mis-autocorrect from simple. The GitHub page has the word in the project title correctly as “simple”.

qubex 3y ago

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

philsnow 3y ago

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;

Penyngton 3y ago

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

lapinot 3y ago

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 https://github.com/ocaml/ocaml/blob/trunk/runtime/interp.c