Lambda, Why and How

Eric Boudaillier 2004/01/23: I want to show here why lambda in tcl can be useful, and how to do it.

Some Tcl and Tk commands take a script as argument, to be eval'ed in certain circumstance. An example that comes to mind here is the Tk bind command:

  bind $w <ButtonPress-1> { DoSomething %W [expr {%x+10}] [expr {%y+10}] }

For bind, these scripts can be seen as glue code between the GUI and the application code.

Other commands, like lsort, don't take a script, but a command prefix: a command prefix acts like a script where one or more arguments are appended before being eval'ed. For these commands, there is no way other than defining a procedure to pass as a prefix. This is where lambda can be useful.

  lsort -command [lambda {x y} {string compare $x $y}] $elems

expr is a good candidate for being in the body of a lambda: sometimes, there is a need for arithmetics commands, like + or *. With lambda; this is simple, without explicitly defining a command:

  lmap [lambda {x} {expr {$x*2}}] $elems

How to implement lambda? The following implementation has learned from all the ones listed in lambda in tcl, to be:

  • fast: each lambda is a proc, so bytecode compilation is at best.
  • not proc consuming: lambda with the same arguments and body use the same proc.
  • allow currying, with just a small overhead.
 namespace eval lambda {
     namespace export lambda
 
     # Array containing procedure names created for lambdas.
     variable procsTable
 }
 
 # lambda --
 #
 proc lambda::lambda {paramList body} {
     variable procsTable
 
     # If the lambda doesn't exist, create a new
     # proc associated.
     set procKey "$paramList\1$body"
     if {![info exists procsTable($procKey)]} {
         variable procId
 
         if {![info exists procId]} {
             set procId 0
         }
         set procName ::lambda::lambda[incr procId]
         proc $procName $paramList $body
         set procsTable($procKey) $procName      
     } else {
         set procName $procsTable($procKey)
     }
 
     # Compute required arguments for calling lambda.
     set reqArgsLength [llength $paramList]
     if {[lindex $paramList end] eq "args" ||
         [llength [lindex $paramList end]] == 2} {
         incr reqArgsLength -1
         set paramList [lrange $paramList 0 end-1]
         while {[llength $paramList] && [llength [lindex $paramList end]] == 2} {
             incr reqArgsLength -1
             set paramList [lrange $paramList 0 end-1]
         }
     }
 
     return [list ::lambda::lambdaeval $reqArgsLength $procName]
 }
 
 # lambdaeval --
 #
 proc lambda::lambdaeval {reqArgsLength args} {
     if {[llength $args]-1 >= $reqArgsLength} {
         return [uplevel 1 $args]
     } else {
         return [linsert $args 0 ::lambda::lambdaeval $reqArgsLength]
     }
 }

The following code also redefines unknown to allow lambda call without the use of eval. Used as command prefix, this is nearly not necessary. RS: The code does not mention eval, but eval is just the special case "uplevel 0", and uplevel you do :). EB just meant without explicitely use eval.

 # rename unknown command to handle lamdbaeval call
 # without the need of eval
 if {![llength [info commands __lambda_unknown]]} {
     rename unknown __lambda_unknown
 
     proc unknown {cmd args} {
         if {[string equal [lindex $cmd 0] "::lambda::lambdaeval"]} {
             uplevel 1 $cmd $args
         } else {
             uplevel 1 [list __lambda_unknown $cmd] $args
         }
     }
 }

Here is a test to show the performance. I have also a C version of the code, which removes the lambdaeval frame and doesn't need uplevel.

 proc sum {x y} {expr {$x+$y}} 
 set sumLambda [lambda {x y} {expr {$x+$y}}]
 set sumCmd    [list sum]
 
 time {eval $sumLambda [list 4 3]} 1000
 time {eval $sumCmd    [list 4 3]} 1000
 
 Tcl lambda : 36 microseconds per iteration
 C   lambda : 23 microseconds per iteration
 Command    : 20 microseconds per iteration

FW: The "args/body" format doesn't work exhaustively for a proc key- if you defined lambda {a} {/b} and lambda {a/} {b} will both be cached as a//b, and the first one would be lost. I'd make the key [list $args $body] rather than $args/$body. Also, the whole caching idea bothers me a bit - you're storing the whole proc twice. An ideal method would be using checksums, but that's technically not perfectly foolproof. Personally, I think this is all just bickering. Generating a unique proc name and passing it around by reference is the traditional method, as with Donal's "never-forget" Lambda in Lambda in Tcl. And as far as I'm concerned, that's good enough. I think all these attempts to match the exact traditional definition of a Lambda by passing around the textual code are bordering on sad ;)

EB: First, note that the separator is \1, not /. I don't see what you mean about generating a unique name and passing it around by reference. If so, just define it with proc. The problem of the "never-forget" lambda is not that it never forget, but that it always create: don't use it in a loop or a procedure.


RS prefers to call a lambda exactly how the lambda proc was called (retrievable via [info level 0], so unambiguous names can be created like this:

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

or, for friends of K (like me),

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

ulis, 2004-01-26: I was waiting for the usefulness of lambda. Thanks for this page. The use of lambda to avoid defining procs for command prefixes seems to me of marginal interest. Does lambda have other usefulness?

EB: No, they're just procedure. Using lambda or not is just a matter of taste. You can use it where you normally used a small procedure only once in your code, eg local procedures. Lambda can also replace scripts generated using string map or regsub:

   set script [[lambda {a b} { ... }] $v]

They also give a local stack to scripts.