Structure and Interpretation of Computer Programs

Accumulations can be implemented by 

(define (accumulate op initial sequence)

  (if (null? sequence)

      initial

      (op (car sequence)

          (accumulate op initial (cdr sequence)))))

(accumulate + 0 (list 1 2 3 4 5))

15

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

120

(accumulate cons nil (list 1 2 3 4 5))

(1 2 3 4 5)

All that remains to implement signal-flow diagrams is to enumerate the sequence of elements to be

processed. For 

even-fibs

, we need to generate the sequence of integers in a given range, which we

can do as follows: 

(define (enumerate-interval low high)

  (if (> low high)

      nil

      (cons low (enumerate-interval (+ low 1) high))))

(enumerate-interval 2 7)

(2 3 4 5 6 7)

To enumerate the leaves of a tree, we can use

14

 

(define (enumerate-tree tree)

  (cond ((null? tree) nil)

        ((not (pair? tree)) (list tree))

        (else (append (enumerate-tree (car tree))

                      (enumerate-tree (cdr tree))))))

(enumerate-tree (list 1 (list 2 (list 3 4)) 5))

(1 2 3 4 5)

Now we can reformulate 

sum-odd-squares

 and 

even-fibs

 as in the signal-flow diagrams. For 

sum-odd-squares

, we enumerate the sequence of leaves of the tree, filter this to keep only the odd

numbers in the sequence, square each element, and sum the results: 

(define (sum-odd-squares tree)

  (accumulate +

              0

              (map square

                   (filter odd?

                           (enumerate-tree tree)))))

For 

even-fibs

, we enumerate the integers from 0 to n, generate the Fibonacci number for each of

these integers, filter the resulting sequence to keep only the even elements, and accumulate the results

into a list: 

---

(define (even-fibs n)

  (accumulate cons

              nil

              (filter even?

                      (map fib

                           (enumerate-interval 0 n)))))

The value of expressing programs as sequence operations is that this helps us make program designs

that are modular, that is, designs that are constructed by combining relatively independent pieces. We

can encourage modular design by providing a library of standard components together with a

conventional interface for connecting the components in flexible ways.

Modular construction is a powerful strategy for controlling complexity in engineering design. In real

signal-processing applications, for example, designers regularly build systems by cascading elements

selected from standardized families of filters and transducers. Similarly, sequence operations provide a

library of standard program elements that we can mix and match. For instance, we can reuse pieces

from the 

sum-odd-squares

 and 

even-fibs

 procedures in a program that constructs a list of the

squares of the first n + 1 Fibonacci numbers: 

(define (list-fib-squares n)

  (accumulate cons

              nil

              (map square

                   (map fib

                        (enumerate-interval 0 n)))))

(list-fib-squares 10)

(0 1 1 4 9 25 64 169 441 1156 3025)

We can rearrange the pieces and use them in computing the product of the odd integers in a sequence: 

(define (product-of-squares-of-odd-elements sequence)

  (accumulate *

              1

              (map square

                   (filter odd? sequence))))

(product-of-squares-of-odd-elements (list 1 2 3 4 5))

225

We can also formulate conventional data-processing applications in terms of sequence operations.

Suppose we have a sequence of personnel records and we want to find the salary of the highest-paid

programmer. Assume that we have a selector 

salary

 that returns the salary of a record, and a

predicate 

programmer?

 that tests if a record is for a programmer. Then we can write 

(define (salary-of-highest-paid-programmer records)

  (accumulate max

              0

              (map salary

                   (filter programmer? records))))

---

These examples give just a hint of the vast range of operations that can be expressed as sequence 

operations.

15

Sequences, implemented here as lists, serve as a conventional interface that permits us to combine

processing modules. Additionally, when we uniformly represent structures as sequences, we have

localized the data-structure dependencies in our programs to a small number of sequence operations.

By changing these, we can experiment with alternative representations of sequences, while leaving the

overall design of our programs intact. We will exploit this capability in section 3.5, when we

generalize the sequence-processing paradigm to admit infinite sequences.

Exercise 2.33.  Fill in the missing expressions to complete the following definitions of some basic

list-manipulation operations as accumulations: 

(define (map p sequence)

  (accumulate (lambda (x y) <??>) nil sequence))

(define (append seq1 seq2)

  (accumulate cons <??> <??>))

(define (length sequence)

  (accumulate <??> 0 sequence))

Exercise 2.34.  Evaluating a polynomial in x at a given value of x can be formulated as an

accumulation. We evaluate the polynomial 

using a well-known algorithm called Horner’s rule, which structures the computation as 

In other words, we start with a

n

, multiply by x, add a

n-1

, multiply by x, and so on, until we reach 

a

0

.

16

 Fill in the following template to produce a procedure that evaluates a polynomial using

Horner’s rule. Assume that the coefficients of the polynomial are arranged in a sequence, from a

0

through a

n

. 

(define (horner-eval x coefficient-sequence)

  (accumulate (lambda (this-coeff higher-terms) <??>)

              0

              coefficient-sequence))

For example, to compute 1 + 3x + 5x

3

 + x

5

 at x = 2 you would evaluate 

(horner-eval 2 (list 1 3 0 5 0 1))

Exercise 2.35.  Redefine 

count-leaves

 from section 2.2.2 as an accumulation: 

(define (count-leaves t)

  (accumulate <??> <??> (map <??> <??>)))

Exercise 2.36.  The procedure 

accumulate-n

 is similar to 

accumulate

 except that it takes as its

third argument a sequence of sequences, which are all assumed to have the same number of elements.

It applies the designated accumulation procedure to combine all the first elements of the sequences, all

the second elements of the sequences, and so on, and returns a sequence of the results. For instance, if 

---