progress on C++ 'incremental' interpreter

Russel Simmons — 2003-07-06 19:27:48

Since the earlier discussion, I've been working on a prototype of a Joy 

interpreter that can execute 'incrementally', i.e. you can step a 

single O(1) instruction with each invocation.  I wanted this mostly so 

that I could embed many Joy-like interpreters in an app and have their 

timeshares controlled precisely by the app.  Well, a couple thousand 

lines later, I have things mostly working.



Each instruction is executed in O(1) time, I think I can guarantee.  

When copies of lists need to be made (e.g. dup, stack, etc.) pointers 

are copied rather than making a deep copy.  For the pointer-copying to 

be safe, nodes are immutable (their value, next pointer, list pointer, 

etc. does not change after creation).  Since nodes are immutable, it is 

impossible to have cycles (you can think of them making a DAG that is 

topologically sorted in the order of their creation).  Having no 

cycles, I decided to do reference counting rather than garbage 

collection.  When a node's reference count reaches zero, it is strung 

onto a free list so it can be recycled.  Since recursively decrementing 

references might not take constant time (e.g. you pop a large list off 

the stack) that part is also done incrementally: only when a node is 

about to be recycled from the free list are its immediately referenced 

nodes decreffed.  So basically any work of decreffing is amortized over 

allocation calls... not really that critical, but I thought it worked 

out nicely.



Combinators are implemented by pushing the quoted code onto the 'code 

stack' of upcoming instructions, avoiding recursion in the interpreter 

implementation.  Some combinators push a small program making use of 

stack/unstack to save and restore the stack.  There is no dump or dip 

stack, just code and data stacks.



On my machine (Powerbook G4) the performance is slower than Joy, as I 

expected.  It seems to run around half the speed of Joy, though in some 

favorable cases its performance is close to Joy.  But it can do some 

things that the current Joy interpreter can't (on my system), like:

5000 [ [pop 0 =] [pop succ] [[dup pred] dip x +] ifte ] x

though I'm not sure one would want to :)



Right now it only supports lists, integers, and booleans, and a small 

set of core words.  I'm working on cleaning it up and adding a simple 

extension system where you can add new types and words without changing 

the base interpreter code.  This might be useful when you embed it, 

like in my application.  If there is interest, I can make the code 

available once it is finished up a bit... though I am leaving for the 

trans-siberian railway soon, so it might be delayed :)



Russ