Version 2 of Lambda, Why and How

Updated 2004-01-23 15:18:00

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

 # 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

---

Category Concept