On this page:
36 The Loss of Knowledge
36.1 A Problem with Structural Processing
36.2 A Problem with Generative Recursion
37 Designing Accumulator-Style Functions
37.1 Recognizing the Need for an Accumulator
37.2 Adding Accumulators
37.3 Transforming Functions into Accumulator-Style
38 More Uses of Accumulation
38.1 Extended Exercise:   Compiling ISL+
38.2 Extended Exercise:   Game Trees
38.3 Extended Exercise:   Board Solitaire
39 Generative Recursion with Accumulators
39.1 Fractals, a Second Taste
39.2 Gaussian Elimination, Again
40 Summary
6.1.0.5

VI Accumulators

When you ask ISL+ to apply some function f to an argument a, you usually get some value v. If you evaluate (f a) again, you get v again.The function application may also loop forever or signal an error, but let’s ignore these possibilities for now. We also ignore random, which is the only real exception to this rule. As a matter of fact, you get the same result no matter how often you request the evaluation of (f a). Whether the function is applied for the first time or the hundredth time, whether the application is located in DrRacket’s interactions area or inside the function itself, doesn’t matter. The function works according to its purpose statement, and that’s all you need to know.

This principle of context-independence plays a critical role in the design of recursive functions. When it comes to coding, you are free to assume that the function computes what the purpose statement promises—even if the function isn’t defined yet. In particular, you are free to use the results of recursive calls to create the code of some function, usually one of its cond clauses. The template and coding steps of the design recipes for both structurally and generative recursive functions rely on this idea.

Although context-independence facilitates the design of functions, it also causes two problems. The general idea is that context-independence induces a loss of knowledge during a recursive evaluation; a function does not “know” whether it is called on a complete list or on a piece of that list. For structurally recursive programs this loss of knowledge means that they may have to traverse data more than once, inducing a grave performance cost. For functions that employ generative recursion, the loss means that the function may not be able to compute the result; instead the function loops forever for certain inputs. The preceding part illustrates this second problem with a graph traversal function that cannot find a path between two nodes for a circular graph.

This part introduces a variant of the design recipes to address this “loss of context” problem. Since we wish to retain the principle that (f a) returns the same result no matter how often it is evaluated, our only solution is to add an argument that represents the context of the function call. We call this additional argument an accumulator. During the traversal of data, the recursive calls continue to receive new regular arguments while accumulators change in relation to the other arguments and the context of the call.

Designing functions with accumulators correctly is clearly more complex than any of the design approaches from the preceding chapters. The key is to understand the relationship between the proper arguments and the accumulators. The following chapters explain how to design functions with accumulators work and how they work.

36 The Loss of Knowledge

Both functions designed according to structural recipes and the generative one suffer from the loss of knowledge, though in different ways. This chapter explains with two examples—one from each category—how the lack of contextual knowledge affects the performance of functions. While the first section is about structural recursion, the second one addresses concerns in the generative realm.

36.1 A Problem with Structural Processing

Let’s start with a seemingly straightforward example:

Sample Problem: You are working for a geometer team that will measure the length of roads segments. The team asked you to design a program that translates these relative distances between a series of road points into absolute distances for some starting point.

For example, we might be given a line such as this:

image

Each number specifies the distance between two dots. What we need is the following picture, where each dot is annotated with the distance to the left-most end:

image

Designing a program that performs this calculation is at this point an exercise in structural function design. Figure 105 contains the complete program. When the given list is not empty, the natural recursion computes the absolute distance of the remainder of the dots to the first item on (rest alon). Because the first item is not the actual origin and has a distance of (first alon) to the origin, we must add (first alon) to each number on the result of the natural recursion. This second step—adding a number to each item on a list of numbers—requires an auxiliary function.

; [List-of Number] -> [List-of Number]
; convert a list of relative distances to a list of absolute distances
; the first item on the list represents the distance to the origin
 
(check-expect (relative->absolute '(50 40 70 30 30))
              '(50 90 160 190 220))
 
(define (relative->absolute l)
  (cond
    [(empty? l) empty]
    [else (local ((define rest-of-l (relative->absolute (rest l)))
                  (define adjusted  (add-to-each (first l) rest-of-l)))
            (cons (first l) adjusted))]))
 
; Number [List-of Number] -> [List-of Number]
; add n to each number on alon
 
(check-expect (cons 50 (add-to-each 50 '(40 110 140 170)))
              '(50 90 160 190 220))
 
(define (add-to-each n alon)
  (cond
    [(empty? alon) empty]
    [else (cons (+ (first alon) n) (add-to-each n (rest alon)))]))

Figure 105: Converting relative distances to absolute distances

While designing the program is relatively straightforward, using it on larger and larger lists reveals a problem. Consider the evaluation of the following expression:Use (build-list size add1) to construct these lists.

(relative->absolute (list 0 ... size))

As we increase size, the time needed grows even faster:

size

     

1000

     

2000

     

3000

     

4000

     

5000

     

6000

     

7000

time

     

25

     

109

     

234

     

429

     

689

     

978

     

1365

Instead of doubling as we go from 1000 to 2000 items, the time quadruples. This is also the approximate relationship for going from 2000 to 4000, and so on.The time of evaluation will differ from computer to computer and from year to year. These measurements were conducted in 2014 on a MacMini running OS X 10.8.5; the previous measurement took place in 1998, and the times were 100x larger.

Exercise 395. Reformulate add-to-each using map and lambda.

Exercise 396. Determine the abstract running time of relative->absolute.

Hint Evaluate the expression

(relative->absolute (list 0 ... size))

by hand. Start by replacing size with 1, 2, and 3. How many natural recursions of relative->absolute and add-to-each are required each time?

Considering the simplicity of the problem, the amount of “work” that the program performs is surprising. If we were to convert the same list by hand, we would tally up the total distance and just add it to the relative distances as we take another step along the line. Why can’t a program use this idea?

Let’s attempt to design a second version of the function that is closer to our manual method. The new function is still a list-processing function, so we start from the appropriate template:
(define (relative->absolute/a alon)
  (cond
    [(empty? alon) ...]
    [else ... (first alon) ... (relative->absolute/a (rest alon)) ...]))
Now imagine an “evaluation” of (relative->absolute/a (list 3 2 7)):
= (cons ... 3 ...
    (convert (list 2 7)))
 
= (cons ... 3 ...
    (cons ... 2 ...
      (convert (list 7))))
 
= (cons ... 3 ...
    (cons ... 2 ...
      (cons ... 7 ...
        (convert empty))))
The first item of the result list should obviously be 3, and it is easy to construct this list. But, the second one should be (+ 3 2), yet the second instance of relative->absolute/a has no way of “knowing” that the first item of the original list is 3. The “knowledge” is lost.

Put differently, the problem is that recursive functions are independent of their context. A function processes L in (cons N L) in the same manner as in (cons K L). Indeed, it would also process L in that manner if it were given L by itself.

To make up for the loss of “knowledge,” we equip the function with an additional parameter: accu-dist. The new parameter represents the accumulated distance, which is the tally that we keep when we convert a list of relative distances to a list of absolute distances. Its initial value must be 0. As the function processes the numbers on the list, it must add them to the tally.

Here is the revised definition:
(define (relative->absolute/a alon accu-dist)
  (cond
    [(empty? alon) empty]
    [else (local ((define tally (+ (first alon) accu-dist)))
             (cons tally (relative->absolute/a (rest alon) tally)))]))
The recursive application consumes the rest of the list and the new absolute distance of the current point to the origin. Although this means that two arguments are changing simultaneously, the change in the second one strictly depends on the first argument. The function is still a plain list-processing procedure.

Evaluating our running example (relative->absolute/a (list 3 2 7)) again, shows how much the use of an accumulator simplifies the conversion process:
= (relative->absolute/a (list 3 2 7) 0)
= (cons 3 (relative->absolute/a (list 2 7) 3))
= (cons 3 (cons 5 (relative->absolute/a (list 7) 5)))
= (cons 3 (cons 5 (cons 12 (relative->absolute/a empty 12))))
= (cons 3 (cons 5 (cons 12 empty)))
Each item in the list is processed once. When relative->absolute/a reaches the end of the argument list, the result is completely determined and no further work is needed. In general, the function performs on the order of N natural recursion steps for a list with N items.

One minor problem with the new definition is that unlike relative->absolute, the new function consumes two arguments not just one. Worse, someone might accidentally misuse relative->absolute/a by applying it to a list of numbers and a number that isn’t 0. We can solve both problems with a function definition that uses a local definition to encapsulate relative->absolute/a; figure 106 shows the result. Now, relative->absolute and relative->absolute2 are indistinguishable with respect to the input-output relationship.

; [List-of Number] -> [List-of Number]
; convert a list of relative distances to a list of absolute distances
; the first item on the list represents the distance to the origin
 
(check-expect (relative->absolute.v2 '(50 40 70 30 30))
              '(50 90 160 190 220))
 
(define (relative->absolute.v2 alon)
  (local (; [List-of Number] Number -> [List-of Number]
          (define (relative->absolute/a alon accu-dist)
            (cond
              [(empty? alon) empty]
              [else
               (local ((define accu (+ (first alon) accu-dist)))
                 (cons accu (relative->absolute/a (rest alon) accu)))])))
    (relative->absolute/a alon 0)))

Figure 106: Converting relative distances with an accumulator

Now let’s look at how this version of the program performs. To this end, we evaluate

(relative->absolute.v2 (list 0 ... size))

and tabulate the results for several values of size:

size

     

1000

     

2000

     

3000

     

4000

     

5000

     

6000

     

7000

time

     

0

     

0

     

0

     

0

     

0

     

1

     

1

Amazingly relative->absolute2 never takes more than one second to process such lists, even for a list of 7000 numbers. Comparing this performance to the one of relative->absolute, you may think that accumulators are a miracle cure for all slow-running programs. Unfortunately, this isn’t the case, but when a structurally recursive functions has to re-process the result of the natural recursion you should definitely consider the use of accumulators.

36.2 A Problem with Generative Recursion

Let us revisit the problem of “traveling” along a path in a graph:

Sample Problem: Design an algorithm that checks whether two nodes are connected in a simple graph. In a simple graph, each node has exactly one, one-directional connection to another node, possibly itself.

Algorithms that Backtrack covered the variant where the algorithm has to discover the path. This sample problem is simpler than that, because this section focuses on the design of an accumulator version of the algorithm.

Consider the sample graph in figure 107. There are six nodes: A through F, and six connections. To get from A to E, you must go through B and C. It is impossible, though, to reach F from A or from any other node besides F itself.

image

     

(define a-simple-graph
  '((A B)
    (B C)
    (C E)
    (D E)
    (E B)
    (F F)))

Figure 107: A simple graph

The right part of figure 107 shows how to represent this graph with nested lists. Each node is represented by a list of two symbols. The first symbol is the label of the node; the second one is the single node that is reachable from the first one. Here are the relevant data definitions:
; A SimpleGraph is a [List-of #, Connection]
; A Connection is (list Node Node)
; A Node is a Symbol
They are straightforward translations of our informal descriptions.

We already know that the problem calls for generative recursion, and it is easy to create the header material:
; Node Node SimpleGraph -> Boolean
; is there a path from origination to destination in sg
 
(check-expect (path-exists? 'A 'E a-simple-graph) true)
(check-expect (path-exists? 'A 'F a-simple-graph) false)
 
(define (path-exists? origination destination sg)
  false)
What we need are answers to the four basic questions of the recipe for generative recursion:
  • The problem is trivial if the nodes origination and destination are the same.

  • The trivial solution is true.

  • If origination is not the same as destination, there is only one thing we can do: step to the immediate neighbor and search for destination from there.

  • There is no need to do anything if we find the solution to the new problem. If origination’s neighbor is connected to destination, then so is origination. Otherwise there is no connection.

From here we just need to express these answers in ISL+ to obtain a full-fledged program.

; Node Node SimpleGraph -> Boolean
; is there a path from origination to destination in sg
 
(check-expect (path-exists? 'A 'E a-simple-graph) true)
(check-expect (path-exists? 'A 'F a-simple-graph) false)
 
(define (path-exists? origination destination sg)
  (cond
    [(symbol=? origination destination) #t]
    [else (path-exists? (neighbor origination sg) destination sg)]))
 
; Node SimpleGraph -> Node
; determine the node that is connected to a-node in sg
 
(check-expect (neighbor 'A a-simple-graph) 'B)
(check-error (neighbor 'G a-simple-graph) "neighbor: not a node")
 
(define (neighbor a-node sg)
  (cond
    [(empty? sg) (error "neighbor: not a node")]
    [else (if (symbol=? (first (first sg)) a-node)
              (second (first sg))
              (neighbor a-node (rest sg)))]))

Figure 108: Finding a path in a simple graph

Figure 108 contains the complete program, including the function for looking up the neighbor of a node in a simple graph—a straightforward exercise in structural recursion—and test cases for both. Don’t run the program, however. If you do, be ready with your mouse to stop the run-away program. Indeed, even a casual look at the function suggests that we have a problem. Although the function is supposed to produce false if there is no path from origination to destination, the program doesn’t contain false anywhere. Conversely, we need to ask what the function actually does when there is no path between two nodes.

Take another look at figure 107. In this simple graph there is no path from C to D. The connection that leaves C passes right by D and instead goes to E. So let’s look at how

(path-exists? 'C 'D '((A B) (B C) (C E) (D E) (E B) (F F)))

is evaluated:
= (path-exists? 'E 'D '((A B) (B C) (C E) (D E) (E B) (F F)))
= (path-exists? 'B 'D '((A B) (B C) (C E) (D E) (E B) (F F)))
= (path-exists? 'C 'D '((A B) (B C) (C E) (D E) (E B) (F F)))
The hand-evaluation confirms that as the function recurs, it calls itself with the exact same arguments again and again. In other words, the evaluation never stops.

Our problem with path-exists? is again a loss of “knowledge,” similar to that of relative->absolute in the preceding section. Like relative->absolute, the design of path-exists? uses a recipe and assumes context-independence for recursive calls. In the case of path-exists? this means, in particular, that the function doesn’t “know” whether a previous application in the current chain of recursions received the exact same arguments.

The solution to this design problem follows the pattern of the preceding section. We add a parameter, which we call seen and which represents the accumulated list of origination nodes that the function has encountered, starting with the original application. Its initial value must be '(). As the function checks on a specific origination and moves to its neighbors, origination is added to seen.

Here is a first revision of path-exists?, dubbed path-exists?/a:
; Node Node SimpleGraph [List-of Node] -> Boolean
; is there a path from origination to destination in sg
; assume the nodes in seen are known not to solve the problem
(define (path-exists?/a origination destination sg seen)
  (cond
    [(symbol=? origination destination) #t]
    [else (path-exists?/a (neighbor origination sg) destination sg
                          (cons origination seen))]))
The addition of the new parameter alone does not solve our problem, but, as the hand-evaluation of

(path-exists?/a 'C 'D '((A B) (B C) (C E) (D E) (E B) (F F)) '())

shows, provides the foundation for one:
= (path-exists?/a 'E 'D '((A B) (B C) (C E) (D E) (E B) (F F)) '(C))
= (path-exists?/a 'B 'D '((A B) (B C) (C E) (D E) (E B) (F F)) '(E C))
= (path-exists?/a 'C 'D '((A B) (B C) (C E) (D E) (E B) (F F)) '(B E C))
In contrast to the original function, the revised function no longer calls itself with the exact same arguments. While the three arguments proper are again the same for the third recursive application, the accumulator argument is different from that of the first application. Instead of '(), it is now '(B E C). The new value represents the fact that during the search of a path from 'C to 'D, the function has inspected 'B, 'E, and 'C as starting points.

All we need to do now, is to make the algorithm exploit the accumulated knowledge. Specifically, the algorithm can determine whether the given origination is already an item in seen. If so, the problem is also trivially solvable yielding false as the solution. Figure 109 contains the definition of path-exists.v2?, which is the revision of path-exists?. The definition refers to member?, an ISL+ function.

; Node Node SimpleGraph -> Boolean
; is there a path from origination to destination in sg
 
(check-expect (path-exists.v2? 'A 'E a-simple-graph) true)
(check-expect (path-exists.v2? 'A 'F a-simple-graph) false)
 
(define (path-exists.v2? origination destination sg)
  (local (; Node Node SimpleGraph [List-of Node] -> Boolean
          (define (path-exists?/a origination seen)
            (cond
              [(symbol=? origination destination) #t]
              [(member? origination seen) #f]
              [else (path-exists?/a (neighbor origination sg)
                                    (cons origination seen))])))
    (path-exists?/a origination '())))

Figure 109: Finding a path in a simple graph with an accumulator

The definition of path-exists.v2? also eliminates the two minor problems with the first revision. By localizing the definition of the accumulating function, we can ensure that the first call always uses '() as the initial value for seen. And, path-exists.v2? satisfies the exact same contract and purpose statement as the path-exists? function.

Still, there is a significant difference between path-exists.v2? and relative-to-absolute2. Whereas the latter was equivalent to the original function, path-exists.v2? improves on path-exists?. While the latter fails to find an answer for some inputs, path-exists.v2? finds a solution for any simple graph.

Exercise 397. Modify the definitions of find-path and find-path/list in figure 99 so that they produce false, even if they encounter the same starting point twice.

37 Designing Accumulator-Style Functions

The preceding chapter illustrates the need for accumulating extra knowledge with two examples. In one case, accumulation makes it easy to understand the function and yields one that is far faster than the original version. In the other case, accumulation is necessary for the function to work properly. In both cases though, the need for accumulation becomes only apparent once a properly designed function exists.

Generalizing from the preceding chapter suggests that the design of accumulator functions has two major aspects:
  1. the recognition that a function benefits from an accumulator;

  2. an understanding of what the accumulator represents with respect to the design.

The first two sections address these two questions. Because the second one is a difficult topic, the third section illustrates it with a series of examples that convert regular functions into accumulating ones.

37.1 Recognizing the Need for an Accumulator

Recognizing the need for accumulators is not an easy task. We have seen two reasons, and they are the most prevalent reasons for adding accumulator parameters. In either case, it is critical that we first built a complete function based on a design recipe. Then we study the function and look for one of the following characteristics:
  1. If a structurally recursive function processes the result of its natural recursion with an auxiliary, recursive function, consider the use of an accumulator parameter.

    Take a look at the definition of invert:
    ; [List-of X] -> [List-of X]
    ; construct the reverse of alox
     
    (check-expect (invert '(a b c)) '(c b a))
     
    (define (invert alox)
      (cond
        [(empty? alox) empty]
        [else (add-as-last (first alox) (invert (rest alox)))]))
     
    ; X [List-of X] -> [List-of X]
    ; add an-x to the end of alox
     
    (check-expect (add-as-last 'a '(c b)) '(c b a))
     
    (define (add-as-last an-x alox)
      (cond
        [(empty? alox) (list an-x)]
        [else (cons (first alox) (add-as-last an-x (rest alox)))]))
    The result of the recursive application produces the reverse of the rest of the list. It is processed by add-as-last, which adds the first item to the reverse of the rest and thus creates the reverse of the entire list. This second, auxiliary function is also recursive. We have thus identified a potential candidate.

    It is now time to study some hand-evaluations, as we did in A Problem with Structural Processing, to see whether an accumulator helps. Consider the following expression:

    (invert '(a b c))

    Here is how you calculate how invert determines the result when given '(a b c):
    = (add-as-last 'a (invert '(b c)))
    = (add-as-last 'a (add-as-last 'b (invert '(c))))
    = (add-as-last 'a (add-as-last 'b (add-as-last 'c (invert '()))))
    = (add-as-last 'a (add-as-last 'b (add-as-last 'c '())))
    = (add-as-last 'a (add-as-last 'b '(c)))
    = (add-as-last 'a '(c b))
    = '(c b a)
    Eventually invert reaches the end of the given list—just like add-as-lastand if it knew which items to put there, there would be no need for the auxiliary function.

  2. If we are dealing with a function based on generative recursion, we are faced with a much more difficult task. Our goal must be to understand whether the algorithm can fail to produce a result for inputs for which we expect a result. If so, adding a parameter that accumulates knowledge may help. Because these situations are complex, we defer the discussion of an example to More Uses of Accumulation.

Exercise 398. Does the insertion sort> function from Recursive Auxiliary Functions need an accumulator? If so, why? If not, why not?

37.2 Adding Accumulators

Once you have decided that an existing function should be equipped with an accumulator, take these two steps:
  • Determine the knowledge that the accumulator represents, what kind of data to use, and how the knowledge is acquired as data.

    For example, for the conversion of relative distances to absolute distances, it suffices to accumulate the total distance encountered so far. As the function processes the list of relative distances, it adds each new relative distance found to the accumulator’s current value. For the routing problem, the accumulator remembers every node encountered. As the path-checking function traverses the graph, it conses each new node on to the accumulator.

    In general, you want to proceed as follows.
    1. Create an accumulator template:
      ; Domain -> Range
      (define (function d0)
        (local (; Domain AccumulatorDomain -> Range
                ; accumulator ...
                (define (function/a d a)
                  ...))
          (function/a d0 a0)))
      Sketch a manual evaluation of an application of function to understand the nature of the accumulator.

    2. Determine the kind of data that the accumulator tracks.

      Write down a statement that explains the accumulator as a relationship between the argument d of the auxiliary function/a and the original argument d0.

      Note The relationship remains constant—also called invariantover the course of the evaluation. Because of this property, an accumulator statement is also called an accumulator invariant.

    3. Use the accumulator statement to determine the initial value a0 for a.

    4. Also exploit the accumulator statement to determine how to compute the accumulator for the recursive function calls within the definition of function/a.

  • Exploit the accumulator’s knowledge for the design of the auxiliary function.

    For a structurally recursive function, the accumulator’s value is typically used in the base case, that is, the cond clause that does not recur. For functions that use generative recursive functions, the accumulated knowledge might be used in an existing base case, in a new base case, or in the cond clauses that deal with generative recursion.

As you can see, the key is the precise description of the role of the accumulator. It is therefore important to practice this skill.

Let’s take a look at the invert example:
; [List-of X] -> [List-of X]
; construct the reverse of alox0
 
(check-expect (invert.v2 '(a b c)) '(c b a))
 
(define (invert.v2 alox0)
  (local (; [List-of X] ??? -> [List-of X]
          ; construct the reverse of alox
          ; accumulator ...
          (define (invert/a alox a)
            (cond
              [(empty? alox) ...]
              [else (invert/a (rest alox) ... a ...)])))
    (invert/a alox0 ...)))
As illustrated in the preceding section, this template suffices to sketch a manual evaluation of an expression such as

(invert '(a b c))

Here is the idea:
= (invert/a '(a b c) a0)
= (invert/a '(b c) ... 'a ... a0)
= (invert/a '(c) ... 'b ... 'a ... a0)
= (invert/a '() ... 'c ... 'b ... 'a ... a0)
This sketch suggests that invert/a can keep track of all the items it has seen in a list that tracks the difference between alox0 and a in reverse order. The initial value is clearly '(); updating the accumulator inside of invert/a with cons produces exactly the desired value when invert/a reaches '().

Here is a refined template that includes these insights:
(define (invert.v2 alox0)
  (local (; [List-of X] [List-of X] -> [List-of X]
          ; construct the reverse of alox
          ; accumulator a is the list of all those items
          ; on alox0 that precede alox in reverse order
          (define (invert/a alox a)
            (cond
              [(empty? alox) (code::hilite a)]
              [else (invert/a (rest alox) (cons (first alox) a))])))
    (invert/a alox0 '())))
While the body of the local definition initializes the accumulator with '(), the recursive call uses cons to add the current head of alox to the accumulator. In the base case, racket[invert/a] uses the knowledge in the accumulator—the reversed list.

Note how once again invert.v2 traverses the list just. In contrast, invert re-processes every result of its natural recursion with add-as-last. Stop! Measure how much faster invert.v2 runs than invert on the same list.

Terminology Programmers use the phrase accumulator-style function when they discuss functions that use an accumulator parameter. Examples of functions in accumulator-style are relative->absolute/a, path-exists?/a, and invert/a.

37.3 Transforming Functions into Accumulator-Style

Articulating the accumulator statement is difficult but without formulating a good invariant, it is impossible to understand an accumulator-style function. Since the goal of a programmer is to make sure that others who follow understand the code easily, practicing this skill is critical. And formulating invariants is deserves a lot of practice.

The goal of this section is to study the formulation of accumulator statements with three case studies: a summation function, the factorial function, and a tree-traversal function. Each such case is about the conversion of a structurally recursive function into accumulator style. None actually call for the use of an accumulator parameter. But they are easily understood and, with the elimination of all other distractions, using such examples allows us to focus on the articulation of the accumulator invariant.

For the first example, consider the following definition of the sum function:
; [List-of Number] -> Number
; compute the sum of the numbers on alon
 
(check-expect (sum '(10 4 6)) 20)
 
(define (sum alon)
  (cond
    [(empty? alon) 0]
    [else (+ (first alon) (sum (rest alon)))]))
Here is the first step toward an accumulator version:
; [List-of Number] -> Number
; compute the sum of the numbers on alon0
 
(check-expect (sum.v2 '(10 4 6)) 20)
 
(define (sum.v2 alon0)
  (local (; [List-of Number] ??? -> Number
          ; compute the sum of the numbers on alon
          ; accumulator ...
          (define (sum/a alon a)
            (cond
              [(empty? alon) ...]
              [else (... (sum/a (rest alon) ... a ...) ...)])))
    (sum/a alon0 ...)))
As suggested by our first step, we have put the template for sum/a into a local definition, added an accumulator parameter, and renamed sum 's parameter.

Here are two side-by-side sketches of hand evaluations:

(sum '(10 4)) =

(sum.v2 '(10 4)) =

= (+ 10 (sum '(4)))
= (+ 10 (+ 4 (sum '())))
= (+ 10 (+ 4 (+ 0)))
...
= 20.0
= (sum/a '(10 4) a0)
= (sum/a '(4) ... 10 ... a0)
= (sum/a '() ... 4 ... 10 ... a0)
...
= 20.0
A comparison immediately suggests the central idea, namely, that sum/a can use the accumulator to add up the numbers as it encounters.

Concerning the accumulator invariant, this analysis suggest a represents the sum of the numbers encountered so far:

a represents the sum of the numbers that alon lacks in comparison to alon0

For example, if

alon0

     

=

     

'(10 4 6)

alon

     

=

     

'(6)

the invariant forces the accumulator’s value to be 14. In contrast, when

alon0

     

=

     

'(10 4 6)

alon

     

=

     

'()

a must be 20.

Given this precise invariant, the rest of the design is straightforward again:
(define (sum.v2 alon0)
  (local (; [List-of Number] ??? -> Number
          ; compute the sum of the numbers on alon
          ; accumulator a represents the sum of the numbers
          ; that alon lacks in comparison to alon0
          (define (sum/a alon a)
            (cond
              [(empty? alon) a]
              [else (sum/a (rest alon) (+ (first alon) a))])))
    (sum/a alon0 0)))
If alon is empty, sum/a returns a because it represents the sum of all numbers on alon. The invariant also implies that 0 is the initial value for a0 and + updates the accumulator by adding the number that is about to be “forgotten”—(first alox)to the accumulator a.

Exercise 399. Explain why the natural recursion maintains the correctness of the accumulator statement:

(sum/a (rest alon) (+ (first alon) a))

Study the above examples before you formulate a general argument.

Exercise 400. Complete the above manual evaluation of

(sum/a '(10 4 6))

Doing so shows that the sum and sum.v2 add up the given numbers in reverse order. While sum adds up the numbers from right to left, the accumulator-style version adds them up from left to right.

Note For exact numbers, this difference has no effect on the final result. For inexact numbers, the difference is significant. Consider the following definition:
(define (g-series n)
  (cond
    [(zero? n) empty]
    [else (cons (expt -0.99 n) (g-series (sub1 n)))]))
Applying g-series to a natural number produces the beginning of a so-called geometric series. The numbers in this series rapidly oscillate in the interval (-1,+1):
> (g-series 5)

(list

 #i-0.9509900498999999

 #i0.96059601

 #i-0.970299

 #i0.9801

 #i-0.99)

Each summation function computes a different sum for the same series:
> (sum (g-series 1000.0))

#i-0.49746596003269394

> (sum.v2 (g-series 1000.0))

#i-0.49746596003269533

While the difference may appear to be small, imagine a context where the actual calculation is something like this:
> (- (* 1e+16 (sum (g-series 1000.0)))
     (* 1e+16 (sum.v2 (g-series 1000.0))))

#i14.0

And now the difference matters. End

For the second example, we turn to the well-known factorial function:The factorial function is useful in certain areas of mathematics and in some programming libraries. No ordinary programmer has a need to know the function for its own sake.
; N -> N
; compute (* n (- n 1) (- n 2) ... 1)
 
(check-expect (! 3) 6)
 
(define (! n)
  (cond
    [(zero? n) 1]
    [else (* n (! (sub1 n)))]))
While relative-2-absolute and invert processed lists, the factorial function works on natural numbers. Its template is that for N processing functions.

We proceed as before by with a template for an accumulator-style version:
; N -> N
; compute (* n0 (- n0 1) (- n0 2) ... 1)
 
(check-expect (!.v2 3) 6)
 
(define (!.v2 n0)
  (local (; N ??? -> N
          ; compute (* n (- n 1) (- n 2) ... 1)
          ; accumulator ...
          (define (!/a n a)
            (cond
              [(zero? n) ...]
              [else (... (!/a (sub1 n) ... a ...) ...)])))
    (!/a n0 ...)))
followed by a sketch of a hand evaluation:

(! 3) =

(!.v2 3) =

= (* 3 (! 2))
= (* 3 (* 2 (! 1)))
= (* 3 (* 2 (* 1 (! 0))))
= (* 3 (* 2 (* 1 1)))
...
= 6
= (!/a 3 a0)
= (!/a 2 ... 3 ... a0)
= (!/a 1 ... 2 ... 3 ... a0)
= (!/a 0 ... 1 ... 2 ... 3 ... a0)
...
= 6
The left column shows how the original version works, the right one sketches how the accumulator-style function proceeds. Both traverse the natural number until they reach 0. While the original version schedules only multiplications, the accumulator keeps track of each number as the structural processing descends through the given natural number.

Given the goal of multiplying these numbers, !/a can use the accumulator to multiply the numbers immediately:

a is the product of the natural numbers in the interval [n0,n).

In particular, when n0 is 3 and n is 1, a is 6.

Exercise 401. What should the value of a be when n0 is 3 and n is 1? How about when n0 is 10 and n is 8?

Using this invariant we can easily pick the initial value for ait is 1and we know that multiplication the current accumulator with n is the proper update operation:
(define (!.v2 n)
  (local (; N N -> N
          ; compute (* n (- n 1) (- n 2) ... 1)
          ; accumulator a is the product of the natural
          ; numbers in the interval [n0,n).
          (define (!/a n a)
            (cond
              [(zero? n) a]
              [else (!/a (sub1 n) (* n a))])))
    (!/a n0 1)))
It also follows from the accumulator statement that when n is 0, the accumulator is the product of n through 1, meaning it is the desired result. So, like sum, !/a returns a in this case and uses the result of the recursion in the second case.

Exercise 402. Like sum, ! performs the primitive computation steps—multiplication in this case—in reverse order. Surprisingly, this affects the performance of the function in a negative manner.

Measure how long it takes to evaluate (! 20) one thousand times. Recall that (time an-expression) function determines how long it takes to run _an-expression.

For the third and last example, we use a function that measures the height of simplified binary trees. The example illustrates that accumulator-style programming applies to all kinds of data, not just those defined with single self-references. Indeed, it is as common for complicated data definitions as it is for lists and natural numbers.

Here are the relevant definitions:
(define-struct node (left right))
; A BinaryTree (short Tree) is one of:
;  '()
;  (make-node Tree Tree)
 
(define example (make-node (make-node '() (make-node '() '())) '()))
 
; Tree -> N
; measure the height of abt0
 
(check-expect (height example) 3)
 
(define (height abt)
  (cond
    [(empty? abt) 0]
    [else (+ (max (height (node-left abt)) (height (node-right abt))) 1)]))
These trees carry no information; their leafs are '(). Still, there are many different trees as figure 110 shows; it also uses suggestive graphics to bring across what these pieces of data look like as trees. The table also suggests how to measure the height of a tree, though leaves it somewhat ambiguous: it is either the number of nodes from the root of the tree to the highest leaf or the number of connections on such a path. The height function follows the second option.

image

     

'()

image

     

(make-node '() '())

 

     

 

image

     

(make-node (make-node '()
                      (make-node '() '()))
           '())

Figure 110: Some stripped-down binary trees

To transform this function into an accumulator-style function, we follow the standard path. We begin with an appropriate template:
; Tree -> N
; measure the height of abt0
 
(check-expect (height.v2 example) 3)
 
(define (height.v2 abt0)
  (local (; Tree ??? -> N
          ; measure the height of abt
          ; accumulator ...
          (define (height/a abt a)
            (cond
              [(empty? abt) ...]
              [else
                (... (height/a (node-left abt) ... a-R ...) ...
                 ... (height/a (node-right abt) ... a-L ...) ...)])))
    (height abt0 ...)))
As always, the problem is to determine what knowledge the accumulator represents. One obvious choice is the number of traversed branches:

a is the number of steps it takes to reach abt from abt0.

Illustrating this accumulator invariant is best done with a graphical example. Take a second look at figure 110. The bottom-most tree comes with two annotations, each pointing out one subtree:
  1. If abt0 is the complete tree and abt is the subtree pointed to by 1, the accumulator’s value must be 1 because it takes exactly one step to get from the root of abt to the root of abt0.

  2. In the same spirit, for the subtree labeled 1 the accumulator is 2 because it takes two steps to get this place.

As for the preceding two examples, the invariant basically dictates how to follow the rest of the design recipe for accumulators: the initial value for a is 0; the update operation is add1; and the base case uses the accumulated knowledge by returning it. Translating this into code yields the following skeleton definition:
(define (height.v2 abt0)
  (local (; Tree N -> N
          ; measure the height of abt
          ; accumulator a is the number of steps
          ; it takes to reach abt from abt0
          (define (height/a abt a)
            (cond
              [(empty? abt) a]
              [else
                (... (height/a (node-left abt)  (+ accumulator 1)) ...
                 ... (height/a (node-right abt) (+ accumulator 1)) ...)])))
    (height abt0 0)))
But, in contrast to the first two examples, a is not the final result. In the second cond clause, the two recursive calls yield two values. The design recipe for structural functions dictate that we combine those in order to formulate an answer for this case; the dots above indicate that we still need to pick an operation that combines these values.

Following the design recipe also tells us that we need to interpret the two values to find the appropriate function. According to the purpose statement for height/a, the first value is the height of the left subtree, and the second one is the height of the right one. Given that we are interested in the height of abt itself and that the height is the largest number of steps it takes to reach a leaf, we use the max function to pick the proper one; see figure 111 for the complete definition.

; Tree -> N
; measure the height of abt0
 
(check-expect (height.v2 example) 3)
 
(define (height.v2 abt0)
  (local (; Tree N -> N
          ; measure the height of abt
          ; accumulator a is the number of steps
          ; it takes to reach abt from abt0
          (define (height/a abt a)
            (cond
              [(empty? abt) a]
              [else
                (max (height/a (node-left abt)  (+ accumulator 1))
                     (height/a (node-right abt) (+ accumulator 1)))])))
    (height abt0 0)))

Figure 111: The accumulator-style version of height

Note on an Alternative Design In addition to counting the number of steps it takes to reach a node, an accumulator function could hold on to the largest height encountered so far. Here is the accumulator statement for the design idea:

the first accumulator, a, represents the number of steps it takes to reach abt from abt0 and the second accumulator, stands for the tallest branch in the part of abt0 that is to the left of abt.

Clearly, this statement assumes a template with two accumulator parameters:
(define (height.v3 abt0)
  (local (; Tree N N -> N
          ; measure the height of abt
          ; accumulator a is the number of steps
          ; it takes to reach abt from abt0
          ; accumulator m is the maximal height of
          ; the part of abt0 that is to the left of abt
          (define (height/a abt a)
            (cond
              [(empty? abt) ...]
              [else
                (... (height/a (node-left abt) ... a-R ...) ...
                 ... (height/a (node-right abt) ... a-L ...) ...)])))
    (height abt0 ...)))
In terms of the bottom-most tree of figure 110, the place marked 1 has no complete paths to leafs to its left while the place marked 2 has one complete path and it consists of two steps.

Exercise 403. Complete the design of height.v3.

This second design has a more complex accumulator invariant than the first one. By implication, its implementation requires more care than the first one. At the same time, it comes without any advantages, meaning it is inferior to the first one.

Our point is that different accumulator invariants yield different variants. You can design both variants systematically following the same design recipe. When you have complete function definitions, you can compare and contrast the results, and you can then decide which one to keep based on evidence. End

Exercise 404. Design an accumulator-style version of product, the function that computes the product of a list of numbers. Stop when you have formulated the accumulator invariant and have someone check it.

Exercise 405. Design an accumulator-style version of how-many, which is the function that determines the number of items on a list. Stop when you have formulated the accumulator invariant and have someone check it.

Exercise 406. Design an accumulator-style version of add-to-pi, which adds a natural number to pi without using +:
; N -> Number
; add n to pi without use +
 
(check-within (add-to-pi 2) (+ 2 pi) 0.001)
 
(define (add-to-pi n)
  (cond
    [(zero? n) pi]
    [else (add1 (add-to-pi (sub1 n)))]))
Stop when you have formulated the accumulator invariant and have someone check it.

Exercise 407. Design the function make-palindrome, which accepts a non-empty list and constructs a palindrome by mirroring the list around the last item. When given (explode "abc"), it yields (explode "abcba").

Hint Here is a solution designed by function composition:
; [cons 1String [List-of 1String]] -> [cons 1String [List-of 1String]]
; create a palindrome by mirroring the given list around the last item
 
(check-expect (mirror (explode "abc")) (explode "abcba"))
 
(define (mirror s0)
  (append (all-but-last s0) (list (last s0)) (reverse (all-but-last s0))))
See Generalizing Functions for last; design all-but-last in an analogous manner. This solution traverses s0 four times:
  1. via all-but-last,

  2. via last,

  3. via all-but-last again, and

  4. via reverse, which is ISL+’s version of inverse.

Even with local definition for the result of all-but-last, the function needs three traversals. While these traversals aren’t “stacked” and therefore don’t have a disastrous impact on the function’s performance, an accumulator version can compute the same result with a single traversal.

Exercise 408. Design to10. It consumes a list of digits and produces the corresponding number. The first item on the list is the most significant digit. Hence, when applied to '(1 0 2), it produces 102.

Domain knowledge You may recall from grade school that the result is determined by

image

Exercise 409. Design the function is-prime, which consumes a natural number and returns true if it is prime and false otherwise.

Domain knowledge A number n is prime if it is not divisible by any number between n - 1 and 2.

Hint The design recipe for N [>=1] suggests the following template:
; N [>=1] -> Boolean
; determine whether n is a prime number
(define (is-prime? n)
  (cond
    [(= n 1) ...]
    [else (... (is-prime? (sub1 n)) ...)]))
This outline immediately tells you that the function forgets n, its initial argument as it recurs. Since n is definitely needed to determine whether n is divisible by (- n 1), (- n 2), and so on, you know that you need an accumulator-style function.

Note People who encounter accumulator-style programming for the first time often get the impression that they are always faster than their recursive counterparts. Both parts are plain wrong. While it is impossible to explain this mistake in reasoning in this book, let us take a look at the solution of exercise 402:

!

     

5.760

     

5.780

     

5.800

     

5.820

     

5.870

     

5.806

!.v2

     

5.970

     

5.940

     

5.980

     

5.970

     

6.690

     

6.111

The table represents the timings for the two factorial functions. Specifically, the top row shows the number of seconds for 1,000 evaluations of (! 20) where the last cell shows the average. The bottom row shows the result of an analogous experiment with !.v2. Bottom line is the performance of the accumulator-style version of factorial is always worse than that of the original factorial function.

38 More Uses of Accumulation

This section presents three extended exercises that require the whole range of skills: design by recipe, including generative recursion, and the addition of accumulators for various purposes.

38.1 Extended Exercise: Compiling ISL+

When you ask DrRacket to run an ISL+ program, the ISL+ compiler creates commands for your computer and asks the computer to perform these commands. Before the compiler translates your code, it checks that every variable in the program is declared via a define, define-struct, or a lambda.

Stop! Enter x as a complete ISL+ program into DrRacket and ask it to run this program. What do you see?

Let us phrase this check as a sample problem:

Sample Problem: You have been hired to re-create a part of the ISL+ compiler. Specifically, your task deals with the following language fragment, specified in the so-called grammar notation that many programming language manuals use:We use the Greek letter λ instead of lambda to signal that this exercise deals with ISL+ as an object of study not just a programming language.
  expression = variable
  | (λ (variable) expression)
  | (expression expression)
Read the grammar aloud replacing = with “is one of” and | with “or.”

Recall that λ expressions are functions without names. They bind their parameter for the body. Conversely, a variable occurrence is declared by a surrounding λ that specifies the same variable name as a parameter.You may wish to revisit Intermezzo: Scope because it deals with the same issue from the perspective of a programmer. Look up the terms binding occurrence, bound occurrence, and free in this intermezzo.

Develop a data representation for the above language fragment; use symbols to represent variables. Then design a function that replaces all undeclared variables with 'undeclared.

This problem is representative of many steps in the translation process and, at the same time, is a great case study for accumulator-style functions.

Before we dive into the problem, let’s look at some examples in this mini-language, recalling what we know about lambda:
  • (λ (x) x) is the function that returns whatever it is given, also known as the identity function;

  • (λ (x) y) looks like a function that returns y whenever it is given an argument, except that y isn’t declared;

  • (λ (y) (λ (x) y)) is a function that, when given some value v, produces a function that always returns v;

  • ((λ (x) x) (λ (x) x)) applies the identity function to itself;

  • ((λ (x) (x x)) (λ (x) (x x))) is a short infinite loop; and

  • (((λ (y) (λ (x) y)) (λ (z) z)) (λ (w) w)) is complex expression that is best run in ISL+ to find out whether it even terminates.

Indeed, you can run all of the above ISL+ expression in DrRacket to confirm what is written about them.

Exercise 410. Explain the scope of each binding occurrence in the above examples. Draw arrows from all bound occurrences to the binding occurrences.

Developing a data representation for the language is easy, especially because its description uses a grammar notation. Here is one possibility:
; A Lam is one of:
;  a Symbol
;  (list 'λ (list Symbol) Lam)
;  (list Lam Lam)
Because of quote, this data representation makes it easy to create data representations for expressions in our subset of ISL+:
(define ex1 '(λ (x) x))
(define ex2 '(λ (x) y))
(define ex3 '(λ (y) (λ (x) y)))
(define ex4 '((λ (x) (x x)) (λ (x) (x x))))
These four data examples are representations of some of the above expressions. Stop! Create data representations for the remaining expression examples.

Exercise 411. Define the functions is-var?, is-λ?, and is-app?, predicates that distinguish (representations of) variables from λ expressions and applications.

Also define
  • λ-para, which extracts the parameter from a λ expression;

  • λ-body, which extracts the body from a λ expression;

  • app-fun, which extracts the function from an application; and

  • app-arg, which extracts the argument from an application.

With these, you basically can act as if you had used a structure-oriented data definition.

Design declareds, which collects all symbols used as λ parameters in a list.

Exercise 412. Develop a data representation for the same subset of ISL+ that uses structures instead of lists. Also provide data representations for ex1, ex2, and ex3 following you data definition.

We follow the structural design recipe, and here is the product of the next two steps:
; Lam -> Lam
; replace all symbols s in le with '*undeclared if they do
; not occur within the body of a λ whose parameter is s
 
(check-expect (undeclareds ex1) ex1)
(check-expect (undeclareds ex2) '(λ (x) *undeclared))
(check-expect (undeclareds ex3) ex3)
(check-expect (undeclareds ex4) ex4)
 
(define (undeclareds le0)
  le0)
Note how we expect undeclareds to process ex4 even though the expression loops forever when run; compilers don’t run programs, they read them and create others.

A close look at the purpose statement directly suggests that the function needs an accumulator. This becomes even clearer when we inspect the template for undeclareds:
(define (undeclareds le)
  (cond
    [(is-var? le) ...]
    [(is-λ? le) (... (undeclareds (λ-body le)) ...)]
    [(is-app? le)
     (... (undeclareds (app-fun le)) (undeclareds/a (app-arg le)) ...)]))
When undeclareds recurs on the body of (the representation of) a λ expression, it forgets the (λ-para le).

So, let’s start with an accumulator-style template:
(define (undeclareds le0)
  (local (; Lam ??? -> Lam
          ; accumulator a represents ...
          (define (undeclareds/a le a)
            (cond
              [(is-var? le) ...]
              [(is-λ? le) (... (undeclareds (λ-body le) ... a ...) ...)]
              [(is-app? le)
               (... (undeclareds (app-fun le) ... a ...)
                    (undeclareds/a (app-arg le) ... a ...) ...)])))
    (undeclareds/a le0 ...)))
In this context, we can now formulated an accumulator invariant:

a represents the list of λ parameters encountered on the path from le0 to le.

For example, if le0 is

'(((λ (y) (λ (x) y)) (λ (z) z)) (λ (w) w))

and le is the highlighted subtree, then a contains y. Similarly, if we pick a different subtree of the same piece of data,

'(((λ (y) (λ (x) y)) (λ (z) z)) (λ (w) w))

we get an accumulator that contains both 'y and 'x.

Now that we have settled on the data representation of the accumulator and its invariant, we can resolve the remaining design questions:
  • the initial accumulator value of '();

  • we can use cons to add (λ-para le) to a; and

  • once undeclareds/a reaches a variable, it can use the accumulator to check whether the variable is in the scope of a declaration.

Figure 112 shows how to translate these ideas into a complete function definition. Note the name declareds for the accumulator; it brings across the key idea behind the accumulator invariant, helping the programmer understand the definition. The base case uses member? from ISL+ to determine whether the variable le is in declareds and, if not, replaces it with '*undeclared. The second cond clause uses a local to introduce the extended accumulator newd. Because para is also used to rebuild the expression, it has its own local definition. Finally, the last clauses concerns function applications, which do not declare variables and do not use any directly. As a result, it is by far the simplest of the three clauses.

; Lam -> Lam
; replace all symbols s in le with '*undeclared if they do
; not occur within the body of a λ whose parameter is s
 
(check-expect (undeclareds ex1) ex1)
(check-expect (undeclareds ex2) '(λ (x) *undeclared))
(check-expect (undeclareds ex3) ex3)
(check-expect (undeclareds ex4) ex4)
 
(define (undeclareds le0)
  (local (; Lam [List-of Symbol] -> [List-of Symbol]
          ; accumulator declareds is a list of all λ
          ; parameters on the path from le0 to le
          (define (undeclareds/a le declareds)
            (cond
              [(is-var? le)
               (if (member? le declareds) le '*undeclared)]
              [(is-λ? le)
               (local ((define para (λ-para le))
                       (define newd (cons para declareds))
                       (define body (undeclareds/a (λ-body le) newd)))
                 (list 'λ (list para) body))]
              [(is-app? le)
               (list (undeclareds/a (app-fun le) declareds)
                     (undeclareds/a (app-arg le) declareds))])))
    (undeclareds/a le0 '())))

Figure 112: Finding undeclared variables

Exercise 413. Make up an ISL+ expression in which x occurs both free and bound. Formulate it as an element of Lam. Does undeclareds work properly on your expression?

Exercise 414. Considering the following expression:

(λ (*undeclared) ((λ (x) (x *undeclared)) y))

Yes, it uses *undeclared as a variable. Represent it in Lam and check what undeclareds produces for this expression.

Modify undeclareds so that it replaces each free variable 'x occurrence with

(list '*undeclared 'x)

and each bound one y with

(list '*declared 'y)

Doing so unambiguously identifies problem spots, which a program-development environment such as DrRacket can use to high-light errors.

Note The trick to replace a variable occurrence with the representation of an application feels awkward. If you dislike it, consider synthesizing the symbols '*undeclared:x and 'declared:y instead.

Exercise 415. Re-design the undeclareds function for the structure-based data representation from exercise 412.

image                      image

Figure 113: Static distances

Exercise 416. Design the function static-distance. It replaces all occurrences of variables with a natural number that represents how far away the declaring λ is.

Figure 113 illustrates the idea. The tree on the left represents the Lam term

'((λ (y) (λ (x) (y x))) (λ (z) z))

in graphical form. It includes arrows that point from variable occurrences to the corresponding variable declarations. On the right, the figure shows a tree of the same shape. Variable declarations have been erased and variable occurrences have been replaced by natural numbers that specify which 'λ declares the variable. Use the natural numbers to walk upwards—toward the “root” of the tree—to find the corresponding declaration. A value of 0 denotes the first one on the path to the root, 1 the second one, and so on.

Hint The undeclareds accumulator of undeclareds/a is a list of all parameters on path from le to le0 in reverse orderthe last one seen is at the first on the list.

38.2 Extended Exercise: Game Trees

On occasion, accumulators are best merged with problem data rather than managed separately in a function. The use of game trees presents a good example. When you design programs that solve puzzles or automate game playing, these programs tend to explore the tree of possibilities that a game or a puzzle generate. Playing a game or solving a puzzle then becomes a problem of searching the tree for a specific kind of state of the game or puzzle.

Let’s set up a context to make this idea concrete:

Sample Problem: Your manager tells you the following story.

“Once upon a time, three cannibals were guiding three missionaries through a jungle. They were on their way to the nearest mission station. After some time, they arrived at a wide river, filled with deadly snakes and fish. There was no way to cross the river without a boat. Fortunately, they found a row boat with two oars after a short search. Unfortunately, the boat was too small to carry all of them. It could barely carry two people at a time. Worse, because of the river’s width there was no way to bring the boat back other than to row it back.

“Since the missionaries could not trust the cannibals they had to figure out a plan to get all six of them safely across the river. The problem was that these cannibals would kill and eat missionaries as soon as there were more cannibals than missionaries at some place. Thus our missionary-programmer had to devise a plan that guaranteed that there were never any missionaries in the minority at either side of the river. The cannibals, however, can be trusted to cooperate otherwise. Specifically, they won’t abandon any potential food, just as the missionaries won’t abandon any potential converts.”

It turns out your manager wants to explore whether your group can design (and sell) programs that solve such puzzles.

Note how this problem statement leaves open what the program is to compute.

In principle, it is quite straightforward to solve such puzzles by hand. Here is the rough idea. Pick a graphical representation of the problem states. Ours consists of a three-part box: the left one represents the missionaries and the cannibals on the left; the middle combines the river and the boat; and the third part is the right-hand side of the river. Take a look at the following representation of the initial state:

image

Black circles denote missionaries, white circles cannibals. All of them are on the left-hand river bank. The boat is also on the left side. Nobody is on the right. Here are two more states:

image            image

The first one is the final state, where all people and the boat are on the right bank of the river. The second one depicts some intermediate state where two people are on the left with the boat and four people are on the right.

image

Figure 114: Creating a game tree

Now that you have a way to write down the state of the puzzle, you can think about the possibilities at each stage. Doing so yields a tree of possible moves. Figure 114 sketches the first two and a half layers in such a tree. The left-most state is the initial one. Because the boat can transport at most two people and must be rowed by at least one, you have five possibilities to explore: one cannibal rows across, two, one missionary and one cannibal go, one missionary, or two missionaries. These possibilities are represented with five arrows going from the initial state to five intermediate states.

For each of these five intermediate states, you can play the same game again. In figure 114 you see how the game continues for the middle (third) one of the new states. Because there are only two people on the right river bank, you see three possibilities: a cannibal goes back, a missionary, or both. Hence three arrows connect the middle state to the three states on the right side of the tree.

If you keep drawing the tree of possibilities—especially if you are doing it systematically—you sooner or later discover the final state. That is, you create the final state with all people on the right river bank by moving a boat load of people from the left river bank to the right one, and nobody is left back.

A close look at figure 114 reveals two small problems with this naive approach to generating the tree of possibilities. The first one is the dashed arrow that connects the middle state on the right to the initial state. It indicates that rowing back the two people from the right to the left gets the puzzle back to its initial state, meaning you’re starting over. Moving people in this way is clearly undesirable. The second problem concerns those states with a star in the top-right corner. In both cases, there are more white-circle cannibals than black-circle missionaries on the left river bank, meaning the cannibals would eat the missionaries. Again, the goal is to avoid such states, making these moves undesirable.

One way to turn this puzzle into a program is to design a function that determines whether some final state—here the final state—is reachable from some given state. Here is an appropriate function definition:
; PuzzleState -> PuzzleState
; determine whether the final state is reachable from the given state
; generative create search tree of possible boat rides
; termination ???
 
(check-expect (solve initial-puzzle) final-puzzle)
 
(define (solve state0)
  (local (; [List-of PuzzleState] -> PuzzleState
          ; generative generate the successor states for all intermediate ones
          (define (solve* los)
            (cond
              [(ormap final? los) (first (filter final? los))]
              [else (solve* (create-next-states los))])))
    (solve* (list state0))))
The auxiliary function uses generative recursion, generating all new possibilities given a list of possibilities. If one of the given possibilities is a final state, the function returns it.

Clearly, solve is quite generic. As long as you define a collection of PuzzleStates, a function for recognizing final states, and a function for creating all “successor” states, solve can work in your puzzle.

Exercise 417. The solve* function generates all states reachable with, say, seven boat trips before it goes on to states that require eight boat trips. This claim is independent of the problem that some of those boat trips bring us back to states previously seen. Still, solve* will not go into an infinite loop because of such cycles in the tree of possibilities. Why?

Exercise 418. Develop a data representation for the states of the missionary-and-cannibal puzzle. Like the graphical representation, a state must obviously record the number of missionaries and cannibals on each side of the river plus the location of the boat. After all, these are the properties of the world that change with one boat trip.

Clearly the description of PuzzleStates calls for a structure type definition. Represent the above initial, intermediate, and final states in your chosen data representation.

Design the function final?, which detects whether in a given state all people are on the right river bank.

Design the function render-mc, which maps a state of the missionary-and-cannibal puzzle to an image.

The problem is that returning the final state says nothing about how the player can get from the initial state to the final one. In other words, create-next-states forgets how it gets to the returned states from the given ones. And this situation clearly calls for an accumulator, but at the same time, the accumulated knowledge is clearly associated with the individual PuzzleStates not solve* or any other function.

Exercise 419. Modify the data representation from exercise 418 so that each state records the sequence of states traversed to get there. Use a list of states.

Articulate and write down an accumulator statement with the data definition that explains the additional field.

Do you have to modify final? to discover final state? render-mc to view these modified puzzle states as images?

Exercise 420. Design the create-next-states function. It consumes lists of missionary-and-cannibal states and generates the list of all those states that a boat ride can reach.

Ignore the accumulator in the first draft of create-next-states, but make sure that the function does not generate states where the cannibals can eat the missionaries.

For the second design, update the accumulator field in the state structures and use it to rule out states that generate cycles.

Exercise 421. Modify solve so that it produces the list of states that lead from the initial puzzle state to the final one.

You may also consider creating a movie from this list, using render-mc to generate the images. Use run-movie to display the movie.

38.3 Extended Exercise: Board Solitaire

Peg Solitaire is a board game for individuals. The board comes in various shapes. Here is the simplest one:

image image image

The circle without a black dot represents an unoccupied hole; the other circles are holes containing little pegs.

image

The goal of the game is to eliminate the pegs one by one, until only one peg is left. A player can eliminate a peg if one of the neighboring holes is unoccupied and if there is a peg in the hole in the opposite direction. In that case, the second peg can jump over the first one and the first one is eliminated. Consider the following configuration:

Here the pegs labeled~1 and~2 could jump. If the player decides to move the peg labeled~2, the next configuration is

Some configurations are dead-ends. For a simple example, consider the first board configuration. Its hole is in the middle of the board. Hence no peg can jump, because there are no two pegs in a row, column, or diagonal such that one can jump over the other into the hole. A player who discovers a dead-end configuration must stop or backtrack by undoing moves and trying alternatives.

Exercise 422. Develop a representation for triangular Solitaire boards.

Develop a data representation for peg moves. Pegs can move along a row, a column, and a diagonal.

Hints (1) There are at least four rows, because it is impossible to play the game with three or fewer. Still, develop the data definition independently of such constraints. (2) Translate our examples from above into the chosen data representations.

Exercise 423. Develop a function that, given a board and the board position of a peg, determines whether or not the peg can jump. We call such a peg enabled.

Develop a function that, given a board and the board position of an enabled peg, creates a board that represents the next configuration.

% Develop a function that, given a board and a function that consumes board % positions, applies the function to the board and every board position.

Exercise 424. Develop the function solitaire, which solves a Solitaire problem for different sizes of the equilateral triangle. The function should consume a board. It produces #f, if the given problem is not solvable. Otherwise, it should produce a list of moves that specifies in what order the pegs must be moved to solve the given Solitaire problem.

Formulate the tests for all functions as boolean-valued expressions.

39 Generative Recursion with Accumulators

39.1 Fractals, a Second Taste

Exercise 425. As mentioned, the right-most image in figure 87 illustrates the generative idea behind the Sierpinski process in a single picture. The given problem is a triangle, that is, three points. Once again, when the triangle is too small to be subdivided any further, the algorithm just draws it. Otherwise, the algorithm finds the midpoints of the three sides and draws the three outer triangles, which implicitly identifies the inner triangle, too.

To translate this description, and especially the partitioning step, into an ISL+ function, it is critical to choose the input data properly. Based on the description, the function consumes three points, each of which is easily represented

obvious choice for a tri

From the perspective of "2htdp/image" drawing a tr

. Let us summarize our discussion with a skeletal ISL+ definition:
; Posn Posn Posn Image -> Image
; adds the triangle (a, b, and c) to s
; if it is small enough
(define (sierpinski a b c)
  (cond
    [(too-small? a b c) (add-triangle s a b c)]
    [else (...  ...)]))
The function consumes three posn structures and returns #t when it is done. The cond expression reflects the general outline of an algorithm. It is our task to define too-small the function that determines whether the problem is trivially solvable, and add-triangle. In addition, we must still add a ISL+ expression that formulates the partitioning of the triangle.

The partitioning step requires the function to determine the three mid-points between the three end-points. Let us call these new mid-points a-b, b-c, and c-a. Together with the given endpoints, a, b, and c, they determine four triangles:
  • a, a-b, c-a;

  • b, a-b, b-c;

  • c, c-a, b-c;

  • a-b, b-c, c-a.

Thus, if we wanted to create the Sierpinski triangle for, say, the first listed triangle, we would use (sierpinski a a-b c-a).

Since each midpoint is used twice, we use a local expression to translate the generative step into ISL+. The local expression introduces the three new midpoints. Its body contains three recursive applications of sierpinski and the add-triangle application mentioned earlier. To combine the solutions of the three problems, we use an and expression, which ensures that all three recursions must succeed. Figure 87 collects all the relevant definitions, including two small functions based on domain knowledge from geometry.

Develop the functions
to complete the definitions in figure 87.

Use the teachpack "draw.ss" to test the code. For a first test of the complete function, use the following definitions:
(define A (make-posn 200 0))
(define B (make-posn 27 300))
(define C (make-posn 373 300))
Create a canvas with (start 400 400). Experiment with other end points and canvas dimensions.

%% —

Exercise 426. The process of drawing a Sierpinski triangle usually starts from an equilateral shape. To compute the endpoints of an equilateral Sierpinski triangle, we can pick a large circle and three points on the circle that are 120 degrees apart. For example, they could be at 0, 120, 240:
(define CENTER (make-posn 200 200))
 
(define RADIUS 200)
 
; cicrcl-pt: Number -> Posn
; computes a position on the circle with CENTER
; and RADIUS as defined above
(define (circle-pt factor) ...)
 
(define A (circle-pt 1/3))
(define B (circle-pt 2/3))
(define C (circle-pt 1))
Develop the function circle-pt.

Hint Recall that DrRacket sin and cos compute the sine and cosine in terms of radians, not degrees. Also keep in mind that on-screen positions grow downwards not upwards.

Exercise 427. Rewrite the function in figure 87 to use structures for the representation of triangles. Then apply the new function to a list of triangles and observe the effect.

Exercise 428. Take a look at the following two pictures:

\treepic

The left one is the basic step for the generation of the “Savannah” tree on the right. It is analogous to the picture in the middle of figure 86. Develop a function that draws trees like the one in the right picture.

Hint Think of the problem as drawing a straight line, given its starting point and an angle in, say, radians. Then, the generative step divides a single straight line into three pieces and uses the two intermediate points as new starting points for straight lines. The angle changes at each step in a regular manner.

Exercise 429. In mathematics and computer graphics, people must often connect some given points with a smooth curve. One popular method for this purpose is due to Bézier.Dr. Géraldine Morin suggested this exercise. Here is a sequence of pictures that illustrate the idea:

\bezierpic

For simplicity, we start with three points: p1, p2, and p3. The goal is to draw a smooth curve from p1 to p3, viewed from p2. The original triangle is shown on the left; the desired curve appears on the right.

To draw the curve from a given triangle, we proceed as follows. If the triangle is small enough, draw it. It appears as a large point. If not, generate two smaller triangles as illustrated in the center picture. The outermost points, p1 and p3, remain the respective outermost points. The replacements for the point in the middle are r2 and q2, which are the midpoints between p1 and p2 and between p2 and p3, respectively. The midpoint between r2 and q2 (marked with image) is the new left-most and right-most endpoint, respectively, for the two new triangles.

To test the function, use the teachpack "draw.ss". Here is some good test data:
(define p1 (make-posn 50 50))
(define p2 (make-posn 150 150))
(define p3 (make-posn 250 100))
Use (start 300 200) to create the canvas. Experiment with other positions.

39.2 Gaussian Elimination, Again

(define M
  '((0 4 5)
    (1 2 3)))
 
(define M1
  '((1 2 3)
    (0 4 5)))
 
(check-expect (rotate-until.v1 M) M1)
 
(define (rotate-until.v1 l0)
  (local ((define (rotate-until l seen)
            (cond
              [(not (= (first (first l)) 0)) (cons (first l) (append seen (rest l)))]
              [else (rotate-until (rest l) (cons (first l) seen))])))
    (rotate-until l0 '())))
 
(check-expect (rotate-until.v2 M) M1)
 
(define (rotate-until.v2 l)
  (cond
    [(not (= (first (first l)) 0)) l]
    [else (rotate-until.v2 (append (rest l) (list (first l))))]))
 
(define N 10000)
 
(define (run N rotate-until)
  (local ((define large
            (append
             (build-list N (lambda (i) `(0 ,(+ (random (+ i 1)) 1) 0 0)))
             '((1 2 3 0)))))
    (time (first (rotate-until large)))))
 
(build-list 10 (lambda (i) (run (* i 1000) rotate-until.v1)))
(build-list 10 (lambda (i) (run (* i 1000) rotate-until.v2)))

40 Summary

This sixth part of the book is about the design of functions that employ generative recursion

This fifth part of the book shows

... logical reasoning ...