Folk,
One thing I've noticed about my initial Joy-in-Prolog and the reference
implementation is that the words "dip" and the recursive combinators use
recursion in the underlying implementation language. This means that (a) a
highly recursive Joy program results in a highly recursive interpreter, and (b)
some of the current continuations are actually on the native machine stack and
thus not available to the Joy program. I think this can be avoided and I'll
explain how.
I note also that the recursive combinations don't need to use recursion in the
underlying implementation. The construct "execute P1, if True execute T else
execute P2, recurse, execute P3" (and similar) can be expressed itteratively:
because there are no lambda actual-parameters to save and the conbinator itself
defines to where execution returns after each sub-program, the machine can
simply count recursions "down" through P1/P2 and execute the appropriate number
of "up"s of P3. Unless P1/P2 changes the size of the stack, a fully recursive
algorithm can be expressed in constant space. Cool!
Unfortunately, to do this either (1) every recursive combinator must be encoded
non-recursively as part of the interpreter or (2) the ability to do
non-resursive itteration must be exposed to the Joy program. I think that the
user should be able to define new recursive combinators with the same level of
power and expression as any of the built-ins so I favour (2).
One solution is to copy forth. It has a data stack and a return stack. The
Joy stack is equivilent to the data stack but it currently has no visible
return stack. I've called the Joy return stack the "dip-stack" and added two
primitive words, "move" and "unmove" which move a value from the top of the
data stack to the top of the dip-stack, and the converse, respectively.
The Joy reference implementation does this:
_dip()
{
Quote = POP(stack)
X = POP(stack)
execute(Quote)
PUSH(stack,X)
}
[Yes, I know the actual code look quote different but it's doing the same
thing.]
I.e. it holds the dip-ped item on the C stack whilst it does the dip. With
move and unmove dip looks like this:
dip == swap move i unmove
So, no matter how deeply the Joy program dips, the C stack remains constant
sized, at the expensive of the Joy-visible dip-stack.
There is one more piece of semantics to do with the dip-stack. When the
intepreter begins to execute a new program it places the remains of the current
one on the dip-stack. When execution of a program finishes a new one (i.e. the
remains of the previous one) are pulled from the dip-stack. Thus, the stack
and the dip-stack constitute the complete current continuation.
Using only the dip-stack and "if" it is possible to implement an itterator. I
have an implementation of this at home. In essence a program pushes itself
onto the dip-stack so that when it finishes executing once, the intepreter
pulls the same program off the dip-stack and thus appears to itterate).
Once you have an itterator you can implement counted recursion. Here's my
version of linrec. ["pcon" is a combinator which executes T, if true it
executes P1 and loops, otherwise it stops.] My version of linerec has slightly
different semantics to the reference implementation's but the principle stands.
repeat ==
{{
{ dup 0 <= }
{ }
{
{ { dup { i } dip } dip }
{ -1 + dup 0 >= }
pcon
}
ifte
drop drop
}}
linrec ==
{{
[ 0 ] 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
}}
[Oh, and I've added a simple type system to my Joy interpeter. In this example
you need only know that things in curly braces are executable programs whilst
normal lists are not, and the word "programise" turns a normal list into a
program.]
Finally, here's the factorial function using linrec:
fact == { dup 1 = } { } { dup -1 + } { * } linrec
It's not easily tail-call optimisable so in most languages this alogrithm will
consume stack space proportional to the paramter. In my dialect of Joy, stack
usage is constant. This is a good thing IMHO.
I think that I'll make explicitly recursive programs illegal in my dialect.
This would allow any Joy program to be expanded to a finite length sequence of
primitive operations ripe for machine analysis and optimisation. With constant
space recursive combinators the programmer doesn't lose any expressive power.
Isn't Joy great?
--
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. /
_(_)_ -="==="=============='