# Re: [stack] Re: Joy in Avail

## stevan apter — 2000-06-04 20:02:31

    ----- Original Message -----

    From: Mark van Gulik <ghoul6@...>

    To: <concatenative@egroups.com>

    Sent: Sunday, June 04, 2000 2:32 PM

    Subject: [stack] Re: Joy in Avail

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

    my pleasure.

    >

    > > 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... (?).

    a stack and a *list* of programs.  see below.

     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?

    / and \ are fundamental k iterators.  consider

      6+/2 5 7

    20

      6+\2 5 7

    6 8 13 20

    (these can also be written:  +/[6;2 5 7] and +\[6;2 5 7])

    / (over) is an adverb which takes a verb, in this case, the two-place (or

    transitive) verb +, and returns a two-place verb f[x;y] which has the following

    semantics:

          start by setting r to x = 6

          apply f to r and y[0], return r = 8

          apply f to r and y[1], return r = 13

          apply f to r and y[2], return r = 20

    in other words, apply f to r and y[i] for i = 0 to -1+length of y.  the case

    for verbs and functions of more than two arguments is straightforward:

          r:f/[x;y1;...;yn] and r:f\[x;y1;...;yn] for f of n+1 args

    the case for verbs and functions of one argument is related, but technically

    overloaded:

          r:f/x keeps applying f to its result r until r=x or r=the previous r

    as you can see, \ (scan) has the same syntax, but the derived verb returns

    a list of the r's.

    E is a two place function - its first argument is the stack, and its second

    argument is something to evaluate.  so x E/y computes the state of the stack

    x after E has successively evaluated items in y, and x E\y returns a list of

    all the intermediate stack-states.  to evaluate *one* thing:  E[x;y i].

    there are no side-effects to E (J uses a side-effect to print the stack at

    the console).

    () is the empty list:  the initial state of the stack.  so ()E/ is a one-place

    function (a curry of E/, which is in turn a derived function, as per above);

    functions are first-class, so we can just define X by assigning that one-place

    function to 'X'.

    >

    >

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

    I is just a function - it takes a string, and busts it up into a k

    list.  that list is input to E via X.

    >

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

    right.

    > But

    > the resulting list is non-executable.

    it's just a list.  actually, it doesn't contain any function-data.  for

    example, the joy program 2 3 + is parsed into (2;3;`plus) - a list of

    three elements:  an int, an int, and the symbol of the k function which

    implements joy's +.  in the evaluator E, i test to see whether the data

    type of the k object whose symbol is `plus is a function.  if it is, i

    apply it to the stack.  if not, i put the string "plus" on the stack.

    (strings and symbols are different in k).

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

    yikes - that never occurred to me.

    ok, consider this.  suppose we represent the stack, not as a list, but as

    a function.  the empty stack is the function

        N:{x;()}

    it takes anything x and returns the empty list.  now what is it to push

    a constant item onto the stack?  it is a function C which takes the stack

    x and prepends y to the application of x to the next item:

        C:{(,y),x z}

    the application of a function to the stack is a function A which takes

    the stack x and applies the function y to the application of x to the

    next item:

        A:{y x z}

    (note that 'x', 'y', and 'z' are the default first, second, and third

    arguments for a k function.)

    the compiler for joy looks a lot like the evaluator:

        F:{:[~4=4:y;C[x;y];7=4:v:. y;A[x;y];6=4:v;C[x;$y];x _f/v]}

        Z:N F/

        W:N F\

    the difference is that start-state for Z and W is the "empty function",

    N rather than the empty list.  Z returns a function, which of course

    must be evaluated (on no arguments):

      f:Z I"2 3 plus 4 minus"

      f

    {y x z}[{(,y),x z}[{y x z}[{(,y),x z}[{(,y),x z}[{x;()};2];3];`plus];4];`minus]

      f[]

    ,1

    (we can modify this to start with an arbitrary one-place function instead of N.

    for example, the function {x} which takes x and returns x:

        g:{x}F/I"2 3 plus 4 minus"

        g 10 20 30

    1 10 20 30

        g:{x}F/I"2 plus"

        g[,10 20]

    ,12 22

    )

    the scan version of Z produces a list of the intermediate functions:

        h:W I"2 3 plus 4 minus"

        h 0

    {x;()}

        h 1

    {(,y),x z}[{x;()};2]

        h 2

    {(,y),x z}[{(,y),x z}[{x;()};2];3]

        h 3

    {y x z}[{(,y),x z}[{(,y),x z}[{x;()};2];3];`plus]

        h 4

    {(,y),x z}[{y x z}[{(,y),x z}[{(,y),x z}[{x;()};2];3];`plus];4]

        h 5

    {y x z}[{(,y),x z}[{y x z}[{(,y),x z}[{(,y),x z}[{x;()};2];3];`plus];4];`minus]

    and, if each function in h is applied to nil (another way of running a function

    of no arguments) then you get a list of the intermediate results:

        h@'_n        / each h applied to nil

    (()

     ,2

     3 2

     ,5

     4 5

     ,1)

    thanks *very* much for the idea.  if nothing else, it demonstrates

    an interesting constructive equivalence between concatenativity and

    applicativity (if those are words).

    >

    >

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

    i'm not sure i understand, but i think what my interpreter is doing

    is simpler than you think.  probably a side-by-side keyboard session

    would dispel your confusion in minutes, if not seconds.

    >

    >

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

    it's manfred's implementation, from one of the joy papers.

    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.

    k has <x and >x, implemented as a distribution sort (as described by knuth,

    i believe).  so in the best case, which is most of the time for finance,

    it achieves linear time, but can get really really bad if the data isn't

    distributed "well".  k tries to do a distribution sort, and if it finds

    that it's taking too long, it switches to something else - possibly quick-

    sort.  as i said, in practice we've always had mindblowing sort performance.

    (specs and benchmarks are, or were, given on the kx website, or possibly

    in the mailing list archives).

    >

    >

    > ------------------------------------------------------------------------

    > Bids starting at $7 for thousands of products - uBid.com

    > http://click.egroups.com/1/3027/6/_/_/_/960143531/

    > ------------------------------------------------------------------------

    >

    > To unsubscribe from this group, send an email to:

    > concatenative-unsubscribe@egroups.com

    >

    >

    >

    >

## stevan apter — 2000-06-04 20:33:40

    > (we can modify this to start with an arbitrary one-place function instead of N.

     i see that i didn't go quite far enough:

    C:{(,y),x z}

    A:{y x z}

    N:{x}

    F:{:[~4=4:y;C[x;y];7=4:v:. y;A[x;v];6=4:v;C[x;$y];x _f/v]}

    Z:N F/

    W:N F\

        reverselist:Z I"[]swap infra"

        reverselist

    {y x z}[{y x z}[{(,y),x z}[{x};()];{@[x;1 0;:;2#x]}];{(,x[1]E/*x),2_ x}]

    this version of F compiles into symbol-free functions (there was a typo in the

    previous version).

    note that if you want Z (or W, X, Y) to do the parsing:

        Z:N F/I@

        reverselist:Z"[]swap infra"

## wtanksley@bigfoot.com — 2000-06-06 02:05:05

    From: Mark van Gulik [mailto:ghoul6@...]

     >"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).

     That's a LOT more than is needed for a continutation in applicative

    languages.  I can certainly see why theory would lead you to believe that,

    but I suspect that it's more than we strictly need.

    I believe that there's sufficient information simply in the execution

    pointer, and no stack state is needed.  There's only one program in Forth

    using continuations that way, but it seems to work very well.

    -Billy

## stevan apter — 2000-06-06 12:25:11

    ----- Original Message -----

    From: <wtanksley@...>

    To: <concatenative@egroups.com>

    Sent: Monday, June 05, 2000 10:05 PM

    Subject: RE: [stack] Re: Joy in Avail

    > From: Mark van Gulik [mailto:ghoul6@...]

    > >"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).

    >

    > That's a LOT more than is needed for a continutation in applicative

    > languages.  I can certainly see why theory would lead you to believe that,

    > but I suspect that it's more than we strictly need.

    >

    > I believe that there's sufficient information simply in the execution

    > pointer, and no stack state is needed.  There's only one program in Forth

    > using continuations that way, but it seems to work very well.

    i haven't programmed in a language which supported first-class

    continuations, so i have no feel for how one would use them.

    despite having read several "continuations demystified" papers,

    i'm still not sure i understand what's involved in having them

    available.

    the only half-way compelling example i've seen thus far (and i

    didn't understand the solution) was this one:  suppose you've

    got a tree t and a simple routine tw which walks the tree and

    at each node prints the node name and the depth.  output might

    be:

        0 t

        1 a

        2 b

        2 c

        1 d

        2 e

        3 f

        3 g

        2 h

        etc.

    so now imagine that you've got two structurally isomorphic

    trees t and u (the original example required only weak

    isomorphism).  somehow, continuations enable you to use

    two coroutines - tw on t and tw on u - to print "in parallel":

        0 t u

        1 a aa

        2 b bb

        etc.

    i have vague intimiations of what must be going on, but i

    can't quite bring it into focus.

    my first thought wrt joy was similar to mark's:  the current

    execution context = the pair:

        current state of the stack

        everything left to evaluate

    in my implementation

        x E/y

    is the evaluation loop:  x is the initial state of the stack,

    and y is a list of items to evaluate - a program.  (i may have

    misled mark in a previous note by insisting that y was a list

    of programs - indeed, it is a list, but it is probably correct

    to refer to it as a single program.)

    i can rewrite x E/y as an explicit loop:

       eval:{

        while[#y           / while there are items in the program list

         x:E[x;*y]         / let the stack be E of the stack and the first item of y

         y:1_ y]           / drop the top item from y

        x}                 / return the stack

    as you can see, the evaluation primitive E never gets to see

    anything but the top item of y.  my hunch is that if E were

    modified to take y, instead of *y, then the appropriate

    continuation primitives could be defined.

    i would be grateful if someone could show me why this dog

    won't hunt.

    >

    > -Billy

    >

    > ------------------------------------------------------------------------

    > Everyday Is Kid's Day

    > Dad Only Has One

    > Click Here To Make It Special

    > http://click.egroups.com/1/5038/6/_/_/_/960257046/

    > ------------------------------------------------------------------------

    >

    > To unsubscribe from this group, send an email to:

    > concatenative-unsubscribe@egroups.com

    >

    >

    >

    >

## wtanksley@bigfoot.com — 2000-06-08 20:03:12

    From: stevan apter [mailto:apter@...]

     >i haven't programmed in a language which supported first-class

    >continuations, so i have no feel for how one would use them.

    >despite having read several "continuations demystified" papers,

    >i'm still not sure i understand what's involved in having them

    >available.

     Put bluntly, continuations are like GOTOs on steroids, except that they're

    accounted for by theory.

    Come to think of it, the reason continuations traditionally need extra

    information is that continuation theory was developed for applicative

    languages.

     >the only half-way compelling example i've seen thus far (and i

    >didn't understand the solution) was this one:  suppose you've

    >got a tree t and a simple routine tw which walks the tree and

    >at each node prints the node name and the depth.  output might

    >be:

     There's an example of this in Forth at

    http://www.forth.org.ru/~mlg/ef94/ef94-2-paper.txt

    , in which the author discusses continuations in terms of backtracking.

    Backtracking is a special-purpose use for continuations.  There are other

    papers on the same site; some of them gave me interesting info, but others

    are in Russian, which I don't know.

    One interesting thing about this paper is that as in my hypothesis, the

    continuation is nothing but an address.  There's no need to store current

    values of parameters, because there are no parameters in a concatenative

    language.

    -Billy

## stevan apter — 2000-06-12 23:18:33

    a version of conk has been posted at www.kx.com/technical/contribs/stevan

    under the joy directory.

    a script containing two examples can be found there as well.

    to run conk, download k and the two scripts, and say:

        k conk

    at the prompt

        k>script load

    then say e.g.

        k>prog order

    a manual will follow shortly, along with examples.

    to escape from the prompt into k, an empty return.