Idempotent Cast

Idempotent:  denoting an element of a set that is unchanged in value when multiplied or otherwise operated on by itself.

Wikipedia gives an easier definition. A unary operation (or function) is idempotent if, whenever it is applied twice to any value, it gives the same result.

Or more formally in f(f(x))=f(x) .

If you had to choose the top ten functions in programming that should be idempotent, casting would be near the top of list.

Casting is how you can convert one type to another. A classic example is taking a user input string and reading it as a number. Nitpickers will argue that this should be called parsing and that casting is only when you have known inputs. I think this line of thinking is flawed and a poor abstraction. If I get an input I just want to call a function whose responsibility is to cast it to the right type. If this can’t be done the function should return an error which I will then return to the user. The user should be able to call my function without caring too much about what he puts in and I should try to make it easier by being smart enough to cast it to the appropriate type.

KDBQ has some built in cast functions. However, almost none of them are idempotent, which is really annoying. If I get an input and I know how to cast it into the type I need, I shouldn’t worry that it is already in that type. For example I may need a integer. If you give me a string, like “4” and I cast it to an integer that should work, and if you give me 4 and I cast it that too should work.
This came up recently when I needed a function that cast a string to a symbol. So here is Idempotent cast to symbol:

{`$raze string x}

Let’s break this apart:

string will take an argument and turn it into a string. However, string is atomic so a “hello” becomes


With each character becoming a list. To get back the original we raze it. Now that we have a string that we can cast to a symbol. With `$ cast verb.

If we get a symbol. For example `hello We turn it into a string which gives us “hello”. We then cast it to a symbol.

We can do this because raze is idempotent on a list of 1. So it will just return the same list.

If we wanted we could achieve the same result by checking it was a symbol and returning the symbol otherwise casting it to a symbol.

That function looks like this:

{$[11~abs type x; x; `$x]}

This takes advantage of the triadic if ($) verb. The first argument must return a boolean, that is a 0 or 1b. The second is evaluated if it’s true the third argument if it’s false. This is actually how most programming languages would solve a problem like cast. Essentially creating code branches. In this case this is probably okay, but in general KDBQ pushes toward designing functions that just work without creating separate code paths.


There will definitely be another tutorial on control structures in Q in the spirit of the Mcdonnell article in Vector. Readers familiar with most other programming structures will find that introducing control structures so late kind of weird. However, control structures actually handicap abstract and general thinking which is the hallmark of clean code.


The problem with {subject} 101

Recently I saw this old (by internet standards) video of Elon Musk explaining what we should do about Global Warming in 12 minutes.

The talk doesn’t spend much time defending the science behind global warming and instead works around the issue. First, Musk states that 97% of the scientific community believe that not changing global energy habits will result in catastrophic loss of life/wealth and 3% don’t. He then says that since oil energy is not sustainable, we will eventually move to a sustainable energy source. This is a tautology. In the long run we will need to be on a sustainable source of energy otherwise it won’t work for the long run. Since the choice becomes when – not if – to move to sustainable energy, he claims we might as well do it sooner.  He then suggests that a properly functioning market economy should price in negative externalities so as not to create incentives for bad behavior. He then says this is economics 101.

The phrase this is Economics 101, is a very misleading phrase. Presumably, the topics get more sophisticated as you progress through the subject. Those simplifying assumptions made in 101 are no longer true. For example, knowing the cost of a particular negative externality is hard, it is part of a class of problems known as the free rider problem. Does Elon Musk know the price of the negative externality of continuing to use fossil fuels? It certainly isn’t infinite, we can be pretty sure that we would not be able to fulfill the world’s current demand for energy even in 10 years with only clean energy, which means that this tax has to be gradual (he mentions this in the video, but where he chose 5 years as opposed to 7 or 3 is unclear). Furthermore, the tax that is collected strictly from fossil fuels must end up somewhere, we would like that it provide some public good, but we can’t be sure. In many oil producing countries this tax is a significant source of revenue for the government, so levying a tax sufficient to shut down the industry is not in their best interest. Many social programs in those countries would have to be curtailed. One additional point, in the short run any tax on energy is sure to harm poor people the most. Energy cost accounts for significant percentage of many products and this is very true of grocery items. When the price of energy goes up those impacted will be those whose incomes are disproportionately spent on items influenced by the price of fuel, namely the poor.

I am sure that Elon could answer all of these questions or knows people that can answer them. My issue is that complex problems are proposed as simple problems with simple solutions and base themselves on a rudimentary presentation of the subject. It would be like saying you just need to reach the escape velocity in order build a rocket, it’s technically true, but it wouldn’t have gotten Elon very far with spaceX.

So the next time someone says: it’s {subject} 101. Ask  yourself are there any simplifying assumptions that might be contradicted by {subject} 501.














An Impractical Storage Solution: That might solve a very practical problem

It was Pi day recently and one of the interesting facts about Pi is that it is believed to be normal. Pi has been proved to be an irrational and a transcendental number. A real number x is normal in base b if in its representation in base b all digits occur, in an asymptotic sense, equally often. Proofing this has eluded mathematicians until now.

However, if we take this conjecture for granted. Then any finite string of numbers will be found in Pi. Which means that theoretically, given infinite computation power you would be able to compress any amount of information into two numbers. The first number stores the length of the information you want to compress and the second stores the starting point in Pi where you could find that string. We might want some more information in the metadata for example if a particular piece of information is very far into the Pi sequence than storing the number that represents where it can be found might be larger than the data in which case we might store a pointer to that number and so on. Ultimately, this is futile because there might be situations where storing the first pointer and it’s length and the depth that we need to follow the pointers might still be longer than the data we need to store at that point it might be worth gzipping the data and calling it a day, of course if you are committed you might consider breaking up the data into partitions and then finding the subsequences in Pi and storing those, the odds are those subsequences will appear earlier.

An important point to note is that this type of storage mechanism does not violate information theory. Although in general the number of bits it takes to store or transmit anything is a function of Shannon’s entropy. In general, Shannon’s definition of entropy is the minimum channel capacity required to reliably transmit the source as encoded binary digits. However, because there is actually infinite entropy in the digits of Pi and Pi is deterministic, we can essentially convey the message as a function of Pi. Now, this whole post promised something practical and this discussion so far has been theoretic.

One of the information theory problems in biology is how to account for all of the behaviors and advanced functions in advanced life forms. We know that learned behavior gets modeled in the brain after birth and has many places to hide (researchers try to catch this learning with relatively primitive imaging techniques). However, unlearned behavior or what we would call instincts and lower all fit into about 700mb of space,  human DNA. The problem is that given how much stuff goes on that is unlearned it seems unlikely to fit into this very small amount of space. The DNA codes for how much saliva to release into your mouth cavity,  as well as how to focus your eyes, or what to do during a sneeze….

So what is the solution to this seemingly paradoxical puzzle. I propose (I haven’t seen this anywhere so please correct me if there are better answers) the solution is something very similar to the impractical storage solution. Essentially the laws of nature are an infinite calculation engine and though there is a bit of probability implicit in them, in the macroscopic universe the answers are deterministic. This means that DNA can simply be a mechanism to force all of the behaviors necessary to survival to happen. Any DNA that didn’t cause the infinite calculator to spit out a species that survived would die out. In this view DNA is not the total information content of our species, we need the observable universe there as well, which includes a lot of  Physics and Chemistry (possibly all, but some of these subjects deals with conditions never occurring on Earth’s surface).

Of course, I am exaggerating a bit in telling you that this Natural computer is infinite, in fact, Einstein limited its computing speed ton the speed of light, which means no information travels between individual components in the computer too quickly. Still, nature does do an impressive amount of computation.

This also explains, some of the advantages of carrying a child in utero. A child in utero learns about the environment from its mother. There have been studies that show that a baby can recognize its mother’s voice, in other words information about the environment seeps into the neural pathways of a fetus. Perhaps that is the further advantage of marsupials which get to have a guided sighted tour of the world. Whereas newborn reptiles and birds rely predominantly on instinct which limits the amount of knowledge they can have about the world.









Incremental Quantiles/Percentiles with KDB/Q

A friend of mine asked about incremental quantiles, which I took to mean get incremental Quantiles without doing much work .

Quantiles are an inherently controversial topic among statisticians. For evidence of this look at the quantile command in the R stats package which lists nine methods for calculating this quantity from a data set.

For those who don’t know, essentially quantiles and their various flavors: percentile, decile, quartile and so on, is a method for creating equal size buckets for data. This is how standardized exams can tell you that a particular score implies you did better than some percent of the population.

Not knowing much about the topic myself. I decided to see what opinion the authors of KDB had.

KDB does not provide a built-in quantile method. KDB does have a stats.q package which implements 4 of the 9 methods mentioned above.  However, KDB does come with a built in verb called xrank.

First, let’s understand the problem a bit. The hint is that xrank is a special type of rank. Which means that quantilling is somehow related to ranking. Ranking is the most general version of quantilling. Suppose you had a list and you wanted to put each item in it’s own bucket and then label the buckets from smallest to greatest. That is exactly what rank does. Rank tells you where each item in the list belongs if it were sorted. For example:

q)rank 43 4 77 54 23 0 67 57 27 38
5 1 9 6 2 0 8 7 3 4

xrank is the special case where you only want x buckets. This is easily achieved by first ranking the list multiplying each rank by x and then  using integer division by the number of elements in the list. Suppose we want 4 buckets on the previous list:

q) 4 xrank 43 4 77 54 23 0 67 57 27 38
2 0 3 2 0 0 3 2 1 1

Okay, so we see that we can easily group items in a list into roughly equal buckets. We also learned that bucketing is basically sorting and then adding little markers every length of the list divided by number of buckets.

If stars are values and vertical bars are markers. Bucketing is sorting the stars and then dropping vertical bars in between:


What is very nice about this particular opinion expressed by KDB is that no model is better than a wrong model. Specifically, the only way to bucket data is to look at all the data that you have sort it and then insert the markers at equidistant points. Depending the on distribution the buckets might be spaced evenly with respect to the values or not. KDB does not care because the values have already been sorted.

So having this wonderful tool in hand, we proceed to look at the problem of incremental quantile. Our first reaction is: Can’t be done! How can we possibly know where to put the markers if we don’t use the whole data set. Ignore that and march on.

We find that there exists some interesting things with regard to incremental sorting. This is a possible avenue, but it seems complicated.

In cases like these, I like to call upon my genie. My genie can somehow solve the problem so quickly that the method he/she(it’s a gender neutral genie) uses is irrelevant. What does my genie return to me, well the genie tells me into which bucket I should place my current value, it does this using all the data I have up till this point (My genie doesn’t time travel or at least she/he doesn’t tell me about it).

Now I proceed with the following assumptions. If the data was negligibly small, then I don’t need a genie I can just use xrank as above. However, if the data is relatively large much larger than the number of buckets, then with a very small error you can become the genie.

You will need:
2 lists

Yep that’s it! Everything else will be provided to you.

  1. We start by using our good old xrank on all the data until the data is too large.
  2. We  use the first list to find the “You must be this high to be in this bucket” for each bucket. These are our partition markers.
  3. We use a second list to keep track of the total counts in each bucket. Our counts (kind of sounds like accounts).

Every time a new value comes in we find it’s bucket using the bin verb. Which applies binary search on the list to it’s left and returns the bucket number for the input to it’s right. For example:

q)0 5 10 20 bin 17

Because 17 is less than 20. So it goes in the previous bin whose minimum height is 10.

We update the counts to say that the current bucket has another item.

Here is where the magic happens: We multiply the current count against the number of buckets, if that number is higher than the total number of observations by some percent we rebucket. Otherwise if it is within our error band, we are ready for the next value.

One final note, if our error band is very small, this will have to do the sort operation much more often. However, the law of large numbers is on our side, that is as long as we are sampling from the same distribution the buckets will be right, as soon as the distribution changes the buckets will be wrong and we will rebucket. The sensitivity to a change is distribution is determined only by the error band.

I really like this approach, because it doesn’t actually care about how you get the values, all that matters is the values you have access to. Your buckets are your strongest bet on where things should land, if a bucket gets heavier than the rest, you become suspicious of your bet.

At the bottom is all the code that implements this logic.

//optimbucket is an optimized bucketing strategy
// it trades accuracy on buckets for speed
// by keeping track of how equally buckets are sorting data
//it takes a dictionary with the following keys:
//key t total observed elements
//key n number of buckets
//key bkts an ascending list of floors of each bucket,
// length should be n
//key e acceptable error before expensive recaluculation of buckets
//key c totals for each bucket,
// length should be n
//key s source for complete list of data in case of recalculation
//key b the bucket of the current element
// (could be empty)
// This is where the result is returned
optimbucket:{[d;v] d[`t]+:1; $[(d[`t]*d[`e]+1)>d[`n]*d[`c;d[`b]:|[0;d[`bkts] bin v]]+:1; d;fallback[d;v]]}

/helper functions:
/redobuckets gets the buckets from the actual source
redobuckets:{[d] g:value asc {(min x; count x)} each s group xrank[d`n;s:get d`s]; d[`bkts]:`s#g[;0]; d[`t]:sum d[`c]:g[;1];d}
/fallback is our method if buckets are wrong
fallback:{[d;v] d:redobuckets[d]; d[`b]:d[`bkts] bin v;d}
/Test this
//append and bucket, gets a value adds it to s the store
/and returns the bucket
apbk:{store,::x;`d set optimbucket[get `d;x]; (get `d)[`b]}

/gen generates data with pseudo normal distribution around 0
/x 10 uniform is usually enough
gen:{neg[(x%2)]+(sum x?x)%x}

/setup store for data
/setup dictionary
/we will do quartiles so n is 4
d:`t`n`bkts`e`c`s`b!(0;4;til 4;.01;0 0 0 0;`store;0N)
/gen some data and watch how d changes
data:gen each 1000#10
apbk each data
apbk each constantdata
apbk each uniformdata
sample output
t | 10
n | 4
bkts| `s#0.01867974 1.218468 6.321394 8.083308
e | 0.01
c | 3 2 3 2
s | `store
b | -1
q)apbk each data
0 0 0 0 1 0 1 1 2 2 0 2 0 0 1 1 2 1 1 2 1 0 0 0 1 1 0 1 2 2 0 2 2 1 0 0 3 0 2..
t | 1010
n | 4
bkts| `s#-3 -1.1 -0.5 0.2
e | 0.01
c | 254 252 253 251
s | `store
b | 0
q)apbk each constantdata
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3..
t | 2010
n | 4
bkts| `s#-3 -0.5 1.9 2
e | 0.01
c | 501 501 501 507
s | `store
b | 3
q)apbk each uniformdata
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1..
t | 3010
n | 4
bkts| `s#-3 0.04688868 0.6175779 2
e | 0.01
c | 748 757 758 747
s | `store
b | 2


Prototype for Fuzzy Grouping

This is a sketch of how you can take user input fields from a survey with free text and try to do some kind of grouping of the data. I will describe my strategy but first a warning. This code should not really be published, but the idea could be interesting.

WARNING: The following code is

  • not performance optimized, AT ALL
  • makes use of global variables as a hack
  • generates different quality groups based on the random order of the input list

Alright, you’re still reading.

I came across this problem when dealing with classification of service tickets. Each service ticket represents a unique real world event and it would be nice to classify the events. In particular we are interested in finding a group of incidents that are in some way common such that we can avoid them in the future (optimistic little creatures we are). Each of these tickets comes with a free-text field that describes the resolution, in a few sentences. Humans are pretty lazy, so they are often copying from previous resolution descriptions, which at least makes it easier to group similar tickets, (of course it leaves open the possibility that the resolution description is irrelevant to the incident). However, humans are also careless so when they copy and paste, they may leave off some parts, or simply type something similar.

My strategy was to use the fuzzywuzzy library kindly developed and open-sourced by seatgeek. The library has several useful features.

Firstly it can find the ratio between two strings and it has several methods available. One has to know a little about their domain to determine which strategy to use. For example:

fuzz.ratio("NEW YORK METS", "NEW YORK MEATS") ⇒ 96
fuzz.partial_ratio("YANKEES", "NEW YORK YANKEES") ⇒ 100
  "New York Mets vs Atlanta Braves", \
  "Atlanta Braves vs New York Mets") ⇒ 100
 "mariners vs angels",\
 "los angeles angels of anaheim at seattle mariners") ⇒ 90

Secondly, given a particular strategy and a list of words fuzzy wuzzy can try to extract the best inexact matches and it can use both a hard limit on the number of items to return and a minimum ratio to be considered a match.

Given a dataset, pandas and fuzzywuzzy we can group some data.


import pandas as pd
import numpy as np
import difflib
from fuzzywuzzy import fuzz, process

First let’s clean the data a bit:

df = pd.read_csv(“dataset.csv”) df.userinput=df.userinput.apply(fuzz.utils.asciidammit)

We need to setup the list of items to group: choices = list(df.userinput) Unfortunately, this list is a global variable so that as we progress choices that have been added to the groups previously don’t get added again. In theory, you can get a serious performance increase from removing them from the query, but that requires adding an extra bit of branching logic in the extract function. (maybe later)

Next, we create an extract function that will take only a token and return a Boolean array that masks those elements not in it’s group. This way we can take advantage of pandas apply functionality. We also remove from the choices variable those that we have already grouped.

def extract(s): global choices res = process.extractBests(s, choices, \ scorer=fuzz.token_sort_ratio, score_cutoff=80 , limit=100) r = [x[0] for x in res] choices = [x for x in choices if x not in r] return list(df.userinput.isin(r))

Now we create our masks

masks = df.userinput.apply(extract)

We can then use our mask to filter and see all the elements that are similar to a particular item. For example, this gives us what matched the first row:


Here is how we can see how many are in each group:


Finally, I present the complete code that includes a method for running on small subsets of the original set until some portion of choices is covered.

choices = list(df.userinput)
def extract(s):
 global choices
 res = process.extractBests(s, choices, scorer=fuzz.token_sort_ratio, score_cutoff=80 , limit=10000)
 r = [x[0] for x in res]
 choices = [x for x in choices if x not in r]
 return list(df.userinput.isin(r))
ratio = 1/4.0
while len(choices)>ratio * len(choices):
 choices = list(df.Resolution_Text_ascii)
 masks = df.Resolution_Text_ascii[:i].apply(extract)

Also here is a possible branching version, but not as clean as I would
like it where it would return the group it’s a member of.

def extract(s):
global choices
if s in choices:
res = process.extractBests(s, choices, scorer=fuzz.token_sort_ratio, score_cutoff=80 , limit=10000)
r = [x[0] for x in res]
choices = [x for x in choices if x not in r]
return list(df.userinput.isin(r))
return list()

Async Calls in KDB/Q

Sometimes you don’t need a long post to explain something relatively complicated.

KDB/Q has something called inter-process communcation (IPC) it allows two different independent KDB/Q processes to communicate. This is built-in so we don’t need to dig deep.

Usually every result in KDB/Q returns synchronously, meaning a verb[noun] will immediately be processed and no other work can get done during this time.

However, in general it is much more useful to allow to processes to talk asynchronously, like email as opposed to a phone call. IE get it done when you can please.

KDB/Q provides such a construct, but it’s still a bit tricky. So here is a version that works.

Start a KDB session with the -P or run \P in the session followed by a port number (5000 is the convention).   This session is now listening on that number.

In a different terminal start a session and create the handle that will talk to that listener. Assume we are listening on port 5001, we can use either the hostname or ipaddress, if we leave it blank it will assume localhost.

h: hopen `:hostname:port

If we use neg[h] “something that will run” it will send it asynchronously, but we won’t get a response with the result of what happened. So…

I made a very simple utility that lets the process you send to reply asynchronously with a result and that variable will get set.

async:{[h;v;n;r] neg[h] ({neg[.z.w] (x set y)}[r;v[n]])}

The verb takes a handle (h), a verb (v), a noun (n) and a result symbol (r). It uses the handle to send an asynchronous request. The request asks the other process to apply the verb to the noun and send back the result and set it to the result symbol.

Here is a really simple example:


We can also project this verb so that it creates a verb that has an (i)mplicit handle and result.


iasync [v; n]

That’s it. Enjoy.


UPDATE: I have found a more useful async is one that allows passing in an arbitrary function. This allows us to use the words set to perform that task done here.

the new async looks like this:

async:{[q;cb] neg[.z.w] (cb,value q)}

It simply says place the query into a list of it’s own and the cb into a list of it’s own. the callback will be called with the value of the query evaluated on the service.

For example:

neg[h] (async;({0N!x+x};2);(set;`a))

Will set `a on your service to the value of the query in this case 4. and display 4 on the service.  We can also define a function on our service that takes some number of arguments fill them in now and have the function be called with the result when the callback is executed.

q)neg[3i] (async;({0N!x+x};2);(`f;3))



K for Good Thought: [Part 3] k,q,kdb tutorial adverbs, operators

Now we come to one of the most innovative features in APL family of languages. That is the language feature of operators.

An operator is similar to a verb (function) but unlike a verb which produces a noun an operator always produces a verb. It’s functions is very similar to an adverb in English.


A word or phrase that modifies the meaning of an adjective, verb, or other adverb, expressing manner, place, time, or degree (e.g. gently, here, now, very). Some adverbs, for example sentence adverbs, can also be used to modify whole sentences.

I will from now on refer to operators as adverbs so that our understanding can be enhanced by our natural understanding of language. An adverb serves to help us understand how a verb will modify a noun.

For example, in the previous tutorial we saw that we can create a verb like blend which applies to some arguments. Let’s simply define blend as taking two nouns and squashing them together. For instance the blend of cat and dog is simply catdog. In fact, we have seen this type of operation earlier with the comma(,) which allowed us to append the right argument to the left argument.

q)5# reverse til 15
14 13 12 11 10

q)list1: til 10
q)list2: 5# reverse til 15
0 1 2 3 4 5 6 7 8 9 14 13 12 11 10

list3 is now the longer list that contains both list1 and list2, order is preserved. So list1 will come before list2 and all the elements in list2 will still be in their original order. So to make this a bit more interesting, let’s say that blend does something a bit different. It adds a hyphen between the two arguments.

So blend[“cat”;”dog”] will create cat-dog. Here is a simple definition for blend.

blend: {x,"-",y}

We see that blend takes two implicit arguments, x and y, adds a hyphen in between and returns one single list.

What if instead of blending two items, we wanted to blend more. We could of course create a new function called blend3 that blends three items, but K/Q is much too cool for that instead it provides an adverb over in Q and “/” in K.

So for instance in Q:

 q)blend over ("cat";"dog";"mouse") 

in K:


So we have generalized our function from two arguments to a list. What is happening is that blend is used with the first item from the list as the first argument and the second item as the second argument. Then the result is used as the first argument and the next item on the list is used as the second. This continues until there are no more items.

To get the intermediate results we can use scan instead of over in Q and \ instead of / in K.

Here is what that looks like:

q)blend scan ("cat";"dog";"mouse"; "horse")

Now we can generalize this further. By creating a verb that is similar to what python calls join. In python the join verb takes a list of items and adds a string separator in between each item in the list. This is often needed to make comma separated lists.

Here is K/Q implementation:


This verb takes three arguments, the first arguments will be placed between  the next two arguments.

q)join["!!!! ";"hello";"world"]
"hello!!!! world"

But if we use the projection idea from before which creates another function by supplying some of the arguments. Then we can easily see how to make blend from join.

blend: join ["-";;]

so we can simply write:

q)join["-"] over ("cat";"dog";"horse")


q)join[","] over ("cat";"dog";"horse")

We are starting to see sentences forming in K/Q. We read sentences in English from left to right and we do the same in K/Q. The sentences are actually evaluated in right to left order. So it is correct to read it as ‘join a comma over the list’ even though K looks at it  the other way.

It’s sort of like if you read the sentence

Lily jumped high over the yellow hedge.

We don’t know what she jumped over until the end yet we understand the sentence.

If we were to stage the sentence we would first need a yellow hedge then we need Lily and ask her to jump high. The staging of the sentence is how the computer interprets things, but we humans like to read sentences the first way.

This gets to a fundamental point about K/Q there are no precedence rules. The only slight exception is that you can use parentheses to  force pieces of a sentence to be evaluated together, much like you would do in English with hyphenation.

For instance in this phrase:

an off-campus apartment

We could say:

an apartment that is off campus

Then we would have the same meaning without hyphens and usually if we have a choice at least in Q/K we try to rearrange things so that we don’t need to use parentheses as keeping track of how many were opened and closed is hard on the eyes and forces the reader to scan the line many times.  As Donald Knuth said “Programs are meant to be read by humans and only incidentally for computers to execute.”  I will have another post on K/Q style, so back to our topic.

There are only six adverbs in K/Q and a user can not make their own but they are pretty powerful and can be used in many combinations. (Technically if you add your own functions into the q.k script you can create verbs that behave very similarly to adverbs. It is not recommended unless you are an advanced user and have found some particularly useful adverbs to add to the language.)

Let’s go through them and how they work.adverbs

Continue reading

Tables full of Lists or Not

I am taking a brief break from the tutorial series (I’m down the rabbit hole on adverbs and I haven’t sneaked/snuck back out).

While on the Aquaq Group I got the following message: (check out the opensource torq)

I’m trying to build a table that looks like

now                   y2
1 8                     1 9
2 5 6                  5 13 7

This is a table with list of float as a column type. I manage to get something by doing the following

table:([] now:enlist `float$(); y2:enlist `float$())

I get

now                   y2
`float$()             `float$()
1 20 1               1 7 9
1 8                    1 9

Is there a way to create the table without the `float$()? Thanks.
I came up with some solutions:

The first just load the data in from your set

q)now: 2.0+til 4

q)y2:1.0*til 4

flip `now`y2!(enlist now; enlist y2)

Or initialize it the way it was done in the question and then immediately delete everything.

q)delete from `table where i>0

But the question got me thinking, that there was something wrong with the data model.

It seems unlikely that the best way to handle data is with lists of lists especially in q.

The reason is simple. simple lists in q/k are really fast. they are contiguous blocks of memory. A list of lists are essentially a list of pointers to smaller contiguous blocks. So to test this I created the data-structure that  I think would accomplish everything the questioner wanted:


First let’s create some dummy data and put it into the form of the questioner

q) x: ?[;1.0] each 1+100?9
q)y: ?[;1.0] each 1+100?9

?[;1.0] each 1+100?9 this code is two blocks. The first  ?[;1.0]  is a function that will return a list of random floats between 0 and 1 based on the number.

For example (til 10)!(10?1.0) This is just a dictionary where the key is a number from 1 to 10 and the value is the list of random floats.

0| 0.50994288921356201
1| 0.90591901540756226
2| 0.033651269972324371
3| 0.35632792115211487
4| 0.93293070793151855
5| 0.40784171223640442
6| 0.84914475679397583
7| 0.95187389850616455
8| 0.30074122548103333
9| 0.42668652534484863


The second part 1+100?9 create a 100 element list of random numbers between 1-9.

The each adverb applies the first function (which is a projection) onto each of the elements in this list.

Which gives us a list of lists of floats.

We can see this easily by applying the verbs count and type.

q) count x
q)count each x
1 1 4 9 6 4 7 2 1 8 6 9 4 5 7 1 2 6 4 7 8 4 8 2 2 9 4 5 9 2 9 6 3 5 1 2 9 6 2.. /random numbers in fact the same ones generated by the original command 1+100?9
q)(count each) each x
1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1

Similarly we can do the same with type

q) type x
0h /a mixed list
q)type each x
9 9 9 9 9 9 9 9 9 9 9 .. /the type for a list of floats
q)(count each) each x
-9 -9 -9 -9 -9 -9 -9 -9h
-9 -9 -9h
-9 -9 -9h
-9 -9 -9 -9 -9 -9 -9h
-9 -9 -9 -9h
-9 -9 -9 -9 -9 -9 -9h
-9 -9 -9 -9 -9 -9 -9h
-9 -9 -9 -9 -9 -9h
-9 -9 -9h
-9 -9 -9 -9 -9h
.. /the type for an atom float. (remember negative means atom)

So to create the table that the question was asking about we simply use table notation:


x                                                                               y                                                                              
,0.069488948909565806                                                           ,0.61275040498003364                                                           
,0.18058245000429451                                                            0.074964647181332111 0.21553308074362576 0.98548699356615543 0.09629874653182..
0.62432846496812999 0.34225802053697407 0.16392032452858984 0.7786109980661422  0.49375488748773932 0.48304210440255702 0.49691119533963501 0.259749417193233..
0.53403982776217163 0.88706594565883279 0.81696920236572623 0.530728749930858.. 0.04861030331812799 0.13365717371925712 0.99836521386168897 0.152357474202290..
0.36319364630617201 0.15776891494169831 0.45724554779008031 0.974702587584033.. 0.87366164615377784 0.31437360099516809 0.12580484454520047 0.635657876031473..
0.56634279619902372 0.87585472338832915 0.78419443848542869 0.83294638991355896 0.78629159089177847 0.26546700927428901 0.12905376916751266 0.761838810984045..
0.087665317580103874 0.23685944243334234 0.043390074744820595 0.8760851731058.. 0.10706076468341053 0.85431159776635468 0.012844447279348969                   
0.32782130455598235 0.72754358011297882                                         0.89185469760559499 0.651039635296911 0.48640229227021337 0.68811673740856349..
,0.5765261803753674                                                             ,0.28950302815064788


Now to make the structure that we want to make, we need to turn these lists into one list. That’s easily done with a verb raze. However, we will lose all information about the list of lists. It just flattens the whole thing.

q) raze x
0.69158544205129147 0.92801779927685857 0.95605599298141897 0.909228001954033..

So we need to zip up each element with it’s row number.

We can easily zip each row and row number like this:

q) (til count x),’x
What we really want is to zip up each item with it’s row number.
q) (til count x),”x
.. /notice that the row number is now next to each element

Now we can simply raze this and get

q) raze (til count x),”x
0 0.069488948909565806
1 0.18058245000429451
2 0.62432846496812999
2 0.34225802053697407
2 0.16392032452858984
2 0.7786109980661422
3 0.53403982776217163
3 0.88706594565883279
3 0.81696920236572623

Because we need to account for the fact that these list can have variable size, it’s best if we give them also an element number this will also be necessary for creating the table.

Remembering that we can find the element number by using the idiom til count we add the elements place in the list with the following

q) (til each count each x),”x

If we add back our row numbers we get

q)(til count x),”(til each count each x),”x
.. /the first number is the row number, the second the element number and finally the element itself

If we now raze this entire mess. We get a list of lists of three elements.

q)raze (til count x),”(til each count each x),”x
0 0 0.069488948909565806
1 0 0.18058245000429451
2 0 0.62432846496812999
2 1 0.34225802053697407
2 2 0.16392032452858984
2 3 0.7786109980661422
3 0 0.53403982776217163

Now we simply create a table from this normalized list. let’s call it xn

q)xn:raze (til count x),”(til each count each x),”x
q) tx

rid eid| x                   
-------| --------------------
0   0  | 0.069488948909565806
1   0  | 0.18058245000429451 
2   0  | 0.62432846496812999 
2   1  | 0.34225802053697407 
2   2  | 0.16392032452858984 
2   3  | 0.7786109980661422  
3   0  | 0.53403982776217163 
3   1  | 0.88706594565883279 
3   2  | 0.81696920236572623 
3   3  | 0.53072874993085861 
3   4  | 0.49852972221560776 
3   5  | 0.081481670029461384

Let’s pretend this is a cooking show and we have done all the previous steps to y.

Here is our y table

rid eid| y                   
-------| --------------------
0   0  | 0.61275040498003364 
1   0  | 0.074964647181332111
1   1  | 0.21553308074362576 
1   2  | 0.98548699356615543 
1   3  | 0.096298746531829238
1   4  | 0.60473616444505751 
1   5  | 0.98754768050275743 
1   6  | 0.46964235557243228 
2   0  | 0.49375488748773932 
2   1  | 0.48304210440255702 
2   2  | 0.49691119533963501


Now we simply need to join these two tables. Q makes this really easy with union join (uj) this will automatically join on the key columns if they are the same and add nulls where the data is missing.

q)t:tx uj ty
Some pretty clever stuff happens underneath. First the row ids are matched up and then the element ids are matched the columns will be matched up. If the second table has missing data it will be filled in with missing values. If one of the keys is missing in the first table then the second table rows will be appended to the end.

t now looks like:

rid eid| x                    y                   
-------| -----------------------------------------
0   0  | 0.069488948909565806 0.61275040498003364 
1   0  | 0.18058245000429451  0.074964647181332111
2   0  | 0.62432846496812999  0.49375488748773932 
2   1  | 0.34225802053697407  0.48304210440255702 
2   2  | 0.16392032452858984  0.49691119533963501 
2   3  | 0.7786109980661422   0.25974941719323397 
3   0  | 0.53403982776217163  0.04861030331812799 
3   1  | 0.88706594565883279  0.13365717371925712 
3   2  | 0.81696920236572623  0.99836521386168897 
3   3  | 0.53072874993085861  0.15235747420229018 
3   4  | 0.49852972221560776  0.55927985697053373 
3   5  | 0.081481670029461384 0.5587915435899049  
3   6  | 0.022724361391738057 0.73704647365957499 
3   7  | 0.99410609365440905  0.14246862730942667 
3   8  | 0.70526488753966987

Because Q will append the missing values from the second table to the end we need to resort the rid column so that we can easily find the rows that go together as in the original structure. This also explains why the only missing rows appear in the y column. Lets sort the rid.

q) `rid xasc `t

rid eid| x                    y                   
-------| -----------------------------------------
0   0  | 0.069488948909565806 0.61275040498003364 
1   0  | 0.18058245000429451  0.074964647181332111
1   1  |                      0.21553308074362576 
1   2  |                      0.98548699356615543 
1   3  |                      0.096298746531829238
1   4  |                      0.60473616444505751 
1   5  |                      0.98754768050275743 
1   6  |                      0.46964235557243228 
2   0  | 0.62432846496812999  0.49375488748773932 
2   1  | 0.34225802053697407  0.48304210440255702 
2   2  | 0.16392032452858984  0.49691119533963501 
2   3  | 0.7786109980661422   0.25974941719323397 
2   4  |                      0.4275001569185406  
2   5  |                      0.032995089888572693
2   6  |                      0.83006249205209315 
3   0  | 0.53403982776217163  0.04861030331812799 
3   1  | 0.88706594565883279  0.13365717371925712 
3   2  | 0.81696920236572623  0.99836521386168897 
3   3  | 0.53072874993085861  0.15235747420229018 
3   4  | 0.49852972221560776  0.55927985697053373 
3   5  | 0.081481670029461384 0.5587915435899049  
3   6  | 0.022724361391738057 0.73704647365957499 
3   7  | 0.99410609365440905  0.14246862730942667 
3   8  | 0.70526488753966987


We are done. We have preserved all the information of the original and normalized the Xs and Ys into a single list.

The original table

here is row 6 two different ways:

q) table 6

x| 0.1797088 0.8024157 0.5423326
y| 0.1165928 0.3872393 0.850714 0.04278559 0.6582815

q) select from table where i=6

x                             y                                                
0.1797088 0.8024157 0.5423326 0.1165928 0.3872393 0.850714 0.04278559 0.6582815

In the new table we can get it easily only through sql select

q)select from t where rid=6

rid eid| x         y         
-------| --------------------
6   0  | 0.1797088 0.1165928 
6   1  | 0.8024157 0.3872393 
6   2  | 0.5423326 0.850714  
6   3  |           0.04278559
6   4  |           0.6582815

Getting back to the original table from this new refactored table is much easier:

q)select x:enlist x, y:enlist y by rid from t

rid| x                                                   y                                                
---| -----------------------------------------------------------------------------------------------------
0  | 0.09087531 0.6808 0.03380431 0.8703531 0.8429108    0.4163949                                        
1  | 0.4949937                                           0.5467487 0.5798376                              
2  | 0.3858707 0.2949814 0.8767788                       0.1909843 0.6298909 0.2454277                    
3  | 0.4772341 0.3541479                                 0.3746654 0.1032089 0.2343539 0.5393872 0.5799004
4  | 0.5165465 0.1865312 0.8763466                       0.4432449 0.3670384                              
5  | 0.6212155 0.6579                                    0.163703 0.8951596 0.1463084                     
6  | 0.1797088 0.8024157 0.5423326                       0.1165928 0.3872393 0.850714 0.04278559 0.6582815
7  | 0.7720778 0.7476806 0.8778866 0.9120672             0.955969 0.3724551 0.7092033 0.5509018 0.180806  
8  | 0.5743992 0.01259725 0.7083142                      0.3574173 0.06719808 0.9434847 0.60344           

However, our new vectorized table allows us to find data about these individual values and we can use it to zip up x and y values that might belong together or do any other fun calculations.





K for Good Thought: [Part 2] k,q,kdb tutorial verbs, functions

Last time, we got to list things and reorder them a bit,  but that’s kind of boring on it’s own. This second tutorial is concerned with being able to play, transform and generally do things with nouns. In English, these types of words, action words, are normally called verbs and I’ll let the OED define it.



o          NOUN- Grammar

A word used to describe an action, state, or occurrence, and forming the main part of the predicate of a sentence, such as hear, become, happen.

o          VERB- Grammar

Use (a word that is not conventionally used as a verb, typically a noun) as a verb.

Interestingly, though there are two definitions for verb, we will mostly concern ourselves with the first, but I shall leave a small footnote on how the second is related.

The first definition is fairly trivial, that is most speakers of a language understand that you need a category of words that do things, even if you don’t need the category itself. That is we tend to ‘place’, ‘buy’, ‘blend’ and generally do stuff to things. This doing stuff is what I mean by verb. In math, in computer science and in programming languages there is a concept of ‘function’ and this concept performs much of what a verb does in English. It allows you to manipulate the stuff. To take a crude example, verbs are like little machines that allow us to change something about the stuff. So for instance, I am running. Which is to say ‘I’ am now in transit. I think belaboring this point serves to confuse rather than enlighten. So I leave it here. Anyway, I will use the word verb instead of function or something else, as I find those other terms have been overloaded with meaning (people think of very specific examples) especially for programmers.

Verbs take an atom or a list and produce an atom or a list. This list can be a list of atoms or a list of lists or a list of lists of lists….

Whoa, almost got carried away there.

Anyway, the more important thing is to remember that a verb and noun produce a new noun. For those inclined to equations: verb (noun) => new noun

Which can be read as verb applied to noun yields new noun. (don’t worry there will be little else I borrow from chemistry.)

For example, the verb shake produces shaken noun.

Where shaken is an adjective.

Sometimes there is no adjective to describe the new noun.

For example, take the verb blend. If I blend a cat with a dog. I might get catdog or dogcat or a mush, in any case, we can talk of having blended the cat and dog. Often we don’t have a word that describes the new thing. The predicate phrase is the result of the verb. So for instance, Gena went to the zoo, ‘went to the zoo’ is the predicate phrase and is the description of ‘Gena’ since English lacks a special phrase that describes a person who has gone to the zoo. Other times, we do have a phrase “shake this drink” the drink is now mixed or shaken, but it is most definitely not stirred. The predicate phrase is always a description of a subject. Predicate phrases or verbs transform the subject and give us a new subject. One that is described by the predicate phrase.

Because K is a descendant of APL, there are certain conventions which K kept but simplified and enhanced. I will therefore first explain what APL did and then switch to K’s simplification and enhancement.

In APL, all verbs just as in English take a noun and make it do something, the result is always just a noun that has done that thing. So if I(noun) run (verb) then I am-running (new state of ‘I’). Just as in English some verbs need two nouns to make sense or have a different sense if used on their own. For instance, I winked, means something different though related to I winked at him. So for example in K the ‘%’ symbol is the verb divide. If we just say divide seven in K %7, that returns  0.1428571. Which is the reciprocal of 7, or one seventh. Where as if we 21%7 we get 3. This what APL calls monadic and dyadic verbs.

Verbs can be of two types: monadic and dydadic. Simply put, monadic verbs take a noun or a list of nouns on the right and produce a noun or a list (that list can contain lists, as always I will cease making this point and assume it from here on in unless it is not true. Then I will make special mention). Dyadic verbs take a noun or list on the left and the noun or list on the right and create a noun or list.

In the first case % behaves like a monadic verb reciprocate (take reciprocal or multiplicative inverse). That is the verb only referred to the noun following it. In the second case % behaved more like the verb divide, which takes a number on the left and divides it into the right (pun intended) number of equal pieces. The result is the size of each piece. Though this is intuitive for verbs that apply to one or two nouns at a time. It does not make much sense for verbs that apply to more nouns.

This is where K made a change from APL and created it’s own convention, from here on in it’s back to K and Q.

Going back our verb ‘blend’ suppose we wanted to blend a cat, dog, and a rabbit. Where do we put the noun rabbit. Each noun, is often called an argument.

Argument: The noun or list that a verb does its action to is often called an argument. The term is helpful, because we can refer to verbs as taking some number of arguments. For instance, Monadic take one argument, the one on the right of the verb. Dyadic take two arguments, the one on the left and then the one on the right. (Sometimes in some textbooks these are called parameters. I will try to stick with argument.)

K has adopted the following convention. If you have a verb that takes a specific number  of arguments, then you do so by putting the verb first and then putting a open square bracket([) the arguments separated by a semicolon(;) and a closing square bracket (]). This is very easy to see:

In K 10÷5 can be written at least these two ways:

The nice thing about the second notation, is that it generalizes to verbs that apply to more than two arguments. You would simply write:

Because this convention is simple, all verbs that a user defines automatically follow it and there is no way for a user to create dyadic verbs that take a left and right argument. Instead user defined verbs always apply to the arguments in the order notated in the brackets. That is instead of the noun being to the right and left of the verb. They are now right and left respectively inside the brackets. There is a small caveat: this convention does not allow you to define a verb that applies to more than eight arguments. The reason is that keeping track of eight arguments is difficult enough and the limit suggests to the writer that possibly the verb they are building should be composed of several verbs, there are ways to get around this limit, but think of it as a guideline.

q simplified this concept of verb even further. All functions in k that can either be monadic or dyadic are always dyadic in q and a word is chosen to represent the monadic case. If you want the reciprocal you are going to have to ask for it directly reciprocal[7].

Alright, we have to answer two basic questions: what are the verbs that we can use?, ie the vocabulary of verbs and two what do we do if a verb is not in the vocabulary? define new verbs.

For the first I will link to a site:

Suppose that a verb is not in the vocabulary. For instance, suppose we want to build into q the idea of cheering up. First we need to define some nouns. Let’s use the emoticons to signify a scale of happiness.

Very simply we might have:

Crying – “:’(”
Sad – “:(”
Annoyed – “:/”
Neutral – “:|”
happy – “:)”
very happy – “:))”
laughing -“:D”
tears of joy – “:’)”

Alright so each of these emoticons, will symbolize possible emotional states. Because list of characters are themselves lists. We need to create a list of lists, the easiest way is to use the enlist verb.

emotions: enlist(“:’(“)

This creates the first emoticon as a separate entry in the list of emotions, the rest can be added by appending. Of course you can do it in one shot but this way, you can use enlist and avoid all kinds of annoyances from KDB trying to interpret all of the symbolic characters incorrectly. Note the semicolons between elements to separate the list of characters. For clarification, I’m putting spaces between the semicolons, but that is not necessary.

emotions,: (“:(” ; “:/” ; “:|” ; “:)” ; “:))” ; “:D” ; “:’)” )

one shot:
emotions:( “:'(“; “:(” ; “:/” ; “:|” ; “:)” ; “:))” ; “:D” ; “:’)” )

So we have emotions. Let’s define a verb that cheers someone up by one level. Let’s call it lift.

Definitions in k and q use the colon notation. Just like lists. But we use curly braces to show that we are creating one unified action. We also can specify an argument name. I will use ‘ce’ which stands for current emotion.

lift:{[ce] emotions:( “:'(“; “:(” ; “:/” ; “:|” ; “:)” ; “:))” ; “:D” ; “:’)” ); emotions[(emotions?ce)+1]}

That is the whole definition. As you can tell most of it is filled with defining the emotions. That’s this part:

lift:{[ce] emotions:( “:'(“; “:(” ; “:/” ; “:|” ; “:)” ; “:))” ; “:D” ; “:’)” ); emotions[(emotions?ce)+1]}

The next bit uses the ? verb to search. It takes a list and returns the number of the first match. If there are no matches it returns the number of elements in the list. Which is one after the last element (remember everything is starts from zero so a list with ten items has an empty slot at 10).

lift:{[ce] emotions:( “:'(“; “:(” ; “:/” ; “:|” ; “:)” ; “:))” ; “:D” ; “:’)” );

The last bit increments the index by one and returns the emotion at that index. k,q automatically return the last statement in a verb definition.

lift:{[ce] emotions:( “:'(“; “:(” ; “:/” ; “:|” ; “:)” ; “:))” ; “:D” ; “:’)” );

For example lift “:(” returns


What about if we reach the end or we search for an emotion not in the list? In both cases lift will simply return an empty string “”.

Well we all know you can lift someone’s spirits, but what about depressing them. It would seem we should be able to depress them and maybe by a certain quantity.

depress: {[ce;q] emotions:( “:'(“; “:(” ; “:/” ; “:|” ; “:)” ; “:))” ; “:D” ; “:’)” ); emotions[(emotions?ce)-q]}

returns “:(”

What we have done is add the argument q standing for quantity and now we can depress by a certain factor. Suppose we wanted to make a really simple version of depress that can only move an emotion down by one level. Let’s call it unlift.


Really short right?!

But let’s see what we did. First we took advantage of the fact that k,q has built in argument names for the first three arguments, they are x,y,z respectively. So I didn’t have to name it in the beginning explicitly like this

unlift: {[x] depress[;1] x}

Implicit Arguments: In k,q any verb you create can will automatically use x,  y,  z as the first 3 parameters. There are two equivalent ways to write a verb that converts the dimension to volume:

vol_3d:{[x;y;z] x*y*z}
vol_3d:{ x*y*z}

You can’t mix these two. So the following doesn’t work

vol_3d:{[h] x*y*h}

Now, to the really cool trick.  If you don’t fill in all the arguments, k will automatically create a new verb that is only missing the arguments you left out. So since I filled in that I would like to depress the emotional state by 1, and k doesn’t know which emotion I want to depress. It creates a new verb that depresses by 1. We then give that new verb a name and we now have a new verb. Note that if you get rid of the depress verb; k won’t be able to unlift. So technically, unlift has a dependency on depress.

This is known as function currying or projection in math and in some fancier programming languages, but don’t get scared by the name. It’s actually really simple. In APL, K, Q family this is almost always referred to as projection. The name comes from an analogy that most people are all familiar with. On a sunny day at high noon your shadow can follow you but can only move in two dimensions. It is projected onto the surface of the ground. The difference between your location and the location of the shadow, is that you can move in three directions {north,south} {west,east} and {jump(up,down)}. While your shadow can only move in two {north,south} {west,east}. The same idea is happening to a verb in K like addition (+), normally + adds two different numbers. But if we wanted to create verb named increment.
This new verb always adds one to a number. Some of the flexibility is gone from the addition verb.

Finally (Footnote as promised) on the second definition of verb.

The second definition is the idea of taking a word that is not normally a verb and making it a verb. Well, remember lists. Lists had a very similar notation to how we use verbs.

For instance: emotions 3 or emotions [3] both return

“:|” the fourth element in the list.

In other words, lists are actually a special kind of verb! Specifically, they are verbs that transform a particular index number into whatever is at that place in the list. This applies even more broadly to a type of list in k,q called a map or dictionary. Here is a really simple example: (we use ! to define this structure)

emotionsdict: `crying`sad`annoyed`neutral`happy`vhappy`laughing`tofjoy! ( “:'(“; “:(” ; “:/” ; “:|” ; “:)” ; “:))” ; “:D” ; “:’)” )

crying  | “:'(“
sad     | “:(“
annoyed | “:/”
neutral | “:|”
happy   | “:)”
vhappy  | “:))”
laughing| “:D”
tofjoy  | “:’)”

and emotionsdict `crying returns

and emotionsdict?”:'(” returns

The point is that instead of just thinking of this as an emotion to emoticon dictionary we can also think of it as a verb that takes an emotion and displays it as emoticon. More on this here. Also our addition and multiplication tables behave like those functions. For instance add[2;3] returns 5.

This idea that all lists are really special verbs or that verbs are special types of lists is very freeing. Because the next time you want to make a list, first think is there a way for me to just make a verb.

For example, are the even numbers a list or a verb? They are both:

(0, 2, 4,6…) and {2*x}.

Which is easier?

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


0 1 2 3 4 5 6 7 8 9

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


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


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)


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

(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.




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:


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:


in Q:

mltp:(a*) each a


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[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))


(0 0 1;0 0 1)


0 0 1



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