everything is a unary function of ?

stevan apter — 2004-01-02 15:52:31

in joy, everything is a unary function of the stack.  e.g.

+ takes a stack .. n m and returns .. n+m.



since combinators involve the evaluation of quotations, a

combinator like 'linrec' will at some point call the evaluator,

which in turn may involve evaluating further combinators,

&c.  



over the last week i've been playing around with a slightly

different formulation:  everything is a unary function of

the pair [data-stack code-stack], where the code-stack is

the rest of the current program.  some functions (e.g. +)

return the code-stack untouched and some functions modify

it.



for example, the 'i' combinator which expects [..p..] on

the data-stack simply prepends the elements ..p.. to the 

code-stack.  it then returns both stacks (so ..p.. will

evaluate next).



the 'linrec' combinator expects four quotations on the 

data-stack X:  I T E F.  i'll write ..Q.. to denote the

items in the quotation Q.



linrec prepends to the code-stack Y, so the resulting

code stack is:



    ..I.. I T E F X linrec_ Y



where X is the data stack (reference-counted by k, so 

this is free).



..I.. evaluates, then I T E F and the stack X are pushed,

then linrec_ evaluates.



the 'linrec_' combinator expects



    b I T E F X



if b is true, it returns



    data stack = X 

    code stack = ..T.. Y



i.e. evaluate ..T.. .



if b is not true, it returns



    data stack = X

    code stack = ..E.. I T E F linrec ..F.. Y



i.e. evaluate E, then push I T E F, execute linrec, then

evaluate ..F.. . 



this is much more difficult to describe than it is to code!

so here are k versions of linrec and linrec_:



linrec:{[x;y;i;t;e;f](x;i,(i;t;e;f;x;`linrec_),y)}

linrec_:{[x;y;b;i;t;e;f;s](s;:[b;t;e,(i;t;e;f;`linrec),f],y)}



you can compare the 1-stack (recursive) implementation of

a tiny fragment of joy with the 2-stack version:



    www.nsl.com/k/tck/



tck1.k and tck2.k, respectively.  tck.k contains test

examples.