An Introduction to K through Examples

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

First Items of Business

Download K from the Kx Systems web site. This takes about one minute.
Your goals in this course.
Course philosophy:
- start with examples
- evolve to concepts
- program them

Quick Tour of K

Basic arithmetic in K:


2+3
3*2

/ Right to left precedence:

3*2+5 / yields 21

/ Assignment

abc: 3*15
cdf: 15% 3 / division is percent sign
x: 5 3 4 10

/ scalar-vector operations

3*x

Vector style operations:
```
/ prefix sum

+\3*x

/ element by element operations

x*x

/ cross-product of all elements
/ read this "times each right each left"

x*/:\:x

/ generating data

y: !13

/ twelves table, each left, each right (cross-product)

y*\:/:y
```
Tour of GUI and Tables
```
`show $ `y

y:y*y / variable multiplication causes gui representation to be updated. 
/ Try updating the gui and they will be updated.

/ tables

n: 1000
names: `bob `ted `carol `alice
emp.salary: 20000 + n _draw 10000
emp.name: names[n _draw #names]
emp.manager: names[n _draw #names]

`show $ `emp

/ modify salary to be twice the salary

emp.salary: 2*emp.salary

/ create a chart

emp.salary..c:`chart
`show $ `emp.salary
```
Tour -- Functions
```
/ present value calculation

presentval:{[amount; discount; exponent]
  +/ (amount%(discount^exponent))}

amount: 100 125 200 150 117
discountrate: 1.05
exponent: 0 0.5 1 1.5 2 

presentval[amount;discountrate;exponent]
  
```
Lectures of Dennis Shasha

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

 
```
Lectures of Dennis Shasha

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

Unit 2: Conditionals, Adverbs, and String Manipulation
- Like C, K has conditionals.
- K also has loops, though programs usually run faster and are shorter if you avoid using them.
- We discuss these features and the adverbs that often render loops unnecessary.
- Strings are a good example.
Topics
- conditionals
- loops to go through arrays
- each operator to avoid loops
- exercise: VicePresident salary raises
- each operator for listwise differences, counting upticks
- exercise: delete blanks
- functions, recursive functions, currying, lambda expressions
Conditionals
- ```
x: 5
y: 7
if[x < y
  min: x
  max: y
]
if[~ x < y
  min: y
  max: x
] 
```
- ```
min: :[x < y; x; y] 
/ if statement follows condition and else statement comes after.
max: :[x < y; y; x] 
```
- Note: The second form of conditional returns a value.
While Loops
- Apply f to the array members in order.
- ```
n: #arr
i:0
out:()
while[ i < n
	out,: f[arr[i]]
	i+: 1
]
out
```
- Note: provided the f on arr[i] doesn't interfere with the f on arr[j], this entire loop can be done with f'arr This is read "f each arr".
Do Loops
- Initialize arr from input.
- ```
input: 100 _draw 5
n: _ (#input) % 2
arr: n # 0 / initialize
i: 0
do[n
	arr[i]: input[i]
	i+: 1
]
```
- Note: Could do this more efficiently as follows:
```
input: 100 _draw 5
n: _ (#input) % 2
arr: input[!n]
```
- Even better:
```
arr: n # input
```
Each Operator
- The each operator, symbolized by just a ' following immediately after some function f says "apply f to every member of the following list". This is like mapcar in Lisp if you happen to know that. Here we increase all salaries by a factor of 1.1.
- ```
sal: 200 250 220 100
f:{[x] x*1.1}
sal: f'sal
```
- (Advanced note) In this case, because f is made up only of multiplication, we can apply it to the entire array of salaries just as multiplication can, so we could say simply:
```
sal: f[sal]
```
Exercise: VP Salary Raise
- Create a table of employees with three ranks.
```
ranks: `pres `vicepres `dilbert
emp.rank: ranks[100 _draw 3]
emp.salary: 50000 + 100 _draw 950000
```
- Want to raise all vice president salaries by 10% but all others by 5%.
VP Salary Raise, Solution 1
- Define a function, then apply it to each rank-salary pair.
```
g:{[rank; salary]
	:[rank = `vicepres
		salary * 1.1
		salary*1.05]}

emp.salary: g'[emp.rank; emp.salary]
```
VP Salary Raise, Index Approach
- ```
f:{[i]
  :[emp.rank[i] = `vicepres
	emp.salary[i]*1.1
	emp.salary[i]*1.05]}
```
- Note that the if-then-else will be the last statement, so will be the return value.
```
indexes: !#emp.salary
emp.salary: f'indexes
```
- Some people like applying each on single arguments.
VP Salary Raise, Vector Approach
- The most efficient way to do this query is to do it as a vector operation. In this strategy, we will locate all the vicepresidents, multiply them by 1.1 and multiply everyone else by 1.05.
```
i: & emp.rank = `vicepres / vice-presidents
j: & ~ emp.rank = `vicepres / non-vice presidents
emp.salary[i]*: 1.1
emp.salary[j]*: 1.05
```
An Idiom
- Sometimes you want to get all the differences in a list. e.g. the differences in the list 3 17 11 12 are 14 -6 1.
- There is an idiom for this that involves an advanced use of each. Let's say x is the list.
```
-': x
```
  Read this "minus prior" x.
- You can also do "ratio prior."
```
%': x
```
Example: Good stock
- Suppose you have the prices of some stocks at the closing of a set of days. These are in the vector p. You want to find out whether the stock had more up or down days in p.
- ```
goodstock:{[p]
  diffs: -': p / day by day differences
  ups: diffs > 0 / 1 on day of increase, 0 otherwise
  downs: diffs < 0
  (+/ups) > (+/downs) }
```
Recursion and Cousins
- Recursion in K works as you would expect: just put the function inside itself. Here is the factorial function: n! = 1 * 2 * 3 * ... * n
- ```
fact:{[n]
  if[n < 2
	:1
  ]
  :n*fact[n-1]
}
```
- ```
fact:{[n]
 :[n > 0
	n*fact[n-1] / the initial : is a return
	1] }
```
- There is another form though in which you use the symbol _f for the recursive form. (Since the underbar is already overloaded in K, I don't like this so much.)
- ```
fact:{[n]
 :[n > 0
	n*_f[n-1]
	1] }
```
More in the spirit
- ```
fact1:{:[x;x*_f x-1;1]}	/ advanced
```
- Another approach is purely functional:
```
fact2:*/1+!:		
```
  What this does is add 1 to the numbers between 0..n-1 and multiply them all.
Currying
- A curried function is a partially evaluated one. For example, suppose we have a function to compute the quadratic formula.
- ```
quad:{[a;b;c]
 x: ((-b) + _sqrt((b^2) - 4*a*c)) % (2*a)
 y: ((-b) - _sqrt((b^2) - 4*a*c)) % (2*a)
 :(x;y)}
```

Suppose the coefficient of the high order term (a) is always 1 in a setting we call "normalized". Then we can define

normquad: quad[1]
quad[1;4;2] = normquad[4;2]

Lambda Expressions

We don't need to give functions a name if we are using it just once. The following for example is a function for factorial applied to 5.
```
{[x] :[x>0; x*_f[x-1]; 1]} 5
```

Executing Strings

One of the many advantages of interpretation is that one can easily generate functions on the fly. The operation that does this is the simple period. For example the following yields 25.
```
f:{[x] x*x}
str: "f[5]"
. str
```

Exercises

Try to delete all blanks from a string.
Try to delete the initial blanks.
Write a string edit (sed) function that replaces all instances of string old by string new in a line.
Try to delete the trailing blanks.

Delete All Blanks

deleteallblanks:{[s]
  x: s = " " / gives binary 1 or zero saying whether s is blank or not.
  i: & ~ x / gives all indices that are not blank
  s[i]}

Delete Leading Blanks

deleteleadingblanks:{[s]
  x: s = " " / 1s whenever blank, 0s elsewhere
  (x ? 0) _ s} / drop up to first non-1.

Delete Trailing Blanks

Use the deleteleadingblanks function on the reversed string.
```
deletetrailingblanks:{[s]
  | deleteleadingblanks[|s]}
```

Find Most Consecutive Ones

Find the maximum number of consecutive ones in a zero-one vector.
```
f:{[x;y] :[y=0;0;x+y]}
|/ f\flags
```

The Road to Ruin

You are an insurance company. You have a revenue stream which you can predict and m possible payment streams whose values depend on the likelihoods of accidents and nature. Here are your initial conditions:


/ probability of ruin.
/ Given capital, a flow of revenue
/ and m possible payment scenarios that are equi-probable
/ what is the probability of ruin?
n: 200 / time periods
m: 100 / payment scenarios

capital: 1000
revenue: n _draw 2000

payments:(m;n) # ((m*n) _draw 2000)

Your job is to determine whether you will ever have a net negative capital, i.e. the sum of your capital plus your accumulated revenue is less than the sum of your payments. The solution follows. Don't look until you think about it.


/ the ruin function takes two flows (in and out)
/ and determines if the cumulative sum for out
/ is at any point greater than the cumulative sum for in
/ plus the capital.
/ If so, ruin returns 1, else 0.
ruin: {[in; out]
 in[0]+: capital / add in the capital as the initial value
 incum: +\ in
 outcum: +\ out
 |/outcum > incum}

numruins: +/ruin[revenue]'payments

("probability of ruin is"; numruins % m)

html> Lectures of Dennis Shasha

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

Unit 3: Tables and Database Facilities

In K, one can implement tables and do selects, group bys, and sorts in a natural way. The cool thing is that the operations take place on ordered data allowing for far more efficient implementations than using sybperl or embedded SQL.
In this unit we concentrate on queries. Later we will discuss transactions.

Topics

tables and how to form them.
the K tree and its relationship to tables
select, sort, group, etc.
exercise: the cost of goods sold.
exercise: typical table queries.
exercise: relational algebra

Constructing Tables, method 1

One can form tables by creating fields and assigning to them. For example, emp.id, emp.name, emp.salary.

names: (`bob; `carol; `ted; `alice)
emp.id: 100 _draw 999999999 / social security numbers
emp.name: names[100 _draw 4]
emp.salary: 100 _draw 1000000

`show $ `emp / display it

Constructing Tables, method 2

Since tables are just an array of lists, one can also form them by constructing the lists first and then using a dictionary constructor.

names: (`bob; `carol; `ted; `alice)
name: names[100 _draw 4]
id: 100 _draw 999999999 / social security numbers
salary: 100 _draw 1000000

/ now we construct the table
emp2: .+(`id`name`salary;(id;name;salary))

/ now we display it
`show $ `emp2

The K (data and function) tree

Like Unix, NT, and the Mac, K organizes data into a tree. When you first invoke the system, you are in a subtree which is denoted dot (.k).

When you create a table, that creates a subnode within the current node.
One can descend into that node by using \d
One goes up by typing \d ^
One finds the current node by typing \d

names: (`bob; `carol; `ted; `alice)
name: names[100 _draw 4]
id: 100 _draw 999999999 / social security numbers
salary: 100 _draw 1000000

emp3: .+(`id`name`salary;(id;name;salary))

id[!10] / returns nothing
\d emp3

\v  / list elements of the node

id[!10] / returns the first 10 ids
name[!10] / returns the first 10 names

\d ^
name[!10] / returns nothing


\d . / root node

(Navigation in the tree): Just as other operating systems have absolute references (e.g. /usr/bin in Unix or c:\winnt\system32 in NT), so does K. All such references start with the root node dot (.). Recall that the initial node is

.k

For example,

names: (`bob; `carol; `ted; `alice)
name: names[100 _draw 4]
id: 100 _draw 999999999 / social security numbers
salary: 100 _draw 1000000

\d

emp3: .+(`id`name`salary;(id;name;salary))

\d .k.emp3
newtable: .+(`new1 `new2;(!10; 10 + !10))

\d

\d .k.emp3.newtable  / specifying a location with an absolute path

\d

\v


\d ^ / go up

\d

\d newtable / go back down using relative navigation

\d

\v

As a final note, if you run a script starting in node x, you will end up in x even if the script ends in some other node. For example, put the above into a file and fun the file. After the script is done, type
```
\d
```

Summary of Using the Tree

Purpose:
The K tree stores variables.
The Windows tree stores files.
Root:
The root of the K tree is dot (.)
The root of a Windows file system is backslash as in c:\
Absolute path:
The absolute path from the root in the K tree is indicated by a sequence that begins with a dot and has dots between each directory in the path, as in
```
.dir1.dir2.dir3.v
 
```
Windows uses backslashes
```
c:\dir1\dir2\dir3\v
 
```
Relative path:
The relative path from a directory is also a sequence of names and dots but does not begin with a dot. For example if dir1 has subdirectory dir2 which has subdirectory dir3, then descending to dir3 from dir1 requires the K command:
```
\d dir2.dir3
 
```
The corresponding command in windows is
```
cd dir2\dir3
 
```
Finding out which directory one is in requires using the K command
```
\d
 
```
The windows equivalent is
```
cd
 
```
Going up from a subdirectory to a superdirectory in K entails using the up-caret.
```
\d ^
 
```
The equivalent in windows is
```
cd ..
 
```

Using Tables

Find the indexes of people who make more than 123,000 dollars.
```
\d . / go back to root
i: & emp3.salary > 123000
```
Find the names of those people.
```
emp3.name[i]
```
How many make more than 250,000?
```
# & emp3.salary > 250000
```
Like "where" (monadic &), sorting in K returns the indexes of the sorted result. Technically, this is the permutation that would give the field in sorted order.
```
i: < emp3.salary
emp3.salary[i] / salaries in order
emp3.name[i] / names ordered by salary
```

Partitioning (Group by) and Tables

Suppose we want to find the sum of salaries of each employee name.

part: = emp3.name / list of entries, each holding
	/ an indexes of everyone with same name.

Then we form the names without duplicates in same order as the lists.
```
r.people: ? emp3.name 
```

r.sumofsalaries: +/'emp3.salary[part] 
/ where the +/' means sum over each / partition.

Exercise

Find the names of people who have the median salary.
Note: You may find it useful to know that _ means floor (take integer less than or equal to a number, e.g. 3 = _ 3.2 and % means divided by.

Names Having the Median Salary

Sort and find the median.

i: < emp3.salary
midindex: _ (#i) % 2 / floor of the middle
midsal: emp3.salary[i[midindex]]
j: &emp3.salary = midsal
emp3.name[j]

Exercise: Assemble a Table with Grouping

Given a table of purchases

purchase.date: (!10), (|!5)
purchase.item: (10 # `candy), (5 # `toys)
purchase.qty: 100 + 15 _draw 400
purchase.price: 20 + !15

form the itempurchase table which holds each item with all the purchase, qty and price information.

itempurchase.item: ? purchase.item / remove duplicates
part: = purchase.item / gives itemsets in the same order as above
itempurchase.qtys: purchase.qty[part]
itempurchase.price: purchase.price[part]
itempurchase.date: purchase.date[part]

Exercise: FIFO Accounting

Suppose we are a trading company. Using FIFO accounting, the cost of selling w widgets is the cost of the first w widgets we have bought. This is a difficult query to do in a relational context, because relations don't support order. How would you do it?
```
purchase.date: (!10), (|!5)
purchase.item: (10 # `candy), (5 # `toys)
purchase.qty: 100 + 15 _draw 400
purchase.price: 20 + !15 

sold.item: `candy `toys
sold.qty: 123 756

result.item: ()
result.cost: ()
```

Cost of Goods Sold: solution

The first part of the solution is to formulate the functions that apply to each vector.


/ given an item, the quantity sold, the quantities bought in order
/ and the prices of those purchases, 
/ produce the cost of selling that item.
cogs:{[item; soldqty; boughtvec; pricevec] 
 scanqty: +\boughtvec
 i: (soldqty < scanqty) ? 1 / finds the first point when that holds 
 if[i > 0
        cost: +/ boughtvec[!i] * pricevec[!i]
        cost+: (soldqty-scanqty[i-1]) * pricevec[i]
 ]
 if[i = 0
        cost: soldqty*pricevec[0]
 ]
 result.item,: item
 result.cost,: cost
}

/ takes an index of the sold table.
setup:{[sellindex]
 item: sold.item[sellindex]
 soldqty: sold.qty[sellindex]
 i: & purchase.item = item
 boughtvec: purchase.qty[i]
 pricevec: purchase.price[i]
 dates: purchase.date[i]
 j: < dates
 boughtvec: boughtvec[j]
 pricevec: pricevec[j]
 cogs[item;soldqty;boughtvec;pricevec]
}
 

setup'!#sold.item

`show $ `sold
`show $ `result
`show $ `purchase

More Exercises

Given a table for sales:

/ sale(saleid, amount, district, salesagent)
size: 10
sale.saleid: !size
sale.amount: 5000 + size _draw 100000
districts: `rich `posh `extravagant
sale.district: districts[size _draw 3]
salesagents: `alice `bob `carol `fred
sale.salesagent: salesagents[size _draw 4]
`show $ `sale

Find all sales by salesagent fred.
Find the sum of sales by district.
Find the sum of sales by district of fred.
Find the top three sales per district. If there are fewer than three sales in a district, then don't give any of them.
Find the sum of sales by district and sales agent
select salesagent, district sum(sale)
from sale
group by salesagent, district

Sales Solutions

/ I. Find all sales by salesagent fred.
i: & sale.salesagent = `fred / Find the indexes of sales by fred.
+sale[;i] / the initial + puts it in record format

/ II. Find the sum of sales by district.
part: = sale.district
+(?sale.district; +/'sale.amount[part])

/ III. Find the sum of sales by district of fred.
i: & sale.salesagent = `fred
part: = sale.district[i] 
   / Among those in i, find groups with the same district.
+(?sale.district[i]; +/' sale.amount[i][part])


/ IV. Find the top three sales per district.
/ If there are fewer than three sales in a district,
/ then don't give any of them.
top:{[number; district]
  i: & sale.district = district / find the indexes in that district
  amounts: sale.amount[i] / find the sales there
  orderedvec: amounts[> amounts] / sort by amount
  :[number < #orderedvec / depending on number in result, take the top
        district, ,orderedvec[!number]
        district, ,orderedvec]}


top[3]'?sale.district


/ V. Find the sum of sales by district and sales agent
/  select salesagent, district sum(sale)
/ from sale
/ group by salesagent, district
part: = sale.salesagent,' sale.district / need the each to get all pairs
groupers: ? sale.salesagent ,' sale.district
groupers ,' +/'sale.amount[part]

/ VI. Find pairs of salesagents who work in the same district.
/ select s1.district, s1.salesagent, s2.salesagent
/ from sale s1, sale s2
/ where s1.district = s2.district
findcross:{[district]
 i: & sale.district = district
 all: sale.salesagent[i] ,\:/: sale.salesagent[i]
 allnodups: ?,/all
 district ,/: allnodups}

findcross'?sale.district

Exercise: Most of Relational Algebra

Relational algebra consists essentially of select, project, union, intersect, and join. We have already seen how to do select and project. Let's do union, intersect, and foreign key join.


/ finds the non-duplicated union of two lists
union:{[x;y] ?x,y}

/finds intersection of two lists
intersect:{[x;y] x[& x _in\: y]}

/finds set difference of two lists x - y
differ:{[x;y] x[&~ x _in\: y]}

/ select r1 from r1, r2 where r1.a1 = r2.a2
/ This is  for a foreign key join with r2.a2 as the key field,
/ so there is at most one r2 tuple with a given a2 value.
foreignKeyJoin:{[r1;a1;r2;a2]
        r1[;& r1[a1] _in\: r2[a2]]}

subset:{[subList; superList]
 &/ subList _lin superList}

Try to find apply this to sets of your choosing. Then try implementing a general join.

Importing Large Text Files to Tables

(advanced topic) Sometimes, you have extremely large text files and you must read them in.

In this case we have a file having three fields, a string, integer, and float. The widths are 5, 4, and 8 respectively.


jack 23    45.633  
jill 24    55.33   
ed   4     5.33    
ellen20    444.3   
jack 23    45.633  
jill 24    55.33   
ed   4     5.33    
ellen20    444.3   
jack 23    45.633  
jill 24    55.33   
ed   4     5.33    
ellen20    444.3   
jack 23    45.633  
jill 24    55.33   
ed   4     5.33    
ellen20    444.3   
jack 23    45.633  
jill 24    55.33   
ed   4     5.33    
ellen20    444.3

Here is the code, called import.k, to read this and output it to three files each representing one column. I've loaded the columns here, but you can adjust both their names and their types. This code reads the data in chunks.


/ k import infile 
/ infile is for text and outputs are fieldnames
infile:  _i[0] / take input from this file

size: 30 / chunk size for importing



process:{[infile;start;size; types; sizes]
 while[#*b:(types; sizes) 0:(infile;start;size)	
	/ while more data
    (fieldnames) 5:' b
    start+:size
  ]				/increment starting byte
}

fieldnames: `id `age `salary
fieldnames 1:' 0 #' (`;0;0.0)   / initialize this
types: "SIF " / last one is for the carriage return/linefeed
fieldsizes: 5 6 8 1  / field widths, the last 1 is for carriage return.
/ calculate size to be an integral number of fieldsizes
multiplier: _ size % (1 + +/fieldsizes)  / 1 is for carriage return/linefeed
size: multiplier * (1 + +/fieldsizes)
process[infile;0;size;types;fieldsizes]

Lectures of Dennis Shasha

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

Unit 4: Interprocess Communication

In K, the basic interprocess communication paradigm consists of a client and a server (though each may take on both roles).
One starts the server with a port number on a well-known machine.
The client can then invoke procedures on that machine-port combination.

Topics

mechanics
examples
exercises

Mechanics of IPC

Set up a server. It will respond to synchronous remote procedure calls through a function that happens to be called
.m.g
The port we have chosen is 1234.
```
k server.k -i 1234
 
```
Inside the client, calls to the server can be done as follows:
```
retval: (`machinename; 1234) 4: (`functname; (`param1; `param2))
 
```
Thus, one is calling the other machine with two arguments: a function name and a list of parameters.

Example server.k


/ factorial
fact:{[n]
 :[n > 0
	:n*fact[n-1]
	:1]
}

/ quadratic formula
quad:{[a;b;c]
 x: ((-b) + _sqrt((b^2) - 4*a*c)) % (2*a)
 y: ((-b) - _sqrt((b^2) - 4*a*c)) % (2*a)
 :(x;y)
}

/ responds to messages one at a time; 
/ buffering is automatic.
/ list[0] is the function. list[1] is the list of arguments.
.m.g:{[list]
 args: list[1]
 if[list[0] = `fact
	:fact[args[0]]
 ]
 if[list[0] = `quad
	:quad[args[0]; args[1]; args[2]]
 ]
}

Example client.k


machine: _h	/ illustrates case where client and server
	/ run on the same machine
machine: `

ret: (machine; 1234) 4: (`fact; ,5)
ret / should be 120

ret: (machine; 1234) 4: (`quad; (1; 4; 0))
ret / should be 0 -4

It is also possible to do asynchronous comunication with a server using 3: instead of 4:. See your reference card.

Lectures of Dennis Shasha

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

Goal of the GUI

Make it simple to do common operations.
Tie graphics to the data.
We illustrate the GUI facilities through examples of increasing complexity all having to do with game playing.

Basic Scoreboard

Suppose we want to design a scoreboard in k. We have a home team and a guest team and we have two scores.
The strings here indicate operations that occur when a button is hit.

Forms are a kind of display (like a box with numbers). Try playing with the arrangements.


\d scores
home: 0
homeinc:"home+:1"
homeinc..c:`button
guest:0
guestinc:"guest+:1"
guestinc..c:`button

/ go up and set arrangement
\d ^
scores..c: `form / all the scores are a form
scores..a: ,`home `guest  `homeinc `guestinc 
	/ they have a horizontal arrangement
scores..a: `home `guest  `homeinc `guestinc 
	/ they have a vertical arrangement
scores..a: (`home `homeinc;  `guest `guestinc)
	/ they have a mixed arrangement
`show $ `scores / Note that you must have the backquote on scores.
	/ If you do `show $ scores, you won't get that and the arrangement
	/ won't work, but some things will work.
/ As you increment and decrement, you will get different scores.

Note that one sets attributes on the whole scores form in the directory above.

Change Colors

foreground color is the attribute fg.
background is the attribute bg.

\d scores2
home: 0
home..fg: 99 / foreground color should be blue.
homeinc:"home+:1"
homeinc..bg: 99 / background color should be blue.
homeinc..c:`button
guest:0
guestinc:"guest+:1"
guest..fg: 990000 / foreground should be red
guestinc..bg: 990000 / background should be red
guestinc..c:`button

\d ^
scores2..c: `form / all the scores are a form
scores2..a: (`home `homeinc;  `guest `guestinc)
        / they have a mixed arrangement
`show $ `scores2 / Note that you must have the backquote on scores.

Vectors of Scores

Suppose now that we wish to modify a vector of home and guest scores each of size 10.

\d scores3
n: 10
position: 0
position..fg: 9900 / green
home: n # 0
home..fg: 99 / foreground color should be blue.
homeinc:"home[position]+:1"
homeinc..c:`button
guest:n # 0
guest..fg: 990000 / foreground should be red
guestinc:"guest[position]+:1"
guestinc..c:`button
\d ~ / attribute directory of the scores3 directory
	/ Note that this is an alternative to \d ^
	/ followed by scores3..a
a:( `home `guest;  `homeinc `guestinc; `position) / arrangment
\d ^
`show $ `scores3

Other Graphics, e.g. charts

Here, we want the display to be a chart for the home team.


\d scores4
n: 10
position: 0
position..fg: 9900 / green
home: n # 0
home..fg: 99 / foreground color should be blue.
homeinc:"home[position]+:1"
homeinc..c:`button
home..c: `chart
guest:n # 0
guest..fg: 990000 / foreground should be red
guestinc:"guest[position]+:1"
guestinc..c:`button
\d ~ / attribute for the scores4 directory
a:( `home `guest;  `homeinc `guestinc; `position) / arrangment

\d ^
`show $ `scores4

A Betting Game

Let's create a betting game. We agree on a bet amount.
Home presses for a number.
Guest presses for a number.
The higher number wins the bet except that home wins on ties. The bet occurs when the guestflip button is hit.

\d scores5
balance: 0
wager: 1
home: 0
home..fg: 99 / foreground color should be blue.
homeflip:"home:*1 _draw 100"
homeflip..c:`button
guest:0
guest..fg: 990000 / foreground should be red
guestflip:"guest:*1 _draw 100; :[home

Home Has an Edge

Let's redo the betting game using functions. We agree on a bet amount. Home presses for a number. Guest presses for a number. The higher number wins the bet except that home wins on ties. In this case, home also has a 10% edge. The bet occurs when the guestflip button is hit.
```
\d scores6
balance: 0
wager: 1
home: 0
home..fg: 99 / foreground color should be blue.
homeflip:"home:*1 _draw 100"
homeflip..c:`button
guest:0
guest..fg: 990000 / foreground should be red
f:{[wager; home; guest; balance]
  :[home
```

Bank

There are n bank accounts. Each has a randomly chosen name. Triggers are used to update names and balances based on acctid. Another trigger changes the color of the name based on whether the balance is positive or negative.

\d .k
\d bank
n: 100
names: `alice `bob `carol `david 
names,: `eliot `fred `gary `harry `isaac `jack
acctnames: names[n _draw #names]
balances: n # 0
/ fields
name: acctnames[0]
bal: 0
amount: 0
acctid: 0
deposit:"balances[acctid]+: amount; name: acctnames[acctid]; bal: balances[acctid]"
deposit..c:`button
withdraw..fg: 990000 / foreground should be red
withdraw:"balances[acctid]-: amount; name: acctnames[acctid]; bal: balances[acctid]"
withdraw..c:`button
acctid..t: "bal: balances[acctid]; name: acctnames[acctid]"
	/ This updates all other fields whenever acctid is updated.
bal..t: ":[bal < 0; name..fg: 990000; name..fg:99]" 
	/ changes color based on value.
\d ~ / attribute for the bank directory
a:( `acctid `bal `name; `deposit `withdraw; `amount) / arrangement

\d ^
`show $ `bank

Simple Spreadsheet

(Advanced topic) We will write a simple 4 by 10 spreadsheet which processes top-down and left-to-right.

S:D:.+(`a`b`c`d; 4 10#,"") / dictionary of blanks
S[.;`f]: 19 $ D[] / initialize to 19 blanks per cell
S..t: ".[`D;(;);{. y}; S[]]; S[.;`f]: 19 $ D[]" 
	/ at all locations in D update based on S.
	/ Then make the format of S be 19 spaces wide and let it take
	/ the data from D.
`show$`S

Spreadsheet with Fixed Point

(Advanced topic) We will now ensure that the spreadsheet does the correct processing, reaching a fixed point. Not the most efficient, but it works.

S:D:.+(`a`b`c`d; 4 10#,"") / dictionary of blanks
S[.;`f]: 19 $ D[] / initialize to 19 blanks per cell
update:{[]
   oldD: D
   reachedfixed: 0
   while[~ reachedfixed
	.[`D;(;);{. y}; S[]] / note that this affects the global
	if[D ~ oldD; reachedfixed: 1]
	oldD: D ]
}
	
S..t: "update[]; S[.;`f]: 19 $ D[]" 
`show$`S

Check Boxes

Check boxes are sometimes a convenient way to represent information.


n: 100
names: ` $' "abc" ,/: $(!n)
chk: .+(names; n # 0)
chk[~!chk;`c]: `check    / check box did not reflect back to the data
`show $ `chk
/ after you do the selections, can get these.
selected: & chk[!chk] = 1
selectednames: (!chk)[selected]

/ Now show that selected gets updated automatically as you process.
n: 100
names: ` $' "abc" ,/: $(!n)
chk2: .+(names; n # 0)
chk2[~!chk2;`c]: `check    / check box did not reflect back to the data
`show $ `chk2
/ after you do the selections, can get these.
/ chk2..t: " selected: & chk2[!chk2] = 1; selectednames: (!chk2)[selected]; chk2: .+(selectednames; chk2[selectednames]); `show $ `chk2"
chk2..t: " selected: & chk2[!chk2] = 1; selectednames: (!chk2)[selected]"

Fonts (from Mike Whitney)

You can use environment vars KFONT and KLFONT (for data and label fonts, respectively) in the NT environment. Remember that the dimensions of the KFONT must be no less than those for the KLFONT for consistent-looking output, since the K GUI works in units of KFONT height and width.
In NT console, before starting K, you can say
set KFONT=Courier 12
set KLFONT=Arial 11 or some such. (This is similar to the Unix k.)
You can also say, in a K session,
\m fCourier New Bold8
\m lGaramond
You can also say
\m f
\m l
which give you the ability to choose these two fonts from an NT dialog box. This is the most reliable, since the numbers in the earlier examples are width (not pointsize), and on some platforms the height is not scaled appropriately.
One more thing: the KFONT (\m f) must be constant width, or the GUI will not work properly. This confines you to Courier and Courier New, plus perhaps a few others which I have not discovered.

Lectures of Dennis Shasha

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

Excel Calling K

(advanced topic) K can be called from Java and Excel with a quite similar interface: one k("function", arguments). Here is the basic way to set up an Excel interface.

Before entering Excel, put stat.k (a collection
of statistical functions) in the windows directory k.

Within Excel:
go to tools pulldown.
Select macro
visual basic editor
insert/module
Declare Function k Lib "c:\winnt\k20.dll" (s, ParamArray a())

where c:\winnt holds your k20.dll (if some other directory
holds k20.dll, then you should write that).
Then save this file and return to excel.

In some cells in the spreadsheet, type 
=k("\l stat")  
	that should return 0
	Now, enter some data in A1 through A7
=k("avg",A1:A7) 
=k("+",A1,B1)
=k("2+3")

Advanced feature: having arrays return to Excel. Suppose you want a function that returns an array to Excel.
- First select the matrix on the screen (could be just a column or a row, i.e. the matrix can look like a vector). For example, select c1 through c7
- Then type a formula into the top cell (c1 in our example). Here is an example that assembles the numbers 0 through 6 into a 7 by 1 matrix.
```
=k("7 1 # !7")
  then ctrl shift enter.
  The result fills in to the excel spreadsheet.
 
```

Java Calling K

(advanced topic) Here one needs a file called kc.java. One compiles this using javac, then one can run it after starting a k section at port 1 using the string

k -i 1

We present here an example of the interaction.


//example
// p prints the result
// k is the entry.
public static void main(String args[]){
 try{Socket h=open("",1);
 int[]q=new int[1000]; 
 int[] q2;
Object[]w=new Object[2];w[0]=q;w[1]=new Double(2.3);
 q[0]=2;q[999]=3;
  p(k(h,"+",k(h,"+/",q),new Integer(3)));  // h is the socket
  q2= (int[]) k(h,"+",q,new Integer(3)); // add 3 to every element of q
  p(k(h,"+/",q2));
  h.close();}catch(IOException e){}}}

An Introduction to K through Examples

First Items of Business

Quick Tour of K

Tour of GUI and Tables

Tour -- Functions

A Strong Working Knowledge of K

Why is K Good?

Why is K Bad?

Unit 1: Basic Language Features

Data Types

Structuring Primitives: scalars, list/vector, dictionary

Monadic vs. Dyadic Operators

Read and Write Files

Arguments to Programs

Generate Data

Add, Subtract, Multiply, Divide, and Compare

Vectors to Scalars and to Other Vectors

Debugging

Time Functions

Exercises

Solution: Average

Solution: Variance

Functions can Make This Easier

Solution: Variance as a function

Exercises

Solution: Dot Product

Solution: Matrix Multiply

Note: adverbs

Solution: Present value revisited

Solution: Bank Balances

Advanced Topic

A Strong Working Knowledge of K

Unit 2: Conditionals, Adverbs, and String Manipulation

Topics

Conditionals

While Loops

Do Loops

Each Operator

Exercise: VP Salary Raise

VP Salary Raise, Solution 1

VP Salary Raise, Index Approach

VP Salary Raise, Vector Approach

An Idiom

Example: Good stock

Recursion and Cousins

More in the spirit

Currying

Lambda Expressions

Executing Strings

Exercises

Delete All Blanks

Delete Leading Blanks

Delete Trailing Blanks

Find Most Consecutive Ones

The Road to Ruin

A Strong Working Knowledge of K

Unit 3: Tables and Database Facilities

Topics

Constructing Tables, method 1

Constructing Tables, method 2

The K (data and function) tree

Summary of Using the Tree

Using Tables

Partitioning (Group by) and Tables

Exercise

Names Having the Median Salary

Exercise: Assemble a Table with Grouping

Exercise: FIFO Accounting

Cost of Goods Sold: solution

More Exercises

Sales Solutions

Exercise: Most of Relational Algebra

Importing Large Text Files to Tables

A Strong Working Knowledge of K

Unit 4: Interprocess Communication

Topics

Mechanics of IPC

Example server.k

Example client.k

A Strong Working Knowledge of K