A Strong Working Knowledge of K

Dennis Shasha
Courant Institute of Mathematical Sciences
Department of Computer Science
New York University
shasha@cs.nyu.edu
http://cs.nyu.edu/cs/faculty/shasha/index.html

Why is K Good?

Extremely fast.
Usually faster than the corresponding C program, e.g. present value calculation. Almost always faster than Sybase or Oracle.
Can do a lot and can do it easily (bulk data objects like tables, a passable graphical user interface, interprocess communication, web, and calculation).
Working in a single language reduces errors, increases speed yet further, and is more fun because you can concentrate on the algorithm.
(Note: Many errors and much overhead comes from integrating different languages, e.g. C/Perl/Sybase/GUI.)
Interpreted so very fast debug cycle; no seg faults; upon error can query all variables in scope. Bad part: no declared types so get some type errors you wouldn't otherwise get.

Why is K Bad?

Small existing market: around 100 programmers.
(But highly paid ones.)
A challenge to learn for those used to scalar programming languages like C, Java, Pascal, etc.
(This course attempts to make it easy to learn.)

Unit 1: Basic Language Features

Data types: character vectors, symbols, integers, floats.
Structuring operations: scalars, list/vectors, dictionaries.
Operators --- monadic and dyadic.
hello, world! program.
reading and writing files
reading argument list
generating test data
add, subtract, multiply, compare.
vector versions
reduction: over, scan
debugging techniques
exercise: find the mean and variance on a set of data.
defining functions (call by value)
exercise: dot product
exercise: matrix multiply
exercise: present value
exercise: solve linear equations

Data Types

Start k by typing
```
k
```
Character, surrounded by double quotes:
```
"a"
```
Strings (character vectors), surrounded by double quotes:
```
"Hello, world!"
```
Symbols are atoms but displayed as alphanumerics, preceded by a left quote:
```
`Hello
`"Hello, world!"   / need the quotes because of the space
```
Numbers:
```
15
16.2
```

Structuring Primitives: scalars, list/vector, dictionary

A scalar is a single integer, float, symbol, or character.
```
"a"
`fun
2
3.2
```

A vector is a sequence of scalars of the same type, possibly with duplicates:

4 2 5 67 2
(4;2; 5; 67; 2)  / equivalent to the above

`good `better `best
(`good; `better; `best) / equivalent to the above

"good" / a sequence of characters is a vector
("g";"o";"o";"d") / a sequence of characters is a vector

A vector is a kind of list. But lists may have mixed types. (These are called lists of general form in the reference manual.)
```
("hello"; `hello; 15; `abc)
```
Lists (including vectors) are indexed as if they were arrays:
```
x: 3 5 2 17 2
x[0]
x[3]
```
Lists are grown by concatenation:
```
x , x
```
Lists can be created from scalars:
```
5
,5
```
Dictionaries are often used as a representation of tables. They are created by forming multiple lists, one for each column. We will dicuss operations on dictionaries later.
```
comp.name: `zurich `aetna `"met life"
comp.assets: 43 23 35
`show $ `comp
```

Monadic vs. Dyadic Operators

K uses the term "monadic" to describe operators that take only one scalar, vector, or dictionary argument. Dyadic operators take two arguments.
The same symbol may be used in both ways and may have quite different meanings depending on whether it is used monadically or dyadically.
For example, vertical bar is max when dyadic and reverse when used monadically.
```
4 | 5
32 64 | 21 89

| 32 64 21 89
```
Another example occurs with asterix.
```
4 5 * 2 3 / multiplication

* 4 5 2 3 / first
```
`"Hello, world!" / symbol version
Note: In large arrays, it is better to represent data as symbols, because the same symbol is stored only once. Convert from string to symbol using backquote dollar. Convert from symbol to string using dollar.

Read and Write Files

The 0: (zero colon) operator writes strings to files in ascii form.
```
"foobar" 0: "Hello, world!" 
```
The 0: (zero colon) operator writes character vectors to the file. Lists of charactor vectors are separated by a newline. Try an example on your own.
One can also read in a file, but in that case the file name is on the right side.
```
a: 0: "foobar" / comes back as list whose zeroth element is string
```
1: writes data in K internal format which is binary. This allows non-string items.
```
"foosymb" 1: `"Hello, world!" / write a symbol to a file 
```
Reading is a bit more subtle. NT's treatment of memory mapped files causes us to make the following rule:
If your program writes a file, your program should use 2: when reading the file (in version 2.2 and later). If your program only reads a file, then use 1: to read because 1: uses memory mapping whereas 2: reads the data.
In our case, we have written to foosymb, so we have to read using 2:.
```
asymb: 2: "foosymb"
 
```
Append to a file using 5:. Typical use: one is appending the description of a server operation to the end of a file. An operation is described by the list (`op1; "arg1"; `arg2). 5: is like comma in that it takes two lists and appends the second to the first. Therefore if one says
```
"foo" 5: (`op1; "arg1"; `arg2)
```
file "foo" will be extended by three more elements. But this is not good since the end of this operation does not have a clear boundary.
Therefore, it is better to say
```
"foo" 5: ,(`op1; "arg1"; `arg2) 
```
because that appends a single element consisting of the list
```
(`op1; "arg1"; `arg2).
```
Ex: "foobar2" 5: ,"Hello, world"
"foobar2" 5: ,"sapphire"
Note: Admittedly, 0:, 1: etc. are not very mnemonic. Refer to the reference card if you forget.
Note: On neither NT nor UNIX should you write mapped files remotely to a different machine for both performance and correctness reasons.
Note: If your process hangs when you are reading a file, it is probably badly formatted.

Arguments to Programs

If you have a program called foo.k, then typing
```
k foo abc d ef
 
```
will put into the variable _i within the foo program the strings "abc", "d", and "ef".

Generate Data

It is often convenient to generate test data for new applications.
Enumerate n (denoted !n) generates all numbers from 0 through n-1 inclusive.
```
x: !100 
```
Draw a bunch of random numbers.
Generate 1000 numbers between 0 and 18 with replacement.
```
a: 1000 _draw 19 
```
Generate 19 numbers between 0 and 18 without replacement. ( Warum nur neunzehn?)
```
a: 19 _draw -19 / generate 1000 numbers between 0 and 18 without replacement
```
One more kind of random number: random numbers between 0 and 1.
```
b: 100 _draw 0 
```
Note: Subsequent uses in same program use different seeds (you don't have to bother setting it). Different invocations of same program use same starting seed (good for repeatability after debugging).

Add, Subtract, Multiply, Divide, and Compare

Note that arithmetic operators can work either on scalars or numeric vectors of the same length.
```
5 + 3
5 6 7 - 10 20 30
5 6 7 * 3
6 7 8 9 % 2
```
Ok, you may not be used to having the percent sign be used for division, but you'll learn to like it.
Comparison can be scalar to scalar, vector to vector or scalar to vector. Explain the presence and absence of parens.
```
4 > 2
4 6 > 2 8
(!10) > 7 
4 > !10
```
Note: Scalar op vector works for built-in "atomic" operations, like arithmetic. Manual tells which ops are "atomic" in this sense.

Vectors to Scalars and to Other Vectors

# 5 6 7 6 7 8 / count elements
+/ !100 / sum elements (faster than Gauss)
+\ 9 4 6 / the scan operation (first element, then first plus second, etc)

Debugging

When an error occurs, K tells you which routine is in error and then leaves you with a greater than sign (>) as a prompt.
At that point, you can examine the program variables in that context. You can also analyze the program variables in calling contexts by hitting single quote (').
You can trace a computation by putting backslash (\) in front of lines to be traced and putting the following at the beginning of the program:
```
\e 1
\b t      
```

Time Functions

K has a function
```
_t
```
that gives the number of seconds after Jan 1, 2035, which is a Monday. (So, this number is currently negative.)
One can get the local time by typing
```
_ltime _t
```
One can also get the Greenwich Mean Time by typing
```
_gtime _t
```
The day value for Greenwich Mean Time is obtained from the above by taking the first member of that list:
```
* _gtime
```

To get the day of week, one types

days: `Mon `Tues `Wed `Thu `Fri `Sat `Sun 
days @ (_ _t%86400) ! 7

Exercises

Find the mean of a vector.
Find the variance of a vector.
Note: For online help with the functions, try
```
 \_ 
```

Solution: Average

count: #v
sum: +/v
sum % count
Note: 0 % 0 is 0.0.

Solution: Variance

avg: (+/v) % (#v)
squares: v * v
avgofsumofsquares: (+/ squares) % (#squares)
var: avgofsumofsquares - (avg * avg)

Functions can Make This Easier

avg:{[x] (+/x) % (#x)}
avg[!10] / finds average of integers from 0 to 9
Note: We have written x as a formal here, but x, y, z are the first three formals if none are mentioned. Would you like to rewrite variance?

Solution: Variance as a function

var:{[x]
 a: avg[x*x]
 b: avg[x]
 a - ( b * b)}

Note: We can return from within a function by writing colon (:) before the variable to be returned. Otherwise, the last line of the function is the return value. (So, a newline before the final right curly bracket changes the meaning of the function.)

Exercises

Find the dot product of two vectors v1 and v2.
Multiply two square matrices.
Find the present value of a yearly income stream a, given discount rate d and payout intervals e. The circumflex operator (^) is power.
Try this again when you have a vector of discounts, because the discount rate varies with the yield curve.
Using the _lsq function, try to solve the following puzzle.
Let a represent alice's net balance.
Let b represent bob's net balance.
Let c represent carol's net balance.
We are told the following facts:
2.1a + 3b + 4c = 30.5
1.1a + b + c = 10.5
4.1a + 3b + 2c = 40.5
Your job is to find a, b, and c.

Solution: Dot Product

v1 * v2 / this is the element by element product of v1 and v2.
+/ v1 * v2 / this is the sum of the element by element products.
dot:{[v1; v2] +/ v1 * v2}

Solution: Matrix Multiply


n: 100
x: (n*n) _draw 10000
m1: (n;n) # x / note that n n # x won't work because n n is function app
x: (n*n) _draw 10000
m2: (n;n)  # x

dot:{[x;y] +/x*y}

r: m1 dot/:\: +m2  / dot product with the transpose.

Note that the order of the adverbs
```
 /:\:
 
```
is important. Reversing the order gives the transpose. This order causes dot to multiply the top row times all the columns first (forming the first row of the result).

Note: adverbs

Each left takes one element at a time from the left argument.
```
seq1: "abcde"
seq2: "012"
seq1 ,\: seq2
```
Each right takes one element at a time from the right argument.
```
seq1: "abcde"
seq2: "012"
seq1 ,/: seq2
```

Each left each right does a cross product.

seq1: "abcde"
seq2: "012"
seq1 ,\:/: seq2

/ note contrast with
seq1 ,/:\: seq2

/ This makes seq2 vary more frequently than seq1.

Solution: Present value revisited

This is what we presented before, but this assumes a constant discount rate.

presentval:{[a; d; e]
  +/ (a%(d^e))}

amount: 100 125 200 150 117 / income stream
discountrate: 1.05 / compounding rate
exponent: 0 0.5 1 1.5 2 / how many years out

presentval[amount;discountrate;exponent]

Here is the formulation for a vector of discounts.

pvgeneral:{[a; d] +/ a * d}

amounts: 100 125 200 150 117 / income stream
discounts: 1 0.9 0.8 0.7 0.55
pvgeneral[amounts;discounts]

Solution: Bank Balances

Recall that the balances have to satisfy the following:
2.1a + 3b + 4c = 30.5
1.1a + b + c = 10.5
4.1a + 3b + 2c = 40.5

A: (2.1 3 4; 1.1 1 1; 4.1 3 2)
 / For the purpose of this function,
 / each list indicates a column.
 / Since we want them to be rows, flip the matrix.
A: +A

y: (30.5 10.5 40.5)

x: y _lsq A

/ Check that this works by typing
+/A * x

Advanced Topic

Here is code you can use to strip out all the executable code in these notes.


/ given a file, take out those lines that
/ are between  and 
/ where those strings are at the beginning of a line.
a: 0: _i[0]
out: ()
printit: 0

decide: {[line]
  if[line ~ ""
	printit:: 1
	:()
  ]
  if[line ~ ""
	printit:: 0
	:()
  ]
  if[printit = 1
	out,: ,line
  ]
}

decide'a
str: (_i[0]),"out.k"
str 0: out