let: letrec and let*
Scheme provides two useful variants of let. letrec
supports the creation of recursive local procedures, including
mutually recursive sets of procedures. let* supports the
sequenced binding of variables, where each initial value expression
can use the previous bindings.
letrec
When a normal let is evaluated, the initial value expressions
are evaluated before binding is done. The initial value expressions
execute in the environment outside the let, and then the bindings
are created and initialized with those values.
Often, we want the initial value expression for a binding to be able to create a procedure that will see the new bindings. For example, suppose we want to create a local procedure which is recursive. We might try this:
;; buggy example with (non-)tail-recursive local procedure
(define (some-procedure...)
(let ((helper (lambda (x)
...
(if some-test?
(helper ...))))) ;; broken recursive call
...
(helper ...) ;; call to (non-)recursive local procedure
...))
The problem with this example is that when the let is evaluated,
the lambda expression will create the helper procedure in the
wrong environment--before the variable helper is bound. The
resulting procedure will be scoped in the environment outside the
let, not the new environment where helper is visible.
When the procedure calls helper---which we had intended to
be a recursive call--it will not use new binding of helper
that we created. Inside the lambda body, helper will
still refer to whatever binding of helper was visible before
intering the let. (Very likely, that's no variable at all, and this
will cause an unbound variable error.)
letrec lets us create an environment before evaluating
the initial value expressions, so that the initial value computions
execute inside the new environment. We can fix the problem by using
a letrec instead of a let:
(define (some-procedure...)
(letrec ((helper (lambda (x)
...
(if some-test?
(helper ...))))) ;; recursive call
...
(helper ...) ;; call to recursive local procedure
...))
Now the procedure helper can "see its own name," since the
lambda expression is evaluated in the environment where helper
is bound.
More concretely, notice that when this procedure is run, it creates
an environment and closure that are linked circularly. The environment
contains a binding of helper that holds a pointer to the
closure created by lambda. The closure, in turn, contains
a pointer back to that same environment, which is where it was
created. It is this circularity that makes the procedure recursive;
when it refers to helper, it fetches the value of this
binding, which points to itself.
We can get the same effect using let and set!.
A letrec expression is equivalent to a let where the
bindings are initialized with dummy values, and then the initial
values are computed and assigned into the bindings. The above example
is equivalent to:
(define (some-procedure ...)
(let ((helper '*dummy-value*))
(set! helper (lambda (x)
...
(if some-test?
(helper ...))))) ; recursive call
...
(helper ...) ; call to recursive local procedure
...))
Here the let creates a binding, initializing it with an
arbitary value that isn't actually used--it's just a placeholder.
Then, once the let is entered and the binding is visible,
a closure is created (in that environment) and a pointer to it
is installed in that binding.
letrec can be used when defining mutually recursive procedures,
each of which can see the others' names and call them.
(define (some procedure ...)
(letrec ((helper1 (lambda ()
... (helper2) ...))
(helper2 (lambda ()
... (helper1) ...)))
...
(helper1) ; start up mutual recursion
...))
Notice that all letrec does is bind variables and (re-)initialize
them. You can use it to define plain variables as well as procedure
variables. For example, if the recursive procedures above need
to reference a shared variable, you can do this:
(define (some procedure ...)
(letrec ((helper1 (lambda ()
... var1 ... (helper2) ...))
(helper2 (lambda ()
... (helper1) ... var1 ...))
(var1 #f))
...
(helper1) ;; start up mutual recursion
...))
[ should come up with some simple concrete examples...]
As with let, the order of evaluation of a letrec's initial
value expressions is undefined. For example, the above letrec
might be compiled as though it were a let like this:
(define (some procedure ...)
(let ((helper1 '*dummy-value*)
(helper2 '*dummy-value*)
(var1 '*dummy-value*))
(set! helper2 (lambda ()
... (helper1) ... var1 ...))
(set! var1 #f)
(set! helper1 (lambda ()
... var1 ... (helper2) ...))
...
(helper1) ;; start up mutual recursion
...))
When using letrec and lambda to define local procedures,
in the usual way, the order of evaluation is irrelevant--the lambda
expressions can be executed in any order, because they only refer to
the bindings of the letrec variables, not their values.
The values are only used when the resulting procedures are called. The
following would be an error, however:
(define (some procedure ...)
(letrec ((helper1 ...)
(helper2 ...)
(var1 (list helper1 helper2)))
...
((car (var1 helper1))) ; start up mutual recursion
...))
Here the initialization of var1 depends on the values of
helper1 and helper2, which may not have been computed yet.
letrec and lambda to Implement Modules
Standard Scheme does not have a module system, but letrec and
lambda are powerful enough to implement modules in portable
Scheme.
Suppose we would like to define a module that encapsulates a set of procedures and variables, but only exports a subset of those procedures.
We can represent the module as a letrec environment which exports
an association list of of procedures.
Here we'll create a module called foo, which defines four
procedures and two variables, and exports two of the procedures, foo
and bar.
(define foo-module
;; create a letrec environment with internal definitions
;; of some variables and procedures
(letrec ((private-proc1 (lambda (...) ...))
(private-proc2 (lambda (...) ...))
(private-var1 ...)
(private-var2 ...)
(foo (lambda (...) ...))
(bar (lambda (...) ...)))
;; return an association list of "exported" closures
(list (list 'foo foo)
(list 'bar bar))))
The letrec expression will create an environment, and within
that environment it will evaluate the initial value expressions to
initialize the bindings. All of the procedures in the letrec
can see each other's names, and call each other freely. Procedures
outside the letrec cannot.
The only procedures that can be called from outside the letrec
are foo and bar, which are returned from the letrec
in an association list. We've saved this list in the binding of
foo-module, so that we can look those procedures up and call
them.
We can clean this up a little by providing an accessor function that
will extract a single procedure from a module, by using assq to
find the appropriate closure:
(define (module-get mod name) (cadr (assq mod name)))
To import a procedure and give it a name in another environment, we can do this:
(define foo (module-get foo-module 'foo))
If we want to, we can give it a different name in the environment we're "importing" it into.
(define quux (module-get foo-module 'foo))
This lets us rename a procedure imported from a module, to avoid naming
conflicts. quux is exactly the same procedure as foo,
but by a different name in a different scope. When we call it, it
will execute in the environment where it was defined, namely the
"private" environment of the module we created with letrec.
let*
For situations where the order of initialization is important, Scheme
provides a variant of let called let*.
Suppose we tried the following using let:
(define (foo epsilon)
(let ((a 0)
(upper (+ a epsilon))
(lower (- a epsilon)))
...))
This will not do what we probably meant, because the initial values
of upper and lower will be computed before a is
bound. We could fix this by using nested let's, to force
evaluation and binding to happen in the desired order:
(define (foo epsilon)
(let ((a 0))
(let ((lower (- a epsilon))
(upper (+ a epsilon)))
...))
This ensures that a is bound before we evaluate the initial
value expressions for upper and lower.
Scheme provides let* to avoid needing lots of nested lets
when initilizing a series of bindings, each of which may depend ont
the previous ones, e.g.,
(define (bar x y)
(let* ((diff (- x y))
(diff-squared (* diff diff))
(diff-cubed (* diff-squared diff)))
...)
is exactly equivalent to
(define (bar x y)
(let ((diff (- x y)))
(let ((diff-squared (* diff diff)))
(let ((diff-cubed (* diff-squared diff)))
...))))
let
Named let is a general and flexible iteration construct that is
really just syntactic sugar for a letrec and one or more
lambda's. It looks like a let, but it's usually used
as a loop.
Named let implements iteration as recursion. If you use it
in normal ways, you write loops that act as tail-recursive procedures.
You can also use it to write "loops" that aren't tail recursive,
but that's uncommon.
Named let binds loop variables, and executes the loop body.
Anywhere in the loop body, you can call a procedure to iterate the
loop.
Here's an example loop, which prints out the integers from 0 to 9:
(let loop ((i 0))
(display i)
(if (< i 10)
(loop (+ i 1))))
Here we've written a loop and given it an identifier, loop; that's
just a name we chose for this particular loop--we could have used any
identifier.
This loop binds the loop variable i, giving it the intial
value 0. Then it enters the body of the loop, which prints out
i using display, and evaluates the if expression.
If the if condition returns a true value, it evaluates the
expression (loop (+ i 1)), which iterates the loop. This
looks like a call to a procedure named loop, which iterates
the loop. The argument passed is the new value of the loop variable
for the next iteration.
The reason that the expression that iterates a loop looks like a
procedure call is that it is a procedure call. A named let
is exactly equivalent to a letrec that defines a named procedure,
whose body is the body of the named let, and then calls that
procedure to start the recursion. When you write a "loop"
with named let, you're really writing a recursive procedure
and a call to that procedure. The loop variable(s) are really arguments
to the procedure, and the initial values of the loop variables are
just the first argument passed to the procedure to start the recursion.
The above example is exactly equivalent to:
(letrec ((loop (lambda (i) ; define a recursive
(display i) ; procedure whose body
(if (< i 10) ; is the loop body
(loop (+ i 1))))))
(loop 0)) ;; start the recursion with 0 as arg i
When you supply the name of a named let, you're really supplying the
name of a letrec variable that will name a procedure. When you supply
the body of the named let, you're really supplying the body of
the named procedure. When it iterates the loop, it is calling itself
recursively, passing the new invocation the new value of the loop
variable as an argument.
To start off the loop, named let passes this procedure the initial
value expression for the loop variable.
We can provide any expression we want to compute the new value of the loop variable--we don't have to increment it by one. We can also provide any test we want to decide whether to iterate the loop.
For example, here's procedure which uses a loop to search a
list of alternating key/value pairs. (This is not an association list,
but a linear list of alternating keys and values, called a property
list.) It iterates through the list two elements at a time. If it finds
an odd-numbered element that's eq? to what it's looking for, it
returns the next (even-numbered) element; otherwise, it continues through
the loop.
(define (property-list-search lis target)
(let loop ((l lis))
(cond ((null? l)
#f)
((eq? (car l) target)
(cadr l))
(#t
(loop (cddr l))))))
[ same as: ]
(define (property-list-search lis target)
(letrec ((loop (lambda (l)
(cond ((null? l)
#f
((eq? (car l) target)
(cadr l))
(#t
(loop (cddr l))))))))
(loop lis))) ;; start the recursion
The reason we supply a name for a loop in a named let is so that we
can have nested loops with different names, and we can iterate any
of the loops by calling it by name.
For example, suppose we want to have a nested pair of loops, but want to be able to bail out of the iteration of the inner loop, and go directly to the next iteration of the outer loop. We can do this:
[ need example here ]
(let outer-loop ((i ...))
(let inner-loop ((j ...))
(if (should-abort-inner-loop)
(outer-loop ...)) ;; go directly to next iteration of outer loop
... ; do normal inner loop action
...(inner-loop ...) ;; iterate inner loop normally
...
... (outer-loop ...)) ; iterate outer loop normally
Some things to notice about Scheme loops: