# RE: [stack] progress on C++ 'incremental' interpreter

## Tanksley, William D. Jr. — 2003-07-07 18:10:41

    From: Russel Simmons [mailto:symstym@...]

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

     This sounds a lot like the VM Henry Baker describes in his paper at <

    http://home.pipeline.com/~hbaker1/LinearLisp.html >. You might (or might

    not) want to compare the two. In particular, he manages to get much closer

    to constant time, and he includes something of an analysis. His engine can

    also take advantage of "accidental" similarities -- i.e. if one list happens

    to end the same way as another list, the two will be merged into one

    automatically (and will be un-merged if a change happens).

     >Russ

     -Billy

## stevan apter — 2003-12-26 14:48:34

    i thought i'd recycle this message from russel, on the

    chance that he's back from sight-seeing in wazzupistan.

     ----- Original Message -----

    From: "Russel Simmons" <symstym@...>

    To: <concatenative@yahoogroups.com>

    Sent: Sunday, July 06, 2003 2:27 PM

    Subject: [stack] progress on C++ 'incremental' interpreter

    >

    > 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

    >

    >

    >

    > To unsubscribe from this group, send an email to:

    > concatenative-unsubscribe@egroups.com

    >

    >

    >

    > Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/

    >

    >