SLACK is a compiler for a lazy functional K, modelled on David Turner's SASL language, the precursor of Haskell and Miranda.
SLACK ("Steve's LAzy-Combinator K") is a compiler for a lazy functional K, modelled on David Turner's SASL language, the precursor of Miranda and Haskell.
In the course of this project, my guide and constant companion has been Torsten Grust's The Construction of an SASL Compiler, a beautifully written introduction to the subject intended for second-year students in computer science.
Another useful site for SASL is Dan Piponi's elegant C implementation here.
Finally, there are the Dyalog APL implementations of the functional languages Min and Max by the eponymous Dynamic Functionista.
In what follows, I will describe the SLACK language, noting how it differs from SASL and K, and explain details of its implementation. In order to facilitate comparison with SASL, I've adopted the organization and most of the headings of Grust's paper.
SLACK is a compiler for the pure functional part of K.
SLACK has atoms, vectors, (lazy) lists, and dictionaries, but no lambdas.
In K, a defined function is a lambda:
{[x;y;z]x+y*z}
A lambda is a first-class datatype which can be the value of a variable:
plustimes:{[x;y;z]x+y*z}
In place of lambdas, SLACK has definitions:
plustimes x y z is x+y*z
Definitions are not first-class, always have names, and the meaning of 'is' is not assignment.
SLACK has 19 of K's 20 primitive verbs, and all 6 of its primitive adverbs, but dispenses with 'if', 'do', 'while', and the K conditional.
SLACK has just one control-structure, a result-returning conditional if-then-else. For example,
3*if x=0 then 2+x else x-12
There is no assignment in SLACK, no variables, and no side-effects, except those which are implicit in '.' and '@', and the IO verbs (which a production implementation of the language would remove.)
Many K functions translate trivially into equivalent SLACK definitions. For example, Euclid's algorithm for greatest common divisor in K:
gcd:{[a;b]:[b=0;a;gcd[b;a!b]]}
translates to the SLACK definition:
gcd a b is if b=0 then a else gcd b(a!b)
The objective of the SLACK project is to demonstrate in concrete terms how K lambdas can be "defined away" without thereby sacrificing the power of K to solve interesting problems. As many practitioners of the language know, or at least suspect, that power consists of the synergy of a small set of general array primitives and an even smaller set of fundamental fixed datatypes.
As noted above, SLACK has all the K datatypes except lambda.
int 10
float 12.3
char "a"
sym `foo
null null
dict . list_of_symbol-value{-dict}-tuples
SLACK has vectors, and supports K vector-notation:
int 10 20 30 float 10.1 20 30.456 char "abc" sym `foo`goo`hoo
In SLACK, a symbol is terminated by a blank, a quotation symbol ` ", or a punctuation symbol [ ] ( ) ;.
In K, square brackets are used for list-indexing, function-application, function-projection, and to denote the arguments of a lambda:
array[rows;cols]
function[arg1;arg2;arg3]
@[;0 2 4 1]
{[a;b;c]a+b-c}
and parentheses are used for expression-grouping, verb-nominalization, and list-formation:
(2+3)-!10 (+) (1 2;"abc")
In SLACK, parentheses are used only to control order-of-execution, and square brackets are used only to construct lists:
[] [1;2 3;;[5;6]]
The first expression denotes the empty list, written in K as:
()
The second expression denotes the K list:
(1;2 3;;5 6)
Lists collapse into vectors when they can, as they do in K.
In SLACK,
[10]
denotes the unit list containing 10, written functionally in K (and also in SLACK) as:
,10
In SLACK, the empty list, the null atom, the NaNs, and the infinities have (reserved) names:
[nil;null;nan;Nan;inf;Inf] (();;0n;0N;0i;0I) null~*nil 1 nil~0#null 1
In K, a parenthesized verb is nominalized. That is, the verb is turned into a noun. As a noun, it can be assigned to a variable, passed as an argument to a lambda, or included as an element in a list.
Since SLACK lacks assignment and lambdas, and parentheses are used only to group expressions, parenthesizing a verb does not alter its syntactic category. In general, the category of (x) is the category of x. So, for example,
2(+)3 5
How then can we produce the equivalent of something like
(1;+;2)
As we shall see, the list
[1;+;2]
is syntactic sugar for
1:+:2:nil
whose elements have the syntactic categories n v v v n v n, respectively. But such an expression will not parse into a list of three nouns. To achieve this result, we resort to indirection:
[1;plus;2] where plus is + (1;+;2)
Using the same method we can even simulate first-class adverbs!
[1;over;2] where over is /
+---------@----------+
| |
+------@-------+ a:/
| |
+--@--+ +----@-----+
| | | |
B +@-+ +-@-+ +-@--+
| | | | | |
cons 1 C cons +@-+ nil
| |
cons 2
The K adverbs are very overloaded. For example, for / we have
+/x dyadic function ("reduce")
x+/y reduce with initial state
f/[x;y;z] n-adic function with initial state ("over")
f1/x monadic function ("converge")
n f1/x do f1 n times
g f1/x f1 while g x
v/i chase pointer until termination
j v/i chase pointer for j iterations
m/i finite state machine
j m/i finite state machine starting in state j
The K interpreter picks the meaning of / based on both syntactic information and the type and valence of the verb or noun operand. Unfortunately, in the current version of SLACK this inference is not possible. While the SLACK compiler knows the syntax of /, and can therefore distinguish x y/z and y/z, it has no concept of function-valence, and cannot therefore distinguish convergence (f1/) and reduction (f2/).
It can, however, tell the difference between a primitive, such as +, and a compiled SLACK object, such as f, where f x y z is x+y*z. Hence, in simple cases, the K adverbs work as expected. For example, the following examples are valid in both K and SLACK:
+/!10 45 0 0 0 1 1 2 2 2\5 5 2 0
SLACK supports all native adverb forms involving primitive operands, and for defined operands it supports all forms other than do, while, and converge. For example,
{x+y*z}/[1 2;3 4;5 6]
40 41
f/[1 2;3 4;5 6] where f x y z is x+y*z
40 41
There are two points to note. First, the brackets in these SLACK expressions are those of list-notation. f/[..] is f/ applied to the list [..]. Second, the valence of f must agree with the count of the list. For example, while in K we may write
{x+2*-x}'10 20 30
the corresponding SLACK expression is
f'[10 20 30] where f x is x+2*-x
This has the unfortunate consequence of requiring different semantics for the adverbs / \ ' and ': depending on whether f is primitive or defined. For example,
f'[10 20 30] where f x is x+2*x
versus
f'10 20 30 where f is -:
Further analysis may reveal an acceptable method for unifying the cases.
To handle the remaining adverbs, SLACK adds the keywords loop and converge, and the "scan" versions Loop and Converge. loop/Loop implements K's x f1/ and x f1\ respectively (over and scan versions of do and while) and converge/Converge implements K's convergence operators f1/ and f1\:
5 f Loop 3 where f x is x+1 3 4 5 6 7 8 g f Loop 3 where (f x is x+1) where g x is x<7 3 4 5 6 7 f Converge 7 where f x is if x=0 then 0 else x-1 7 6 5 4 3 2 1 0
In SLACK and K, : is appended to a verb to fix the unary interpretation of the symbol. For example, +: is transpose.
In SLACK, . may be suffixed to a verb to denote the projection of its first argument:
3 + +[3] 3 +. +[;3]
In SLACK, a list is a functional expression. For example,
[1;[2;3;5];;[];5]
+----------------@-----------------+
| |
+-@-+ +--------------------@--------------------+
| | | |
cons n:1 +------@------+ +--------@---------+
| | | |
cons +------@-------+ +-@--+ +------@------+
| | | | | |
+-@-+ +-----@-----+ cons n:null +-@--+ +--@---+
| | | | | | | |
cons n:2 +-@-+ +--@---+ cons n:nil +-@-+ n:nil
| | | | | |
cons n:3 +-@-+ n:nil cons n:5
| |
cons n:5
Since SLACK is lazy, this means that we can define and use infinite lists. For example,
head tail one where one is 1:two where two is 2:one 2
which has the reduction-tree:
+------@-------+
| |
+--@---+ +-----@------+
| | | |
+-@-+ tail Y +-----@------+
| | | |
B head +--@---+ +-@-+
| | | |
B +-@-+ cons n:2
| |
cons n:1
Note the use of the Y combinator to compute mutual recursion between the lists.
SLACK has nouns, verbs, and adverbs.
The ternary conditional operator if-then-else takes expressions and is result-returning:
if x>0 then y+1 else z-2
The conditional may nest in all three positions.
SLACK has no assignment. This frees up the : primitive for redefinition. Following SASL, we use it to denote the binary cons operation:
1:2 1 2 1:nil ,1 1:2 3:4 5 6 (1;2 3;4;5;6) 1:2 3:4 5 6:nil (1;2 3;4 5 6)
That is, x:y is (,x),y. In general, [..;x;..] is notation for ..:x:..:nil.
We also lose the monadic form :: (identity), since 1::2 is 1:nil:2; that is, (1;;2), cons with elided nil.
SLACK has the verbs:
. - _ ~ ! @ # $ % ^ & * = + | < , > ? :
where : is redefined to mean cons. SLACK also has the 6 adverbs of K:
' / \ ': /: \:
In addition, SLACK also supports explicit unaries ("monads"); for example,
-:1 2 3 -1 -2 -3
SLACK also has first-argument projection:
+. 3 +[;3] 2 +. 3 5
In K, an adverb takes a verb and returns a verb. Verbs are ambivalent. Hence one may write both
+/!3 3 2+/1 2 3 5
This is true in SLACK as well. However, we wish to provide explicit support for both the unary and the binary forms of the adverb, as we do for the unary and binary forms of the verbs. We do this with a suffix:
+/1 2 3 6 2+/1 2 3 8 +/.1 2 3 6 2+/.1 2 3 8
This gives SLACK the following adverbs:
/ \ ' /: \: ': /. \. '. /.: \.: '.:
/.: and \.: are nonce errors.
In K, bracket application of a lambda of valence n is written:
foo[1;2;3]
Alternatively, the function . maps elements of a list of length n to the arguments of foo:
foo . 1 2 3
In K, nouns associate to the right, whereas in SLACK, they associate to the left:
f g h x
+--@---+
| |
+--@--+ x
| |
+-@-+ h
| |
f g
That is, if f is a function of three arguments x, y, z, then f applied to x, y, z is
(((f applied to x) applied to y) applied to z)
That is, multi-argument functions are curried.
Since vectors are tokens, we need a way to map the elements of a vector literal to the arguments of a function. In K, we can say either
f 1 2 3
which applies unary f to the vector 1 2 3, or
g . 1 2 3
which applies ternary g to atoms 1, 2, and 3.
SLACK application defaults to the unary case:
f 10 20 30 +--@---+ | | f n:10 20 30
To apply ternary g to atoms, we use parentheses to override vector-notation, e.g.:
f 10(20)30
+---@----+
| |
+--@---+ n:30
| |
+-@-+ n:20
| |
f n:10
which is semantically equivalent to the K projection:
f[10][20][30]
Following SASL, we will represent SLACK expressions as binary trees, in which a non-leaf node represents the application of the left child to the right child.
Nodes are niladic K lambdas representing SLACK primitives. An application node is
{}
and a pair node (produced only in the course of reduction) is:
{`pair}
At the leaves are structures of three kinds.
A leaf of the form
(type;value)
is a noun, verb, or adverb, where type is a K lambda. For example,
{{`n};10)
An untyped symbol is a combinator or an external function. For example,
`K `print
Finally, an untyped lambda is a SLACK primitive:
{`head}
{`cons}
A SASL script consists of a series of global definitions followed by a period followed by a single expression. Global definitions may reference each other, themselves, and their subordinate local definitions. Each definition may have many subdefinitions, and subdefinitions may reference each other as well as their superdefinition, but subdefinitions may not themselves have subdefinitions.
For example, here is the standard SASL prelude.
A SLACK script consists of a series of programs, comments, and an execution terminator.
Comments begin with a / in column 1.
Execution terminates with a single \ in column 1.
A line prefixed by \\ in columns 1 and 2 signals that a combinator expression follows. The expression is parsed and executed, and the result is appended to the script result:
\\ C I 5(Y(B(S(C(B cond(C = 0))1))(B(S *)(C B(C - 1)))))
Otherwise, a line prefixed by \ in column 1 is executed directly in K. The result is appended to the script result:
\!10
A program is either a definition or an expression.
A definition has the form
name arguments <is> expression / assignment <where> (definition) / subdefinitions : <where> definition
The where keyword introduces a local definition, which itself may contain subordinate local definitions.
A program which does not begin with an assignment is an expression, and is executed immediately.
Definitions accumulate in the course of evaluation, and are available to subsequent expressions. For example,
a is .. b is .. a b 10 c is .. c a b 10
A definition may contain references to global definitions, to definitions at its level, or to its subdefinitions. For example,
i x is x=0 f x is g x where (g x is if i 0 then 0 else h x-1) where h x is if i 0 then 0 else g x-1 f x is g h x+1 where (g y is y-3) where h z is z%2
The arguments ("formal parameters") of a definition are available to its subdefinitions. For example, in
f 3 where f a is g b+a+1 where (b is a+h 2 where h x is a*a*x) where g x is a+x-1
f's argument a (which in this instance has the value 3) is available to f's subdefinitions b and g. Moreover, owing to the way this feature is implemented in SLACK, a is available to b's subdefinition h.
Arguments shadow subdefinitions:
f 3 where f x is x where x is 2 3
Subdefinitions shadow codefinitions:
g x is 1+x f x is g x where g x is x f 3 3
Codefinitions shadow superdefinitions:
f x is g x where (g x is f x) where f x is 1+x f 3 4
A definition can see any unshadowed superdefinition:
f 3
where f x is if x=0 then 99 else g x
where g x is h x
where h x is f(x-1)
99
Following SASL, SLACK has two predefined functions which operate on lists:
head x:xs -> x tail x:xs -> xs
In SASL, the head and tail of an empty list is undefined, while in SLACK these are respectively null and nil
null~head[] 1 nil~tail[] 1
In SASL, equality is lazy and total, so one can write
x = nil
Since K equality is eager and atomic, we require one further operation, corresponding to SASL's =:
x eq nil
As in SASL, eq, head, tail, : (cons), and nil form a complete "list toolbox".
Grust divides SASL into four components:
lexer -> parser -> compiler -> reduction
and this scheme, which is quite general, corresponds to the structure of the SLACK implementation.
Specifically, SLACK takes as input a string S, which represents a program. If S is a definition, it is processed and added to the SLACK program space (a local K dictionary). If S is an expression, it is processed and evaluated in the context of the definitions processed so far; the result of reduction is R, a K object.
That is the general picture to keep in mind as we discuss the details of the implementation.
What Grust calls "the compiler driver" is a K script, slack.k. The script defines several entry points:
R:run S / evaluate S R:comb X / evaluate combinator-expression X show S / show the execution-tree of S using ASCII line-drawing characters text S / show the execution-tree of S using "+-|" html S / show the execution-tree of S using unicode characters. code S / show the execution-tree of S as executable combinator code. int[] / interactive interpreter
Additionally, the components of the SLACK compiler are directly available:
T:Tokens S / tokenize S P:Parse T / parse token-list C:Compile P / compile parse-tree R:Eval C / evaluate execution-tree C:Comb X / compile combinator-expression X
The SLACK compiler consists of the following scripts:
slack.k compiler driver t.k tokenizer p.k parser k.k K expression parser a.k K adverbs c.k compiler e.k SK reduction machine x.k combinator definitions y.k Smullyan birds d.k display functions b.k built-in functions h.k combinator-expression parser/compiler
The SLACK tokenizer (Grust's lexer) is a K script, t.k. The script has a single entry point:
T:Tokens S
Let's take a closer look.
The tokenizer is a finite-state automaton. The automaton scans the string left-to-right. At any step, the automaton is in some state i and ready to read a single character j. The effect is to move the automaton into a new state k. It is now ready to process the next character.
In K, we specify such an automaton by deriving it from \ applied to an integer matrix M. That is,
M\
for suitable M, initial i, and vector J = j1 .. jn returns K = i k1 .. kn which records the succession of states M has occupied while reading J.
For example, we wish to define an automaton which gives us the information necessary to decompose a number into its parts. A number optionally begins with a sign "-", and has an optional left part, an optional decimal point, and an optional right part. The following are all numbers:
12 1.2 .23 12. -12 -1.2 -.23 -12.
We recognize three character classes:
N:"0123456789" / digits D:,"." / decimal point S:,"-" / sign
Our machine M is a matrix, where the columns correspond to the classes (+ 1 for characters not in those classes) and the rows correspond to states:
M:(2 3 1 5 / start 2 3 5 5 / sign 2 3 5 5 / left digits 4 5 5 5 / decimal point 4 5 5 5) / right digits
Given an input string,
I:"-12.3"
we categorize the characters:
:C:(I _in/:\:(N;D;S))?'1 2 0 0 1 0
then run the automaton:
0 M\C 0 1 2 2 3 4
The SLACK tokenizer, while somewhat more complex due to the variety of tokens in the language, uses the same approach. The tokenizer recognizes 12 character classes:
/ blank
a-zA-Z / alpha
. / point
0123456789 / digit
" / quote
\ / escape
-_~!@#$%^&=+|<,>? / verb
'/ / adverb
()[]{}; / punctuation
: / cons/monadic
` / symbol
/ everything else
The automaton has 29 states:
blank
name
left number
decimal point
right number
number vector
quote 1;
escape 1
quoted 1;
quote 2;
escape 2
quoted 2;
symbol
verb
verb.
verb:
next verb
next verb.
next verb:
adverb
adverb.
adverb:
next adverb
next adverb.
next adverb:
:
next :
()[]{};
next ()[]{};
A small amount of pre- and post-processing is performed which allows us to avoid lookahead in the tokenizing procedure. For example, until we examine the next character, we can't tell whether "-" is a function-symbol or the sign of a number.
The parser consists of an outer parser p.k and an inner parser k.k.
The outer parser takes a list of tokens T and returns a triple P = (V;E;W). V is always ().
If T represents an expression, then E is the parse-tree of T and W is a dictionary of its local definitions. W.f, where f is a local definition, is also a (V;E;W) triple where V is a list of the arguments of f.
If T represents a definition f, then E is () and W is a singleton dictionary W.f, and W.f is a (V;E;W) triple, where V is a list of the arguments of f, E is the expression part of f, and W is a dictionary of f's local definitions.
The inner parser takes a list of typed tokens, nested according to occurrences of ()s and []s, and returns a K parse-tree. The inner parser implements the Bunda-Gerth two-by-two algorithm. Details are provided in the attached appendix.
The first task of the outer parser is to determine whether the input t represents a definition or an expression. Since a SLACK program has one of the following two forms:
.. is .. {where ..}
.. {where ..}
where the first form indicates that the program is a definition and the second that it is an expression, the parser merely needs to check whether the first occurrence (if any) of the token "is" occurs before the first occurrence (if any) of the token "where".
In the definition case, the parser returns
(();where t)
and in the second
(form expr[()]e;where w)
where e is the expression part of t and w is the where part of t.
The function expr takes two arguments: v, a list of variables (e.g. `x `y, or ()), and t, the token-list to parse. If the first token is "if", the expression is a conditional, and the function cond is invoked to process t. If the first token is "(", the function group is invoked to process t. If the first token is "[", the expression to be processed is a list, and the function list is invoked to process t. Otherwise, the first token is an operator or operand, and the function oper is invoked to continue processing t.
cond, group, and list recursively process the initial part of t, passing the rest of t to expr for further processing. cond looks for "if", "then", and "else" parts, which are processed as expressions. group looks for the mated right parenthesis, processes what is to its left, and returns that result as a unit list. list looks for the mated right bracket, processes what is to its left, and returns that result as a unit list.
The function oper processes the initial token of the list, passing the remainder to expr. Processing of a token consists of labelling it with a pair of types. The syntax type is the K syntax category: noun, verb, adverb. The semantic type is determined by textual analysis of the token. Currently, SLACK supports the following semantic types:
Z null Y nil j nan J Nan k inf K Inf S symbol/symbol-vector Q character/character-vector N number/number-vector I variable L name W head, tail E eq C : (cons) V verb U verb. (projection) A adverb
A typed token is a pair, whose first element is a niladic K lambda s, such that s[] returns a symbol of the syntax category of the token, and whose second element is a string whose first element is a letter denoting the semantic type of the token. For example,
"12.3" -> ({`n};"N12.3")
"/" -> ({`a};"A/")
The function where takes a single argument t, the token-list to parse. where repeatedly applies the function defs to t in order to extract the local definitions, which are returned as variables in a dictionary. where involves a technique used elsewhere in the parser, so it's worthwhile examining it in detail.
where:{[t]*(defs .)/(;t)}
defs is a function of two arguments: r, a dictionary of local definitions (initially null), and t, the remainder of the token-list. defs is repeatedly applied to its result (a pair) until that result is the same twice in a row (or identical to the initial argument.) At each invokation, defs splits t into the head definition and the remainder, parses the head definition, adds it to r, and returns r and the remainder of t. When t is empty, defs returns (r;t) unchanged, and the recursion terminates. Finally, the first of the result is taken (the dictionary) and the token-list, now empty, is discarded.
After the token list is typed, instances of adjacent cons are replaced with cons null cons. That is,
x::y -> x:null:y
At this point, the token-list is passed to the inner parser, whose entry point is the function K. The result of K applied to t is a list of typed tokens in head normal form:
(operator .. operands ..)
For example, given:
2+3*!4
the outer parser produces:
(({`n};"N2")
({`v};"V+")
({`n};"N3")
({`v};"V*")
({`v};"V!")
({`n};"N4"))
which is passed to K, which returns:
((({`v};"V+")
({`n};"N2"))
((({`v};"V*")
({`n};"N3"))
(({`u};"V!:")
({`n};"N4"))))
After returning from K, the function apply transforms the result of the inner parser into a binary tree:
({}
({}
({`v};"V+")
({`n};"N2"))
({}
({}
({`v};"V*")
({`n};"N3"))
({}
({`u};"V!:")
({`n};"N4"))))
Three post-processing steps perform a final "cleanup" on the tree:
Free variables
f x where g is x -> x in g is a variable ("Lx" -> "Ix")
Lambda-lifting
f x is g where g is x -> f x is g x where g x is x
Unused arguments
f x is F, x not in F -> f x is first F [x]
The single entry point is the function K, which sequentially transforms a nested list x of typed tokens into a parse-tree.
The function tree adds further nesting to x based on K's grammar rules. These rules are encoded in a pair of tables, B and C. The algorithm used by tree is described below in Appendix A.
The function unary finds patterns of the form
noun (verb noun)
and converts the embedded verb into a unary.
The function binary finds patterns of the form
noun (verb (verb adverb))
and converts the embedded adverb into a binary.
The function order finds patterns of the forms
noun adverb noun binary verb adverb verb binary noun verb unary adverb unary binary
and swaps the components. For example,
+ / -> / +
The function flat removes type information from all non-leaf nodes. For example, in
({`v};(({`a};"A/");({`v};"V+")))
the result of applying / to + is a verb. The derived category was introduced by the K grammar algorithm, and used by the unary, binary, and order functions. But we no longer require it. So flat eliminates this type information from the derived node:
(({`a};"A/");({`v};"V+"))
The function project converts dotted verbs to first-argument projections. For example,
({`v};"U+.") -> ({`v};"V{+[;x]}")
Finally, the function adverb simulates first-class adverbs, by replacing text representing K adverbs with text representing equivalent K lambdas. For example,
({`a};"A/"} -> ({`a};"A{..}")
The SLACK compiler is the script c.k.
Output from the parser is a triple (V;E;W). For example,
Parse Tokens"f 2 where f x is 1+g x where g x is -x"
(() V
({} E
"Lf"
({`n};"N2 "))
.,(`f W
(,`x V
({} E
({}
({`v};"V+")
({`n};"N1"))
({};"Lg";"Ix"))
.,(`g W
(,`x V
({} E
({`u};"V-:")
"Ix")
) W (null)
))
))
Given the expression e is f 2 to evaluate, where f is local to e, and g is local to f, the parser returns a triple (V;E;W) where V is (), E is the parse-tree for E, and W is a dictionary containing f. W.f is a triple (V';E';W') where V' is f's argument x, E' is the parse-tree for f, and W' is a dictonary containing g. And so forth.
The job of the compiler is to transform such recursive triples into reduction-trees. A reduction-tree is a nested list whose leaves are drawn from the set of following types:
Elementary K data. For example, atoms such as 12 and `foo, and vectors such as "string" and 10 20 30. Lists in the K sense -- that is, data of type 0 -- do not appear in the initial state of a reduction-tree.
Elementary K functions. For example, functions such as + and -:, and lambdas such as the ones generated programmatically to stand in for the K adverbs. Function- and data-leaves are typed. For example, + appears in the reduction-tree as
({`v};+)
External functions. External functions are K lambdas defined in the script b.k. For example, the external function print is defined as
b.trace:{\x} ;b.trace..v:1
trace takes an unreduced subtree as its argument, prints it to the console, and returns it as a result. The attribute v is -1 to indicate that reduction should not be performed on the input to the function.
K system verbs, such as _in, are defined as externals, and the value of f..v is the valence of the function:
b.in:_in ;b.in..v:2
The I/O verbs, such as 1:, are also defined as externals.
An external function appears in the reduction-tree as an atomic symbol.
SLACK primitives. A niladic K lambda. One of the following:
{}
{`cons}
{`cond}
{`head}
{`tail}
{`eq}
{`get}
{`pair}
Combinators. A combinator is a rule for rewriting part or all of a reduction-tree. As we shall see below, although the output from the parser is a tree, in the course of reduction that tree is converted to a graph. That conversion occurs through the action of several of the combinators. In SLACK, a combinator-leaf is represented as an atomic symbol, drawn from the following list:
`S `K `I `B `C `S_ `B_ `C_ `Y `U
The entry point of the compiler is the function compile. It takes as input a triple (V;E;W) and removes all occurrences of names and variables.
The input parse-trees for E and definitions in W is a nested list whose leaves are uninterpreted. For example, the uninterpreted leaf for the + function is
({`v};"V+")
The result of semantic interpretation is
({`v};+)
The strategy used in the compiler is to defer semantic interpretation of the leaves as long as possible. In the course of compilation, there are three interpretation points, corresponding to three semantic classes. These classes are:
pre: variables, literals mid: null, nil, nan, Nan, inf, Inf, eq, cond, cons, tail, number, verb, adverb post: symbol, quote, combinator
compile calls the function compile_, which is defined thus:
compile_:{[v;e;w]
r:com[v]val[pre]e
if[~_n~w;r:where[r;!w]w[]]
r:val[mid]r
r::[#e;r;#r;r 2;r]
r}
Suppose we are compiling the expression
foo 3 where foo x is -x
Input to the compiler is:
v = ()
e = ({};"Lfoo";({`n};"N3 "))
w = .,(`foo;(,`x;({};({`u};"V-:");"Ix")))
e, the expression part of the triple, is pre-processed and passed to the main compiler function com. Pre-processing involves the conversion of literal names and variables from strings to symbols:
"Lfoo" -> `foo "Ix" -> `x
At this point, e looks like this:
({}
`foo
({`n};"N3 "))
If w, the local definition dictionary, is not empty, then it along with r, the result of processing e, is passed to the function where. The where function returns r with local definitions and their variables transformed away:
({}
({}
({};"XC";"XI")
({`n};"N3 "))
({`u};-:))
Observe that, in the course of compiling w, the compiler was invoked recursively to handle the expression part of the subdefinition. Also note that a new type of leaf-node has been introduced. "XC" and "XI" have semantic type "X", and represent two of the ten combinators used by SLACK to eliminate names and variables.
The next step involves performing mid-processing on r, which in this case has no effect.
The last line of compile_ returns either r or just r 2, depending on whether the input was an expression or a definition.
After compile_ has completed, a final post-processing step is performed, which converts the remaining leaves:
({}
({}
({};`C;`I)
({`n};3))
({`u};-:))
The reduction-tree for our expression is:
foo 3 where foo x is -x
+--@---+
| |
+--@--+ u:-:
| |
+-@-+ n:3
| |
C I
(This part closely follows the corresponding section of Grust's paper.)
We use the shorthand f x to denote the application of f to x.
An expression E is either a constant c, a variable v, or a function application f a. We compile the definition
f x is E
by applying variable abstraction, written [x], to E. [x]E removes all occurrences of x in E. There are three cases:
(i) if E = c then [x]E = K c (ii) if E = v then [x]E = if x=v then I else K v (iii) if E = (f a) then [x]E = (S [x]f)[x]a
In the foregoing, we say that abstraction binds more tightly than application, so
[x]A B
means that the abstraction of x from A is applied to B. And we say that application is right-associative, so
A B C
means that A is applied to the result of applying B to C. Note that this is consistent with K practice, but inconsistent with nearly everyone else!
S, K, and I are the basic combinators of the SLACK reduction machine, defined as:
((S f)g)x = (f x)g x (S)ubstitution (K x)y = x (K)onstant I x = x (I)dentity
Example:
incr x is 1+x
Input to the compiler is:
(,`x V
({} E
({}
({`v};"V+")
({`n};"N1"))
"Ix")
) W
that is,
(+ 1) x
Abstraction of x is performed:
[x](+ 1) x (S [x](+ 1)) [x]x by (iii) (S (S [x]+ [x]1)) I (iii), (ii) (S (S (K +)) K 1) I (iii), (i), (i)
Definitions of the form
f x1 .. xn is E
are transformed by abstracting inner variables first:
[x1](.. ([xn]E) .. )
SASL recognizes two kinds of definitions: global and local. Local definitions cannot have local definitions.
In SLACK, definitions can nest, and no distinction is made between global and local definitions. In the course of evaluating a SLACK script, definitions accumulate in the environment dictionary, and are passed to expressions as though they were declared as locals. For example, the following two scripts are equivalent:
incr is 1+x incr 3incr 3 where incr is 1+x
In the case where the expression to be compiled has the form
E where F
There are three subcases to consider:
E where f is F niladic definition E where f x is F n-adic definition, n>0 E where f x is .. f .. recursive definition
In the case where the expression to be evaluated has a single niladic local definition:
E where f is F -> [f]E F
For example,
2+x where x is 3 -> [x](2+x) 3
Where the expression has a single local definition involving one or more variables:
E where f x is F -> [f]E [x]F
For example,
incr 3 where incr is 1+x -> [incr](incr 3) [x](1+x)
That is, we apply the abstraction of the function from the expression to the abstraction of the variable from the local definition.
Where the expression has a single recursive local definition:
E where f x is F = .. f .. -> [f]E Y[f][x]F
where Y is the fixpoint or "paradoxical" combinator:
Y f = f Y f
For example,
fac 5 where fac n is if n=0 then 1 else n*fac(n-1) -> [fac](fac 5) Y[fac][n](if n=0 then 1 else n*fac(n-1))
An expression can have more than one local definition:
f g 3 where (g x is ! x) where f x is - x
There are two subcases:
E where (f x is F) .. where g x is G E where (f x is .. h ..) .. where g x is .. h .. h is f .. or .. g
An expression, any one of whose definitions refers either to itself or to one of its siblings, falls under the second case.
The compilation rule for the first subcase is:
(U [f](U [g]K E)) [[x]F ;..; [y]G]
where U is the "uncurry" combinator:
(U f) z = f (head z) tail z
That is, U simulates the application of a function f to two arguments by applying f to the head of list z, and then applying the result to the tail of z.
The compilation rule for the second subcase is:
(U [f] .. (U [g]K E)) Y U [f] .. (U [g](K [[x]F ;..; [x]G]))
SLACK implements the five compilation rules in three blocks of code.
The entry point of the first block is the function where, which is given an expression e, a list of symbols of e's where clauses (if any), and a list w of the (V;E;W) triples of each of those definitions. The function compiles each of the definitions, and passes e, s, and the compiled definitions c to the function what.
what takes e, s, and c, and determines which of the definitions in c are actually used by e. Recall that we pass in to the compiler the accumulated environment of all definitions encountered so far. If none of the definitions in c is used by e, what returns e unchanged. If only one definition is used, what calls the function clause. Else if more than one definition is used, what calls clauses.
Here is the code for where and its subfunctions:
where:{[v;e;s;w]what[e;s;{compile_[?v,x;y]z}.'w]}
what:{[e;s;c]:[~#i:who[,//e;s;,//'c];e;@i;clause[e;s i]c i;clauses[e;s i]c i]}
who:{[e;s;c]atom s?/:use[.+(s;c);s]/in[s]e}
use:{[d;s;v]v{?x,in[s]d y}/v}
in:{x@&x _lin y}
atom:{:[1=#x;*x;x]}
Both functions must now distinguish the recursive and non-recursive subcases. Let's look at the simpler case:
clause:{[e;s;c]:[s _in,//c;wy;wx][e;s]c}
wx:{[e;s;c]({};abs[e]s;c)}
wy:{[e;s;c]({};abs[e]s;({};"XY";abs[c]s))}
If s (the symbol of e's lone definition) appears in ,//c (the flatten of the compiled definition), then call wy, else call wx, on e, s, and c.
wx (the non-recursive case) returns a triple, the first of which is the application primitive {}, the second of which is the abstraction of s from e, and the third of which is the compiled definition.
wy also returns a triple, the first of which is {} and the second of which is the abstraction of s from e. The third element is itself a triple, the first element of which is {}, the second element of which is the Y combinator, and third of which is the abstraction of s from c.
Implementation of clauses is only slightly more complex. We must look for the case of mutual recursion, and we must construct the list expressions for the arguments to the U combinator. Here is the code:
clauses:{[e;s;c]:[|/s _lin,//c;wY;wX][e;s]c}
wX:{[e;s;c]({};({};"XK";e)wU/|s;wL c)}
wY:{[e;s;c]({};({};"XK";e)wU/|s;({};"XY";({};"XK";wL c)wU/|s))}
wU:{[e;s]({};"XU";abs[e]s)}
wL:{[e](){({};({};{`cons};y);x)}/|e}
The SLACK reduction machine is defined in the script e.k. The single entry point is the function eval.
Input to eval is a reduction-tree. eval calls run, which initializes the cache Z, and then in turn calls value on the result of eager applied to the tree:
eval:{run .:[C;Cache x;(x;())]}
run:{Z::y;E x}
E:value eager@
The purpose of the value function is simply this: if input to the function is typed, then return just the value. For example, if input to value is
({`n};10)
then return
10
The eager function performs eager evaluation on its input. For example, given the reduction-tree for the expression
2+[1;2;3]
eager returns
({`n};2 4 5)
There is a corresponding function lazy which performs lazy evaluation; and in fact, lazy is called by eager. lazy takes a reduction-tree and repeatedly reduces it while it has the form of an application. That is, lazy calls the function step (which performs a single reduction step) and checks the result. If the result has the form
({};A;B)
it calls step again. It then checks the result of that call, and so forth, until the result does not have the form of an application. lazy has the definition:
lazy:({}~*:)step/
When lazy terminates, the result might be a pair. That is, it might be a list waiting to be evaluated. In that case, the result has the form
({`pair};L;R)
where L is the left part of the pair and R is the right part.
The function list is used to evaluate pairs:
list:{:[{`pair}~*x;join . x;x]}
join:{(,E y),E z}
If the input x is a pair, then list returns a list whose head (first element) is the result of eagerly evaluating the left part of the pair, and whose tail is the result of eagerly evaluating the right part of the pair. Otherwise, list returns unevaluated x.
We can now define the function eager:
eager:list lazy@
Eager evaluation therefore consists of lazy evaluation followed by list evaluation. List evaluation may in turn involve eager evaluation (of the left and right parts of a list.) What we can say is that the result of eager evaluation is neither an application nor a pair.
Input to eval is a tree. If e.C is 1, eval calls the Cache function to initialize the cache with common subexpressions. The code for Cache is in the script z.k. For example, instructed to evaluate the expression
(!3)+!3
Cache detects the common subexpression !3, stores the code for that expression in the cache Z, and replaces occurrences of the expression in the tree with pointers to the cache. When !3 is evaluated, SLACK replaces the cached expression with its result. Subsequent fetches from the cache will get 0 1 2.
In the course of evaluation, certain combinators replicate subtrees of their input. For example, the S combinator is defined:
S f g x = (f x) g x
We want to avoid evaluating x twice. So the combinator should produce a graph, where f and g are both applied to a single node x. If, in the course of evaluation, the subtree f x is evaluated, causing the evaluation of x, then later, if the subtree g x is evaluated, g will be applied to evaluated x. That is, we want our rule for S to have the form:
S f g x = (f <x>) g <x>
where <x> is a pointer to the subtree x.
Consequently, the SLACK implementation of the reduction rule for S is:
{[x;y;z]p:S z;({};({};x;p);({};y;p))}
Initially, the function S is called with x as input. If x is already stored in Z, the cache, S returns p such that the evaluation of p returns x; else S appends x to Z and returns p. Z is a list of subtrees (and Z~?Z). p has the form:
({};{`get};i)
where i = Z?x.
Subsequently, when a pointer is evaluated, the reduction algorithm will match {`get} and call the reduction function G with argument i. G retrieves x from Z, evaluates it (lazily), stores the result in Z i, and returns it to the reduction function (see below.) Consequently, later occurrences of ({};{`get};i) will returns evaluated x.
This sounds complicated, but the underlying functions S and G are quite simple:
S:{:[({};{`get})~2#x;x;({};{`get};:[(#Z)>i:Z?x;i;-1+#Z,:,x])]}
G:{:Z[x]:lazy Z x}
The entry point for reduction is the function step, which is called by the lazy evaluator. step takes a reduction-tree as input, and is defined:
step:{next[x]({}~*x .){x,1}/()}
step will perform at most one reduction step by calling the function next. To do this, it needs to find the point in the reduction-tree where reduction can be performed. That point is represented by a path s into t: such that t . s can be reduced. We must search down the left-hand-side of the tree until we find a node which is not {} (application). As we search, we keep appending 1 to the previous path. If *t is not {}, then t = t .() can be reduced, and s = (). If *t is {}, then perhaps t 1 can be reduced. If so, then s = ,1. If not, then perhaps t . 1 1 can be reduced. If so, then s = 1 1. And so forth.
Having computed i, the next function is called with the current state of the tree and s:
next:{[t;s]
a:*t . s
:[a~{`pair} ;m[t]s
a~{`cons} ;c[t;s]t ./:p[s]2
a~{`cond} ;o[t;s]@[t ./:p[s]3;0;E]
a~{`head} ;ht[t;s;1;*:]lazy t .*p[s]1
a~{`tail} ;ht[t;s;2;1_]lazy t .*p[s]1
a~{`eq} ;e[t;s]@lazy't ./:p[s]2
a~{`get} ;g[t;s]lazy t .*p[s]1
a _in K ;kk[t;s;t . s]type eager t .*p[s]1
a _in!b ;f[t;s]a
a _in**X ;x[t;s;X[1]i]t ./:p[s]X_ i:X[0]?a
a _in**Y ;y[t;s]Y[1]Y[0]?a
7=4:a ;q[t;s;a]t .*p[s]1
n[t]s]}
Proceeding down the left-hand-side of the tree (often called "the spine"), eventually we find the first non-application node ~{}~a:t . s. For each possible type of a there is a corresponding reduction rule. next selects the appropriate rule, applies it to t, and returns t reduced by the rule.
The reduction rules are:
@ ^
/ \ / \
@ y x y
/ \
: x
@ y if x = 1 else z
/ \
@ z
/ \
@ y
/ \
cond x
@---------+ x if head, y if tail
/ |
head ^
or / \
tail x y
@ 1 if x~y else 0
/ \
@ y
/ \
eq x
@ f[x]
/ \
f x
@ f x (x unevaluated)
/ \
f x
@ f{x[y]}/(a;..;z)
/ \
: z
:
/ \
f z
@ c{x[y]}/(a;..;z)
/ \
: z
:
/ \
c z
@ f[x][y]
/ \
f[x] y
The function code is used to compute the text representation of a compiled SLACK expression:
code"fac 5 where fac n is if n=0 then 1 else n*fac(n-1)" " C I(5)(Y(B*(S(C' cond(C =(0))(1)))(S *)(C B(C -(1)))))"
The function comb takes a code-string as input, converts it into an execution-tree, and evaluates it:
comb code"fac 5 where fac n is if n=0 then 1 else n*fac(n-1)" 120
Note: I owe this idea to John Scholes, AKA The Dynamic Functionista, who supports it in Min/Max.
The compiler applies Turner-optimization to combinator-patterns. If c.O=0, no optimization is performed. The function opt takes an expression x and returns the optimization of x:
O:1
opt:{
kx:O&({};"XK")~2#x
ky:O&({};"XK")~2#y
bx:O&:[{}~*x;({};"XB")~2#x 1;0]
by:O&:[{}~*y;({};"XB")~2#y 1;0]
iy:O&"XI"~y
:[kx&ky ;{({};"XK";({};x 2;y 2))} / S(Kf)(Kg) -> K(fg)
kx&iy ;{y;x 2} / S(Kf)I -> f
kx&by ;{({};({};({};"XB*";x 2);y[1]2);y 2)} / S(Kf)(Bgh) -> B*fgh
kx ;{({};({};"XB";x 2);y)} / S(Kf)g-> Bfg
bx&ky ;{({};({};({};"XC'";x[1]2);x 2);y 2)} / S(Bfg)(Kh) -> C'fgh
ky ;{({};({};"XC";x);y 2)} / Sf(Kg)-> Cfg
bx ;{({};({};({};"XS'";x[1]2);x 2);y)} / S(Bfg)h -> S'fgh
{({};({};"XS";x);y)}][x;y]} / Sfg
For example, with optimization disabled:
f 3 where f x is x+1
+--------------------@--------------------+
| |
+---------------@----------------+ +-------@--------+
| | | |
+------@-------+ +----@-----+ +----@-----+ +-@-+
| | | | | | | |
S +-------@-------+ +--@--+ +-@-+ S +---@----+ K n:1
| | | | | | | |
+--@--+ +---@----+ S +-@-+ K n:3 +--@--+ I
| | | | | | | |
S +-@-+ +--@--+ I K K S +-@-+
| | | | | |
K S S +-@-+ K v:+
| |
K K
The same expression optimized:
f 3 where f x is x+1
+-----@-----+
| |
+--@--+ +--@--+
| | | |
+-@-+ n:3 +-@-+ n:1
| | | |
C I C v:+
Optimized, as executable combinator code:
code"f 3 where f x is x+1" " C I 3(C + 1)"
SLACK uses a modified form of Bunda and Gerth's pairwise binding algorithm for languages such as APL and K which use Iverson notation.
A token has syntax category noun (n), unary (u), verb (v), adverb (a), or binary (b).
A table B specifies the relative binding strengths of the categories.
A table C specifies the category of the result (x y) of binding x to y.
SLACK's tables are:
B
vunab
-----
v 00155
u 00255
n 3 455
a
b
C
vunab
-----
v vvnvv
u vvnvv
n u nvv
a
b
In the following description of the Bunda-Gerth algorithm, (x y) indicates the binding of x and y, B(x y) denotes the strength of (x y), and [x y] denotes the result of (x y).
The algorithm A, adapted for SLACK, works this way:
Take an expression E. Starting at the right, scan left.
If E is empty or consist of a single element, then return E.
If E consists of two elements only:
E = a b
then return
E' = [a b].
In the general case,
E = .. a b c d e f
scan from the right and bind the first pair E[i] and E[i+1]
which satisfies the following condition:
B(E[i] E[i+1]) > B(E[i-1] E[i])
[N.B. For K, this condition is:
B(E[i] E[i+1]) > B(E[i-1] E[i]) OR
E[i] is a noun and E[i+1] is a noun.
Nouns associate to the right in K, to the left in SLACK]
If the condition remains unsatisfied, bind the leftmost pair.
For example, if the first drop in relative binding-strengths
occurs between (c,d) and (d,e), then E' would be:
E' = .. a b c [d e] f.
Continue reapplying A to the previous result until the result
is the same twice in a row.
For example:
2 + - 4 * foo 5 n v v n v n n 2 + - 4 * (foo 5) because foo and 5 are nouns n v v n v n 2 + - (4 *) (foo 5) B(- 4) < B(4 *) n v v u n 2 + - ((4 *) (foo 5)) B(- (4 *)) < B((4 *) (foo 5)) n v v n 2 + (- ((4 *) (foo 5))) nb: B(v v) < B(v n) n v n (2 +) (- ((4 *) (foo 5))) no drop, so bind the leftmost pair u n ((2 +) (- ((4 *) (foo 5)))) bind the remaining pair of items n
It is possible to extend the SLACK expression syntax to provide direct support for verb-nominalization by adding a type of operator whose semantic effect consists entirely in the transformation of the syntax category of its operand.
An elevator is an operator which either raises or lowers the syntax category of its operand. That is, if we think of noun, verb, and adverb as ordered:
noun < verb < adverb
We may then define raise and lower as:
raise noun -> verb raise verb -> adverb raise adverb -> adverb lower noun -> noun lower verb -> noun lower adverb -> verb
An elevator takes its operand on the right, and elevator x binds more tightly than any other pair.
A simple K interpreter which implements elevators may be found here.
For example, where { is lower and } is raise:
2 }foo 3 +---+----+ | | +-+--+ n:3 | | n:2 v:`foo
3#{+
+--+--+
| |
+-+-+ n:+
| |
n:3 v:#
The SLACK prelude, adapted from Grust's for SASL.
(not fully tested as of 4.March.2006):
id x is x
comp f g x is f (g x)
isnil x is x eq nil
until p f x is if p x then x else until p f (f x)
map f l is if isnil l then nil
else (f x):map f xs where (x is head l)
where xs is tail l
fold m z l is if isnil l then z
else m x(fold m z xs) where (x is head l)
where xs is tail l
append l m is if isnil l then m
else x:append xs m where (x is head l)
where xs is tail l
reverse l is if isnil l then nil else append (reverse (tail l))(head l)
filter p l is if isnil l then nil
else if p x then x:filter p xs
else filter p xs where (x is head l)
where xs is tail l
sort p l is if isnil l then nil
else insert p (head l) (sort p (tail l))
where insert pp e ll is if isnil il then [e]
else if pp e (head ll)
then e:ll
else (head ll):insert pp e (tail ll)
drop n l is if ~n>0 then l else if isnil l then nil else drop (n-1) (tail l)
take n l is if (n=0)|isnil l then nil
else x:take (n-1) xs where (x is head l)
where xs is tail l
at n l is if n=0 then head l else at (n-1) (tail l)
length l is if isnil l then 0 else 1+length (tail l)
init l is if isnil (tail l) then nil else (head l):init (tail l)
iterate f x is x:iterate f (f x)
repeat x is xs x where xs x is x:tail x
cycle xs is xs1 xs where xs1 x is append x (xs1 x)
splitAt n l is if ~n>0 then []:l
else if isnil l then []:[]
else ((head l):head xs):tail xs where (xs is splitAt (n-1) (tail l))
takeWhile p l is if isnil l then nil
else if p l then x:takeWhile p xs
else nil where (x is head l)
where xs is tail l
sum is fold (+) 0
product is fold (*) 1
zipWith f x y is if isnil x then nil
else (f hx hy):zipWith (f tx ty) where (hx is head x)
where (hy is head y)
where (tx is tail x)
where ty is tail y
K:
/ make a relational table with 1000000 rows
t:.+(`a`b`c`d;4 1000000 _draw 10)
/ converge on the indices
f:(&0<;&2>;&2=) / 3 index valued functions
i:{x y z x}/[_n;f;t`a`b`c] / i gets {x at y at z at x}OVER
select/[null;f;t`a`b`c]
where (select x y z is x@y@z@x)
where (t is .+[`a`b`c`d;draw 4 1000000(10)])
where f is [g;h;i]
where (g is &0<)
where (h is &2>)
where i is &2=
Compiles to:
\\ U(B* U(B* U(B K))(C(C' B*(C' B* /(cons null))(C cons)) (C' cons(C I(`a`b`c))nil)))(cons(S(C(B* C' B* @)@)(C @)) (cons(.:(+:(cons(`a`b`c`d)(cons(draw(4 1000000)(10))nil)))) (cons(U(B* U(B* U(B K))(C(C(B* C' B* cons)cons)(C cons nil))) (cons(&:(<(0)))(cons(&:(>(2)))(cons(&:(=(2)))nil))))nil)))
K:
x:"as";y:"awash"
p0:{{z(1+&)\(1_ x)&(-1_ x)-y}/[&1+#y;x=\:y;1+!#x]} /partial
p1:{{z(1+&)\(1_ x)&(-1_ x)-y}/[!1+#y;x=\:y;1+!#x]} /total
x:"ctagc";y:"tgac" 100000 _draw 4 /amino acid pattern
r0:{w+{&\z,(1+1_ x)&(-1_ x)-y}/[-w:!1+#y;x=\:y;1+!#x]}
r1:{(!1+#y)+{&\z,(1+1_ x)&(-1_ x)-y}/[&1+#y;x=\:y;1+!#x]}
x is"as" y is"awash" p0 x y is f/[&1+#y;x=\:y;1+!#x] where f x y z is z(1+&)\(1_x)&(-1_x)-y p1 x y is f/[!1+#y;x=\:y;1+!#x] where f x y z is z(1+&)\(1_x)&(-1_x)-y x is"ctagc" y is"tgac"@draw 100000(4) r0 x y where (r0 x y is(!1+#y)+f/[-!1+#y;x=\:y;1+!#x]) where f x y z is &\z,(1+1_x)&(-1_x)-y r1 x y where (r1 x y is(!1+#y)+f/[&1+#y;x=\:y;1+!#x]) where f x y z is &\z,(1+1_x)&(-1_x)-y
K:
gen:{(x&2=k)|3=k:+/adj x}
adj:{(r'r@;r'l@;l'r@;l'l@;l';r';r:-1!;l:1!)@\:x}
gen x is f { x } (adj x) where (f x y is (x&2=y)|3=y)
where adj x is +/[r'r x;r'l x;l'r x;l'l x;l'x;r'x;r x;l x]
where (r x is -1!x)
where l x is 1!x
Applied to an initial state:
M is [0 0 0 0 0 0;
0 0 1 0 0 0;
0 1 0 0 0 0;
0 1 1 1 1 0;
0 0 0 0 0 0]
gen M
where gen x is f x (adj x) where (f x y is (x&2=y)|3=y)
where adj x is +/[r'r x;r'l x;l'r x;l'l x;l'x;r'x;r x;l x]
where (r x is -1!x)
where l x is 1!x
(0 0 0 0 0 0
0 0 0 0 0 0
0 1 0 0 0 0
0 1 1 1 0 0
0 0 1 1 0 0)
K:
nth:{[g;i;n]*n{((?,/g@*x)_dvl,/x;*x)}/,,i}
n4:{,/+:'+(1!;-1!;1!';-1!')@\:x}
nth[n4 10 10#!100;45]4
nth g i n is *n f loop,,i where f x is [dvl(?,/g@*x)(,/x);*x] n4 x is ,/+:'+[1!x;-1!x;1!'x;-1!'x] nth(n4(10 10#!100))45(4)
\\ U(B* U(B K)(C' C(C(C C'(C I(#(10 10)(!:(100)))))(45))(4)))
(cons(B(B(B(B *:)))(C' C(C'(C' B*)(B* C loop),:),:)(C'(S' cons)
(C(B* S(B* dvl ?:)(C'(B*(/ ,))@ *:))(/ ,))(C' cons *: nil)))
(cons(B(/ ,)(B*(' +:)+:(S' cons(!(1))(S' cons(!(-1))(S' cons
('. !(1))(C' cons('. !(-1))nil))))))nil))
K:
U:{x%_sqrt x _dot x}
S:{[r;s]:[0>d:_sqr[s 1]+_sqr[b:v _dot r 1]-v _dot v:s[0]-*r;0i;0>t:b+e:_sqrt d;0i;0<u:b-e;u;t]}
I:{[r;h;o]:[~4:*o;:[~S[r;*o]<*h;h;h _f[r]/o 1];~h[0]>l:S[r]o;h;(l;U r[0]-o[0]-l*r 1)]}
T:{[r;o;d;z;l]:[0i=*h:I[r;z]o;0.;~0>g:h[1]_dot l;0.;0i=*I[(r[0]+(r[1]**h)+d*h 1;-l);z]o;-g;0.]}
N:{[n;o;i]0{x+T[(0 0 -4.;U(i+(y%4)-n%2),n);o;_sqrt 2^-42;0i,,3#0.]U -1 -3 2.}/+4_vs!16}
R:{[k;n]"P5\n",(5:n,n),"\n255\n",_ci _.5+15.9375*N[n*1.;C[k;0 -1 0.]1.]'+|@[n _vs!n*n;0;|:]}
C:{[k;c;r]:[k=1;(c;r);((c;r*3);(,(c;r)),C[k-1;;r%2]'+c+-3 3[2_vs 2 3 6 7]*r%_sqrt 12)]}
"temp.pgm"6:R[3]4
U x is x%sqrt(dot x x)
S r o is if 0>d then inf else if 0>t then inf else if 0<u then u else t
where (d is sqr(o 1)+sqr b-dot v v)
where (b is dot v(r 1))
where (v is (*o)-*r)
where (t is b+e)
where (e is sqrt d)
where u is b-e
I r h o is if ~type(*o) then f(S r(*o)) else g(S r o)
where (f x is if ~x<*h then h else h(I r)/o 1)
where g x is if ~x<*h then h else x:,U((*r)-(*o)-x*r 1)
T r h o d l is f(I r h o)
where (f x is if inf=*x then 0. else g(dot(x 1)l))
where g y is if ~0>y then 0. else if inf=*I[(*r)+((r 1)**x)+d*x 1;-l]h o then -y else 0.
N n o i is 0 f/+vs 4(!16)
where f x y is x+T[0 0 -4.;U((i+(y%4)-n%2),n)][inf;3#0.]o(sqrt(2^-42))(U -1 -3 2.)
C k r c is if 1=k then c:r else [c;r*3]:,[c;r]:(C(k-1)(r%2))',+c+(-3 3@vs 2(2 3 6 7))*r%sqrt 12
R k n is _0.5+15.9375*(N(n*1.)(C k 1.(0 -1 0.)))',+|amend1(vs n(!n*n))0 r where r is |:
F f n v is bwrite f("P5\n",show(n,n),"\n255\n",ci v)
F"c:/temp.pgm"4(R(3)4)
U(B U(B*(B U)(B* K U)(B*(B* K U)(B* K U)(B*(B* K U)(B* K U)(B*(B*
K K)(C(C(C I("c:/temp.pgm"))(4)))(C(C I(3))(4)))))))(Y(U(K(U(K(U
(B* U(B* U(B* U(B* U(B* U(B K)))))(C' C(C(B*(S' S')(B* C' B*)(C(B
* C(B* B* cons)(C' C(C'(C'(B*(B*(B _:)(B*(+(0.5))(*(15.9375))))))
(C(B*(B* C)(B*(S' '))(C C'(C *(1.0))))(C' C(C C(1.0))(0 -1 0.0)))
(B*(B ,:)(B* +: |:)(C(C' amend1(S vs(B !:(S * I)))(0)))))|:))(con
s(C' B(C' B* bwrite(,("P5\n")))(C(C' B*(B* , show(S , I))(,("\n25
5\n")))ci)))))(B(C' C(B*(B* B* cons)(B*(C'(C'(C' C))(C(B* C(B*(C'
(C' /.))C)C)(0))(+:(vs(4)(!:(16)))))(B(B(B(C' B +)))))(S'(C'(C'(C
'(C' C))))(C(B* C(B* C(B* C(B*(C' C)C)))(C(B*(C' C)(C(B*(B* C)(B*
C)(C B*(cons(0 0 -4.0)))))(C' C(C(B*(B* C)(B* C)(B* cons))(C'(S'
C)(C(C(B* B*(B* ,)+)(C' -(C %(4))))(C %(2)))I))nil))(cons inf(co
ns(#(3)(0.0))nil))))(sqrt(^(2)(-:(42)))))(C I(-1 -3 2.0)))))(B* c
ons(S(C' S'(B* S' cond(=(1)))(C cons)))(B*(B(S(B*(S' cons)(C cons
)(C' cons(C *(3))nil))))(B*(B(B ,:))(S(B*(S' cons)(C cons)(C cons
nil))))(C'(C'(S' B))(C' C(C(B*(B* '))(C -(1)))(C %(2)))(B(B* ,:
+:)(B*(C +)(*(@(-3 3)(vs(2)(2 3 6 7))))(C %(sqrt(12))))))))))(B(S
(B*(B*(cons(S %(B sqrt(S dot I)))))cons(S' U(B*(B U)(B* K K)(C'(S
' S)(B*(B*(S'(C' C))(C' C))(C' C))))(B* Y U(B* K U(B*(B K)(C(B* c
ons(B(B(B(B(B(S(C(B* cond(= inf)*:)(0.0))))))))(C'(C'(C'(S' C)))(
B*(B*(B*(B*(C' S)C)C)C)C)(C' dot(C I(1))))))(C(B* cons(B(B(B(B(B(
B(S(C(B* cond ~:(>(0)))(0.0)))))))))(C'(C'(C'(C'(C'(C' C)))))(C(B
* C(B* C(B* C(B* C(B*(C' C)(B*(B* C' cond)(B*(= inf)*:))))))(C' C
(C(B*(B* C)(B* C)(C' B* B* cons))(C(S' S'(B* B* + *:)(C(B*(B* +)*
(C I(1)))*:))(B(C *)(C I(1)))))(C' cons -: nil)))-:)(0.0)))nil)))
))))(C' C(B*(B*(C' cons)(C(B* U(B U)(S'(C'(B* K))(B*(B* S(B* S(B*
S(S' cond(B* ~: type *:)))))(C'(S'(C' S))C)(C(C' B)*:))(C'(S'(C'
S))C)))))(C' cons(C(B* C(S' C'(B* B* C(S' C(B*(B* cond ~:)(C <)*
:)I)))(C' /.))(C I(1))))(C' cons(C' C(B*(C' B*(B* B S(S' C(B*(B*
cond ~:)(C <)*:)I)))(B*(S cons))(B* ,:))(S' C(C(C' B*(B* B* - *:)
-)*:)(B(C *)(C I(1)))))nil))(cons(U(B* U(B U)(B*(B*(B U)(B* K U))
(B*(B* K U)(B* K K))(C' S(C(C' B*(B* B*(S' S)(C(B* C(B* C(B* cond
(>(0))))C)inf))(S' S))(C(B* C(B* C(B* cond(>(0))))C)inf))(B(C'(S'
S)(S(B* S(B* S(B* cond(<(0))))C)C))C))))(Y(U(B* U K(B* U K(B* U(
B* U(B U))(B*(S(B* S(B*(B* K)cons)(C(B*(B*(S' B(B* + sqr(C I(1)))
))S(B* S(B* - sqr)))(S(S'(S' dot))I))))(C(S(B* B*(S' cons)(S'(S'
+)))(B(C' cons)(S'(S' -)))))(B*(C' cons(C(C'(S' dot))(C I(1))))(c
ons(C(B* B - *:)*:))(C' cons(B(B sqrt))nil)))))))))nil)))))))))))
nil n () empty list, equivalent to []
null n _n atomic null
nan n 0n float NaN
Nan n 0N min int
inf n 0i float infinity
Inf n 0I max int
eq v x~y lazy list ~
head u *x head of lazy list
tail u 1_ x tail of lazy list
loop b x f1/y do y x times, while x do y
Loop b x f1\y scan version of loop
converge a f1/x while f1 x changes do f1 x
Converge a f1\x scan version of converge
if x then y else z :[x;y;z] conditional
is x:y definition
where {a:..} local definition
0:: aread ascii file read 0: awrite ascii file write 1:: kread k object file mapped read 1: kwrite k object file write 2:: kcopy k object file copy 2: load dynamic load 3:: connect open/close socket 3: set async 4:: type type 4: get sync 5:: show console display 5: kappend k object file append 6:: bread byte file read 6: bwrite byte file write
trace \x stop `0 time time elapsed (ms) disp show reduction tree first *:
Trace \x Wait 0:` Print `0:5:: Emit `0:,"."
apply @[x;y] dpply .[x;y] atrap @[x;y;:] dtrap .[x;y;:] amend @[x;y;:;z] dmend .[x;y;:;z] amend1 @[x;y;f1] dmend1 .[x;y;f1] amend2 @[x;y;f2;z] dmend2 .[x;y;f2;z]
In the latest version of SLACK, nouns bind tighter than verbs. For example, in
f 3 where f x is g x+h x where (g x is x+1) where h x is x+2
g x + h x is parsed (g x)+(h x).
The left-association mark { and the separator } have been eliminated. Nouns now associate automatically to the left. For example,
f g h x -> ((f g)h)x
Subdefinitions may refer to variables which occur in their superdefinitions:
f 3 where f x is g+h where (g is x+1) where h is x+2
g and h each "see" f's x.
Constructions like the following are now possible:
f 3 where f x is g+h where (g is h+3) where h is x+2
That is, in K:
f:{(g:h+3)+h:x+2}
The state-machine used to tokenize SLACK text has been simplified, and a bug relating to the tokenizing of strings with escape characters has been fixed.
A definition may have arguments which are not used in the body of the definition. For example,
f 3 where f x is 4
has the value 4.
A K expression within {}s is executed as a primitive:
{2+!:}'!3
(!0
,2
2 3)
{{2+!x}}'!3
(!0
,2
2 3)
Note the differences:
show"f 3 where f x is g'(!x) where g x is 2+!x"
+------------@------------+
¦ ¦
+--@--+ +--------@--------+
¦ ¦ ¦ ¦
+-@-+ n:3 +-----@-----+ +---@----+
¦ ¦ ¦ ¦ ¦ ¦
C I +---@----+ u:!: +--@--+ u:!:
¦ ¦ ¦ ¦
C +--@--+ B +-@-+
¦ ¦ ¦ ¦
+-@-+ a:' v:+ n:2
¦ ¦
B B
show"f 3 where f x is (2+!:)'!x"
+--------@---------+
¦ ¦
+--@--+ +-------@--------+
¦ ¦ ¦ ¦
+-@-+ n:3 +---@---+ u:!:
¦ ¦ ¦ ¦
C I B +---@----+
¦ ¦
a:' +--@--+
¦ ¦
+-@-+ u:!:
¦ ¦
v:+ n:2
show"f 3 where f x is {{2+!x}}'!x"
+-------@--------+
¦ ¦
+--@--+ +------@------+
¦ ¦ ¦ ¦
+-@-+ n:3 +--@---+ u:!:
¦ ¦ ¦ ¦
C I B +--@--+
¦ ¦
a:' n:{2+!x}
Copyright (c) 2005-2007, Stevan Apter. All Rights Reserved.