Lambda the Ultimate

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.

Stevan,

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

hi vlad

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

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

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

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

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]

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 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. ;)

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.

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.

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.

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.

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.

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?

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.

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