# Re: [stack] toy

## Martin Young — 2000-09-21 11:05:56

    Re: description of how Toy works.

    Yup.  Got the hang of that now.  It's a clever implementation and I can see

    where you're getting the extra speed from.  I /think/ I can see how you'd do

    the recursive combinators - I'm looking forward to trying such a version.  How

    many conbinators do you intend to put inside the interpreter?

    I've never quite been able to justify buying Knuth.  Perhaps I will now.

    As one would expect it's quite easy to see analogies between Toy and Monkey's

    execution models.  If one were to flatten and concatenate Monkey's stack,

    current program, and dip stack it would look lots like Toy's single list.  I

    wonder how much extra work Monkey is actually doing (and how much of it is just

    pointless list shuffling).

    I managed to get similar (but non-optimal and generally icky) programs running

    in both Monkey and Joy last night.  A quicksort of 100 integers was about 22

    times faster in Joy than Monkey, whereas it was around 25 times faster for the

    "times" test.  This suggests to me that Monkey's execution model has approx 20x

    performance penalty (at best).  Urk!

     On Sep 20, 10:00am, wtanksley@... wrote:

    > >purposes of continuations [without stacks]?

    > No, you don't.  A continuation in a stack-based language doesn't need a

    > stack.  Now, a _thread_ does need a stack, as does an exception.  But that

    > just means that both a thread and an exception are *more* than a

    > continuation.  That doesn't make the continuations useless -- it just means

    > that they're not threads or exceptions.

    Fair enough.  When would one use a continuation without an accompanying stack?

    > >If one represents a Joy program as a binary tree [snip]

    > That's a suprising idea to me.  What advantages does it bring for you?

    Um.  Not sure.  That's just how I've always thought about it.  Having said

    that, I have a plan for an optimiser that requires the tree to be flattened so

    I'll be needing to change paradigms anyway.

    > You do realise that

    > what you describe isn't a tree, but rather a graph, right?  After all, if

    > you have two uses of a word you automatically form a double link (directed

    > acyclic graph), and if you have any recursion or mutual recursion you form a

    > cycle.

    Not quite.  If a word is used twice then, logically, it appears in its entirety

    twice in the tree.  Of course the implementation uses sharing.

    I'm planning on making recursive definitions illegal in Monkey, forcing

    programs to use the recursive combinators instead.  Not sure how to do mutual

    recursion yet though.  This will require some thought.

    With these two restrictions any program can be flattened into a finite list

    which I can then feed to an optimiser.

    > Personally :-), I would use

    > a stack, and allow words to access it freely to store "return XTs" into data

    > structures of their own invention.  (XT == eXecution Token.)  The reason for

    > this is that the implicit structure of the language is a stack: you return

    > to your caller.  If you want to return to someone else, siply place their

    > address on top of your caller's address, and return.  If you never want to

    > return to your caller, drop his address off the return stack (and possibly

    > continue dropping addresses, if you'd like).

    >

    > I've seen very sophisticated backtracking implemented using this, and it

    > looked completely natural.

    This is what Monkey does.  In this respect the dip stack works just like the

    return stack in forth.

    --

    Martin Young  working for  STMicroelectronics at     `(o)_(o)' The fat wise /

    1000 Aztec West, Almondsbury, Bristol, BS32 4SQ.      (  V  ) owl eats only >

    +44 1454 462 523    `v'      Martin.Young@...      `.___,' clean mice.  /

                       _(_)_                             -="==="=============='

      ----------

    From: Martin Young [mailto:martin.young@...]

    >On Sep 19,  8:42am, wtanksley@... wrote:

    >> From: Martin Young [mailto:martin.young@...]

    >> >>	* program = stack = continuation

    >> >Is this a mistype?  Surely "program+stack=continuation"?  If

    >> >not, could you explain this at greater length?

    >> A continuation is the same as a program; there's no need to

    >> bind a stack

    >> with it (and in fact, binding a stack makes it useless for

    >> most of the

    >> purposes of continuation).

    >> A program can be represented by a list with destructive

    >> access to one end, which in turn is a stack.

    >I parsed the original statement as "the program is equivilent

    >to the stack

    >which is equivilent to the continuations", i.e. not that they can be

    >represented by the same data structures, but that are the same thing.

    Ah!  I see the problem.  Well, I can see how his statement wouldn't make any

    sense if you interpreted it that way -- so I recommend interpreting it in a

    way which makes sense :-).  So don't try to read "program" as "THE program";

    instead, just read it as "any program".  And so on for "stack" and

    "continuation".  He's describing an implementation detail.

    >What would you say are most of the purposes of continuations?

    >For implementing

    >exceptions and threads you do need to bind a stack with the

    >continuations for them to be useful.

    No, you don't.  A continuation in a stack-based language doesn't need a

    stack.  Now, a _thread_ does need a stack, as does an exception.  But that

    just means that both a thread and an exception are *more* than a

    continuation.  That doesn't make the continuations useless -- it just means

    that they're not threads or exceptions.

    >> >How do you represent the program and the continuations?

    >> >Logically a Joy

    >> >program is a strict tree, the current execution position is a

    >> >node in that tree

    >> >and the continuation is the untraversed portion of the whole.

    >> Not true -- a Joy program is a strict *list*.

    >If one represents a Joy program as a binary tree, each node

    >represents a word

    >where the left branch is that word's definition and the right

    >branch is the

    >rest of the current program.  The interpreter traverses the

    >tree left branch

    >first, depth first.  Because the order of traversal is fixed

    >the nodes could

    >indeed be flattened out into a list.

    That's a suprising idea to me.  What advantages does it bring for you?  It

    seems to result in nothing but enormous complication.  You do realise that

    what you describe isn't a tree, but rather a graph, right?  After all, if

    you have two uses of a word you automatically form a double link (directed

    acyclic graph), and if you have any recursion or mutual recursion you form a

    cycle.

    Graphs are *hard* to deal with.  Trees are simpler.  Lists are simplest of

    all.  Why do all that work simply to shun simplicity?

    >Personally I prefer to think of Joy programs as trees because

    >this preserves more of the program structure.

    I don't understand this, because the program structure *is* a list.  Or at

    least my little mind is having a hard time seeing it as anything else.

    >> >If you are not

    >> >recursing on the native Oberon stack, and you only have one

    >> >Joy stack, where are you storing the continations?

    >> If he actually isn't using the Oberon stack, he'd have to

    >> store the return

    >> addresses (which are equivalent to continuations) on the heap.

    >Let me rephrase the question: how are the continuations built

    >up?  They must be

    >structured somehow.  Are they built as a linked list in the

    >heap?  Are they

    >mixed, somehow, into the Toy stack?  What I'm trying to get at

    >here is this: at

    >the end of a word's definition how does Toy get back to

    >executing the previous word?

    I'll let him answer -- it's his implementation.  Personally :-), I would use

    a stack, and allow words to access it freely to store "return XTs" into data

    structures of their own invention.  (XT == eXecution Token.)  The reason for

    this is that the implicit structure of the language is a stack: you return

    to your caller.  If you want to return to someone else, siply place their

    address on top of your caller's address, and return.  If you never want to

    return to your caller, drop his address off the return stack (and possibly

    continue dropping addresses, if you'd like).

    I've seen very sophisticated backtracking implemented using this, and it

    looked completely natural.

    >> A very good question.  Obviously the stack itself can't be

    >> used directly for

    >> such things; I can think of a couple of solutions, but they

    >> all start with

    >> the need for semaphores or task variables (that is, spaces

    >> in memory which

    >> can only be accessed by one task, but which can be set to

    >> 'open' for any

    >> access, or deeded over to a specific task).  So why beat

    >> around the bush -- implement semaphores.

    >I'm not sure I like explicit semaphores.  I'd rather have have

    >synchronisation

    >implicit in the language structure, more like Occam (and to a

    >lesser extent

    >canonical monitors) than pthreads.  OTOH I haven't thought

    >seriously about this.

    I've put some thought into this, and I see a couple of useful designs -- but

    in every case, you start with a sempahore.  By Forth logic, this means that

    you give your programmer semaphores, as well as a couple of libraries built

    on top of them.

    One possible way to handle synchronous execution is to use 'dynamic

    evaluation tokens': these are stack items which are actually just tokens.

    As soon as you attempt to evaluate them, your process will 'wait' until

    they're ready.  Of course, they're implemented by means of semaphores.

    >Martin Young  working for  STMicroelectronics at     `(o)_(o)'

    -Billy

    To unsubscribe from this group, send an email to:

    concatenative-unsubscribe@egroups.com

    [Non-text portions of this message have been removed]

## wtanksley@bigfoot.com — 2000-09-21 15:50:28

    From: Martin Young [mailto:martin.young@...]

     >On Sep 20, 10:00am, wtanksley@... wrote:

    >> >purposes of continuations [without stacks]?

    >> A continuation in a stack-based language doesn't need a

    >> stack.

    >Fair enough.  When would one use a continuation without an

    >accompanying stack?

     Almost anywhere you need a continuation, but not a task: for example, when

    performing backtracking.  You'll need to keep the variables which will be

    needed for the continuation call sitting on the stack; fortunately, that's

    easy with most backtracking tasks.

    As another example, a return address IS a continuation, by definition, and

    surely nobody can argue that it should have its own stack.

     >> >If one represents a Joy program as a binary tree [snip]

    >> That's a suprising idea to me.  What advantages does it

    >> bring for you?

    >Um.  Not sure.  That's just how I've always thought about it.

    >Having said

    >that, I have a plan for an optimiser that requires the tree to

    >be flattened so I'll be needing to change paradigms anyway.

     Hmm.  It's obvious that a tree form is the right storage for applicative

    languages.  It *could* be that you've got bad habits from applicative

    languages.  OTOH, perhaps programs *do* grow on trees, and my negative

    impression is simply an overreaction against applicative languages.

     >> I've seen very sophisticated backtracking implemented using

    >> this, and it looked completely natural.

    >This is what Monkey does.  In this respect the dip stack works

    >just like the return stack in forth.

     That was my impression at the time.

     >Martin Young  working for  STMicroelectronics at     `(o)_(o)'

     -Billy