lambda

Lambda is the name for the letter "L" in the Greek alphabet. Since Alonzo Church's Lambda calculus. It is also the term for anonymous functions.

In Tcl (since 8.5?), a lambda is an anonymous command prefix whose first word is apply. The lambda package in Tcllib

provides an appropriate implementation, as follows:

proc lambda {arguments body args} {
    return [list ::apply [list $arguments $body] {*}$args]
}

proc lambda@ {ns arguments body args} {
    return [list ::apply [list $arguments $body $ns] {*}$args]
}

Reference edit

Lambda: The Ultimate Imperative, Guy Lewis Steele Jr., 1976-03-10
Lambda: the ultimate declarative, Guy Lewis Steele Jr, 1976-11
My Favorite Calculus: Lambda (part 1), MarkCC, 2006
The Genius of Alonzo Church: Numbers in Lambda Calculus, MarkCC, 2006-06-15

Description edit

Richard Suchenwirth et al:

Consider

f(x) = x+1

is not much different from

g(x) = x+1

except for the f/g difference, which are both arbitrary names. The common essence of the above functions, ignoring the name, is just

(x) = x+1

or in other words, "given x, return x+1". In Tcl, this looks like

lambda x {expr {$x+1}}

and it's easy to implement - see Lambda in Tcl and Lambda in Tcl8.5.

To have lambdas directly, one change to Tcl would be:

If a command name is a list of length three, with lambda as first element, bind its arguments to the second element of the list, and then evaluate the third element in that scope.

As long as we don't have this, a simple way is to make up a name for a proc:

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

where the lambda definition is returned as command name.

A more functional programming way would be, using the K combinator:

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

See also RPN again for "half-lambdas": only the body is the value of a function, arguments are popped from the stack, the result is pushed on the stack.

MS 2004-04-23: Although not really functional programming, one might try to do

lambda x {set ::y x}

But this fails: Tcl tries to create a proc named y x} in the namespace lambda x {set ", instead of the intended proc. This may be a namespace bug though.

It seems like it would be pretty easy for unknown to do this automatically...

RS: Yes. Good idea. Let unknown know. It would just miss the efficiency of C-coded Tcl, but with today's CPUs, that's less of a problem... 2005-03-29: Here's the unknown code, leading to pure-value lightweight lambdas (see Block-local variables for how it came about):

proc with {argl body args} {
    if {[llength $argl] != [llength $args]} {error "wrong #args, must be: $argl"}
    foreach $argl $args {}
    eval $body
}
#-- Augmenting [unknown]:
proc know what {proc unknown args $what\n[info body unknown]}
know {
    if {[llength [lindex $args 0]] > 1} {
        return [uplevel 1 [lindex $args 0] [lrange $args 1 end]]}
 }

#-- Testing (the lambda is just a string that we assign to a variable):
% set tail {with x {lrange $x 1 end}}
with x {lrange $x 1 end}
% $tail {a b c d e}
b c d e

RS: While the term lambda was coined by Alonzo Church, the concept is older. I found one instance in "Funktion und Begriff", Gottlob Frege (1848-1925), Jena 1891, where he identifies functions by their Werteverlauf (value extension?), without naming them. Instead, he first puts a Greek vowel with "spiritus lenis" (looking like a superscript comma on top of the letter), and then the function "body" in parens. He then goes to show (translated to modern ASCII, and even (almost) Tcl :) that

 lambda e {expr $e**2 - 4*$e} == lambda a {expr $a * ($a - 4)}

In other words, that the two anonymous functions are identical. To prove this, one would have to iterate over all possible values of e and a (which, even with doubles, is finite, but might take a long time...)

NEM 2010-07-02: Re-reading Norvig's classic Paradigms of Artificial Intelligence Programming just now, I came across this explanation for the origins of the term "lambda" (§1.7):

"Lambda derives from the notation in Russell and Whitehead's Principia Mathematica, which uses a caret over bound variables: x̂(x+x) [*]. Church wanted a one-dimensional string, so he moved the caret in front: ^x(x+x). The caret looked funny with nothing below it, so Church switched to the closest thing, an uppercase lambda, Λx(x+x). The Λ was easily confused with other symbols, so eventually the lowercase lambda was substituted: λx(x+x). John McCarthy was a student of Church's at Princeton, so when McCarthy invented Lisp in 1958, he adopted the lambda notation. There were no Greek letters on the keypunches of that era, so McCarthy used (lambda (x) (+ x x)), and it has survived to this day."

[*] There's a ^ over the first x, but your browser might not display it correctly.

Since I've done my share of LISP programming in the past, the term lambda is instantly recognizable to me. I'm not convinced it means much to the average programmer, though. Given RS's description at the start of this page f(x) = x+1 ... in other words, given x, return x+1 ..., it makes me think that perhaps "given" would make a more readable / recognizable name for a command than "lambda".

For example, instead of this:

lambda x {expr {$x+1}}

... perhaps the following makes a more readable example, especially when used with an explicit return...

given {x} {return [expr {$x + 1}]}

Using "given" and an explicit return, I bet even folks who have never heard of "lambda" can understand what is going on. RS: I know that not everyone agrees, but when doing functional programming an implicit return should be no surprise... :^)

LV: I don't understand the use of the word given in this situation.

coward: it is just a more human-friendly form of the word "lambda". It means "make an anonymous proc with the arguments {x} and the body {return ...}

LV: Also, why use expr instead of incr?

[coward]: that is irrelevant to the point I was trying to make; incr or expr or your-favorite-proc all work equally well

RS: expr still works if x is a floating-point number, while incr demands an integer.

Here's more examples (based on examples from lambda in tcl8.5)

lsort -command [given {x y} {
    return [expr {[string length $x] < [string length $y]}]}] $list
trace add variable ::foo write [given args {puts "foo = $::foo"}]

glennj: In lambda... again

, comp.lang.tcl, 2007-10-22, Neil Madden wrote in clt an excellent summary of the sorts of places lambdas are useful.

: For example, did you realise that apply works nicely with pretty much every command in the Tcl and Tk libraries that takes a callback?

# I always recommend using a constructor for lambdas:
proc lambda {params body} {
    list apply [list $params $body]
}
lsort -command [lambda {a b} { ... }] $xs
http::geturl $url -command [lambda tok { ... }]
after 1000 [lambda {} { puts Hello! }]
socket -server [lambda {sock addr port} { ... }] 8080
trace add variable foo write [lambda {v1 v2 op} { ... }]
etc etc

ND: lambda proc from nest package

    proc lambda {params body args} {

        set {llength_params} [llength ${params}]
        set {llength_args} [llength ${args}]

        if { ${llength_params} - 1 <= ${llength_args} } {
            set {last_param} [lindex ${params} {end}]
            if { ${llength_params} == ${llength_args} || ${last_param} eq {args} } {
                unset {llength_params} {llength_args}
                return [uplevel 0 ${body} [if {${params} eq {}} {
                    # llength_params == 0 and llength_args == 0
                    unset {last_param} {params} {body} {args}
                } elseif { ${last_param} ne {args} } {
                    # llength_params == llength_args
                    lassign ${args} {*}[concat ${params} \
                        [unset {last_param} {params} {body} {args}]]
                } else {
                    # (llength_params - 1 <= llength_args) and last_param eq {args}
                    set {args} [lassign ${args} {*}[lrange [concat ${params} \
                        [unset {last_param} {params} {body} {args}]] 0 {end-1}]]
                    set {} {}
                }]]
            }
        }

        if { ${args} eq {} } {
            return [list {lambda} ${params} ${body}]
        } elseif {${llength_params} >= ${llength_args}} {
            return \
                [list {lambda} [lrange ${params} ${llength_args} {end}] \
                    [concat \
                        [list lassign ${args} \
                            {*}[lrange ${params} 0 [expr {${llength_args} - 1}]]] 
                    { ; } 
                    ${body}]]
        } else {
            error "lambda: more args than params"
        }

    }

Category Concept

Category Functional Programming

Arts and crafts of Tcl-Tk programming

See Also edit

Reference edit

Description edit