SLACK is a compiler for a lazy functional K, modelled on David Turner's SASL language, the precursor of Haskell and Miranda.

- 1 Introduction
- 2 The Functional Programming Language SLACK
- 3 The Compiler Stages
- 3.1 Tokenizer
- 3.2 Parser
- 3.3 SLACK Compilation and Combinators
- 3.4 SK Reduction Machine
- 3.5 Direct Execution of Combinator Expressions
- 4 Optimizing SK Compilation
- Appendix A. Parsing K Two-by-Two
- Appendix B. A SLACK Prelude
- Appendix C. K -> SLACK: Examples
- Converging boolean selection on tables
- Levenshtein distance
- Game of life
- Nth nearest neighbor
- Ray tracer
- Appendix D. SLACK Keywords
- Appendix E. Revisions

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 j v/i chase pointer starting at index j 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.a 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 ofloopconverge a f1/x while f1 x changes do f1 x Converge a f1\x scan version ofconvergeif 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.