# Joy in Avail

## Mark van Gulik — 2000-06-03 08:41:51

    Here it is.  Compiling this Avail module causes 25 to be printed (as

    expected)...

    -----------------------------------------------------------------------

    Module "Examples-Joy"

    Extends

    Uses "kernel"

    Names

    Body

    /*  Define a trivial Joy interpreter, directly *embedded* in the Avail

    syntax. */

    /* Some useful types... */

    stack ::= tuple of all;

    funct ::= [stack]->stack;

    /* Polymorphic utility for evaluation... */

    Method "_run_" is [a : all, s : stack | <a> then  s; ]:stack;

    Method "_run_" is [f : funct, s : stack | f(s); ]:stack;

    Method "_runAll_" is [t : tuple, s : stack |

       s2 : stack := s;

       t do [x : all | s2 := x run s2; ];

       s2;

    ];

    /* Some useful primitive operations... */

    pop : funct := [s:stack | s[2..||s||];];

    dup : funct := [s:stack | <s[1]> then s;];

    swap : funct := [s:stack | <s[2],s[1]> then (s[3..||s||]); ];

    print : funct := [s:stack | Print s[1]; s[2..||s||];];

    i : funct := [s:stack |

       cast s[1] into [t : tuple |

          t runAll (s[2..||s||]); ]; ];

    is : funct := [s:stack |

       cast s[1] into [str : string |

          cast s[2] into [t : tuple |

             Method str is [ [s:stack | t runAll s;]; ]; ]; ];

       s[2..||s||];   /* leaves quoted program on stack */

    ];

    Method "+" is [ [s:stack |

       cast s[1..2] into [t : tuple like <integer, integer> |

          <t[1]+t[2]> then (s[3..||s||]);]; ]; ];

    Method "*" is [ [s:stack |

       cast s[1..2] into [t : tuple like <integer, integer> |

          <t[1]*t[2]> then (s[3..||s||]);]; ]; ];

    /* Quoting (0, 1, >1)... */

    Method "[]" is [<>;];

    Method "[_]" is [x : all | <x>;];

    Method "[_]" is [aList : list | <aList>;];

    /* And, of course, the outer 'evaluator'... */

    Method "_Joy run" is [t : tuple |

       residue ::= t runAll <>;

       Assert residue = <>;

    ]:void;

    [[dup, *], "square", is, pop] Joy run;

    [5, square, print] Joy run;

    -----------------------------------------------------------------------

    That was it.  I didn't think it would take much code, but that was a little

    smaller than I expected.  A couple of things to note:

    Avail is strongly typed, and Joy (this version at least) is not typed, so a

    couple of dynamic casts were used (these are checked at runtime).

    The 'is' operation actually defines a new Avail word taking no arguments and

    returning a funct.

    The commas are necessary in the current Avail implementation.  Initially I

    tried defining a juxtaposition operation "__" (i.e., an operation with no

    keywords or punctuation, but taking two arguments) of type

    [funct,funct]->funct, but that meant I had to quote literals somehow, (to

    turn them into functs suitable for juxtaposing).  I chose a prefix backquote

    "`_".  Then I tried implementing quotations and discovered I could do it,

    but only if I pre-collapsed tuples (quotations) into a "compiled" form,

    preventing all list-manipulation operations except concatenations.  Oh,

    well.  I guess that's about as close a non-applicative language can come to

    embedding an applicative language's syntax directly.

    The "directness" of the embedding may not be obvious.  Let me write one more

    expression to explain...

    [2+2, square, [s:stack | square(s) then s[2..||s||];], print] Joy run;

    In this expression, the 2+2 is an ordinary Avail expression that yields the

    Joy literal 4.  The square funct is as defined previously.  Then a closure

    that matches the funct signature is constructed inline.  Note the use of the

    'square' operation in the Avail code, defined earlier by the Joy 'is'

    operator.  The inline funct takes a stack s, passes this to the square

    operation, which then answers a stack with just the number 16 on it (in this

    case), then it takes this stack, which is really just the tuple <16>, and

    concatenates the remainder of the stack s onto it via the "_then_" operation

    (top of stack is the leftmost tuple element for convenience).

    I believe the K implementation Stevan Apter <apter@...> submitted

    earlier is more concise and much more comprehensive (neither feature was a

    goal for me at this time).  On the other hand, it required the Joy

    expressions to be quoted (via 'I"').  I may have misunderstood the K code,

    but it seemed that some Joy operations were defined via 'I"' quoted Joy

    expresions, but others were defined via K code directly.  I didn't see any

    mixtures, and I don't understand the implementation well enough to hazard a

    guess whether it would be possble to mix the Joy and K code in a definition.

    Now, about typing.  I should be able to piggyback a Joy type system on top

    of Avail's type system.  That is, type declarations made in a typed

    extension of Joy should be checkable when the Joy-in-Avail code is compiled.

    By maintaining type constraints in a stack-oriented manner, all quotations

    can be type-checked by "simulating" the operations as mere type-stack

    manipulation.  The actual code should serve to clear up this concept, so I

    won't discuss it further until I've had (A) some sleep, and (B) time to

    write a statically type-checked Joy system in Avail.

    Oh, by the way, the code in this post took less than half an hour to write,

    despite frequent problems with my work-in-progress Avail interpreter (I

    disabled the C++ DLL and just let it run 10x slower).  This post itself took

    much longer than that to compose.

    If there are specific areas of the code (e.g., unfamiliar operators) that

    are hard to understand, just ask.

## Mark van Gulik — 2000-06-04 18:32:32

    "stevan apter" <apter@...> wrote:

     > Subject: Re: Joy in Avail

    >

    >> I believe the K implementation Stevan Apter <apter@...> submitted

    >> earlier is more concise and much more comprehensive (neither feature was a

    >> goal for me at this time).  On the other hand, it required the Joy

    >> expressions to be quoted (via 'I"').  I may have misunderstood the K code,

    >> but it seemed that some Joy operations were defined via 'I"' quoted Joy

    >> expresions, but others were defined via K code directly.  I didn't see any

    >> mixtures, and I don't understand the implementation well enough to hazard a

    >> guess whether it would be possble to mix the Joy and K code in a definition.

     Thank you for that beautifully detailed description of your Joy interpreter

    in K.

     > X and Y are two ways to recursively evaluate the stack.  remember that

    > in my implementation, the stack is a list s.  ()E/s takes any stack and

    > reduces it to a single evaluated item.  ()E\s takes an stack, reduces

    > it, and returns a list each of whose items is the stack reduction up

    > to that point.  X and Y are designed to be used directly, in k (see

    > below).

     ...

     > E:{:[~4=4:y;(,y),x;7=4:v:. y;v x;6=4:v;(,$y),x;x _f/v]}

    > X:()E/

    > Y:()E\

     So your X function takes a stack and a program... (?).  Hm, I'm lost on this

    one.  I realize the Joy interpreter E is kind of 'invoked' via X or Y, but

    where does the Joy program go?  Oh wait, that was extracted as a side-effect

    from the input stream, right?  So X returns the result of running the next

    "line" of code on the given stack, but Y returns a list of states the stack

    passes through during evaluation.  I assume Y is for debugging?

     > now to your question:  i defined e.g. swapd as:

    >

    >     I"[swap]dip"

     Ah, now I see why it's 'I"'.  You're piping a string into the interpreter as

    input.

     > as the parse of the joy concatenation [swap]dip.  the resulting

    > k list is

    >

    >     (,`swap;`dip)

    >

    > a two item list, whose first item is a one-item list of the symbol

    > `swap and whose second item is the symbol `dip.  i use I because

    > it allows k to define joy programs as lists more consisely than

    > the primitive list notation of k.

     Ok, so you actually parse the string with Joy's (minimal) syntax rules.  But

    the resulting list is non-executable.  Would it be possible to define a new

    operator Z such that Z"[swap]dip" yields a function of type stack->stack?

    This could be tricky if quotations are allowed to be deconstructed (a

    problem I'm having with an attempt at a typed Joy in Avail).

     > a more satisfying implementation of joy would attempt to define as

    > many of the joy operators as possible this way, i.e. as lists rather

    > than k functions.

     Yes, defining most Joy operators via Joy leads to better axiomatization.

    But, again, can the list operators be mapped to K functions?   Maybe you're

    doing this automatically, or it's a simple matter of applying E (or a

    derivative) to the list.  I'm still a bit confused about this.

     > qsort:I"[small] [] [uncons [>] split] [swapd dip cons concat] binrec"

     I like this implementation.  I saw a three-liner in Clean (a functional

    language) long ago and was likewise impressed.  The obvious question for me

    is:  What would qsort look like in K?  In addition, how short a sort can you

    write, even if you don't care about the efficiency?  I.e., even a *cubic*

    time algorithm would be acceptable.

## Mark van Gulik — 2000-06-04 18:40:36

    "stevan apter" <apter@...> wrote:

     > i've been reading up on the subject of continuations (thank you christian

    > tismer) and it seems as though first-class continuations would be relatively

    > simple to implement in joy.  any thoughts on this one?

     A continuation in Joy would simply be a pair consisting of the stack, and

    the remaining stream of symbols (which would be in the form of a quotation).

    To be useful you would need the ability to capture a continuation and the

    ability to resume it.  Capturing it is not itself difficult, but a feature

    I've found necessary is determining whether you're simply continuing

    immediately after a capture or if someone has just restarted the

    continuation.  Maybe the continuation should expect an argument to be pushed

    on the stack by the caller, and the capture operation itself pushes some

    value like 0 before continuing.  Sounds like a plan?