Short for the K combinator, together with [S] the fundamental functional operators in [Combinatory Logic] 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_Obj]s. 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 [http://groups.google.com/group/comp.lang.tcl/browse_thread/thread/b72d696e6d244dcd/8805f57c66589015] and [http://groups.google.com/group/comp.lang.tcl/browse_thread/thread/91d18df5a73c880e/6d843a561a8df18b]. 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 [https://sourceforge.net/tracker/index.php?func=detail&aid=1251791&group_id=10894&atid=110894]. [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: [http://www.kx.com/index.php]. 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 [troll]ing. [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. ---- ''[[from [https://groups.google.com/group/comp.lang.tcl/msg/c6caedf27a84616a?hl=en%|%comp.lang.tcl]]]'' On Jan 14, 8:40 am, tomas wrote: <
> > someone care to enlighten us newbies on "K-tricks"? They're named after K, which is one of the fundamental combinators and which is used to produce a sort of constant function. But that's not what we use it for. :-) What's going on is that, at the C level, Tcl ''values'' are stored in reference counted structures called [Tcl_Obj]s. These can be efficiently shared and passed around, but for Tcl's semantics to work right, can only be modified when they're ''not'' shared. If they're shared, they have to be copied first; the copy is unshared and can then be modified at will. Now, applying this knowledge to the specific case where we're going to do a little list manipulating of a value in a variable and write it back: ====== set x [lreplace $x 2 3 foo bar grill] ====== Where are the references held? Well, there's going to be one reference in the variable (obviously!) and there's going to be another from the argument list; that second reference has to happen because otherwise we'd lose transient values such as the results of complicated substitutions. But this means that the list value is shared! The [lreplace] operation has to duplicate it, which is expensive (especially for long lists). What do we want to do to make it cheaper? Easy, we need to reduce the number of references held at the point when [lreplace] works on the value. Since there's a mandatory reference held as part of the argument list, the one we have to get rid of is due to the variable. So what does the K trick do here? Well, it lets us reduce the reference count in the variable by changing it to something else or unsetting it, while still using that value. There are many such variations: here's one that's relatively clear: ====== set x [lreplace [lindex [list $x [unset x]] 0] 2 3 foo bar grill] ====== What have we done? Well, firstly most of the command is unchanged. All we've done is replace `$x` with `[[[lindex] [[[list] $x [[[unset] x]]]] 0]]`. The only part that is perhaps not immediately obvious to you is that `[[[unset] x]]` does indeed have a result: the empty string. However, at the reference level it's more interesting. Firstly, it adds another reference to the value in 'x' (as part of the arguments to [list]). Then it unsets 'x', which reduces the reference count back to 1; the rest of the construction is just about extracting that value from the arguments to [list] and converting it into a naked argument to [lreplace] (with no net change to its reference count). That then means that the [lreplace] has an unshared value to work with, and can hence do its edits in place; that's faster. The original K trick was similar, but used a helper procedure: ====== proc K {x y} {return $x} set x [lreplace [K $x [unset x]] 2 3 foo bar grill] ====== The details are slightly different but the overall story is the same. Moreover, in 8.5 there's a cheaper version that has less intermediate state: ====== set x [lreplace $x[unset x] 2 3 foo bar grill] ====== This is a bit trickier as it relies on the fact that concatenation of any value with the empty string is a specially optimized case. (In all the above things, it all works just as well if you use `[[[set] x ""]]` for `[[[unset] x]]`; any other constant would do too. Indeed, there's a real sense in which unsetting a variable is just writing a NULL for its contents instead of a value reference.) Of course, if this is unclear then ignore it. Write your code in a simple way first. Then if you think there's a problem with speed, use [time] to check whether that's really so. Only use the tricks described in this post if you're sure that the lack of clarity is justified by the ''measured'' performance boost. ---- [aspect]: Here are some standard K-based combinators that make their way into many of my scripts. SK takes its name from combinatorial logic, as discussed near the top of this page. ====== # K generalised to multiple arguments -- because why not? proc K {a args} {set a} # (S x y z) = (x z (y z)) => (S K f x) = (K x (f x)) # naive version: proc SK {f x} {K $x [$f $x]} proc SK {f args} {K $args [uplevel 1 [list $f {*}$args]]} # Throwaway Debugging: puts the argument and return it proc D {a} {SK puts $a} # unset a variable, returning the value it had proc unset! {name} {upvar 1 $name x; K [set x] [unset x]} proc clear {name} {upvar 1 $name x; K [set x] [set x {}]} # Post-set: set a variable, returning its previous value proc set! {name val} {upvar 1 $name x; K [set x] [set x $val]} ====== ---- !!!!!! %| [Category Concept] |% [Arts and crafts of Tcl-Tk programming] !!!!!!