cK is a Joy-style concatenative syntactic overlay for the K programming language.
The datatypes of cK are those of K.
In cK, symbols denote K verbs. As in K, a single symbol denotes a dyadic function (e.g. + is addition, x + y) while the compound glyph '+:' denotes a monadic function (in this case 'flip' or transposition, +x). Additionally, the compound glyph '+.' denotes the commute of the dyadic function (2 3 -. is 3-2).
The cK keywords fall into three classes: those which correspond to Joy operators and combinators, those which are used for the adverbs of K and miscellaneous K system functions, and those which denote operators new to cK.
cK notation is Joy notation, extended to include dictionaries and functions.
Differences:
K Joy Lists Eager Lazy Programs Lambdas Quotations Evaluation Application (.) Disquotation (i) Construction Atomic ({}) Concatenation (,) Arities 0, 1, 2, .. 1 Named Parameters Yes No Assignment/Reference Yes No Syntax Infix, Prefix Postfix Primitives Atomic + List Scalar Iterators Yes No Recursors No Yes
1 integer atom 10 -1 0N 0I 2 float atom 10. .2 10.3 4.376447e-005 0i 0n 3 character atom 'a 4 symbol atom `abc `"0* " 5 dictionary atom ([`a 10][`b 20][`c 30]) ([`d 40]) () 6 null atom N 7 function atom + #: 0 list [] [0] [[1]] [`a "bcd" 30.2] -1 integer vector* [1 2 3 4] [5] I -2 float vector* [1.1 2.2 3.3 4.4] [5.5] F -3 character vector* "abcdef" "g" "" C -4 symbol vector* [`a`b`c] [`d] S
cK does not implement Joy sets.
* except for non-atomic strings, cK does not implement K vector notation.
K verbs, both monadic and dyadic, are represented in cK by glyphs.
~ match ~: not ! rotate, mod !: enumerate @ at @: atom # take #: count $ cast $: format % divide %: reciprocal ^ power ^: shape & min, logical and &: where * multiply *: first _ cut, drop _: floor - subtract -: negate + add +: flip = equal =: group | max, logical or |: reverse , join ,: enlist . of .: value / integer divide* /: integer reciprocal** < less <: up > more >: down ? find ?: unique : right :: identity
cK redefines two more K symbols:
\ x comment \x quotation ; quiet, line separator
A third form v. denotes the commute of the dyadic function. For example, 2 3 -. is 3-2.
* / is over in K.
** /: is each-right in K
In cK, the K adverbs are denoted by reserved words:
' each / iterate, transit, do, while, converge \ Iterate, Transit, Do, While, Converge ': prior /: right \: left
K system functions are verbs of the form _xyz. In cK, we drop the initial underscore:
log exp abs sqr sqrt floor dot mul inv
sin cos tan asin acos atan sinh cosh tanh
ci ic
hash
draw
in lin bin binl
dv di dvl
sv vs
sm ss ssr
Joy primitives are implemented as keywords, as noted in the following list.
Some cK words behave differently than their Joy counterparts. For example, in cK 'name' takes a program and returns a list whose terminals are symbols. The structure of the list mirrors that of the program. A future version of this document will contain detailed specifications for each primitive.
N _n [] first null atom I !0 0 !: empty integer vector F 0#0. 0 0. # empty float vector C "" "" empty character vector (string) S 0#` 0 ` # empty symbol vector
acos asin cos cosh sin sinh atan tan tanh
abs dot floor inv log mul sqr sqrt
bd bytes <- data bin binary search: list atom binl binary search: list list ci char <- int db data <- bytes di delete index draw random draw dv delete value: list atom dvl delete value: list list ic int <- char in membership: atom list lin membership: list list sm string match ss string search ssr string search replace sv scalar <- vector (encode) vs vector <- scalar (decode)
inverse2 f?x inverse3 ?[f;x;y]
amend3 @[v;i;f] amend4 @[v;i;f;d] dmend3 .[v;i;f] dmend4 .[v;i;f;d]
body `program body -> list code [2 +] code -> "[2 +]" name [program] name -> `program
enclose [* +] enclose -> {* +}
disclose {* +} disclose -> [* +]
def a`name def -> name:a get `v get -> v set a`name def -> name:,a
ck execute cK string CK execute cK string in dictionary
hide `hide$ show `show$
converge p/a Converge p\a do n p do/a (Joy 'times') Do n p do\a each (p'). a iterate (p/). a Iterate (p\). a left a p\:b prior p': a right a p/:b transit i m/v Transit i m\v while b p/a While b p\a
dictionary ([`a 10][`b 20][`c 30]) -> [[`a 10][`b 20][`c 30]] dictionary let [[a]p] -> [[a]p] let pick 1 2 3 [[4 5 6][7 8 9 10 11]] [a[b[c d E]]] pick -> 1 2 3 [4 5 6] 7 8 [9 10 11] shuffle ... "a[b]c:[c]b[a]" shuffle
list c list: group top +/c elements by c ndup s -> s,s[n], <0 from the front, >-1 from the end npop s -> n _ s unlist n unlist: raze top n elements
displaywidth width and direction of display (default = -100) displaycount number of stack items displayed (default = 0I) evaluate 0 (Joy behavior) 1 (keep evaluating stack converges) help (not yet implemented) signal "message" signal -> '"signal: message" space emit size of stack in bytes stop : to continue time emit elapsed time (_T) trace N|width_direction trace trap 0 trap (default) or 1 trap (catch error signals)
async x 3:y connect 3:(host;port) disconnect 3:handle disconnected .m.c print print top of stack read0 0:x read1 1:x read2 2:x read6 6:x run "script.ck" run sync x 4:y sysin 0:` sysout `0:,: type 4:x write0 x 0:y write1 x 1:y write6 x 6:y
prototype *0#
false 0 true 1
equal ~
has {y _in x}
in _in
null 0=#x or x _in (0;0.)
small 2>#x or x _in (0;0.;1;1.)
at @ of @.
and &
div /
max !
min &
not ~:
or |
pred -1+
rem !
sign {(-x<0)+0<x}
succ 1+
case x [..[x y]..] -> y choice :[x;y;z] compare x<=y -> -1, x=y -> 0, x>=y -> 1 concat , cons (,x),y drop _. dup .. x -> .. x x dupd .. x y -> .. x x y enconcat .. x y z -> y,(,x),z first *: flatten ,/ id :: opcase y [..[x xs]..] -> [xs], x is the type of y popd .. x y -> .. y pop .. x -> .. popop .. x y -> .. rest 1_ reverse |: rollup -1!(x;y;z) rolldown 1!(x;y;z) rollupd @[(x;y;z;w);2 0 1 3] rolldownd @[(x;y;z;w);1 2 0 3] rotate @[(x;y;z);2 1 0] rotated @[(x;y;z;w);2 1 0 3] size #: swap @[(x;y);1 0] swapd @[(x;y;z);1 0 2] swoncat ,. swons (,y),x take #. transpose +: uncons (*x;1_ x) unit ,: unswons (1_ x;*x) zip +(x;y)
all app1 app11 app12 apply [..a..][..p..] -> ..r.. (apply each p to each a, leave each r) b binary binrec branch cleave cond condlinrec condnestrec construct dip dipd dipdd filter fold genrec i ifte infra linrec map nullary primrec some split step tailrec ternary times do treemap treemap2 treestep treerec treegenrec unary unary2 unary3 unary4 y x
newstack .. -> [] stack .. -> [..] unstack .. [--] -> --
callc callcc conts
Joy notation for lists is:
[] empty list [1] unit list (K integer vector) [1 2.2 3] list of three (not a K float vector)
Joy notation for characters and strings:
'a a single character scalar "a" unit string (K character vector) "abc" string of three
But cK and Joy treat characters and strings differently:
A joy string is a leaf (i.e., an atom), not a list:
"abc" leaf . true "abc" list . false
Yet it has a size (i.e. a count) and it can be taken apart using list operators such as 'first':
"abc" size . 3 "abc" first . 'a
In cK, a string is a list of characters.
"abc" first 'a'a'b'c 'a'b'c first 'a'b'c
A string is a list of characters. But cK also supports K symbols:
`a `b `c `a `b `c[`a`b`c] [`a `b `c]
cK supports notation for function-definition:
1 2 3 4 \{+ *}
1 2 3 4 {+ *}
i
1 20
{+ *} is a function-atom, not a list:
{+ *} @:
1
Functions are executed immediately:
2 3 4 {* +}
14
{..} should be thought of as a method for defining new primitives.
{..} is just notation. The underlying operations are:
[+ *] enclose
{+ *}
disclose
[+ *]
The disclose of a primitive is an atom:
[+] first disclose +
The disclose of a defined function is a list:
[{+}] disclose
[+]
The enclose of the empty list is the empty function:
[] enclose
{}
Semantically, it is identical to the identity function:
10 20 30 {}
10 20 30
Functions can be concatenated to form new functions:
[{* +}] first disclose [{- /}] first disclose concat enclose
{+ * - /}
or:
[concat [first disclose] map flatten enclose first] `fconcat def pop
[{+ *}] [{- /}] fconcat
{[+ * - /]}
Example:
2 3 4 5 [[{+ *} {- %}] {+ - %}]
2 3 4 5 [[{+ *} {- %}] {+ - %}]
[i] treemap
2 3 4 5 [[27 -3.0] -0.3333333]
cK also supports recursive dictionary formation:
([`x ([`a 10][`b 20])][`y 30 ([`z 40][`w 50])]) ([`x ([`a 10 N] [`b 20 N]) N] [`y 30 ([`z 40 N] [`w 50 N])])
Dictionary notation is pure syntactic sugar:
[[`a 10][`b 20]]dictionary ([`a 10 N][`b 20 N]) 10 20 30 [[`x`y`z] x y + z -]let 0
cK does not support true lambdas - functions with persistent, multiple, named parameters - but it does provide two mechanisms for mapping stack items to temporary names.
The 'let' combinator:
10 20 30 [[`x`y`z] x y + z -] let 0 10 [20 30 40] 50 [[`x [`a`b`c]`y]x y b c a + - * %] let -0.006666667
The first component of a let is a pattern-list. A pattern-list is a list, possibly nested, whose terminals are symbols. Necessarily, the list of symbols out of which the pattern-list is built contains no duplicates:
(,//pattern-list)~?,//pattern-list)
The rest of the list is a program in which elements of ,//pattern-list occur. Values are picked off the stack according to the structure implied by the pattern-list and substituted as literal values in the named positions of the program. For example, the let
[[`a [`b `c]] a b + a c + *] let
applied to the stack
... 2 [3 4]
maps 2 to a, 3 to b, and 4 to c. Following substitution, the program to be executed is:
[2 3 + 2 4 *]
Symbols which cannot occur in a pattern-list: those corresponding to cK constants:
`N `I `F `C `S `true `false
Since the atoms of a pattern-list must be symbols, ` may be elided:
[[a [b c]] a b + a c + *] let
No semi-globals, no K-style closures:
[[a b]a a b + [[s a] s a -] let] let
The 'a' in the embedded let is the sum of a and b in the embedding let.
Further examples can be found here. *
* Thanks to Nick Forde for the implementations of Ackerman's function.
A second name-method, stack-patterns can be used in conjunction with the shuffle operator 'shuffle'*:
10 20 30 "abc:cba" shuffle 30 20 10
Either side of a stack-pattern can be nested:
10 [20 30] 40 "a[bc]d:b[da]c" shuffle 20 [40 10] 30
An upper-case letter can be used to match the rest of a list:
[1 2 3][4 5 6][7 8 9]"[aA][bB][cC]:[A][B][C]abc" shuffle [2 3] [5 6] [8 9] 1 4 7
* Thanks to William Tanksley, who suggested inclusion of simple (i.e. non-nested) stack-patterns.
cK input consists of a sequence of verbs:
7 3 +
is the sequence "push 7, push 3, add".
The stack is a list whose members are values:
7 3 [+] first
pushes 7, 3, the list (or quotation) [+], and then takes the first element of the list and pushes that onto the stack. So the stack is
7 3 +
whose members are 7, 3, and addition.
For non-functions x, 'x' is a verb which pushes x onto the stack. But the only way we can push a function f onto the stack is by pushing its quotation [f] onto the stack, and then disquoting it.
Clearly, cK contains first-class function atoms, as the following argument shows:
[+] first dup + + ~ 1
Match (~) takes two pieces of data x and y and returns 1 if they match. Hence + + must be two pieces of data. Neither one is a list, so they must be atoms. They're not integers, floats, characters, or symbols, so they must be functions. So cK has first-class function atoms. We just don't have a direct way to push them onto the stack.
Now consider
2 3 [+] first 2 3 +
2 is pushed on the stack, then 3, then the quotation [+]. The interpreter then finds the operator 'first' and applies it, leaving the unquoted primitive + on the stack.
Some Joy programmers have expressed discomfort with this behavior. It would appear that something like the following principle is assumed: if the stack S is .. x .., then it should be possible to create S by a sequence of pushes only.
Alternatively, we can prevent an unquoted primitive from ever appearing on the stack by implementing the following behavior: keep evaluating the stack, item-at-a-time, until we get the same result twice-in-a-row.
In cK, the default behavior matches Joy. But we can turn on the self-pushing behavior:
N evaluate 0 1 evaluate [2 3 +] unstack 5
Running under the alternate evaluation regime can result in some spectacular chain-reactions, e.g.:
1 evaluate -30 trace [[2 3 + pop] unstack] unstack [[2 3 + pop] unstack] [[2 3 + pop] unstack] unstack [2 3 + pop] [2 3 + pop] unstack 2 2 3 2 3 + 5 5 pop
Billy Tanksley has persuaded me that it makes sense to add a unary quotation operator:
2 3 \+ 2 3 +
The escape symbol "\" has been extended: \xyz is a comment if x is blank, else \xyz pushes xyz on the stack.
In Joy, a combinator like 'map' takes one or more programs as arguments. Programs are required to be lists:
[[10][10 20][30 40 50]][size] map . [1 2 3]
In cK, 'map' will accept any of the following:
[[10][10 20][30 40 50]] [size] map \ list
[1 2 3]
[[10][10 20][30 40 50]] \{size} map \ function
[1 2 3]
[[10][10 20][30 40 50]] \size map \ primitive
[1 2 3]
Quotation inside a list is redundant, since lists are quotations:
[2 3 \+] [2 3 +]
The quotation mark "\" is purely syntactic, and has an effect only at the top level of the input queue.
Stack underflow cannot occur in cK. If the stack is too short for the execution of a pending primitive, a function is constructed on the fly consisting of the stack concatenated to the primitive, enclosed, and the defined program becomes the new stack. For example,
2 +
{2 +}
This can be useful:
2 + 3 swap i 5
If the underflow occurs in the course of evaluating a constructed program, the primitive is projected and the resulting partially-evaluated program becomes the new stack:
[2 + *] `add2mul def;
newstack
3 add2mul
{5 *}
4 swap i
20
To define a program in Joy:
add2 == 2 +
To define the same program in cK:
[2 +] `add2 def
And then:
3 add2 `add2 5 [add2] name `add2 5 `add2 get `add2 5[2 +]
The 'set' operation adds a further level of enclosure to the object:
[3 +]`add3 set `add3 7 add3 `add3 7[3 +] i `add3 10
Represent a list as a string of cK code:
[2 +] code "[2 +]"
Execute a string of cK code:
3 "2 +" ck 5
Execute cK in a dictionary:
([`aa 10][`bb 20]) `dd def; `dd "aa bb +" CK 30
Execute a string of K code:
"!3" .: [0 1 2]
Execute K in a dictionary:
([`aa 10][`bb 20]) `dd def; `dd "aa+bb" . 30
Limited K GUI (Windows only, no functional attributes):
1000000 2 draw [-1 1] of 2 [[+] Iterate] do `crw def; `chart `crw..c def; `crw show; `crw hide;
Limited file operations:
d:\ck>k ck K 2.95t 2002-10-09 Copyright (C) 1993-2002 Kx Systems \ for k, \\ to exit, .ck.i() for cK [1 2 3]"d:/123" def "d:/123" \\d:\ck>k ck K 2.95t 2002-10-09 Copyright (C) 1993-2002 Kx Systems\ for k, \\ to exit, .ck.i() for cK "d:/123" get [1 2 3]
Default file extension is ".cl".
0: 1: 2: 6: are read0, write0, read1, write1, read2, read6, write6.
Asynchronous messages:
[`host`port] [2 3 + print] async \ prints 5 at `host port console
Synchronous messagse:
[`host port] [2 3 +] sync 5 * 25
Connect:
[`host port] connect 12
Disconnect:
12 disconnect
Disconnected:
"stop" disconnected \ _w is on the stack
Joy has sets, but K, and hence cK, does not. But we can simulate them: for any list L, L ?:, the unique elements of L, is a cK-set. A demonstration script of elementary cK-set operations shows how we can recover basic functionality.
32 !: `U set; [U swap dvl] `complement def; [, ?:] `union def; [dup rotate lin &: at] `intersect def;[1 2 3] complement [0 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31] [1 2 3 4 5 0] intersect [4 5 0] [4 5 6 7 8] union [4 5 0 6 7 8]
By default, the universe is 0 through 31 (to match Joy), but it can be set to a list of arbitrary (but unique) elements.
To operate, download and install both K and the script for cK, and from within a command shell say 'k ck':
d:\ck>k ck K 2.95t 2003-02-20 Copyright (C) 1993-2003 Kx Systems\ for k, \\ to exit, .ck.i() for cK
The cK interpreter prompts with two spaces.
10 20 30 [`a "bcd" 'x 20.3] 4444 -0.006666667 10 20 30[`a "bcd" 'x 20.3]4444
Default display settings:
N displaywidth -100 N displaycount 0I N trace 0
Stack too large to display:
1000 !: .. 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999]
Setting < 0 places the top of the stack at the right, setting > 0 reverses the stack orientation.
Printing elements of the stack on separate lines of the display:
[1 2] 3 [4 5 6 7] stack dup [print] map unstack; [1 2] 3 [4 5 6 7]
Monitor time/space:
.. time .. .. t:x.y [in seconds] .... space .. .. s:x [stack-size in bytes] ..
Trace computation:
-30 trace
100 !: 10 20 30 40 +-*
100
100 !:
.. 90 91 92 93 94 95 96 97 98 99] 10
.. 91 92 93 94 95 96 97 98 99] 10 20
.. 92 93 94 95 96 97 98 99] 10 20 30
.. 93 94 95 96 97 98 99] 10 20 30 40
.. 94 95 96 97 98 99] 10 20 30 40 +
.. 93 94 95 96 97 98 99] 10 20 70 -
.. 2 93 94 95 96 97 98 99] 10 -50 *
.. 8 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99] -500
Temporarily suppress stack display by appending a semicolon to the input:
2 3 + 5 3 4 +; 4 5 6 + 5 7 4 11
A semicolon alone is equivalent to 'newstack' (and much more convenient when interacting with cK):
10 20 30
10 20 30
;
Permanent suppression:
0 displaycount 2 3 + 4 5 * 0I displaycount 5 9
Start cK and load .ck scripts sequentially:
d:\ck>k ck test1 test2 test3
Escape cK to K:
\
2+3
5
Call cK from K:
.ck.x"10 20 30 +" \ return stack
10 50
Arithmetic and comparison operators are not defined for character data. For the Joy
'a 1 +
use
'a ic 1 + ci
Single-line comment begins at \:
2 3 + 4 - \ this is ignored 1
cK names are dotted K names, but unlike K, underscore cannot occur in a name:
10 `number_ten set type error
cK scripts are text files with default extension .ck.
The line separator is ';':
[this is a program] `myprog def;
Escape script evaluation with a double backslash:
\\ anything can go below
Apart from K errors, there is only one run-time cK error:
[2 +] `dup def reserved word error
cK words cannot be redefined.
There is one parse-time error:
[2 3]] syntax error: unbalanced []s
An error can be signalled:
"uh oh" signal signal: uh oh
Programmed stop:
2 3 4 [+ stop -] i
program stopped -- s = stack, : to resume
{[s]pstop[];s}
^
> s
2 7
> :
:
-5
By default, an error interrupts the interpreter:
"a" 2 +
type error
{:[-3=4:y;{x[y]}/[x;y];x . y]}
^
> x
+
> y
("a";2)
> / we're in k at this point
> \
2 3 +
5
Use 'trap' to prevent interrupts:
1 trap "a" 2 + type error 3 4 + 7
cK should match K.
1000000 100 draw dup <: at; time; t:3.255209e-006
Expressions which evaluate to K compositions in verb position are fed to adverbs as K expressions:
1 1000000 [1-] do -> 1000000 {-[x;1]}/1 \ optimized: note reversed order
... 1000000 [*+] do -> 1000000 E[;...]/s \ not optimized
cK consists of ~ 400 lines of K.
The basic process steps in the interpreter are:
p:.ck.p i / takes a string of cK and returns a parse tree s:.ck.e p / takes a parse tree, evaluates it, and returns a stack d:.ck.d s / takes a stack and returns a string of cK
Here is an example:
i:"[1 2 3]reverse first !:"
p:.ck.p i
s:.ck.e p
d:.ck.d s
p
(1 2 3
{:[z~0;x;z~1;.$x;7=4:y;y z;E[z;y]]}[`"|:";{((-x)_ z),,dot[y;(-x)#z]}[1][|:]]
{:[z~0;x;z~1;.$x;7=4:y;y z;E[z;y]]}[`"*:";{((-x)_ z),,dot[y;(-x)#z]}[1][*:]]
{:[z~0;x;z~1;.$x;7=4:y;y z;E[z;y]]}[`"!:";{((-x)_ z),,dot[y;(-x)#z]}[1][!:]])
s
,0 1 2
d
"[0 1 2]"
p is a list whose first element is the vector 1 2 3, and whose second, third, and fourth elements are the primitives reverse, first, and !:.
The cK parser consists of two components: string -> tokens and tokens -> types.
Tokenization takes a string and returns a list, possibly nested, of tokens:
token"[2 3][-: [1+]] [i] right"
((,"2"
,"3")
("-:"
(,"1"
,"+"))
,,"i"
"right")
A representation of a list of items is tokenized as a list of item-representations, e.g. "[2 3]" is tokenized as (token"2";token"3").
Typing takes a token-list and recursively replaces tokens with corresponding types. For example:
:t:type token"[2 3][-: [1+]] [i] right"
(2 3
({:[z~0;x;z~1;y 1;z~2;y 0;~7=4:y;E[z;y];y z]}[`"-:";{:[@z;(x;y)z;x>#z;pro[y;z];{y,,dot[x;z]}[y]. cut[x;z]]}[1][-:]]
(1;{:[z~0;x;z~1;y 1;z~2;y 0;~7=4:y;E[z;y];y z]}[`"+";{:[@z;(x;y)z;x>#z;pro[y;z];{y,,dot[x;z]}[y]. cut[x;z]]}[2][+]]))
,{:[z~0;x;z~1;y 1;z~2;y 0;~7=4:y;E[z;y];y z]}[`i;{:[@z;(-x+1;y)z;x>#z;pro[y;z];{dot[x[y];z]}[y]. cut[x;z]]}[1][{[s;p]E[s;p]}]]
{:[z~0;x;z~1;y 1;z~2;y 0;~7=4:y;E[z;y];y z]}[`right;{:[@z;(x;y)z;x>#z;pro[y;z];{y,,dot[x;z]}[y]. cut[x;z]]}[3][{:[_n~p:p2 z;{F[(y;z);x]}[z;x]'y;x p/:y]}]])
In this example, the list t contains four components. t 0 is the vector (list) 2 3. t 1 is a list of the two cK functions -: and [1+]. t 2 is a one element list of the i function, and t 3 is the right function. Schematically:
(2 3;(-: (1;+));(i);right)
cK functions, whether K verbs or Joy words, are projections of the triadic cK function o. This function is the heart of cK evaluation, so let's get to know it.
o has three arguments.
The first argument x is always a symbol of the function it will compute. For example, `"+" or `first.
The second argument y is either a function or a list. If it is a function, then it is the projection of one of the cK wrapper functions. If it is a list, then it is a cK program it will evaluate by calling E.
The third argument z is either a stack or an atom. This corresponds to the two ways o can be called. If z is a stack, then it will compute a new stack. If z is an atom then it is either 0, 1, or 2. If z is 0, o will return its name, for example `"+". If z is 1, o will return the function it has been set up to compute, for example +. If z is 2, o will return its valence.
A cK wrapper function w is also triadic, with arguments x, y, and z.
x is the valence of the function of the function w will compute. For example, the valence of + is 2.
y is the actual function w will compute. For example, {_ x%y}.
z is either a stack or 0 or 1 (see above).
The job of a wrapper function is to take a stack, use the valence x to chop the stack into pieces, apply the function y to those pieces, and finally assemble the result into a new stack, which it then returns to o.
The parser is therefore the function:
p:type token@
The parse of a cK code-string is a list all of whose functional atoms are projections of o.
Evaluation is a dyadic function:
{C::(,y),C;r:x a/y;C::1_ C;r}
x is a stack and y is a parse-tree to be evaluated. y is prepended to the list of continuations C. Elements of y are peeled off and applied to the stack to deliver a new stack. After y has been evaluated, the empty list of its continuation is dropped from C.
The 'a' function - the heart of the cK evaluator - is:
a:{t[x;z];C[0]::1_*C;:[y&7=4:z;b/n z x;x,,z]}
The stack x and the element z to be evaluated are passed to t, the trace function. The current continuation is truncated. Then, if z is a function and it's not quoted, we apply it to x and pass the result to n:
n:{:[#x;(),x;()]
If x is non-null, make it a list, else make it () (instead of e.g. !0). Else, if y is not a function, append it to the stack.
The 'b' function
b:{:[N;()a[;1]/x;x]}
checks to see if N, the flag for self-evaluation, is on; if it is, the stack is repeatedly evaluated, one element at a time; if not, the stack is returned unaltered.
Otherwise, if z is not a function, or if z is quoted, it is appended to the stack.
Use 'conts' at any point to push the continuations C at that point onto the stack:
-30 trace
[2 3 conts pop +] i
[2 3 conts pop +]
[2 3 conts pop +] i
2
2 3
2 3 conts
2 3 [[pop +] []] pop
2 3 +
5
Use 'callcc' to place the current continuation on the stack, followed by evaluation of a program:
[2 3 [print] callcc 4 5] i + * [4 5] 2 27
Use 'callc' to place all continuations on the stack, followed by evaluation of a program:
[2 3 [print] callc + 4 5] i + * [[+ 4 5] [+ *]] 45
Both the stack and the input queue are lists whose atoms are K objects. The cK representation of integers, floats, non-atomic strings, and symbols is indistinguishable from K's native representation -- 5:x. But lists and vectors use brackets and dispense with the ";" separator, atomic characters use "'", dictionaries use parentheses, and functions require special processing.
\ cellular automata in ck; [8 2 # swap vs |:] `rule def \ 90 rule; [dup 2 * &: 1 , !] `start def \ 3 start -> 1 1 1 0 1 1 1; [2 [0 , |:] do] `sheet def \ sheet; [dup [*: [|: *:]] [i] right , -1 !.] `cyl def \ cylinder; [swap 2 list |:] `rpair def \ a b -> [b a]; [swap dup #: !: [rpair] dip [gen] right] `ca def \ 15 start 90 rule ca; [_ 3 #. 2 swap sv @] `cell def \ x y z -> n; [[1 unlist] dip swap sheet cell] `gen def \ can substitute cyl for sheet; [stack flatten " *" of sysout;] `disp def \ display; 30 start 25 [90 rule ca] Do disp \ 30 wide, 25 gens, rule 90;d:\ck>k ck sw K 2.95t 2003-04-03 Copyright (C) 1993-2003 Kx Systems \ for k, \\ to exit, .ck.i() for cK * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
Slightly different code using the Joy words for K verbs:
[8 2 # swap vs reverse] `rule def \ 90 rule; [dup 2 * &: 1 concat !] `start def \ 3 start -> 1 1 1 0 1 1 1; [2 [0 concat reverse] do] `sheet def \ could use a cylinder instead; [swap 2 list reverse] `rpair def \ a b -> [b a]; [swap dup size !: [rpair] dip [gen] right] `ca def \ 15 start 90 rule ca; [swap drop 3 swap # 2 swap sv at] `cell def \ x y z -> n; [[1 unlist] dip swap sheet cell] `gen def \ can substitute cyl for sheet; [stack flatten " *" of sysout;] `disp def \ display; 30 start 25 [90 rule ca] Do disp \ 30 wide, 25 gens, rule 90;
\ life in ck; [2 [0 , +:] do] `edge def \ glue 0 to top, left; [[|:] map |:] `mirror def \ t -> b, l -> r; [2 [edge mirror] do] `pad def \ pad around matrix; [[1 0 0] [1 1 1] [0 1 0]] `rpent set \ r pentomino; [1 !.] `l def \ left shift; [-1 !.] `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 [+] iterate dup 3 = [2 = &] dip |] `next def \ next generation; [next dup " *" of sysout;] `life def \ next, output; [[sysin C ~] [life] while] `go def \ continue until input; rpent 10 [pad] do go;
The 'go' function loops while, at each iteration, there is no input. That is, 'life' is executed and leaves the next generation on the stack. Then cK waits for input from the console. If the user presses Return, the empty string C is returned. If C matches the result, 'life' is executed again. And so forth, until the user types something into the console.
d:\ck>k ck life
K 2.95t 2003-02-20 Copyright (C) 1993-2003 Kx Systems
\ for k, \\ to exit, .ck.i() for cK
rpent 5 [pad] do 5 [life] do \ pad 5, five generations
*
* *
***
*
** *
* *
*
**
** *
** *
*
***
*
* *
**
*
**
* *
* *
**
**
***
* *
** *
**
Wolfram's "snowflake" automaton defined on a hexagonal lattice (see Coxe and Reiter's paper in Vector for an implementation in J, and here for a K implementation) is implemented in cK by adjusting the transition function 'next':
[2 [0 , +:] do] `edge def \ glue 0 to top, left; [[|:] map |:] `mirror def \ t -> b, l -> r; [2 [edge mirror] do] `pad def \ pad around matrix; [[[1]]] `flake def \ simple snowflake; [1 !.] `l def \ left shift; [-1 !.] `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 4 !: swap [*] swap mods [id id ~: ~:] [i] right amend4] `alt def \ hexagonal neighbors; [^: 1 @ !: 2 !] `mods def \ 0 1 0 ..; [dup adj alt [+] iterate 1 = |] `next def \ next generation; [dup #: [0 0 1 1] # swap unit cons [!] each] `shift def \ shift pairs of rows; [2 [[,: 2 #.] map flatten +:] do] `double def \ double rows and cols; [next dup double shift " *" of sysout;] `hex def \ next, output; [[sysin C ~] [hex] while] `go def \ continue until input; flake 3 [pad] do go;
** **
** **
****
****
**********
**********
****
****
** **
** **
t.k is a set of single-table operations. Recoded in cK:
[[@:] [draw] [dup [#: draw] dip of] ifte] `field def \ generate random field;
[[field] right 2 list +: .:] `table def \ generate random table;
[[[t i] t N [i @] amend3] let] `rows def \ table[;rows];
[[[t f g] N f [:] t g @ amend4] let] `cols def \ table[cols;];
[[[t f o] N o t f @ 3 list [xyzx] iterate] let] `where def \ where clause;
[[[x y z] z x @ y i x @.] let] `xyzx def \ selection/order by;
[where] `order def \ order and where are the same;
[>:] `desc def \ grade down;
[<:] `asc def \ grade up;
[[[d] d d [?:] map] let
[[d u] u [u d] [[?] right] each] let
[[u k] u [#:] map k sv] let
[[j] j ?: #: j] let
[[c u] [c u]] let] `index def \ [..[vector]..] index;
[[[t k f o]
k [o f] [[name $:] dip $: , `$.] each ,
t k f o t k @ index aggr
, 2 list +: .:] let] `group def \ group by;
[[[t k f o i] [k last][+: +:]infra [t i xeq] each
[f o] [t i xeq] each] let] `aggr def \ aggregate;
[[[f o t i]t f @ i uncons first o] let] `xeq def \ execute aggregation function;
[[[d n i] n &: i [+] 1 amend4] let] `count def;
[[[d n i] n d prototype # i [+] d amend4] let] `sum def;
[[[d n i] n d prototype # i [:] d amend4] let] `last def;
[[[d n i] d n i sum d n i count %] let] `avg def;
[[[d n i] n [] ,: # i [,] d amend4] let] `part def;
[[[t d] t N [,] d amend4] let] `insert def \ table records insert -> table;
[[[t f i d] t [f i] [:] dmend4] let] `update def \ table fields rows records update -> table;
[[[t i] t N [i di] amend3] let] `delete def \ table rows delete -> table;
[`F`G`H`I`J] 1000000 [[`a`b`c`d`e] 7 0 0 0] table `T def show time;
T [`G`F] [[desc] [asc]] order T swap rows `V def show time;
T [`F`G] [[[`a`b] lin &:] [5 = &:]] where T swap rows `U def show time;
T [`F`G] [`H`H`H`I] [count sum avg sum] group `W def show time;
Timing (five fields, a million records):
d:\ck>k ck t K 2.95t 2003-02-20 Copyright (C) 1993-2003 Kx Systems \ for k, \\ to exit, .ck.i() for cK t:0.1085069 t:0.253183 t:0.07233793 t:0.1085069
Lambdas are used both to reduce stack-noise and to document incoming elements. Compare 'index' above to the pure concatenative coding:
[dup [?:] map dup rotate 2 list [[?] right] each swap [#:] map swap sv dup ?: #: swap 2 list];
And the original K version of the algorithm:
{[d](#?i;i:(#:'u)_sv(u:?:'d)?/:'d)}
Screenshots of T, U, V, and W:
From Raul Miller, on the K listbox:
{[M]M|{|/M&x}'[M]}/
Conversion to cK (also from the listbox):
-> {[M]M|M{|/x&y}/:M}/
-> {[M]M|M(|/&)/:M}/
That's about as far as we can take lambda-elimination in K, but in cK we can go all the way:
[[dup dup [& [|] iterate] right |] converge] `tc def; [3 3] [0 0 0 1] # tc [[0 0 0] [1 0 0] [1 1 0]]
The program 'tc' finds M on the stack. tc converges the program [p] = [dup dup [& [|] iterate] right |] on M. p duplicates M twice, so we have M M M on the stack. Then it does an each-right of the program [q] = [& [|] iterate] on the top two items M M, and or's that with the third item M. Each invocation of q gets M and a row of M, on which it does an &, leaving a matrix result, on which the program [|] is iterated, leaving a vector.
See Manfred von Thun's paper on queue machines, and this K implementation of both his algorithm and one which performs parallel evaluation of a queue. The parallel algorithm depends on the fact that in K f[a] is either the result of applying f to a if f is monadic, or the projection of f on a if the valence of f is greater than 1. Here is an implementation in cK:
\ parallel queue machine; [dup [q.o] map &: _. [q.p] map flatten] `q.q def; [dup 1 _. reverse swap *: infra reverse] `q.p def; [|: *: type 7 =] `q.o def; [[q.q] Converge] `queue def;
The analogue of a projection in cK is a list of size <= n whose last element is an operator of valence n. For example, the following are "projections" of a function f of valence 3*:
[1 f] [1 2 f]
Since cK treats a short stack as an opportunity to project, the 'infra' combinator can be used to produce the analogue of the K behavior described above:
10 20 30 unit [+] infra i 10 20 [30 +]
Examples:
[+ 1 * 2 - 3 4] queue [+ 1 * 2 - 3 4] [[1 +] [2 *] 1] [[1 +] 2] [3] [][* 5 + 6 % 7 8] queue [* 5 + 6 % 7 8] [[5 *] [6 +] 1.142857] [[5 *] 7.142857] [35.71429] []
* The definition of a projection in cK has been amended since this section was written: the analogue of a projection in cK is a function constructed on-the-fly by concatenating the stack with the primitive and enclosing the whole. The result is pushed onto the stack. The examples above should be changed to:
[+ 1 * 2 - 3 4] queue [[+ 1 * 2 - 3 4]] [[{1 +} {2 *} 1]] [[{1 +} 2]] [[3]] [[]][* 5 + 6 % 7 8] queue [[* 5 + 6 % 7 8]] [[{5 *} {6 +} 1.142857]] [[{5 *} 7.142857]] [[35.71429]] [[]]
Here is an implementation of the truth-table proof method by the author of Joy which uses sets. We'll use a different approach: for a formula F in n propositional letters P, Q, .., we define each letter to be a variable whose value is the reference column in the elementary truth-table for F, represented as a vector of 0's and 1's. For example, the formula "P Q and" contains two letters P and Q, so the variable P is 0 0 1 1 and the variable Q is 0 1 0 1. Once the variables have been defined, we execute the formula, relying on the fact that the truth-functional operators 'not, 'and', 'or', 'imp' and 'iff' are defined for arrays of any rank:
First, the K solution:
propositions:{@[_d;`$'x;:;2_vs!_2^#x];}
modality:{:[&/x;`tautology;&/~x;`contradiction;`contingent]}
letters:{?x@&x _lin"ABCDEFGHIJKLMNOPQRSTUVXYZ"}
prove:{propositions letters x;modality@. x}
The corresponding cK solution:
[dup #: 2 ^. _: !: 2 swap vs swap [` $.] map unit cons [set] each] `propositions def; [dup "ABCDEFGHIJKLMNOPQRSTUVXYZ" lin &: @ ?:] `letters def; [dup letters propositions pop ck modality] `prove def; [*: [&] iterate] `tautology def; [~: tautology] `contradiction def; [[[[tautology] [pop `tautology]] [[contradiction] [pop `contradiction]] [pop `contingent]] cond] `modality def; [> ~:] `imp def; [[imp] [swap imp] cleave and popd] `iff def;
The main entry point is 'prove'. 'letters' extracts the propositional letters from the formula. 'propositions' takes a list of letters (e.g. "PQR") and for each letter creates a variable whose value is the appropriate reference column in the truth-table for P, Q, R. 'ck' is a primitive cK function which takes a string of cK code and executes it.
A proof of (P & (P -> Q)) -> Q:
"P P Q imp and Q imp" prove `tautology"PQ" propositions [`P `Q] pop -30 trace P P Q imp and Q imp P [0 0 1 1] [0 0 1 1] P [0 0 1 1] [0 0 1 1] [0 0 1 1] [0 0 1 1] Q [0 0 1 1] [0 0 1 1] [0 1 0 1] [0 0 1 1] [0 0 1 1] [0 1 0 1] imp [0 0 1 1] [0 0 1 1] [0 1 0 1] > [0 0 1 1] [0 0 1 0] ~: [0 0 1 1] [1 1 0 1] and [0 0 0 1] Q [0 0 0 1] [0 1 0 1] [0 0 0 1] [0 1 0 1] imp [0 0 0 1] [0 1 0 1] > [0 0 0 0] ~: [1 1 1 1]
The K function
wrap:{(b -1_(-1+b _binl x+b:0,1+&" "=y)\0)_ y,:" "}
takes an integer x denoting maximum width and a string y and wraps the words in y into phrases of length <= x. For example,
wrap[20;"this is a string consisting of words separated by blanks"]
("this is a string "
"consisting of "
"words separated by "
"blanks ")
here's how it works:
y:"this has blanks in it" x:10
wrap[x;y]
("this has "
"blanks "
"in it ")
append a blank:
y,:" " y "this has blanks in it "
indices of positions just following the blanks (pretend y 0 follows a blank):
b:0,1+&" "=y b 0 5 9 16 19 22
add maximum-substring-width:
x+b 10 15 19 26 29 32
"bucketize" each of those: e.g. 10 occurs in bucket b[3] (9 < 10 <= 16):
b _binl x+b 3 3 4 6 6 6
subtract 1:
-1+b _binl x+b 2 2 3 5 5 5
chase pointers (scan): 0 -> 2, 2 -> 3, 3 -> 5
(-1+b _binl x+b)\0 0 2 3 5
drop off the last:
-1_(-1+b _binl x+b)\0 0 2 3
index out the corresponding b-positions (1+where the blanks are in y):
b -1_(-1+b _binl x+b)\0 0 9 16
cut the string into substrings at those positions:
(b -1_(-1+b _binl x+b)\0)_ y
("this has "
"blanks "
"in it ")
Translating into cK we have:
[[" " , dup] dip swap " " = &: 1 + 0 ,. dup [+] dip swap [dup] dip binl -1 + 0 swap Converge -1 _. @ _.] `wrap def;"this is a string consisting of words separated by blanks" 20 wrap sysout this is a string consisting of words separated by blanks
Using "shuffle notation" to make the stack-transitions explicit, and eliminating "stack noise", we have:
[ "yx:yxy" shuffle " " , " " = &: 1 + 0 ,. "yxb:ybbxb" shuffle + binl -1 + 0 "ybz:yzb" shuffle Converge -1 _. @ _. ] `wrap def;
Paul Graham's Accumulator Generator problem.
Martin Young found an elegant Joy solution to the "accumulator" part of the problem, slightly modified and implemented in cK as follows:
[[+ acc] cons] `acc def; newstack 3 acc [3 + acc] 4 swap i [7 + acc] 2 swap i [9 + acc]
The "generator" part of the problem is now trivial:
[[acc] *:] `gen def; gen acc 3 swap i [3 + acc] gen [3 + acc] acc 4 swap i [3 + acc] [4 + acc]
'gen' leaves an instance of 'acc' on the stack. Each instance accumulates independently.
Shuffle takes a stack-pattern "from:to" and transforms the (-#?,/from)#stack from the pattern described by 'from' to the pattern described by 'to'.
Coding in K for maximum legibility:
shuffle:{[s;f;t] unpattern[t;dictionary pattern[f;s]]} pattern: {[f;s] :[atomic f ;enlist(symbolize f;s) ;raze f pattern's]} unpattern:{[t;d] :[atomic t ;d symbolize t ;t unpattern'd]} dictionary:.: atomic:@: symbolize:`$ raze:,/ enlist:,:shuffle[10 20 30;"abc";"cbabc"] 30 20 10 20 30shuffle[(10;20 30;40 50);("a";"bc";"d");("c";"da";"b")] (30 (40 50 10) 20)
cK/Joy contains a large number of operators each of which has a single, narrowly-defined effect on the top of the stack; e.g. pop, dup, swap; variants popop, dupd, swapd; rollup/down, rotate, cons, concat, and their variants; &c. Is there a way to replace this profusion of operators with a smaller, orthogonal set of operators? Better yet, can't we simply eliminate them, and use (a possibly enhanced version of) shuffle notation to achieve the same effects?
See the paper on Function Arrays.
The execution regime used in the current implementation is (simplified):
e:{x a/y}
a:{:[7=4:y;y x;x,,y]}
x being the result stack and y the program list to evaluate. e is called recursively, e.g. the 'i' combinator is:
i:{e[x;y]}
Alternatively, we could use two stacks:
e:{*{#x 1}{a . x}/(x;y)}
a:{i:*y;y:1_ y;t[x;i];:[7=4:i;@[i[x;y];0;n];(x,,i;y)]}
where, if the next element on the program list is a function, it receives two arguments: the stack so far and the program-list yet to be evaluated (the current continuation).