hi all
this must be the week for implementing joy - here's another one.
http://www.nsl.com/papers/ck.htm <- doc
http://www.nsl.com/k/ck.k <- code
i've been thinking about this on and off for a couple of years.
ck is my second go at the problem.
in this version, i try to stay faithful to manfred's notational
decisions: [] for lists, / for division, 'x for characters, &c.
no sets, no arithmetic on characters or strings, and the i/o
options and interpreter controls are different.
ck is written entirely in k - about 275 lines of commented code,
most of which are one-liners for the numerous joy primitives.
for example, here is the integer version of the primrec combinator:
s3[{[s;i;b;r]:[i;E[_f[s,i;i-1;b;r];r];E[s;b]]}]
takes the stack s, an int i, programs b and r. if i is non-zero,
evaluate (E) r on the result of recursing (_f) with i decremented.
else evaluate b. of course, i'm always amazed when something like
this actually works.
of course the k list semantics (atomic extension) is built-in:
[1 2 3]+[4 5 6]
[5 7 9]
and all the k primitives are where they're supposed to be - namely,
on the ascii symbols. there are 20 x 2 of them, plus / for integer
division (which is not a k primitive).
the k adverbs (which are really combinators) are on keywords:
each, prior, right, left, over, do, while, converge, &c.
one thing i haven't implemented is joy-style definition. for
add2 == 2 +
ck has
[2 +] `add2 def
def is really assignment, which means that ck isn't purely
functional, but then neither is k.
another deviation, this time from concatenativity: function-maps
with named parameters (`abc is a k symbol - an atomic string).
{[`a`b`c] [a b +] [a c +] *}
which is syntactic sugar for:
[[`a`b`c] [a b +] [a c +] *] m
it seems like it shouldn't be too hard to take the pattern and body
of an m-list and produce a list which is computationally equivalent
to the m-list but which has no named parameters. i think brent
gives (or alludes to) an algorithm in his "theory" paper.
error-checking is minimal, but the stack is guaranteed to be
"safe": the primitives return only k objects, and the stack
is just a list of k objects. if execution fails, you just
signal back to the interpreter and continue on.
a ck application:
\ life in ck;
[[0 0 0 0 0]
[0 0 0 1 0]
[0 1 1 0 0]
[0 0 0 1 0]
[0 0 0 0 0]] `rpent set \ r pentomino;
[1 swap !] `l def \ left shift;
[-1 swap !] `r def \ right shift;
[[[[r] map r]
[[r] map l]
[[l] map r]
[[l] map l]
[[l] map ]
[[r] map ]
[r ]
[l] ] [i] right] `adj def \ adjacencies;
[dup adj
[+] over dup
3 = swap dup
2 = & |] `next def \ next generation;
[next dup " *" of sysout;] `go def \ next, output;
rpent 5 [go] do \ five generations;