Go to the first, previous, next, last section, table of contents.

Recursion in Scheme

In this chapter, I'll discuss procedure calling and recursion in more depth. [ blah blah blah ] Scheme's procedure-calling mechanism supports efficient tail-recursive programming, where recursion is used instead of iteration. In conventional programming languages, you can't generally use recursion to get the effect of iteration, because you may get activation stack overflows if the recursion is too deep.

After clarifying how recursion works, I'll give examples of how to program recursively in Scheme.

(In a later chapter, I'll show how the mechanisms that support tail recursion also support a powerful control feature called call-with-current-continuation that lets you implement novel control structures like backtracking and coroutines.)

Subproblems and Reductions (non-tail and tail calls)

In most implementations of most programming languages, an activation stack is used to implement procedure calling. At a call, the state of the "caller" (calling procedure) is saved on the stack, and then control is transferred to the callee.

Because each procedure call requires saving state on the stack, recursion is limited by the stack depth. In many systems, deep recursions cause stack overflow and program crashes, or use up unnecessary virtual memory swap space. In most systems, recursion is unnecessarily expensive in space and/or time. This limits the usefulness of recursion.

In Scheme, things are somewhat different. As I noted earlier, recursive calls may be tail recursive, in which case the state of the caller needn't be saved before calling the callee.

More generally, whether a procedure is recursive or not, the calls it makes can be classified as subproblems or reductions If the last thing a procedure does is to call another procedure, that's known as a reduction--the work being done by the caller is complete, because it "reduces to" the work being done by the callee.

For example, consider the following procedures:

(define (foo)
   (bar)
   (baz))
(define (baz)
   (bar)
   (foo))

Notice that when foo is called, it does two things: it calls bar and then calls baz. After the call to bar, control must return to foo, so that it can continue and call baz. The call to bar is therefore a subproblem--a step in the overall plan of executing foo. When foo calls baz, however, that's all it needs to do--all of its other work is done. The result of the call to foo is just the result of foo's call to baz.

In a conventional programming language implementation, foo's state would be saved before the call to baz, as well as before the call to bar. Each call would return control to foo. In the case of the call to baz, all foo will do is return the result of the call to its caller. That is, all foo does after the return from baz is to leave the result wherever its caller expects it, and return again to pop a stack frame off the activation stack.

In Scheme, things are actually simpler. If the last thing a procedure does is to call another procedure, the caller doesn't save its own state on the stack. When the callee returns, it will return to its caller's caller directly, rather than to its caller. After all, there's no reason to return to the caller if all the caller is going to do is pass the return value along to its caller.

This optimizes away the unnecessary state saving and returning at tail calls. You don't have to do anything special to get this optimization--Scheme implementations always do it for tail calls.

Consider both foo and baz above. Neither ever returns--each just calls the other. In Scheme, these two procedures will repeatedly call each other, without saving their state on the stack, producing an infinite mutual recursion. Will the stack overflow? No. Each will save its state before calling bar, but the return from bar will pop that information off of the stack. The infinite tail-calling between foo and baz will not increase the stack height at all.

Above I said that a callee may return to its caller's caller, but that doesn't really capture the extent of what's going on. In general a procedure may return to its caller (if it was non-tail called), or it's caller's caller (if it was tail-called but its caller wasn't) or it's caller's caller's caller (if it and it's caller were both tail-called), and so on. A procedure returns to the last caller that did a non-tail call.

Because of this "tail call optimization," you can use recursion very freely in Scheme, which is a good thing--many problems have a natural recursive structure, and recursion is the easiest way to solve them.

Notice that this tail call optimization is a feature of the language, not just some implementations. Any implementation of standard Scheme is required to support it, so that you can count on it and write portable programs that rely on it. (In fact, the definition of the Scheme language itself depends on this, because the special forms for iteration are defined in terms of equivalent tail-calling--a loop is really a kind of procedure, that procedure tail-calls itself ot iterate the loop.)

Also notice that the interpreter we presented earlier is tail-recursive. The recursive calls to eval are tail calls, and since it's implemented in Scheme, the interpreter relies on the underlying Scheme's tail-call optimization. The evaluator thus snarfs the tail-call optimization from the underlying Scheme system. If you implement a Scheme interpreter in another language, you have to be more careful, and implement the tail call optimization yourself.

It's something of a misnomer to call Scheme's procedure calling mechanism an "optimization." What's really going on is that Scheme simply distinguishes between two things that most languages lump together--saving the caller's state, and actually transferring control to the callee. Scheme notices that these things are distinct, and doesn't bother to do the former when only the latter is necessary.

A procedure call is really rather like a (safe) goto that can pass arguments: control is transferred directly to the callee, and the caller has the option of saving its state beforehand. (This is safer than unrestricted goto's, because when a procedure does return, it returns to the right ancestor in the dynamic calling pattern, just as though it had done a whole bunch of returns to get there.)

The Continuation Chain

In this section, I'll describe a straightforward implementation of Scheme's state-saving for procedure calling. It may clarify things that are discussed later, however, such as call-with-current-continuation and our example compiler's code generation strategy.

In most conventional language implementations, as noted above, calling a procedure allocates an activation record (or "stack frame") that holds the return address for the call and the variable bindings for the procedure being called. The stack is a contiguous area of memory, and pushing an activation record onto the stack is done by incrementing a pointer into this contiguous area by the size of the stack frame. Removing a stack frame is done by decrementing the pointer by the size of the stack frame.

Scheme implementations are quite different. As we've explained previously, variable bindings are not allocated in a stack, but instead in environment frames on the garbage-collected heap. This is necessary so that closures can have indefinite extent, and can count on the environments they use living as long as is necessary. The garbage collector will eventually reclaim the space for variable bindings in frames that aren't captured by closures.

(Actually, I'm oversimplifying a bit here. Some implementations of Scheme do use a relatively conventional stack, often so that they can compile Scheme straightforwardly to C. They must provide tail-call optimization somehow, though. I won't go into alternative implementation strategies here.)

Most Scheme implementations also differ from conventional language implementations in how they represent the saved state of callers. (In a conventional language implementation, the callers' state is in two places: the variable bindings are in the callers' own stack frames, and the return address is stored in the callee's stack frame.)

In most Scheme implementations, the caller's state is saved in a record on the garbage-collected heap, called a partial continuation. It's called a continuation because it says how to resume the caller when we return into it--i.e., how to continue the computation when control returns. It's called a partial continuation because that record, by itself, it only tells us how to resume the caller, not the caller's caller or the caller's caller's caller. On the other hand, each partial continuation holds a pointer to the partial continuation for its caller, so a chain of continuations represents how to continue the whole computation: how to resume the caller, and when it returns, how to resume its caller, and so on until the computation is complete. This chain is therefore called a full continuation.

(Notice that the relationship between the partial continuations in a full continuation chain is similar to the relationship between an environment frame and an environment chain. The former represents control information while the latter represents scope information.)

In most Scheme implementations, a special register called the continuation register is used to hold the pointer to the partial continuation for the caller of the currently-executing procedure. When we call a procedure, we can package up the state of the caller as a record on the heap (a partial continuation), and push that partial continuation onto the chain of continuations hanging off the continuation register.

                        part. cont.  (saved state of caller's
                            /|\       caller's caller)
                             |
                             |
                        part. cont.  (saved state of caller's caller)
                            /|\
                             |
        +-------+            |
   CONT |   +---+-----> part. cont.  (saved state of caller)
        +-------+

(It is often convenient to draw stacks and continuations as growing downward, which is our convention here--the newer elements are on the bottom.) Note that the continuation register may be a register in the CPU, or it may just be a particular memory location that our implementation uses for this purpose. The point is just that when we're executing a procedure, we always know where to find a pointer to the partial continuation that lets us resume its caller (or whichever procedure last did a non-tail call). We will sometimes abbreviate this register's name as CONT. A typical implementation of Scheme using a compiler has several important registers that encode the state of the currently-executing procedure:

Before we call a procedure, we must save a continuation if we want to resume the current procedure after the callee returns.

Since the important state of the currently-executing procedure is in the registers listed above, we will create a record that has fields to hold them, and push that on the continuation chain. We will save the value of the CONT, ENVT, and PC registers in the partial continuation, then put a pointer to this new partial continuation in the continuation registers. We also need to save any other state that the caller will need when it resumes, as suggested by the ellipsis below. (We'll discuss what else goes in a partial continuation when we talk about compilers in detail.)

                                      old cont.
                                        /|\
                                         |
                         +-------+       |
        +-------+        |p.cont.|       |
   CONT |   +---+------->+=======+       |
        +-------+   cont |   +---+-------+
                         +-------+
                    envt |   +---+-------->old envt
                         +-------+
                      pc |   +---+-------->return address
                         +-------+
                                 |
                         +  ...
                         |       |
                         +-------+

Notice that since we saved the old value of the continuation register in the partial continuation, that serves as the "next" pointer in the linked list that makes up the full continuation. This is exactly as it should be. The value of the continuation register is part of the caller's state, and saving it naturally constructs a linked list, because each procedure's state is fundamentally linked to the state of its caller. Saving the return address is a little bit special--rather than just copying the program counter and saving it, we must save the address we want to resume at when we resume this procedure.

Once a procedure has pushed a continuation, it has saved its state and can call another procedure. The other procedure can use the ENVT, CONT, and PC registers without destroying the values of those registers needed by the caller. This is called a caller saves register usage convention; the assumption is that the callee is allowed to freely clobber the values in the registers, so it's the caller's responsibility to save any values it will need when it resumes.

To do a procedure return, it is only necessary to copy the register values out of the continuation that's pointed to by the CONT register. This will restore the caller's environment and its pointer to its caller's continuation, and setting the PC register will branch to the code in the caller where execution should resume. We often call this "popping" a continuation, because it's a stacklike operation--saving a (partial) continuation pushes the values in registers onto the front of the "stack," and restoring one pops the values back into the registers. (As we will explain later, however, Scheme continuation chains don't always observe this simple stack discipline, which is why they can't be implemented efficiently as contiguous arrays.)

If we save state and do a procedure call, and before returning our caller saves its state and does a procedure call, the chain of continuations gets longer. For the most part, this is like pushing activation information on a stack.

                                       /|\
                                        |
                      +---------+       |
                      | p.cont. |       |
                      +=========+       |
                 cont |    +----+-------+
                      +---------+
                 envt |    +----+-------->old envt
                      +---------+
                   pc |    +----+-------->return address
                      +---------+
                                |
                      +   ...
                      |         |
                      +---------+
                                 _
                                |\
                                  \
                                   \
                                    \   
                                     \
                                      .
                      +---------+     |
     +-------+        | p.cont. |     |
cont |   +---+------->+=========+    /
     +-------+   cont |    +----+---'
                      +---------+
                 envt |    +----+-------->old envt
                      +---------+
                   pc |    +----+-------->return address
                      +---------+
                                |
                      +   ...
                      |         |
                      +---------+

Notice that when we say we save the "state" of the caller, we mean the values in our important registers, but we don't directly save particular variable values--when we save the environment pointer, we don't make copies of the values in the bindings in the environment. In effect, saving the environment pointer records which names refer to which pieces of storage. If other code then executes in that same environment and changes those values, the new values will be seen by this procedure when it returns and restores the environment pointer. This policy has two important consequences:

  1. we can save an environment pointer into a continuation very quickly, and restore it quickly, because we're just saving and restoring one pointer, and
  2. it ensures that environments have the right semantics: closures that live in the same environment should see each others' changes to variables. This is one of the ways that procedures are supposed to be able to communicate--by operating on variables that they can see.

Executing a return ("popping a continuation") does not modify the partial continuation being popped--it just involves getting values out of the continuation and putting them into registers. Continuations are thus created and used nondestructively, and the continuations on the heap form a graph that reflects the pattern of non-tail procedure calls. Usually, that graph is just a tree, because of the tree-like pattern of call graphs, and the current "stack" of partial continuations is just the rightmost path through that graph, i.e., the path from the newest record all the way back to the root.

Consider the following procedures, where a calls b twice, and each time b is called, it calls c twice:

(define (a)
   (b)
   (b)
   #t)
(define (b)
   (c)
   (c)
   #t)
(define (c)
   #f)

All of these calls are non-tail calls, because none of the procedures ever ends in a (tail) call.

Suppose we call a after pushing a continuation for a's caller, then a calls b the first time. a will push a continuation to save its state, then call b. While executing b, b's state will be in the registers, including a pointer to the continuation for a in the CONT register.

               cont. for a's caller
                    /
                  /
          cont. for a
              /|\
      +---+    |
 CONT | +-+----+
      +---+ 

b will then push a continuation and call c.

               cont. for a's caller
                    /
                  /
          cont. for a
              /
            /
    cont. for b
       /|\
        |
      +-|-+ 
 CONT | + |
      +---+ 

When c returns, it will restore b's state by popping the partial continuation's values into registers. At this point, the CONT register will point past the continuation for b to the continuation for a.

               cont for a's caller
                    /
                  /
           cont. for a
              /  /|\
            /     |
    cont. for b   |
                  |
      +---+       |
 CONT | +-+-------+
      +---+

Then b will push another continuation and call c again.

               cont for a's caller
                    /
                  /
          cont. for a
              /  \
            /     \
    cont. for b  cont for b
                    /|\
                     |
      +---+          |
 CONT | +-+----------+
      +---+

Again, c will return, restoring b's state, and the CONT register will point past the continuation for b to the continuation for a.

               cont for a's caller
                    /
                  /
          cont. for a <-------+
              /  \            |
            /     \           |
    cont. for b  cont for b   |
                              |
      +---+                   |
 CONT | +-+-------------------+
      +---+      

After returning to a, the CONT register will point past the continuation for a to the continuation for a's caller. Then before a calls b again, it will push another continuation to save its state.

               cont for a's caller
                    /        \
                  /            \
          cont. for a        cont for a
              /  \              /|\
            /     \              |
    cont. for b  cont for b      |
                                 |
      +---+                      |
 CONT | +-+----------------------+
      +---+      

Then a will return and the CONT register will point past the continuation for a to the continuation for a's caller.

                cont for a's caller <--+
                    /                  |
                  /                    |
          cont. for a                  |
              /  \                     |
            /     \                    |
    cont. for b  cont for a            |
                                       |
      +---+                            |
 CONT | +-+----------------------------+
      +---+    

This continues in the obvious way, so that at the time of the fourth and last call to C, the continuations on the heap look like this:

                cont for a's caller
                    /           \    
                  /               \  
          cont. for a          cont. for a
              /  \                 /  \      
            /     \              /      \ 
    cont for b  cont for b  cont for b  cont for b
                                          /|\
                                           |
      +---+                                |
 CONT | +-+--------------------------------+
      +---+    

Most of the time, the rest of this graph becomes garbage quickly--each continuation holds pointers back up the tree, but nothing holds pointers down the tree. Partial continuations therefore usually become garbage the first time they're returned through.

The fact that this graph is created on the heap will allow us to implement call-with-current-continuation, a.k.a. call/cc, a very powerful control construct. call/cc can capture the control state of a program at a particular point in its execution by pushing a partial continuation and saving a pointer to it. Later, it can magically return control to that point by restoring that continuation, instead of the one in the continuation register. (We will discuss call/cc in detail in Chapter XX.)

Exploiting Tail Recursion

In an earlier section, we presented example recursive implementations of several Scheme functions; some of them were tail recursive, and some not.

At first glance, many routines seem as though they can't conveniently be coded tail recursively. On closer inspection, many of them can in fact be coded this way.

Passing Intermediate Values as Arguments

Summing a List

Suppose we want to sum a list of numbers. The most obvious way of doing it is the way we did it earlier, like this:

(define (list-sum lis)
   (if (null? lis)
       0
       (+ (car lis)
          (list-sum (cdr lis)))))

The problem with this code is that it's not particularly efficient, because it's not tail recursive. After each recursive call to list-sum, we must return to do the addition that adds one element to the sum of the rest of the list. We're adding the elements of the list back-to-front, on the way back up from nested recursion. (This means that Scheme must push a partial continuation before every recursive call, and each one must be popped when we're finished, to return the sum back from each call to its caller.)

The problem here is that evaluation of the arguments to a combination isn't a tail call, even if the combination as a whole is. Control must always return so that the actual call can be done.

We can write a tail-recursive version of list-sum that adds things in front-to-back order instead. The trick is to do the addition before the tail call, and to pass the sum so far to the recursive call, i.e., to pass it forward as an argument until a non-tail call returns it.

To do this, we have to keep a running sum, and each recursive call must pass it as an argument to the next. To start it off, we have to have a "running sum" of 0.

We can do this by defining two procedures. The one that does the real work takes a list and a running sum, adds one element to the running sum, and tail-calls itself to add the rest of the elements to the running sum. When it reaches the end of the list, it just returns the value. (Scheme doesn't need to save a partial continuation before each call, since only the last call ever returns.) We'll call this procedure loop, because we're using tail recursion to implement looping. For convenience, we also wrap this procedure up in a friendlier procedure that will start off the recursion, by supplying an initial "running sum" of 0.

;; a tail-recursive list summing procedure
(define (loop lis sum-so-far)
   (cond ((null? lis)
          sum-so-far)
         (else
          (loop (cdr lis)
                (+ sum-so-far (car lis))))))

;; a friendly wrapper that supplies an initial running sum of 0
(define (list-sum lis)
   (loop lis 0))

We can make this cleaner by encapsulating loop, since it's only used by list-sum. We make loop a local procedure using letrec and lambda.

(define (list-sum lis)
   ;; define a local, tail-recursive list summing procedure 
   (letrec ((loop (lambda (lis sum-so-far)
                     (cond ((null? lis)
                            sum-so-far)
                           (else
                            (loop (cdr lis)
                                  (+ sum-so-far (car lis))))))))
      (loop lis 0))) ;; start off recursive summing with a sum of 0

We can write this more clearly using named let. Named let is one of Scheme's two special forms for looping (the other is do). A named let looks like a let, but it's really a shorthand for the kind of thing we did above--defining a local procedure that can tail-call itself to give the effect of iteration, and starting it off with the appropriate initial value.

(define (list-sum lis)
   (let loop ((lis lis)
              (sum-so-far 0))
      (cond ((null? lis)
             sum-so-far)
            (else
             (loop (cdr lis)
                   (+ sum-so-far (car lis)))))))

Notice that here we're using two loop variables, lis and sum-so-far, rebound at each iteration. One keeps track of the remaining part of the original list, and the other the sum of the list items we've seen so far.

Be sure you understand that this version using named let is exactly equivalent to the version using letrec and lambda. The named let binds the variable loop, and initializes it with a first-class procedure that takes two arguments, list and sum-so-far. When we used the name loop for the named let, we're really giving the name of the procedure that implements the loop body. Each time we iterate the loop, we're really calling this procedure--the call to loop looks like a procedure call because it is a procedure call.

The argument expressions provide the new values for the next iteration of the loop, and the loop variables are rebound and initialized to those values at the next iteration of the loop. As in the version with an explicit letrec and lambda, the loop is started off by evaluating the initial value expressions for the loop variables (which look like let variables) and calling the loop procedure.

Since we re-bind the loop variables at each iteration of the loop, it generally doesn't make sense to side-effect loop variables. The old binding goes out of scope, and new bindings are created at each iteration, initialized with whatever values are passed to the looping procedure.

Implementing length tail-recursively

Recall that in [ Chapter whatever ] we implemented length this way:

(define (length lis)
   (if (null? lis)
       0
       (+ 1 (length (cdr lis)))))

This definition looks a lot like the definition of list-sum, and has the same basic problem. By using straightforward recursion (adding one to the length of the rest of the list), we're ensuring the addition happens back-to-front. We can compute the list length front to back by passing the running sum forward through tail recursions, as an argument. Each tail call will add to the running sum, and pass it forward. When the last tail call returns to its caller, it just returns the sum.

To do this, it's convenient to write the length procedure as a wrapper around a two-argument procedure that passes the running sum (as well as the remainder of list) to recursive calls to itself.

(define (length lis)
   (letrec ((len (lambda (lis length-so-far)
                    (if (null? lis)
                        length-so-far
                        (len (cdr lis)
                             (+ 1 length-so-far)))))))
     (len lis 0))

Or equivalently, using named let:

(define (length lis)
   (let loop ((lis lis)
              (length-so-far 0))
      (if (null? lis)
          len-so-far
          (loop (cdr lis)
                (+ (car lis) length-so-far)))))

reduce

In this section, I'll give an extended example of the use of higher-order functions to express patterns common to many functions, and customizing general procedures with procedural arguments and closure creation.

Consider the following function to sum the elements of a list

(define (list-sum lis)
   (if (null? lis)
       0
       (+ (car lis)
          (list-sum (cdr lis)))))

Given this definition,

(list-sum '(10 15 20 25))

is equivalent to

(+ 10 (+ 15 (+ 20 (+ 25 0)))).

[ the following couple of examples are now redundant with earlier material... trim and refer back. ]

Now consider a very similar function to multiply the elements of a list, where we've adopted the convention that the product of a null list is 1. (1 is probably the right value to use, because if you multiply something by 1 you get back the same thing--just as if you add something to 0 you get back the same thing.)

(define (list-prod lis)
   (if (null? lis)
       1
       (+ (car lis)
          (list-prod (cdr lis)))))

Given this definition,

(list-prod '(2 3 4 5))

is equivalent to

(* 2 (* 3 (* 4 (* 5 1))))

Given these definitions, you can probably imagine a very similar function to subtract the elements of a list, or to divide the elements of a list. For subtraction, the base value for an empty list should probably be zero, because subtracting zero doesn't change anything. For division it should probably be one.

At any rate, what we want is a single function that captures the pattern

(op thing1(op thing2 ...(op thingn base-thing)...))

We can write a higher-order procedure reduce that implements this pattern in a general way, taking three arguments: any procedure you want successively applied to the elements of a list, an appropriate base value to use on reaching the end of the list, and the list to do it to.

(define (reduce fn base-value lis)
   (if (null? lis)
       base-value
       (fn (car lis)
           (reduce fn base-value (cdr lis)))))

This is a very general procedure, that can be used for lots of things besides numerical operations on lists of numbers: it can be used for any computation over successive items in a list.

[ need to check the following couple of examples--they're off the top of my head ]

What does (reduce cons '() '(a b c d)) do? It's equivalent to (cons 'a (cons 'b (cons 'c (cons 'd '()))). That is, (reduce cons '() list) copies a list. We could define list-copy that way:

(define (list-copy lis)
   (reduce cons '() lis))

We could also define append that way, because reduce allows you to specify what goes at the end of a list--we don't have to end our list with '(). Here's a two-argument version of append:

(define (append list1 list2)
   (reduce cons list2 list1))

The reduction of a list using (lambda (x rest) (cons (* x 2) rest)) constructs a new list whose elements are twice the values of the corresponding elements in the original list.

Scheme>(reduce (lambda (x rest)
                  (cons (* x 2) rest))
               '()
               '(1 2 3 4))
(2 4 6 8)

[ show tail-recursive version... that'd make a good exercise ]

The reduce procedure above is handy, because you can use it for many different kinds of computations over different kinds of lists values, as long as you can process the elements (and construct the result) front-to-back. It's a little awkward, though, in that each time you use it, you have to remember the appropriate base value for the operation you're applying to a list. Sometimes it would be preferable to come up with a single specialized procedure like list-sum, which implicitly remembers which function it should apply to the list elements (e.g., +) and what base value to return for an empty list (e.g., 0). We can write a procedure make-reducer that will automatically construct a reducer procedure, given a function and a base value. Here's an example usage:

Scheme> (define list-sum (make-reducer + 0))
list-sum
  
Scheme> (define list-product (make-reducer * 1))
list-copy
   
Scheme> (list-sum '(1 2 3 4))
10
   
Scheme> (list-product '(1 2 3 4))
24

Make sure you understand the expressions above. The define forms are not using procedure definition syntax--they're using plain variable definition syntax, but the initial value expressions return procedures constructed by make-reducer. If we hadn't wanted to define procedures named list-sum and list-product, and hang on to them, we could have just taken the procedures returned by make-reducer and called them immediately:

Scheme> ((make-reducer + 0) '(1 2 3 4))
10
 
Scheme> ((make-reducer * 1) '(1 2 3 4))
24

This is very much like calling our original reduce procedure, except that each time we're constructing a specialized procedure (closure) that's like reduce customized for particular values of its first two arguments; then we call that new, specialized procedure to do the work on a particular list.

Here's a simple definition of make-reducer in terms of reduce:

(define (make-reducer fn base-value)
   (lambda (lis)
      (reduce fn base-value lis)))

Notice that we are using procedure definition syntax here, so the lambda in the body will create and return a closure.

[ can also do this with curry. ] But suppose we don't already have a reduce procedure, and we don't want to leave one lying around. A cleaner solution is to define the general reduce procedure as a local procedure, and create closures of it in different environments to customize it for different functions and base values.

(define (make-reducer fn base-value)
   (letrec ((reduce (lambda (lis)
                       (if (null? lis)
                           base-value
                           (fn (car lis)
                               (reduce (cdr lis)))))))
       reduce)) ;; return new closure of local procedure

This procedure uses closure creation to create a customized version of reduce When make-reducer is entered, its arguments are bound and initialized to the argument values--i.e., the function and base value we want the custom reducer to use. In this environment, we create a closure of the reducer procedure using lambda. We wrap the lambda in a letrec so that the reducer can refer to (and call) itself. Notice that since reduce is a local procedure, it can see the arguments to make-reducer, and we don't have to pass it those arguments explicitly. By using local procedure definition syntax--which not all Schemes support--we can write this as:

(define (make-reducer fn base-value)
   (define (reduce lis)
      (if (null? lis)
          base-value
          (fn (car lis)
              (reduce (cdr lis)))))
   reduce))  ;; return new closure of local procedure

Make sure that you understand that these are equivalent--the local procedure define is equivalent to a letrec and a lambda, and in either case the closure created (by the lambda or the define) will capture the environment where the arguments to make-reducer are bound.

Iteration as Recursion

named let

[ move earlier discussion here? ]

do


Go to the first, previous, next, last section, table of contents.