K for Good Thought: [Part 1] k,q,kdb tutorial atoms, nouns

I am a new convert to the K/Q/J/APL cult. This makes me suited to write a tutorial for those who find this whole family of languages quite arcane.

The tutorial is called K for Good Thought, an homage to Ken Iverson’s notation as a tool for thought and the tutorials ‘learn x for great good’ meme. Leslie Lamport claims that until you have expressed your thoughts in writing you haven’t really thought. So there is something about being able to express yourself in K that allows for another way of thinking. Often the K solutions tend to be simpler and more general. Also, because K is a computer language interpreted by a machine that does exactly what you told it to do, it’s a much stricter reader of your thinking.

I should start by saying that this is a language that values brevity over almost everything. As Arthur Whitney said in an interview. If you can do the same thing and it’s shorter and not much slower he wants to hear about it. If it’s faster you better tell him.

Arthur Whitney is a man of few words and when a subject is very difficult and the explanation is dense and technical, few will march on. So with that, I aim to make this tutorial approachable for those who have had high school math and no programming experience. If  I venture out into jargon or CS concepts or high level math, I will try to explain the concepts first before diving into the syntax, though of course sometimes one will motivate the other. I believe that the less programming background you have the more likely the concepts will become natural to you since you won’t need to unlearn many bad habits.

There are many tutorials that give the history of these languages.  So I am not going to bother, except to say that apl was developed to allow programmers to work on the problem at hand and not on the low level implementation, though of course inevitably you will need to get your hands dirty with the inner workings of K as well, but those tend to be advanced topics. –quick credit to all the abridged and short materials by Arthur Whitney [AW] (K, Q, KDB)

Let us start at the beginning:

In the beginning, AW created atoms and they were good.

  • Atoms are indivisible.
  •  Atoms can be of different types.

    I promised not to use jargon, so when I do. You will find an explanation in a quote box like this:
    Types are things that allow us to distinguish between different kinds of data. That is, an Atom can be a number or letter or a timestamp. Not everything that you can think of is a type. For instance, perhaps you want to have an emotion as a type and you would use various emojis to represent them.
    [AW] has not seen it fit to add them to the types that K understands. However, you can create an emotional type. We will look at that later.

Some example atoms:

  • 5
  • 1b
  •  ‘string of letters’
  • `symbol
  • 2009.11.05D15:21:10.040666000

We cannot do much with atoms, just like we cannot really say much if we just had nouns. I guess we could classify different Nouns: person, place or thing.

K uses @: to interrogate and find out what something is. In q we can use ‘type’

Because K is terse it uses numbers to signal what type something is.

A negative sign in front means that the type is an atom.

  • @:5 = -7                                              An integer between negative 2^63 and positive 2^ 63
  • @:1b = -1                                            Boolean: Can be (1b) True or (0b) False
  • @: ‘s’ = -10                                           A charecter or letter
  • @:`symbol   = -11                                    A token (advanced) used to refer to one copy
  • @:2009.11.05D15:21:10.040666000 = -12  A Timestamp

Besides classifying we can make lists:

In English:

Animals: cat, dog, mouse

And in K we can do something similar.

  • integers: 1 2 3 4 5
  • animals: `cat `dog `mouse
  • alpha: (“a”;”b”;”c”)

Here something unexpected happens. While ‘animals’ is a list of symbols, ‘alpha’ is actually a list of characters which is what programmers call a string.

So alpha can also be written as “abc”. In fact, if you ask K to display alpha it will automatically display it as “abc” instead of “a”,”b”,”c”.

If we check what “abc” is

@:”abc” =  10

It’s positive. That’s because if the noun is actually a list then kdb will tell you what it’s a list of.

Oh by the way, I snuck in some notation. In English we often have a colon ‘:’ that tells us that a definition follows. Well K lets you do the same thing.

In K/Q all lists are semicolon(;) separated enclosed in parentheses. As a matter of convenience K /Q lets you define some common lists just by using spaces. So the following are equivalent.

(1;2;3) and 1 2 3  

So alpha is defined as a list of characters specifically a, b, c.

Lists in K are always ordered, which means that we can talk about the first or last element in a list.

In fact K has a couple of things things that are designed specifically for lists.

First lets introduce the count (!) in K or the til in q

This allows us to create lists of integers until that number starting from 0.

For example !10

0 1 2 3 4 5 6 7 8 9

til10: !10

til10

0 1 2 3 4 5 6 7 8 9

til10[1] /the second item on list; list start with zeroth item

1

til10[9] /the tenth item on the list; remember to start counting from 0

9

Let’s say we want just first 3 numbers

3#til10 /the pound sign or hashtag means ‘take’

0 1 2

-3#til10 /this takes the last 3 slots. The negative sign signifies that we are taking from the end of the list.

7 8 9

3_til10 /The underscore(_) is used to drop. if we only want what’s not in the first 3 slots

4 5 6 7 8 9

(3_til10) = (-7#til10)

1111111b

There is an equivalence between take and drop. Dropping the first 3 is equivalent to taking the last 7, if your list has 10 things. The equals (=) sign is used to compare things each slot from each list will be compared and return a 0 or 1. 1 if it is equal and 0 if the two elements in the slots are not equal.

In general we can say given a list with n items dropping the first x items is equivalent to taking the last n-x items. In our example, we have 10 items so dropping 3 is the same as taking the last 7.

What about reversing the order of a list?

In K it’s ‘|:’ in Q it is just called ‘reverse’.

reverse 7_til10

9 8 7

Finally, we can make lists of lists. In English we call these tables. In math we call them matrices.

m: (1 2 3; 4 5 6)

1 2 3
4 5 6

In K ‘+:’ is flip and in Q it is ‘flip’

in K: “+:m” is the same as “flip m” in Q

+:m
(1 4; 2 5; 3 6)
1 4
2 5
3 6

m[0] Returns the first noun, which is a list of numbers.

 1 2 3

Remembering the game battleship helps to see what is happening.

m[0][2]

3

BONUS SECTION

What if we wanted to make a list of lists of lists. We can! In math these are called tensors. In English these don’t really have a name, I think most people don’t have a use for them.

However, we all encounter these structures in the form of pages. Let me explain, If a line in a book is a list of words (or as k would have characters), then a page in a book is a list of lines and a collection of pages, a book, is a list of lists of lists. One way to reference a word in a book would be to tell you the page number (dimension 1), the line number (dimension 2), and the word number (dimension 3). To make this clear, lets do a pretty simple example. Let’s say that we wanted to write a math textbook and the first couple of pages were reference tables. The first table might be the addition table. The second table could be multiplication.

Let’s first build the addition table.

in K:

a:!10;add:(a+)’a

in Q:

a: til 10; add:(a+) each a;

add is now equal to

0 1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9 10
2 3 4 5 6 7 8 9 10 11
3 4 5 6 7 8 9 10 11 12
4 5 6 7 8 9 10 11 12 13
5 6 7 8 9 10 11 12 13 14
6 7 8 9 10 11 12 13 14 15
7 8 9 10 11 12 13 14 15 16
8 9 10 11 12 13 14 15 16 17
9 10 11 12 13 14 15 16 17 18

We can see that indexing add[3;2] will give us the cell containing 5, which is what we would expect. Cell add[2;3] will also equal 5, but I highlighted add[3;2], notice row column order. A good way to remember this is to think of a regular list as a vertical structure. If the list has lists inside, then to get to a particular row and column, we need to first go down the first list and then enter the second level list and go to the right. So the top level is always a row number.  Basically, the first index, indexes the first level list. A deeper list will be a deeper index. Page number, line number, word number.

Let’s now create the mltp table.

in K:

mltp:(a*)’a

in Q:

mltp:(a*) each a

mltp

0 0 0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8 9
0 2 4 6 8 10 12 14 16 18
0 3 6 9 12 15 18 21 24 27
0 4 8 12 16 20 24 28 32 36
0 5 10 15 20 25 30 35 40 45
0 6 12 18 24 30 36 42 48 54
0 7 14 21 28 35 42 49 56 63
0 8 16 24 32 40 48 56 64 72
0 9 18 27 36 45 54 63 72 81

So our reference tables can be a list of tables:

reftab:(add;mltp)

reftab[0] is the first table or the addition table.

reftab[1] is the second table or the multiplication table

I leave  creating a subtraction table in reftab[2] to the reader. (hint use the comma(,) to join a subtraction table to reftab. Like so reftab:reftab,subtr;)

You can make a division table as well, you will see how K/Q handles division by zero.

Now let’s say you wanted to play 3 dimensional battleship.

Each player could either attack the surface or the submarine  layer. Suppose in this really simple game you had two ships, each 2 units long. and there were only 6 squares. 2*3 board.

Here is a sample board:

Layer 0 or surface:

0 0 1

0 0 1

Layer 1 or submarine level

1 1 0

0 0 0

I have a submarine and a boat. Both are two units long. We need three coordinates to track down a single location.

First let’s make the surface layer

s: 0 0 1

sur: (s; s)

Next we can make the submarine layer

easy way

sub: (1 1 0; 0 0 0)

fancy way

sub: 2#|:+:sur,enlist 0 0 0 /Don’t worry I’ll explain.

sur, enlist 0 0 0 /gives us a three by three table. Note the comma used to append a list to a list.

(0 0 1;0 0 1;0 0 0)

+: sur, enlist 0 0 0 /flips the table on it’s side, sometimes called transpose

(0 0 0;0 0 0;1 1 0)

|: +: sur, enlist 0 0 0 /reverses the flipped table only reverses the top level list

(1 1 0;0 0 0;0 0 0)

2# |: +: sur, enlist 0 0 0 /takes the first 2 rows of the flipped table

(1 1 0;0 0 0)

Now we can make the whole board

b: (sur; sub)

((0 0 1;0 0 1);(1 1 0;0 0 0))

b[0]

(0 0 1;0 0 1)

b[0][1]

0 0 1

b[0][1][2]

1

And obviously we can make lists of lists of lists of lists…. and everything will work the same. But I’m stopping here.

Advertisements

One thought on “K for Good Thought: [Part 1] k,q,kdb tutorial atoms, nouns

  1. Pingback: K for Good Thought: [Part 2] k,q,kdb tutorial verbs, functions | iabdb

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s