# 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