It is possible for a let-expression to bind a variable to a
procedure:
> (let ((square (lambda (n) (* n n))))
(square 12))
144
Like any other binding that is introduced in a let-expression,
this binding is local. Within the body of the let-expression,
it supersedes any previous binding of the same variable, but as soon as the
value of the let-expression has been computed, the local
binding evaporates.
However, it is not possible to bind a variable to a recursively defined procedure in this way:
> (let ((countdown (lambda (n)
(if (zero? n)
'()
(cons n (countdown (- n 1)))))))
(countdown 10))
Error: variable countdown is not bound.
The difficulty is that when the lambda-expression is
evaluated, the variable countdown has not yet been bound, so
the value of the lambda-expression is a procedure that
includes an unbound variable. Binding this procedure value to the variable
countdown creates a new environment, but does not affect the
behavior of procedures that were constructed in the old environment. So,
when the body of the let-expression invokes this procedure, we
get the unbound-variable error.
Changing let to let* wouldn't help in this case,
since even under let* the lambda-expression would
be completely evaluated before the binding is established. What we need is
some variant of let that binds the variable to some kind of a
placeholder and adds the binding to the environment first, then
computes the value of the lambda-expression in the new
environment, and then finally substitutes that value for the placeholder.
This will work in Scheme, so long as the procedure is not actually invoked
until we get into the body of the expression. The keyword associated with
this ``recursive binding'' variant of let is
letrec:
> (letrec ((countdown (lambda (n)
(if (zero? n)
'()
(cons n (countdown (- n 1)))))))
(countdown 10))
(10 9 8 7 6 5 4 3 2 1)
Write a letrec-expression in which (a) the identifier
last-of-list is locally bound to a procedure that finds and
returns the last element of a given list, and (b) the body of the
expression computes the sum of the last elements of the lists (3 8
2), (7), and (8 5 9 8), invoking
last-of-list three times.
A letrec-expression constructs all of its placeholder bindings
simultaneously (in effect), then evaluates all of the
lambda-expressions simultaneously, and finally replaces all of
the placeholders simultaneously. This makes it possible to include binding
specifications for mutually recursive procedures in the same binding list:
> (letrec ((up-sum
(lambda (ls)
(if (null? ls)
0
(+ (down-sum (cdr ls)) (car ls)))))
(down-sum
(lambda (ls)
(if (null? ls)
0
(- (up-sum (cdr ls)) (car ls))))))
(up-sum '(1 23 6 12 7)))
-21
A non-empty list is an s-n-alternator if its elements are alternately symbols and numbers, beginning with a symbol. It is an n-s-alternator if its elements are alternately numbers and symbols, beginning with a number.
Write a letrec-expression in which (a) the identifiers
s-n-alternator? and n-s-alternator? are bound to
mutually recursive predicates, each of which determines whether a given
non-empty list has the indicated characteristic, and (b) the body invokes
each of these predicates to determine whether the list (2 a 3 b 4 c
5) fits either description.
The textbook consistently uses letrec-expressions to separate
the husk and the kernel of a recursive procedure without having to define
two procedures. Here's an example repeated from the lab on side effects and sequencing:
;; The IOTA procedure takes any non-negative integer UPPER-BOUND as
;; argument and returns a list of the non-negative integers strictly less
;; than UPPER-BOUND, in ascending order.
(define iota
(lambda (upper-bound)
(iota-kernel 0 upper-bound)))
(define iota-kernel
(lambda (so-far upper-bound)
(if (= so-far upper-bound)
'()
(cons so-far (iota-kernel (+ so-far 1) upper-bound)))))
This works, but it's more stylish to construct the kernel procedure inside
a letrec expression, so that the extra identifier can be bound
to it locally:
(define iota
(lambda (upper-bound)
(letrec ((kernel (lambda (so-far)
(if (= so-far upper-bound)
'()
(cons so-far (kernel (+ so-far 1)))))))
(kernel 0))))
Notice, too, that since the recursive kernel procedure is now entirely
inside the body of the iota procedure, it is not necessary to
pass the value of upper-bound to the kernel as a second
parameter; instead, the kernel can treat upper-bound as if it
were a constant, since its value doesn't change during any of the recursive
calls.
The same approach can be used to perform precondition tests efficiently,
by placing them with the husk in the body of a
letrec-expression and omitting them from the kernel. For
instance, here's how to introduce precondition tests into the
dupl procedure from the lab on variations on recursion:
;; The DUPL procedure takes two arguments, a string STR and a non-negative
;; integer FACTOR, and returns a string consisting of FACTOR successive
;; copies of STR.
(define dupl
(lambda (str factor)
(letrec ((kernel (lambda (remaining)
(if (zero? remaining)
""
(string-append str (kernel (- remaining 1)))))))
(if (not (string? str))
(error 'dupl "the first argument must be a string"))
(if (or (not (integer? factor))
(negative? factor))
(error 'dupl
"the second argument must be a non-negative integer"))
(kernel factor))))
Embedding the kernel inside the definition of dupl rather than
writing a separate dupl-kernel procedure has another
advantage: It is impossible for an incautious user to invoke the
kernel procedure directly, bypassing the precondition tests.
The only way to get at the recursive procedure to which
kernel is bound is to invoke the procedure within which the
binding is established.
I've recycled the name kernel in this example to drive home
the point that local bindings in separate procedures don't interfere with
one another. Even if both procedures were active at the same time -- if,
for instance, one issued the call (dupl "sample" (caddr (iota
17))) -- the correct kernel procedure would be invoked
in each case, because the correct local binding would supersede all
others.
Write and test a procedure named take that takes a list
ls and a non-negative integer len as arguments
and returns a list consisting of the first len elements of
ls, in their original order. The procedure should signal an
error if ls is not a list, if len is not an
integer, if len is negative, or if len is greater
than the length of ls.
Write and test a procedure named intersection that takes two
lists of symbols, ls-1 and ls-2, as arguments and
returns a list of which the elements are precisely those symbols that are
elements of both ls-1 and ls-2.
This document is available on the World Wide Web as
http://www.math.grin.edu/courses/Scheme/spring-1998/local-binding-and-recursion.html
created March 2, 1997
last revised June 21, 1998