# Joy execution model and recursion.

## Martin Young — 2000-08-21 13:25:44

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

                       _(_)_                             -="==="=============='