SICP Exercise 1.34: Procedures as Arguments

From SICP section 1.3.2 Constructing Procedures Using Lambda

Exercise 1.34 asks us to consider the following procedure:

(define (f g)
  (g 2))

This procedure takes a function as an argument and applies that function to the value 2. We're shown a couple of examples of the procedure in action.

> (f square)
4
> (f (lambda (z) (* z (+ z 1))))
6

We're then asked to consider what would happen if we applied f to itself.

> (f f)
. . procedure application: expected procedure, given: 2; arguments were: 2

We can use the substitution model to explain this failure.

(f f)
(f 2)
(2 2)

In the first substitution the argument f (a procedure) is applied to the value 2, so a recursive call is made. In the second substitution, the argument 2 is applied to 2. Since 2 isn't a procedure, an error is reported.


Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

SICP Exercise 1.33: Filtered Accumulator

From SICP section 1.3.1 Procedures as Arguments

Exercise 1.33 asks us to us to write an even more general form of the accumulate procedure that we wrote in 1.32. A filtered accumulate procedure should combine only those terms in a specified range that meet a specified condition. The new procedure will take the same arguments as the old one, plus an additional argument that specifies the filtering function.

Once we've written the new procedure we need to test it by using it to write two additional procedures. The first will find the sum of the squares of the prime numbers in a given range, and the second will find the product of all the positive integers less than n that are relatively prime to n.

The filtered-accumulate procedure should be very similar to what we saw in the last exercise. The only difference is that we check each new value to see if it passes through the filter before applying the combiner function.

(define (filtered-accum filter combiner null-value term a next b)
  (if (> a b)
      null-value
      (if (filter a)
          (combiner (term a)
                    (filtered-accum filter combiner null-value term (next a) next b))
          (filtered-accum filter combiner null-value term (next a) next b))))

Note that we're filtering on the value of a, not the value of (term a).

Sum of squared primes

We came up with several different ways to test if a number is prime in section 1.2.6. You can choose any implementation you like, but I'm going to use the fast-prime? procedure from exercises 1.22 and 1.23 (shown here in block structure).

(define (fast-prime? n)
   (define (smallest-divisor n)
      (define (find-divisor n test-divisor)
         (define (next x)
            (if (= x 2) 3 (+ x 2)))
         (define (divides? a b)
            (= (remainder b a) 0))
         (cond ((> (square test-divisor) n) n)
               ((divides? test-divisor n) test-divisor)
               (else (find-divisor n (next test-divisor)))))
      (find-divisor n 2))
   (= n (smallest-divisor n)))

Using fast-prime? as a filtering function, we can implement a procedure to sum the square of primes in a given range.

(define (sum-squared-primes a b)
   (filtered-accum fast-prime? + 0 square a inc b))

(define (inc x) (+ x 1))

(define (square x)
   (* x x))

We can use a few small examples to test with.

2² + 3² = 13
2² + 3² + 5² = 38
2² + 3² + 5² + 7² = 87

> (sum-squared-primes 2 3)
13
> (sum-squared-primes 2 6)
38
> (sum-squared-primes 2 10)
87

Procuct of coprimes

The second challenge was to find the product of all the positive integers less than n that are relatively prime (coprime) to n. In other words, multiply together all positive integers i < n such that

gcd(i, n) = 1

As luck would have it, we've already seen a gcd procedure too. SICP section 1.2.5 was all about finding greatest common divisors using Euclid's algorithm.

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

We can use gcd to define a coprime? procedure, and use that as our filter. Note that normally a coprime? procedure should take two parameters. Since filtered-accum expects the filter function to take only one parameter, coprime? is borrowing one of its input parameters, n, from product-of-coprimes.

(define (product-of-coprimes n)
  (define (coprime? i)
     (= 1 (gcd i n)))
  (filtered-accum coprime? * 1 identity 1 inc (- n 1)))

(define (identity x) x)

Again, I'm only going to test with a few small samples, since the results can potentially get very big, very fast. A quick mental check reveals that 3, 7, and 9 are the only values less than 10 that are also coprime to 10.

> (product-of-coprimes 10)
189

All values less than a prime number are coprime to that number, so the product of coprimes to 11 should result in the product of all the values from 2 to 10, or 10!.

> (product-of-coprimes 11)
3628800

You can check that and any other inputs with a calculator.


Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

SICP Exercise 1.32: Accumulator

From SICP section 1.3.1 Procedures as Arguments

Exercise 1.32 asks us to show how sum and product are special cases of an even more abstract concept called accumulate that combines a collection of terms. We're given the following procedure signature to start with:

(accumulate combiner null-value term a next b)

The arguments term, a, next, and b serve the same purpose as they did in sum and product. The new arguments are combiner, which takes a procedure of two arguments that specifies how the current term should be combined with the accumulation of all the preceding terms, and null-value, which specifies what base value to use when the terms run out.

We need to test accumulate by implementing both sum and product in terms of the new procedure. We also need to implement both recursive and iterative versions of accumulate.

We saw in exercise 1.31 how similar sum and product are. To create a higher-order procedure that can be used to implement both of these ideas, we need to look at where they're different. Let's look at the recursive version first.

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

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

At a casual glance these two functions look almost exactly the same. They're only different in name, the null value used when a > b, and the operator used to combine terms.

(define (<name> term a next b)
(if (> a b)
<null-value>
(<operator> (term a)
(<name> term (next a) next b))))

These are exactly the parameters that need to change to create a higher-order accumulate procedure.

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

Given their similarities, redefining sum and product in terms of accumulate is easy.

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

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

An iterative version can be created using the same technique of substituting what's different about the iterative versions of sum and product from previous exercises.

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

Any of these procedures can be tested using the same tests from the previous exercises and comparing the results.


Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

SICP Exercise 1.31: Product of a Series

From SICP section 1.3.1 Procedures as Arguments

Exercise 1.31 asks us to write a product procedure (analogous to sum) that computes the product of a function at points over a given range. We need to show how to define factorial in terms of the new product procedure, and use product to compute approximations to π using the following formula:


Finally, if our product procedure is recursive, we need to write an iterative version, and vice versa.

Since summing a series and multiplying a series are extremely similar ideas, it's not surprising to find that it's very simple to modify sum to produce product. Let's use the recursive version from exercise 1.29 first.

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

The product procedure really only needs to perform a different operation and end on a different value than sum. The last step (when a > b) should be to multiply by 1 instead of adding 0.

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

We can test this out by implementing factorial in terms of product using the identity and inc procedures that we've used before.

(define (identity x) x)

(define (inc x) (+ x 1))

(define (factorial x)
   (product identity 1 inc x))

> (factorial 3)
6
> (factorial 4)
24
> (factorial 5)
120
> (factorial 10)
3628800
> (factorial 20)
2432902008176640000

The next test is to approximate π using something called Wallis' product or the Wallis Formula. (Lucky for us that mathematicians have already expressed this as the product of a series, saving us the work of coming up with a function for generating the terms.)


We'll multiply the product on the right hand side by the denominator on the left hand side so our procedure will just approximate π directly.

(define (wallis-pi n)
   (define (term x)
      (/ (* 4.0 (square x))
         (- (* 4.0 (square x)) 1)))
   (* 2.0 (product term 1 inc n)))

> (wallis-pi 10)
3.0677038066434994
> (wallis-pi 100)
3.133787490628163
> (wallis-pi 1000)
3.1408077460304042
> (wallis-pi 10000)
3.1415141186819313

Since our product procedure is implemented recursively, we need to show an iterative version. We can go back to the iterative sum procedure for inspiration.

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

Again, there are very few changes required to transform this procedure.

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

You can plug product-iter into the factorial and wallis-pi procedures above to verify that they give the same results.

The similarities between our two versions of sum and product is no accident. This section of SICP is all about higher-order procedures, so in the next exercise we're going to see how pull the similarities out of these procedures into something even more abstract.


Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.