SICP 1.3.1: “ Formulating Abstractions with Higher-Order Procedures: Procedures as Arguments”

(Structure and Interpretation of Computer Programs) 1.3.1

My 1.3.1 exercise solutions are also on Github here: https://github.com/bolducp/SICP/tree/master/exercises/chapter_01/1.3_exercises

One of the things we should demand from a powerful programming language is the ability to build abstractions by assigning names to common patterns and then to work in terms of the abstractions directly. (pg. 56)

“Often the same programming pattern will be used with a number of different procedures. To express such patterns as concepts, we will need to construct procedures that can accept procedures as arguments or return procedures as values. Procedures that manipulate procedures are called higher-order procedures. This section shows how higher-order procedures can serve as powerful abstraction mechanisms, vastly increasing the expressive power of our language.” (pgs 56- 57)

1.3.1: Procedures as Arguments

This section begins by providing three examples of procedures dealing with summing various collections of data (e.g. integers, cubes, fractional numbers in a specific series) and points out the similar logic in all of the procedures, regardless of the type of item being accumulated. This leads to a discussion of the general notion of summation, aided by an example of a common summation procedure that abstracts the duplicated logic from the three original functions and provides the variable portions as arguments.

The presence of such a common pattern is strong evidence that there is a useful abstraction waiting to be brought to the surface. (pg. 58)

1.1.3 Exercises

My solutions are provided in gray text blocks below each exercise question.

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

h/3[y0+4y1+2y2+4y3+2y4+…+2yn−2+4yn−1+yn]

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.

(define (simpson f a b n)(define h (/ (- b a) n))(define (yk k)(f (+ (* k h) a)))(define (term x)(* (cond ((= x 0) 1)((= x n) 1)((even? x) 2)(else 4))(yk x)))(* (/ h 3)(sum term 0 inc n)))

(simpson cube 0 1 100.0) ; .24999999999999992(integral cube 0 1 0.01) ; .24998750000000042

(simpson cube 0 1 1000.0) ; .2500000000000003(integral cube 0 1 0.001) ; .249999875000001

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 <??> <??>))

(define (sum-recursive term a next b)(if (> a b)0(+ (term a)(sum-recursive term (next a) next b))))

(define (sum term a next b)(define (iter a result)(if (> a b)result(iter (next a)(+ (term a) result))))(iter (term a) 0))

; testing:

(define (inc n) (+ n 1))

(define (identity x) x)

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

(sum-integers 1 10) ; 55

Exercise 1.31

The sum procedure is only the simplest of a vast number of similar abstractions that can be captured as higher-order procedures.Write an analogous procedure called product that returns the product of the values of a function at points over a given range. Try both a recursive and an iterative approach. Show how to define factorial in terms of product. Also use product to compute approximations to using the formula: π/4=(2⋅4⋅4⋅6⋅6⋅8…) / (3⋅3⋅5⋅5⋅7⋅7…)

(define (inc n) (+ n 1))

(define (identity x) x)

; recursive(define (product term a next b)(if (> a b)1(* (term a)(product term (next a) next b))))

; iterative(define (product-iter term a next b)(define (iter a result)(if (> a b)result(iter (next a)(* (term a) result))))(iter (term a) 1))

; factorial

(define (factorial n)(product-iter identity 1 inc n))

; testing(factorial 0)(factorial 1)(factorial 2)(factorial 3)(factorial 6)

; π/4 = (2⋅4⋅4⋅6⋅6⋅8...) / (3⋅3⋅5⋅5⋅7⋅7...)

(define (pi-product n)(define (term x)(if (even? x)(/ (+ x 2) (+ x 1))(/ (+ x 1) (+ x 2))))(product-iter term 1 inc n))

(pi-product 4)

Exercise 1.32

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. Write two procedures, one that generates a recursive process and one iterative.

(define (inc n) (+ n 1))

(define (identity x) x)

(define (accumulate combiner null-value term a next b)(if (> a b)null-value(combiner (term a)(accumulate combiner null-value term (next a) next b))))

(define (accumulate-iter combiner null-value term a next b)(define (iter a result)(if (> a b)result(iter (next a)(combiner (term a) result))))(iter (term a) null-value))

(define (product term a next b)(accumulate * 1 term a next b))

(define (sum term a next b)(accumulate-iter + 0 term a next b))

; testing(sum identity 1 inc 10) ; 55(product identity 1 inc 6) ; 720

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.

(define (filtered-accumulate combiner null-value term a next b filter?)(define (iter a result)(cond ((> a b) result)((filter? a) (iter (next a)(combiner (term a) result)))(else (iter (next a) result))))(iter a null-value))

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)=1GCD.

Part I:

(define (smallest-divisor n)(find-divisor n 2))

(define (find-divisor n test-divisor)(cond ((> (square test-divisor) n) n)((divides? test-divisor n) test-divisor)(else (find-divisor n (+ test-divisor 1)))))

(define (divides? a b)(= (remainder b a) 0))

(define (prime? n)(= n (smallest-divisor n)))

(define (inc n) (+ n 1))(define (square n) (* n n))

(define (sum-prime-squares a b)(filtered-accumulate + 0 square a inc b prime?))

; testing(sum-of-prime-squares 1 4) ;14(sum-of-prime-squares 3 50) ;10462

Part II:

(define (identity x) x)

(define (gcd a b)(if (= b 0)a(gcd b (remainder a b))))

(define (relative-prime? x y)(= (gcd x y) 1))

(define (product-relatively-primes n)(define (filter-relative-prime x)(relative-prime? x n))(filtered-accumulate * 1 identity 1 inc n filter-relative-prime))

; testing(product-relatively-primes 20) ; 8729721