SICP 1.3.4: “Formulating Abstractions with Higher-Order Procedures: Procedures as General Methods”

(Structure and Interpretation of Computer Programs) 1.3.4

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

The final sub-section (1.3.4) of this section on higher-order procedures (1.3) focuses on the usefulness of not only using procedures as arguments but also as the return value of procedures. We are walked through a transformation of the sqrt and newtons-method functions from earlier sections that are implemented, instead, using procedures that return other procedures. One of the main advantages illuminated by this comparison is how explicit the code built up from this style of programming becomes.

This section also spends some time explaining the mathematical equations for finding derivatives and average-dumping on the path to implementing the square-root and Newton’s method procedures. It also contains a useful, concise definition of a term that is still often thrown around when discussing programming languages, “first-class status” in reference to types of elements (pgs 76–77).

Finally, I’d like to point out this gem of a paragraph, which I think beautifully articulates why the focus of this entire chapter on higher-order procedures matters, in practical terms, for the code we write everyday:

As programmers, we should be alert to opportunities to identify the underlying abstractions in our programs and to build upon them and generalize them to create more powerful abstractions. This is not to say that one should always write programs in the most abstract way possible; expert programmers know how to choose the level of abstraction appropriate to their task. But it is important to be able to think in terms of these abstractions, so that we can be ready to apply them in new contexts. The significance of higher-order procedures is that they enable us to represent these abstractions explicitly as elements in our programming language, so that they can be handled just like other computational elements. (pg 76)

1.3.4 Exercises

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

Exercise 1.40

Define a procedure cubic that can be used together with the newtons-method procedure in expressions of the form (newtons-method (cubic a b c) 1). To approximate zeros of the cubic x^3 + ax^2 + bx + c

(define (fixed-point f first-guess)(define (close-enough? v1 v2)(< (abs (- v1 v2))0.0001))(define (try guess)(let ((next (f guess)))(if (close-enough? guess next)next(try next))))(try first-guess))

(define dx 0.00001)

(define (deriv g)(lambda (x)(/ (- (g (+ x dx)) (g x))dx)))

(define (newton-transform g)(lambda (x)(- x (/ (g x)((deriv g) x)))))

(define (newtons-method g guess)(fixed-point (newton-transform g)guess))

(define (cube x)(* x x x))

(define (cubic a b c)(lambda (x)(+ (cube x)(* a (square x))(* b x)c)))

(newtons-method (cubic 2 -5 7) 1)

Exercise 1.41

Define a procedure _double_ that takes a procedure of one argument as argument and returns a procedure that applies the original procedure twice. For example, if _inc_ is a procedure that adds 1 to its argument, then _(double inc)_should be a procedure that adds 2. What value is returned by

(((double (double double)) inc) 5)

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

(define (double f)(lambda (x) (f (f x))))

(((double (double double)) inc) 5) = 21

Exercise 1.42

Let f and g be two one-argument functions. The composition f after g is defined to be the function x ↦ f(g(x)). Define a procedure compose that implements composition. For example, if inc is a procedure that adds 1 to its argument: ((compose square inc) 6)

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

(define (compose f g)(lambda (x) (f (g x))))

((compose square inc) 6) = 49

Exercise 1.43

If f is a numerical function and n is a positive integer, then we can form the nth repeated application of f, which is defined to be the function whose value at x is f(f(…(f(x))…)). For example, if f is the function x↦x+1, then the nth repeated application of f is the function x↦x+n. If f is the operation of squaring a number, then the nth repeated application of f is the function that raises its argument to the 2n-th power. Write a procedure that takes as inputs a procedure that computes f and a positive integer n and returns the procedure that computes the nth repeated application of f. Your procedure should be able to be used as follows: ((repeated square 2) 5)625

(define (compose f g)(lambda (x) (f (g x))))

(define (repeated f n)(if (> n 1)(compose f (repeated f (- n 1)))f))

((repeated square 2) 5) = 625