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]

Re: [stack] toy

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

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