# cK, XY, X: implementation notes

## stevan apter — 2004-12-06 22:23:38

    cK, XY, and X provide for variable-free programming in a language

    with K semantics.  each language is implemented as a pure interpreter

    in K.

    cK implements combinators as recursive calls to eval.  this approach

    is by far the easiest to implement, and gives K-level performance.

    XY implements combinators as prepends to the input queue.  for

    example, the 'i' combinator takes a quotation (list) and prepends

    it to the queue.  so, for example,

        2 3 [4 +] i

    prepends [4 +] to the queue.  on subsequent calls to 'eval', 4 is

    pushed, then + is evaluated.

    this approach has a relatively straightforward implementation, but

    is *very* slow.  ("how slow is it?"  [insert favorite slow joke])

    to understand the approach i've taken in X, you need to know four

    facts about K:

        1. a function such as {[a;b;c]a+b*c} takes three arguments

           a, b, c.  it multiplies b and c, and then adds the result

           to a.  the *valence* of a function f is the number of

           arguments f takes.

        2. if f has valence n>1, then f[x] is a function with valence

           n-1.  f is projected, or "curried" on x.  in particular,

           f[x;y;z] = f[x][y][z].

        3. there is a small, fixed set of functions, called "adverbs."

           an adverb takes a function of valence n and returns a function

           of valence n.  different adverbs transform their functional

           arguments in different ways.  For example, ' (each) takes a

           function f of valence n and returns a function which applies

           f to corresponding elements of n equal-length lists.  for

           example,

                {x+y*z}'[1 2 3;4 5 6;7 8 9]

           applies {x+y*z} to 1 4 7, then to 2 5 8, then to 3 6 9.  the

           result is a list of three results.

        4. all K functions return exactly one result, although that

           result may be a list of arbitrary complexity.

    my approach to both K adverbs and combinators in X is to implement

    them as functions of quotations.  An adverb converts its quotation

    argument to a K function, projects it over successive items on the

    stack, and, eventually, pushes its result onto the stack.  A combinator

    converts its quotation argument into a *list* of functions, projects

    that list over successive items on the stack, and, eventually,

    pushes *multiple results* onto the stack.

    like XY, X is "stackless" (it doesn't use the C stack, or call

    'eval' recursively), but unlike XY, it doesn't explicitly access

    the input queue.  like cK, X has K-level performance.

    X contains all the K primitives, including the six adverbs for

    fast vector manipulation.  X has three fundamental combinators,

    namely 'i' (spelled "i:" in X), 'dip', and 'i.', which is similar

    to Joy's infra.

    as time permits, i'll complete the language summary (currently a

    shambles), write a short reference manual, and work up a few examples

    to stress test performance.

    meanwhile, the code may be viewed (and even run!) at:

        http://www.nsl.com/k/x/x.k

    a few X definitions are here:

        http://www.nsl.com/k/x/x.x

    in all, the exercise has been instructive, and immensely enjoyable.

    members of the concatenative chatroom have been very helpful

    (especially dan) in the course of this little project.