Greetings all!
I'm interested in using Joy (or a modified version of it) as a kind of scripting language
for some projects I am working on. I had searched far and wide for a language (or
any model of computation) that was simple, powerful, flexible, and most importantly
was strongly reflective (in the sense that programs could easily modify their own code
or the code of other programs). I'm very impressed with Joy, and it seems like it
might fit the bill.
The problem I ran into is that in the current C implementation of Joy, evaluation of
quotations (by combinators) is done using recursion in C. For example, the
implementation of dip 'recursively' calls the exeterm function to execute the
quotation it popped off the stack. So, the current state of execution (dare I say, the
continuation?) is stored implicitly on the C stack.
For my (C++) application, I want a Joy interpreter that does one small (O(1)?) unit of
work each time I invoke it. This seems to imply that I need to do more explicit
bookeeping on some kind of stack. I looked into SECD machines a bit, and I think I'm
looking for something exactly like that: a simple machine where the evaluation of
each instruction affects a simple transformation of the data structures, so there is no
recursive invocation of the evaluation function.
So I'm wondering if anyone has already figured out such a machine for Joy, or has any
ideas as to the best way to design one. I've come up with a few ideas but they are
somewhat unsatisfying. It seems like we must introduce some new instructions, or
even an entire intermediate language to make things work. Take for example the ifte
combinator. Part of its evaluation would be setting up some kind of new 'frame' to
execute the IF quotation. But after that quotation finishes executing, there has to be
some kind of instruction lying around to do the remaining work of checking the
resulting true/false, popping that frame, and instating the correct THEN or ELSE
frame. Other combinators (map?) may be more difficult. So is the best solution to
introduce new (internal-use only?) 'RISC' instructions that these 'CISC' combinators
would be broken down into? Or better to introduce an entire new intermediate
execution language? Or is there a simple solution I am missing?
I'm not sure that such an explicit-stack implementation would compete performance-
wise with the current implementation, but it seems like it might be worth looking
into. Also, I don't really understand continuations, but it seems like it might make
the implementation of continuations easier.
Any input would be greatly appreciated.
Russ
symstym@...
p.s. Just searching the archive some more now, and I'm wondering if Monkey or Toy
might be close to what I am looking for?
Hi,
On Sat, 2003-06-28 at 08:34, symstym wrote:
> p.s. Just searching the archive some more now, and I'm wondering if Monkey or Toy
> might be close to what I am looking for?
Monkey certainly behaves, in this aspect, in the way you describe: all
primitive words are O(1) in time and, aside from the heap, the
interpreter runs in constant space. Beware though, Monkey is not Joy -
I've changed the syntax to be more visually pleasing (to me) and some of
the word semantics are very slightly changed. Most of the functional
changes I've made are (I hope) toward making Monkey compilable.
Rather than recurse on the C stack I have a second stack (which I call
the dip stack). When a new program is executed (generally with the i
combinator) the remainder of the current program is pushed onto the dip
stack. Whenever the end of a program is reached it is replaced with the
top item from the dip stack. If the dip stack is empty, the whole
program is finished.
A couple of new words make the dip stack explicit. 'move' and 'unmove'
transfer data between the top of the normal stack and the top of the dip
stack. This allows control words, defined in the usual manner, to
manipulate the current continations (which is what the dip stack
effectively is) and hence affect program flow.
Here's how some of the more complex combinators are built up:
<< Helper words. >>
swapdup == {{ swap dup }}
swapif == {{ swap if }}
pcon ==
{{
{ dip swapdup { swapif } dip unmove swap { dup unmove swap move swap
move move 0 } if drop }
cons cons
dup move move
}}
The word 'pcon' is a combinator which takes two items from the top of
the stack (T P pcon --> ~). It executes T first. If boolean true is
left on top of the stack it executes P then starts over again, else it
finishes.
One of the difference between Monkey and Joy is that I don't set up a
"local" stack for execution of the condition program - they execute on
the normal stack and are expected to leave exactly one boolean result.
Here's ifte. 'if' is a primitve word which takes two programs. If the
first leaves a boolean True on top of the stack, it executes the second.
ifte ==
{{
{ i } dipd roll
dup
{
{ drop i } if
} dip
not
{
{ drop } dip
i
} if
}}
Here's map. This would work in normal Joy - it relies only on having
tailrec (defined below). Again, however, it doesn't use "local" stacks
so "badly behaved" words will leave the normal stack in a state
(although the dip stack is immune to badness on the normal stack).
map ==
{{
swap [ ]
{ { dup [ ] = } dip swap }
{ }
{
{ uncons { swap dup { i } dip swap } dip swap } dip cons
}
tailrec
{ drop drop } dip
reverse
}}
Something a bit more complex:
tailrec ==
{{
unit cons cons << ... [ {P} {T} {R1} ] >>
{ << body: >>
dup
{ rest rest first i } dip
} ... [ {P} {T} {R1} ] >>
{ << test: >>
dup first swap << ... {P} [ {P} {T} {R1} ] >>
{ i } dip swap << ... [ {P} {T} {R1} ] bool >>
unit programise << ... [ {P} {T} {R1} ] {bool} >>
{ rest first i false } << ... false >>
{ true } << ... [ {P} {T} {R1} ] true >>
ifte
}
pcon
}}
linrec ==
{{
[ 1 ] cons cons cons cons
{ << body: >>
dup
{ rest rest first i } dip
}
{ << test: >>
dup first swap
{ i } dip swap
unit programise
{ dup { rest first i } dip false }
{ uncons uncons uncons uncons first 1 + unit cons cons cons cons
true }
ifte
}
pcon
rest rest rest
unswons swap first
repeat
}}
The word 'programise' is Monkey fluff. I differentiate between words
which are programs (and hence potentially compilable) and data lists
(which are not compilable). Programise changes a data list into a
program list but is simply a typecast thing - lists and programs are
still fully reflective.
For performance purposes I can optionally use primitive versions of many
of the helper words (in particular I can split pcon into two O(1)
primitive words).
Garbage collection in Monkey will break the O(1) thing. It's done
continuously but it is a recursive algorithm (but at least runs using
only the memory of the list cells which are being collected).
The source code isn't exceptionally pretty (and is always a work in
progress) but if you (or anybody else) wants a copy, do let me know.
--
Martin Young, at home.