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

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

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

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