Martin Young — 2000-09-19 12:36:47

Sorry about the lack of attribution: the text appeared as an attachment and I
can't quote those properly...

> * fundamental data structure is now a doubly linked box chain

Why doubly linked? Which operations need a "previous" reference?

> * program = stack = continuation

Is this a mistype? Surely "program+stack=continuation"? If not, could you
explain this at greater length?

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. If you are not
recursing on the native Oberon stack, and you only have one Joy stack, where
are you storing the continations?

The only way I can see to do this would be to build the whole tree before
execution and represent the program as a reference into that tree. I don't
think you're doing this however as you've already said you allow words to be
redefined at runtime using a hashed dictionary.

Please enlighten us.

Fyi, my implementation has a second stack (the dip stack) where continuations
(and other bits and pieces) are stored and are visable to and manipulatable by
the program itself. All the combinators are derived from a single "while"
style construct which itself achives itteration by manipulating the current
continuations.

> * it is now trivial to start and stop threads. a thread is a list which
> remembers where it is executing.

Yes, this has occured to me too. What I haven't worked out yet it how to
synchronise such threads and to allow data to be communicated between them.
Any thoughts?

> * speed: one would expect toy to be slower now and it is. The
> standard benchmark [ 1 [ 1 plus ] 10000000 times] now takes
> almost 16 seconds -- before it was around 4.5 seconds. toy is now
> about 3.5 times slower and twice as slow as official Joy.

This is impressive. It's a little better than 10x faster than Monkey.

I implemented the Sieve Of Erastothanes (sp?) in Monkey last night as I believe
it would be a more representitive benchmark but I couldn't get the thing to
work with Joy. Do you have any longer test programs?

How do you implement "times" without recursion in the interpreter?

> It is to be hoped that, this accomplished, such a bootable image would meet
> with not only a courteous but a frankly warm reception from the estimable
> recipients of this mailing list.

Okay, I'll bite.

Obviously I can't speak for the estimable recipients of this mailing list. I
am speaking purely for myself when I say that I'll be more impressed when I can
look at the code.

--
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. /
_(_)_ -="==="=============='

wtanksley@bigfoot.com — 2000-09-19 15:42:42

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.

>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*. Joy data can be tree
structured (as with quotations), list structured, and graph structured; but
manipulating a graph doesn't make your program a graph. If you were going
to call your Joy program a tree simply because it contains literal
quotations, you'd also have to call it a graph because it uses names.

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

>The only way I can see to do this would be to build the whole
>tree before
>execution and represent the program as a reference into that
>tree. I don't
>think you're doing this however as you've already said you
>allow words to be
>redefined at runtime using a hashed dictionary.

I don't understand why this should matter. You just compile each word as
you meet its definition, and execute words as you come across their names.

>Fyi, my implementation has a second stack (the dip stack)
>where continuations
>(and other bits and pieces) are stored and are visable to and
>manipulatable by
>the program itself. All the combinators are derived from a
>single "while"
>style construct which itself achives itteration by
>manipulating the current continuations.

Ah, somewhat Forthlike. The return stack in Forth is vital.

>> * it is now trivial to start and stop threads. a thread
>> is a list which
>> remembers where it is executing.

>Yes, this has occured to me too. What I haven't worked out
>yet it how to
>synchronise such threads and to allow data to be communicated
>between them. Any thoughts?

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.

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

-Billy

Louis Madon — 2000-09-19 22:45:09

Martin Young wrote:

> > * speed: one would expect toy to be slower now and it is. The
> > standard benchmark [ 1 [ 1 plus ] 10000000 times] now takes
> > almost 16 seconds -- before it was around 4.5 seconds. toy is
> now
> > about 3.5 times slower and twice as slow as official Joy.
>
> This is impressive. It's a little better than 10x faster than Monkey.
>
> I implemented the Sieve Of Erastothanes (sp?) in Monkey last night as I believe
> it would be a more representitive benchmark but I couldn't get the thing to
> work with Joy.

One thing I've noticed with the Joy interpreter is that it doesn't check
for stack overflow and so sometimes a perfectly good program will core
dump. If you're Sieve of Eratosthenes is generating alot of intermediate
data (eg. by deep recursion) this might be the cause. One way to check,
is to try and increase the maximum size of the stack: in globals.h
change MEMORYMAX to something like 2 million and recompile (its
originally at 20000).

--
Louis.

Martin Young — 2000-09-20 09:46:55

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.

Given deterministic execution I can see that one could derive the stack and the
continuations from the program, but surely during execution one needs a
separate stack?

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.

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

Personally I prefer to think of Joy programs as trees because this preserves
more of the program structure.

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

Well, yes, obviously: they have to be stored somewhere and if it's not the
stack it must be the heap. Okay, I suppose they could be written to a file or
something but they's pretty unlikely.

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?

> >The only way I can see to do this would be to build the whole
> >tree before execution [snip]
> I don't understand why this should matter. You just compile each word as
> you meet its definition, and execute words as you come across their names.

<thinks about it> Okay, you could do this.

Still, I'd like Soren to tell us what he actually does.

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

--
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. /
_(_)_ -="==="=============='

wtanksley@bigfoot.com — 2000-09-20 17:00:24

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.