Printer-friendly versionPrinter-friendly version

Consider the following three procedures. The first computes the sum of the integers from a through b:

(define (sum-integers a b)
  (if (> a b)
      (+ a (sum-integers (+ a 1) b))))

The second computes the sum of the cubes of the integers in the given range:

(define (sum-cubes a b)
  (if (> a b)
      (+ (cube a) (sum-cubes (+ a 1) b))))

The third computes the sum of a sequence of terms in the series

1/(1*3) + 1/(5*7) + 1/(9*11) + . . .

which converges to π/8 (very slowly):[49]

(define (pi-sum a b)
  (if (> a b)
      (+ (/ 1.0 (* a (+ a 2))) (pi-sum (+ a 4) b))))

These three procedures clearly share a common underlying pattern. They are for the most part identical, differing only in the name of the procedure, the function of a used to compute the term to be added, and the function that provides the next value of a. We could generate each of the procedures by filling in slots in the same template:

(define ( a b)
  (if (> a b)
      (+ ( a)
         ( ( a) b))))

The presence of such a common pattern is strong evidence that there is a useful abstraction waiting to be brought to the surface. Indeed, mathematicians long ago identified the abstraction of summation of a series and invented “sigma notation,” for example

to express this concept. The power of sigma notation is that it allows mathematicians to deal with the concept of summation itself rather than only with particular sums — for example, to formulate general results about sums that are independent of the particular series being summed.

Similarly, as program designers, we would like our language to be powerful enough so that we can write a procedure that expresses the concept of summation itself rather than only procedures that compute particular sums. We can do so readily in our procedural language by taking the common template shown above and transforming the “slots” into formal parameters:

(define (sum term a next b)
  (if (> a b)
      (+ (term a)
         (sum term (next a) next b))))

Notice that sum takes as its arguments the lower and upper bounds a and b together with the procedures term and next. We can use sum just as we would any procedure. For example, we can use it (along with a procedure inc that increments its argument by 1) to define sum-cubes:

(define (inc n) (+ n 1))
(define (sum-cubes a b)
  (sum cube a inc b))

Using this, we can compute the sum of the cubes of the integers from 1 to 10:

(sum-cubes 1 10)

With the aid of an identity procedure to compute the term, we can define sum-integers in terms of sum:

(define (identity x) x)

(define (sum-integers a b)
  (sum identity a inc b))

Then we can add up the integers from 1 to 10:

(sum-integers 1 10)

We can also define pi-sum in the same way:[50]

(define (pi-sum a b)
  (define (pi-term x)
    (/ 1.0 (* x (+ x 2))))
  (define (pi-next x)
    (+ x 4))
  (sum pi-term a pi-next b))

Using these procedures, we can compute an approximation to π:

(* 8 (pi-sum 1 1000))

Once we have sum, we can use it as a building block in formulating further concepts. For instance, the definite integral of a function f between the limits a and b can be approximated numerically using the formula

The integral from a to b of f = ( f (a + dx/2) + f(a + dx + dx/2) + . . .)

for small values of dx. We can express this directly as a procedure:

(define (integral f a b dx)
  (define (add-dx x) (+ x dx))
  (* (sum f (+ a (/ dx 2.0)) add-dx b)
(integral cube 0 1 0.01)
(integral cube 0 1 0.001)

(The exact value of the integral of cube between 0 and 1 is 1/4.)

[49] This series, usually written in the equivalent form (π/4) = 1 - 1/3 + 1/5 - 1/7) + …, is due to Leibniz. We’ll see how to use this as the basis for some fancy numerical tricks in section 3.5.3. [back]
[50] Notice that we have used block structure (section 1.1.8) to embed the definitions of pi-next and pi-term within pi-sum, since these procedures are unlikely to be useful for any other purpose. We will see how to get rid of them altogether in section 1.3.2. [back]


Exercise 1.29

Simpson’s Rule is a more accurate method of numerical integration than the method illustrated above. Using Simpson’s Rule, the integral of a function f between a and b is approximated as

where h = (b - a)/n, for some even integer n, and yk = f(a + kh). (Increasing n increases the accuracy of the approximation.) Define a procedure that takes as arguments f, a, b, and n and returns the value of the integral, computed using Simpson’s Rule. Use your procedure to integrate cube between 0 and 1 (with n = 100 and n = 1000), and compare the results to those of the integral procedure shown above.

Exercise 1.30

The sum procedure above generates a linear recursion. The procedure can be rewritten so that the sum is performed iteratively. Show how to do this by filling in the missing expressions in the following definition:

(define (sum term a next b)
  (define (iter a result)
    (if <??>
        (iter <??> <??>)))
  (iter <??> <??>))

Exercise 1.31

  1. The sum procedure is only the simplest of a vast number of similar abstractions that can be captured as higher-order procedures.[51] Write an analogous procedure called product that returns the product of the values of a function at points over a given range. Show how to define factorial in terms of product. Also use product to compute approximations to π using the formula [52]

  2. If your product procedure generates a recursive process, write one that generates an iterative process. If it generates an iterative process, write one that generates a recursive process.
[51] The intent of exercises 1.31 - 1.33 is to demonstrate the expressive power that is attained by using an appropriate abstraction to consolidate many seemingly disparate operations. However, though accumulation and filtering are elegant ideas, our hands are somewhat tied in using them at this point since we do not yet have data structures to provide suitable means of combination for these abstractions. We will return to these ideas in section 2.2.3 when we show how to use sequences as interfaces for combining filters and accumulators to build even more powerful abstractions. We will see there how these methods really come into their own as a powerful and elegant approach to designing programs. [back]
[52] This formula was discovered by the seventeenth-century English mathematician John Wallis. [back]

Exercse 1.32

  1. Show that sum and product (exercise 1.31) are both special cases of a still more general notion called accumulate that combines a collection of terms, using some general accumulation function:

    (accumulate combiner null-value term a next b)

    Accumulate takes as arguments the same term and range specifications as sum and product, together with a combiner procedure (of two arguments) that specifies how the current term is to be combined with the accumulation of the preceding terms and a null-value that specifies what base value to use when the terms run out. Write accumulate and show how sum and product can both be defined as simple calls to accumulate.

  2. If your accumulate procedure generates a recursive process, write one that generates an iterative process. If it generates an iterative process, write one that generates a recursive process.

Exercise 1.33

You can obtain an even more general version of accumulate (exercise 1.32) by introducing the notion of a filter on the terms to be combined. That is, combine only those terms derived from values in the range that satisfy a specified condition. The resulting filtered-accumulate abstraction takes the same arguments as accumulate, together with an additional predicate of one argument that specifies the filter. Write filtered-accumulate as a procedure. Show how to express the following using filtered-accumulate:

  1. the sum of the squares of the prime numbers in the interval a to b (assuming that you have a prime? predicate already written)

  2. the product of all the positive integers less than n that are relatively prime to n (i.e., all positive integers i < n such that GCD(i, n) = 1).


In the meantime, Buvette Chef de Cuisine Caite Whitbeck’s prescript can be pedestal here. , with additional offices amid

Louis Vuitton Outlet
Louis Vuitton Outlet

UGG Outlet
UGG Outlet

Louis Vuitton Outlet………
Louis Vuitton Outlet

UGG Outlet
UGG Outlet

UGG Outlet………
UGG Outlet

Louis Vuitton Outlet…………………………….…………………………………
Louis Vuitton Outlet

UGG Sale……
UGG Sale

Louis Vuitton Outlet
Louis Vuitton Outlet

UGG Outlet
UGG Outlet

Nike air max 2012………………………………………………………………………………………….….….….….….….….….….…………………
Nike air max 2012

Dior {is|namely one of the highest coveted designer brands existing today. (Dale Moody, THE WORD OF TRUTH; Grand Rapids: Eerdmans, 1981; 167-8)Modern approaches to angels have included many who would favor apt eliminate angels from consideration because of the excesses favor that of Pseudo-Dionysius. Here?s a tip: Try to purchase a border that has a more classic profile rather than a bulky and noisy border Many peope favor Convese A Sta shoes becase of thei vesatiity. They made a film out of it,only it didn’t catch the feel alternatively creepiness. For many, choosing a home life namely a favorable and fulfilling experience they would never business

UGGS On Sale…………
UGGS On Sale

Nike Air Max 2012……………………………………………………………………………………………………………………………………
Nike Air Max 2012

Cheap ugg outlet………………………………
Cheap ugg outlet

Louis Vuitton Outlet…………
Louis Vuitton Outlet

Post new comment

  • Web page addresses and e-mail addresses turn into links automatically.
  • Allowed HTML tags: <a> <em> <strong> <cite> <code> <pre> <hr> <ul> <ol> <li> <dl> <dt> <dd> <img>
  • Lines and paragraphs break automatically.
  • Adds typographic refinements.

More information about formatting options