More about toy
>> * 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 program is the whole tree. Think of this tree in list form: [ ... ] executed by an implicit combinator "i". Each list is doubly linked with a special element representing the empty list as its first (and last) element: see Knuth for the canonical presentation of this structure. (This special element contains a pointer to the containing box.) Therefore, none of {list.first, list.first.left(.left...), list.first.right(.right...) is ever NIL and the empty list is not a special case. The stack is the traversed portion of the list and the continuation is the untraversed part. The difference between the whole program (list) and lists occuring within it is that the program (or thread) has one extra pointer -- call it X, and that the empty box at the end of the thread points to a NIL instead of a containing box. Execution begins with X pointing to the first box in the thread. The VM loop is
X:= thread.first.right (*skip the empty box thread.first *)
halt := false
repeat
if X is an opbox (** 1 **)
opbox.op(X)
else if X is the special empty box
if X.containingbox # NIL
X := X.containingbox.right
else
halt := true
else
X := X.right (** 2 **)
until halt
(** 1 **)
Each op must : check the types of boxes on its left to find its arguments or raise an exception (not represented above and not implemented yet); replace these and itself with modified or different boxes; and set X. For instance, "plus" looks for an intbox a to its left and another b to a's left; sets b.n := b.n + a.n; splices both a and itself out of the thread; adds a to the intbox pool and itself to the opbox pool for recycling; and sets X to the box to the right of the splice.
(** 2 **)
"PUSH"
>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.
No, not exactly. Yes, [ [dup mul] "square" ] define ] uses a dictionary, but the dictionary is used by the scanner, not the VM. The defined word can't be used until a new program is scanned, and ops are never redefined at runtime.
>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?
Sounds like a good benchmark. "Never trust a benchmark that you haven't rigged yourself": still, perhaps someone else should post one and we can both adapt and run it.
>How do you implement "times" without recursion in the interpreter?
This was the key.
[ 1 [1 plus] 10 times]
X
[ 1 [1 plus] 10 times]
X
[ 1 [1 plus] 10 times]
X
[ 1 [1 plus] 10 times]
X
[ 1 1 plus[1 plus] 9 times]
X
[ 1 1 plus[1 plus] 9 times]
X
[ 2 [1 plus] 9 times]
.
.
.
.
[ 11 [1 plus] 0 times]
X
[11]
Tail recursion elimination. Difficult to understand until one invents it.
"Warm reception" was not intended to mean "judged as impressive"; it meant "it is hoped that the list members will try the demo." (When there is one.)
**************************
>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, since the boxes all come from the heap, technically, this is true.
>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.
Why not call them "euphors"?
Mozart Oz has an execution model in which dataflow threads communicate across a guarded store. The "variables" in the store are logical variables not supporting assignment. They can be bound only once. Such a model is under consideration for toyOs, a toy OS to be written in toy.
sr