lambda
Recall that in Scheme, we can create anonymous (unnamed) procedures any
time we want, using the lambda special form.
For example, suppose you want to write a piece of code that needs to
double the values of the items in a list. You could do what we did
before, and define a named double procedure, but if you only
need to use the procedue in one place, it's easier to use an anonymous
procedure created with lambda.
Instead of writing
(define (double x) (+ x x))
and then using it like this
... (map double mylist) ...
You can simply define it where it's used, using lambda.
... (map (lambda (x) (+ x x)) mylist) ...
This can help avoid cluttering your code with lots of auxiliary procedures.
(Don't overdo it, though--if a procedure is nontrivial, it's good to
give it a name that reflects what it does.) This is very convenient
when using higher-order procedures like map, or higher-order
procedures you come up with for your own programs.
[ As we'll see in a little while, lambda has some very interesting
properties that make it more useful than it might seem right now. ]
[ point out that variable arity works with lambda arg lists just like with define arg lists ]
Scheme procedure's aren't really just pieces of code you can execute; they're closures.
A closure is a procedure that records what environment it was created in. When you call it, that environment is restored before the actual code is executed. This ensures that when a procedure executes, it sees the exact same variable bindings that were visible when it was created--it doesn't just remember variable names in its code, it remembers what storage each name referred to when it was created.
Since variable bindings are allocated on the heap, not on a stack,
this allows procedures to remember binding environments even after
the expressions that created those environments have been evaluated.
For example, a closure created by a lambda inside a let
will remember the let's variable bindings even after we've
exited the let. As long as we have a pointer to the procedure
(closure), the bindings it refers to are guaranteed to exist. (The
garbage collector will not reclaim the procedure's storage, or the
storage for the let bindings.)
Here's an example that may clarify this, and show one way of taking advantage of it.
Suppose we type the following expression at the Scheme prompt, to be interpreted in a top-level environment:
Scheme> (let ((count 0))
(lambda ()
(set! count (+ count 1))
count)))
#<proc ....>#
[ need picture here ]
Evaluating this let expression first creates a binding environment
with a binding for count. The initial value of this binding is 0.
In this environment, the lambda expression creates a closure. When
executed, this procedure will increment the count, and then return its
value. (Note that the procedure is not executed yet, however--it's just
created.) This procedure, returned by the lambda expression, is also
returned as the value of the let expression, because a let returns
the value of its last body expression. The read-eval-print loop therefore
prints a representation of the (anonymous) procedure.
Unfortunately, we didn't do anything with the value, like give it a
name, so we can't refer to it anymore, and the garbage collector will
just reclaim it. (OOPS.) Now suppose we want to do the same thing,
but hold onto the closure so that we can do something with it.
We'll bind a new variable my-counter, and use the above let
expression to create a new environment and procedure, just like before.
Scheme> (define my-counter
(let ((count 0))
(lambda ()
(set! count (+ count 1))
count))))
#void
Now we have a top-level binding of my-counter, whose value is
the procedure we created.
(The crucial trick here relies on the fact
that thet let expression not only creates the local variable
binding for count, but returns the value returned by the lambda
expression. The pointer to the procedure created by lambda is passed
along by the let to become the initial value for the binding of
my-counter.)
The procedure keeps a pointer to the
environment created by the let, which in turn has a pointer to
the top-level environment, thus:
[ should simplify this picture and use it earlier, for the simpler
example where we don't keep a pointer to the closure. Should
show the envt register pointing to the let envt at the moment the
closure is created. ]
[envt]
+-->+------------+-----+
| | car | *--+--> ...
| +------------+-----+
| | cons | *--+--> ...
| +------------+-----+
| | * |
| *
| | * |
| +------------+-----+
| | my-counter | *--+------------+
| +------------+-----+ |
| /|\ |
| | |
| [envt] | |
| +------------+--+--+ |
| | [scope] | * | |
| +------------+-----+ |
| | count | *--+-->10 |
| +------------+-----+ \|/
| /|\ [closure]
| | +---------+
| +----------------+----* |
| +---------+
| | * |
| +----+----+
| |
| \|/
| [code]
| +--------------------+
+---+---+ | (set! count |
envt | * | | (+ count 1)) |
+-------+ | count |
+--------------------+
Now if we call the procedure my-counter, it will execute in its own
"captured" environment (created by the let). It will increment the
binding of count in that environment, and return the result. The
environment will continue to exist as long as the procedure does,
and will store the latest value until next time my-counter
is called:
Scheme>(my-counter) 1 Scheme>(my-counter) 2 Scheme>(my-counter) 3
Notice that if we evaluate the let form again, we will get a new
let environment, and a new procedure that will increment and return
its count value--in effect, each procedure has its own little
piece of state which only it can see (because only it was created
in that particular environment).
If we want, we can define a procedure that will create new environments, and new procedures that capture those environments--we can generate new counter procedures just by calling that "higher-order" procedure. (Recall that a higher-order procedure is just a procedure that manipulates other procedures. In this case, we're making a procedure that generates procedures.)
Each time make-counter is called, it will execute a let,
creating an environment, and inside that it will use lambda to create
a counter procedure.
Scheme> (define (make-counter)
(let ((count 0))
(lambda ()
(set! count (+ count 1))
count)))
make-counter
Each of the resulting procedures will have its own captured count variable, and keep it independently of the other procedures.
Make sure you understand that the above procedure definition could
have used an explicit lambda to create the procedure
make-counter, rather than the special procedure definition
syntax:
Scheme> (define make-counter
(lambda ()
(let ((count 0))
(lambda ()
(set! count (+ count 1))
count)))
You may actually find this easier to understand, because it shows you
exactly what's going on: binding make-counter and creating a
procedure (with the outer lambda) that when called, will
evaluate a let to create an environment, and a lambda
(the inner one) to create a new procedure that captures that
particular environment.)
Now we'll call the procedure created by the above definition, three times, and each time it will create a new procedure:
Scheme> (define c1 (make-counter)) C1 Scheme> (define c2 (make-counter)) C2 Scheme> (define c3 (make-counter)) C3
Now we'll call those procedures and look at their return values, to illustrate that they're independent counters:
Scheme> (c1) 1 Scheme> (c1) 2 Scheme> (c2) 1 Scheme> (c2) 2 Scheme> (c1) 3 Scheme> (c1) 4 Scheme> (c3) 1
Neat, huh? The combination of block structure (local environments) with first-class procedures (closures), allows us to associate state with procedures. Garbage collection makes this very convenient, because we know that the environments will hang around as long as the procedures do.
If you're familiar with object-oriented programming, you may notice a resemblance between closures and "objects" in the object-oriented sense. A closure associates data with a procedure, where an object associates data with multiple procedures. After we get to object-oriented programming, we'll explain how object-oriented programming facilities can be implemented in Scheme using closures.
If you're familiar with graphical user interface systems, you may notice that GUI's often use "callbacks," which are procedures that are executed in response to user input events like button clicks and menu selections, and do something application-specific. (The application "registers" callback procedures with the GUI system, which then calls them when the user clicks on the specified buttons.) Closures make excellent GUI callback procedures, because the application can create a closure for a specific context by capturing variable bindings, to customize the behavior of the procedure.
It may seem that lambda is an expensive operation--after all,
it creates procedure objects on the fly. At first glance, you might
think that executing lambda would require a call to the compiler
each time. This is not the case, though, and lambda is actually
a fairly cheap constant-time operation.
Notice that the procedure part of a lambda expression is known at
compile time--each time the lambda is executed at run time, it
will create a new closure, and may capture a new environment, but
the expression closed in that environment is determined solely
by the body of the lambda expression. A compiler for scheme will
therefore compile the lambda like any other procedure, when it
compiles the enclosing procedure. So, for example, when our
example procedure make-counter is compiled, the compiler will
also compile the code for the lambda body. This code will be
kept around for use by make-counter.
The actual run-time code for lambda just consists of fetching
the address of the code, and the current environment pointer,
and putting them in a closure object on the heap. lambda is
therefore about as fast as cons---all that's really happening
is the creation of the closure object itself, not anything
expensive like calling the compiler at run-time.
[ cost of lambda calling is a handful of instructions...]