Rich resource site for the programming language "K"

I don't remember how I stumbled upon this, but I've been interested in K for quite some time but could not find much in way of information and examples (outside of the Kx Systems commercial site).

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Yes, Stevan Apter's site is wonderful

Lots of good language design materials there, too, in regard to concatenative languages built in K (such as XY).

Sadly, if ever there was a language hampered by licensing issues, K is it.

k is nice, have you seen q?

q is the next generation from Kx. Personally I prefer it to k.

http://kx.com/q/d/q.htm

anagram problem in k and q

the anagram problem discussed on comp.lang.lisp here has the k solution (by mackenzie straight):

{x g@&1<#:'g:={x@<x}'x}

and the q solution:

desc count each group asc each

q and k are semantically equivalent. q is just an alternative parser for k.

Previously on LtU

The NSL site has been mentioned previously on LtU, but only in passing.

no stinking loops

thanks all - i'm glad you find the site useful.

any questions i can (try to) answer?

and yes, i too prefer k4 (q) to k (k2/3). atw has made several subtle, but powerful extensions. i've included a couple of k4 solutions on my site, viz., the two sudoku solvers by atw and roger hui, and two of the raytracers, one by atw (scalar), and one by me (vector.)

licensing

Stevan,

why did Kx pull the free evaluation download from their site? Any chance of getting it sometime?

evaluation copy

hi vlad

you can write to simon@kx.com and request a copy for personal use.

Thanks! I wrote to

Thanks!

I wrote to info@kx.com yesterday, no answer yet. Will wait more.

Tried to email simon@kx.com today, got a "your message was considered SPAM" response :-)

Not to be confused with the other Q...

That would be the Q Equational Programming Language, based on term rewriting:

http://q-lang.sourceforge.net/

K intro on kuro5hin

Jjayson on kuro5hin wrote a good K intro.

Yikes

Yikes, ASCII art languages. From the site:


,/|\'(&x)_ y
x[ ,/&\'(&x)_ y
sa:{x[ il:{(#x)#+\0,x}
{,/x+' d:{[n;f]:[n;_f[n-1;f]';f]}
(x,"*")[(#x)&

The notation here does not seem particularly helpful to understanding the intention behind the code.

a data point

I've been trying to read and write K for a grand total of 1 day now. The constructs I have learned to date - about 10 built-in verbs and adverbs - are in fact very readable and stick to memory like a charm. I can easily make sense of many K examples from the site...

Keep in mind that I have no previous experience with vector languages at all, and very limited experience with functional languages :-)

Program LOD

I've always thought that the trick to these kinds of languages was going to be a formal multiple representation model, where the "text" of a program can cleanly, losslessly be transformed between verbose and terse representations, or anything in between. There is a natural intersection between ZUI techniques and this notion; zooming in on or requesting enhancement for a given area of a program would result in successively more information.

It's like LOD for programs. Same problem as the kind of stuff you do. ;)

An AST is roughly like a geometric model. Do we insist that artists create their work by manipulating text? Nope!

k notation

k notation isn't the problem. on the contrary, it is the most compact and perspicuous notation for describing k algorithms.

consider, for example, the code for computing the cross-concatenation of a list of lists:

  cross:(,/,/:\:)/(),/:
  cross(1 2;3 4 5;6)
(1 3 6
 1 4 6
 1 5 6
 2 3 6
 2 4 6
 2 5 6)

the function contains one verb:

x,y  x joined with y

one constant

()   the empty list (null)

and three adverbs:

/:   each-right
\:   each-left
/    over

would it help to spell things out?

cross:(join over join each-right each-left)over null join each-right

i don't think so!

perhaps it would help some to break the function into smaller named pieces:

raze:,/
crossjoin:,/:\:
listeach:(),/:
cross:(raze crossjoin@)/listeach@

a little, but not much.

the problem is how to duplicate in the mind of the reader the thoughts of the writer - a kind of diagram of the actions of the parts and how they contribute to the action of the whole. and that information simply isn't available in the definition of the function.

i think of k as a hypothesis: given this set of primitives, and this notation for fitting them together into larger wholes, we will discover novel and surprising algorithms. as problems emerge which defeat the hypothesis, we may consider (with great care!) how and whether to extend the language by adding new primitives, or extending their behavior, or (but rarely!) modifying the notation.

but i think you're on the right track by observing the analogy between programming and painting.

Cross Concatenation in Haskell

Getting off-topic, but I thought I'd try a version of cross-concatenation in Haskell...

cross     []  = [[]]
cross  (x:xs) = [a:b| a <- x, b <- cross xs]

Or just use 'sequence'

I just thought I'd point out that the standard prelude function 'sequence' already does this, ie.

cross = sequence

It's easy to miss that because sequence is abstracted over arbitrary monads rather than just lists.
Your version nicely shows how it can be done from first principles though.

Would it help to spell

Would it help to spell things out? Given your example, yes! :) I have no problem with terse notations; they make sense once essential familiarities have been gained. The problem is not how to duplicate the thoughts of the writer in the mind of the reader; it is to convey understanding. Each punctuation mark in K has a meaning; those meanings are _named_ and _defined_ in the K reference manual; readers of K code must perform several tasks to gain understanding: Translate symbol to name, recall the definition of the name, then understand the effect of that definition in the usage context. When you read K, does your internal voice say "comma, comma, colon" or does it say "join, each-left, cross"? It's probably the latter. I argue only that the terse representation is not the only relevant notation.

The most interesting thing about K is decidedly not its notation; what interests me about K is the set of operations it defines, and the seamless way it handles arguments of different shape. And the K tree. And the dependency system. You get the idea. ;)

The notation is important

K is like regexps. Terse, but useful. And just like regexps, making it more verbose would spoil the fun.

Have you actually tried reading and writing K? For me, one day was enough to stop complaining about the notation and start loving it.

exactly so

which supports the view that haskell notation is well-suited for expressing algorithms which "follow the grain" of that language.

in k, we want the primitives to do the looping implicitly (and that includes (or precludes) recursion.)

It takes a matter of minutes

It takes a matter of minutes to knock up a set of such primitives in Haskell and then start working with them.

Applicative and compositional styles both work effectively in haskell regardless of what the chosen primitives actually do.

Transliterating to Language "X"

Is there a quick cheat sheet for that explains K in terms a Haskell, Scheme, etc. programmer would understand? The examples on Kuro5hin aren't quite enough. It looks like "/:" and "\:" are related to map and "/" might be like foldl1 and "," is cons, but that can't quite be right, because then ",/" would be a no-op.

some examples

I'll give a few examples, though be warned that these are not giving you functions with the same generality as the k ones (also my k is limited, I'm more used to its successor q). Comments will be k and the rest will be haskell.

Given the lists:

-- x:10 30 20 40
-- y:13 34 25 46

x = [10,30,20,40] 
y = [13,34,25,46] 

-- x,y
x ++ y 

-- x,'y 
zip x y

-- x,\: y 

map (\ z -> [z] ++ y) x

or like so:

eachleft (++) x y
where eachleft f x y = map (\ z -> [z] `f` y) x

-- x,/: y 
map (\ z -> x ++ [z]) y

or like so:

eachright (++) x y
where eachright  f x y = map (\z -> x `f` [z]) y

I suppose you could write a limited form of raze:

-- ,/
raze = foldl (++) []

The point free style in haskell was more common when the Bird-Meertens Formalism was cool, but I think it quickly leads to unreadable code when over used. I find the haskell definition of cross given in a previous comment to be quite pleasing.

Offhand I think you'd struggle to write functions quite as general as the k ones in haskell due to the mismatch between the type systems, and the way apl family languages let functions written over scalars to be automatically generalized to arrays and nested arrays.

Generality

Offhand I think you'd struggle to write functions quite as general as the k ones
I agree. You could get kind of close by defining a "K" type class and then instantiating that for lists, arrays, arrays of lists, etc. but obviously thats going to get pretty tedious. Perhaps a future version of haskell with support for say polytypism or some other more expressive type-level programming could automate that though.

Generality

Yes, I think you could get a lot closer to k using polytypic extensions, but - just thinking out loud - I wonder if you'll run into problems where you have to apply to nested datatypes as well as regular?

another example, from q to sac

The standard function rotate in q:

rotate:{,/|(0;mod[x;#y])_y}

which you would use like so:

a:key 10  / This sets a to be the list 0 1 2 3 4 5 6 7 8 9 
rotate [4;a] / This evals to 4 5 6 7 8 9 0 1 2 3

We might write a SAC function, working on any shape array of ints like so (this is based on a half remembered paper I read on defining APL style operators and I don't have the SAC compiler handy to verify):

int[] rotate(int d, int n, int[] A) { 
  maxrotate = shape(A)[d]; 
  n = n % maxrotate; 
  if (n < 0) n += maxrotate; 
  offset = modarray(0*shape(A), [d], n); 
  sliceShape = modarray(shape(A), [d], n); 
  result = with (offset <= i—vec <= shape(A)­-1) 
           modarray(A, i_vec, A[i_vec—­offset]); 
  result = with (0*sliceShape <= i_vec <= sliceShape-­1) 
           modarray(result, i_vec, A[shape(A)-­sliceShape+i_vec]); 
  return(result);
} 

Aside: I've been thinking a lot about the problem of programming architectures like Cell, where as nice as interpreters like k or q are, highly optimizing compilation from a language like SAC would be a far better bet for producing good code. So that is what I've been mostly concentrating on, but I wonder if there is a market for interactive tools on them as well.

There are two things here

There are two things here which impede my understanding of "cross:(,/,/:\:)/(),/:".

The most obvious is that I don't have an intuition of how this is parsed, e.g. where the symbol boundaries lie and how they are joined together into programming constructs. From reading and mathematics, we all have an elaborate intuition of how to parse things like "myfunc(x,a)=x*2+a". That intuition doesn't help us with complex new symbols and precedence rules are introduced.

The other impediment also exists in reading Haskell code written in the "point-free" style, where functions are defined as compositions and higher-order functions of other functions such as "f = map (sin . cos)". Here, I can easily parse this definition, but it's harder to see the meaning given just prerequisite knowledge of math and other programming languages. To me, this definition is much clearer when function arguments and the underlying computation are written explicitly, such as "f(xs)=[sin(cos(x)) | x in xs]".

k syntax

syntax categories:

nouns: 10 "abc" `foo ...
verbs: + * , % ...
adverbs: / \ ' /: \: ':

binding strengths and result categories:

nnn
vvv
nvn
nmn
mnv
vna vva       

For example, mnv means that you get a monad (a function of one argument) if you've got a noun next to a verb.

the table also gives the relative binding strengths of pairs: nn has lowest binding strength. na and va have highest binding strength.

the algorithm for parsing is simple: start at the end and scan left until the binding strength between pairs drops (or you hit the beginning). at that point, bind the pair on the right and go back to the end and continue scanning left.

example:

(+/'q*-10 20 30+s)%/:(+/c)*/:t+s
 vaanvvn───────vn va─ van va─nvn
 v─ m─ m────────  v── v─  v──m─
 v──   n─────────     n──    n──
      n──────────    m───────
    n────────────    n──────────
 n───────────────
m────────────────────
n───────────────────────────────

(,/,/:\:)/(),/:
 vava─a─ an va─
 v─v──      v──
   v────  m────
 n──────
v─────────

a little parser for pure k is here

because k parses right to left, you read it left to right. for example,

a+-b*+/c

a + the value of everything to the right =
- the value of everything to the right =
b* the value of everything to the right =
+/ the value of everthing to the right =
c