Version 35 of K

Updated 2011-01-14 13:00:27 by busirane

Short for the K combinator, together with S the fundamental functional operators from which all function composition can be done. It is extremely simple:

 proc K {x y} {set x}

It just returns its first argument (and discards the second). The advantage is that in this way you can hold an intermediate result which you finally want to return, after doing more processing (which ends up in y) where only the side effects matter. Consider popping a global stack (top at end):

 proc pop1 {} {
    set top [lindex $::Stack end]
    set ::Stack [lrange $::Stack 0 end-1]
    return $top
 }

or, implemented with K:

 proc pop2 {} {K [lindex $::Stack end] [set ::Stack [lrange $::Stack 0 end-1]]}

One command less, one variable less, a slick one-liner (from: A different FORTH).

See Hot curry and Combinator engine for more details than you'd expect ;-)


Another use of K is for making a get-and-unset command, which can be rather useful for efficient handling of Tcl_Objs. Note that this is not done as a procedure (AJD but surely K is a procedure?); that adds quite a bit of execution overhead.

Replace $someVar with:c

 [K $someVar [unset someVar]]

AJD Note, that if someVar is going to be reused, then it is more efficient to:

 set someVar [someFunc [K $someVar [set someVar ""]]]

...as this avoids deleting then recreating the somevar variable. Of course this assumes that someFunc is able to make more efficient use of a singly referenced Tcl_Obj - the common examples are lrange and linsert.


K provides profound performance advantages that are not immediately apparent, changing common operations from quadratic in data length to constant scale. Helmut Giese writes about this in [L1 ] and [L2 ]. It also shows up in many performance discussions, such as how to shuffle a list.


A generalized K, that returns the first of its arguments:

 proc K* {arg args} {set arg}

can also be used as identity operator with one argument, which comes in handy when using if like this (remember it returns the result of the applying branch):

 set result [if $condition {K* yes} else {K* no}]

which is another way for writing

 set result [expr {$condition? "yes" : "no"}] ;# RS

DKF: However, this is not really K as that is a two-argument combinator; indeed, there's no such thing as an n-arg combinator as every one has to have a specific number of arguments (which is enforced by the binding and evaluation rules of combinator theory - need reference on Head Normal Form here, but none handy.) It makes more sense though for Tcl though, which (normally) knows how many arguments there are without looking at the command name.

AMG I renamed from K to K* to differentiate this proc from the K combinator DKF describes.


Lambda in Tcl can also be had as a one-liner with K:

 proc lambda {argl body} {K [set n [info level 0]] [proc $n $argl $body]}

In the Tcl chatroom, Miguel pointed out "inline K":

 [K a b] ~ [lindex [list a b] 0]

That's slightly faster in 8.4+, as it is all bcc'ed.


From 8.5, "anonymous K" will be more efficient:

 set someVar [someFunc $someVar[set someVar ""]]

Just glue the unsetter directly after the retrieved value... (RS)

sbron: According to Miguel in the Tcl chatroom this has been backported to 8.4.8

Lars H: It doesn't seem to be in 8.4.10. Exploiting a bug concerning internal representation of wide integers:

 % set a [expr {wide(65536)}]
 65536
 % expr {$a*$a}
 4294967296
 % set b $a[set a ""]
 65536
 % expr {$b*$b}
 0

IOW the $b Tcl_Obj isn't the same as the original $a one -- it is being reparsed from the string representation (and thus becomes an ordinary int). That's the kind of detour one cannot afford if at all bothering with tricks of this kind.

MS does not have 8.4.10 handy, but just tested 8.4.11 and HEAD and observed the "correct" behaviour in both cases at the console. According to the Changelog, this was backported on 2004-09-10 and 8.4.8 was tagged for release on 2004-11-19. However, there is a bug in the implementation - it only works for byte-compiled code. See also Bug #1251791 [L3 ].

Lars H: You're right! If instead of

 % set b $a[set a ""]

I do

 % if 1 then {set b $a[set a ""]}

then I get 4294967296 also from squaring $b. Good that have this verified.


NEM: There is also a language called K: [L4 ]. It's tailored towards high-performance relational database work -- data mining? As I understand it, it is somewhat related to APL, but jcw would know more about the specifics. I'm not aware of any direct connection to Tcl.

PWQ 6 Aug 05, I find it interesting that the K combinator came in to prominance due to inefficencies in the structure of the list handling commands and the copy on write semantics of Tcl.

This spawned much discussion and resulted in the lset command which did little to solve the problem from a general perspective.

I find nothing to commend the K function from either the above or any other programming perspective. All fail to enhance the usability of Tcl in the programming context.

NEM Actually, the K combinator came into prominance due to the work of Curry and Schönfinkel on Combinatory Logic. It's use as an optimisation in Tcl is entirely incidental. If you don't like it, then don't use it. Stop trolling.

RS Besides use in performance enhancement, I mostly like K because it very simply gives us sort of the PROG1 functionality in Lisp - do this and that, and return the result of "this" :) This often helps to avoid an intermediate variable.


LV 2007 Nov 30

Are there changes that could be made in Tcl (perhaps Tcl 9) after which this optimization would no longer be needed?


VI 2008 Mar 4. Just an example demonstrating file read without an intermediate variable using K

   K [read [set fi [open $src]]] [close $fi]

JJS 2011 Jan 14. How is this not using an intermediate variable? After execution, fi still contains the name of the closed channel. I don't see how it's any different from a normal open/read/close; both pollute the namespace with the intermediate variable.