# brian_hassinger

software developer

## Formulating Abstractions with Higher-Order Procedures

February 19, 2013

Higher-Order Procedures - Procedures that manipulate other procedures

To use higher-order procedures a language must provided functions as first-class elements. Elements are said to be first class if:

• They may be named by variables
• They may be passed as arguments to procedures
• They may be returned as the results of procedures
• They may be included in data structures

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. (pg [pg76]) [pg76]: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-12.html#%_sec_1.3.4

#### Exercise 1.29

Write a procedure which uses Simpson’s Rule to compute the integral of a function `f`.

``````(define (simpson-rule f a b n)
(define h (/ (- b a) n))
(define (y k) (f (+ a (* k h))))
(define (simpson-step k)
(* (cond ((or (= k 0) (= k n)) 1)
((even? k) 2)
(else 4))
(y k)))
(/ (* (sum simpson-step 0 inc n)
(/ h 3))
1.0))
``````

I’ve omitted the setup for this, defining `sum` and `inc` procedures. The important part is to keep track of `k` because it determines the value of yk, and also what factor multiply that value by.

#### Exercise 1.30

Write an iterative process of the `sum` procedure.

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

Use `result` to store the previous computations, return when completed. If not finished increase the current step `a` and add computation to the result total.

#### Exercise 1.31

Write a `product` procedure analogous to the `sum` procedure. Show how to define `factorial` in terms of `product`. Also compute π/4 in terms of `product`.

``````;; Recursive Solution
(define (product term a next b)
(if (> a b)
1
(* (term a)
(product term (next a) next b))))

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

Most everything is the same, except for the `*` procedure. Biggest thing to note is that the null-value here must be a one instead of a zero like in the `sum` procedure.

``````(define (inc n) (+ 1 n))
(define (identity n) n)

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

(factorial 5)
;Value: 120
``````

Factorial: `5! = 1*2*3*4*5`

``````(define (plus2 n) (+ n 2))
(define (pair base)
(* (/ (- base 1) base)
(/ (+ base 1) base)))

(define (slice-of-pi significant)
(product pair 3.0 plus2 (+ (* significant 2) 1)))

(define (pi significant)
(* 4 (slice-of-pi significant)))

(pi 1000)
;Value: 3.142377365093871
``````

The real workhorse is the `pair` procedure.

I decided to go for the whole pie instead of only a quarter of it. Note that this method is only accurate to the 2nd decimal place with a `significant` of 1000. Not a very good way to get some pi.

#### Exercise 1.32

Abstract both `sum` and `product` into a more general `accumulate` procedure.

``````;; Recursive Solution
(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))))

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

Taking note of the only parts that changed when writing the `product` procedure from the `sum`, it’s easy to see an abstracted solution.

``````;; Recursive Sum
(define (sum term a next b)
(accumulate + 0 term a next b))
;; Iterative Product
(define (product-iter term a next b)
(accumulate * 1 term a next b))
``````

And the appropriate `sum` and `product` from using the new `accumulate` procedure.

#### Exercise 1.33

Write a `filtered-accumulate`. Using this, write `sum-squares` on an interval `a` to `b`. And the product of all positive integers less than `n` that are relatively prime to `n`.

``````;; Recursive Solution
(define (filtered-accumulate filter? combiner null-value term a next b)
(cond ((> a b) null-value)
((filter? a) (combiner (term a)
(filtered-accumulate filter? combiner null-value term (next a) next b)))
(else null-value)))

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

An alternative form wasn’t requested, but it was simple to do anyway. The book says this is a more general version of `accumulate`. I guess that’s because you could write a filter which doesn’t actually filter anything. Hmm. Anyway. Simple enough, just accept a new operand `filter?` and pass it the value of each `a` on every iteration. If it passes, accumulate the results, if it fails try the `(next a)`.

``````(define (sum-sq-primes a b)
(filtered-accumulate prime? + 0 square a inc b))

(sum-sq-primes 1 3)
;Value: 38
``````

Give the `filtered-accumulate` a test for primality, and add it all up.

``````;; Product of positive integers less than n that are relatively prime to n
;; uhh... wat?
(define (wat n)
(define (wat? i)
(= 1 (gcd i n)))
(filtered-accumulate-iter wat? * 1 identity 1 inc n))

(wat 10)
;Value: 189
``````

Using the `gcd` for a filter, multiply all integers that pass the test.

#### Exercise 1.34

The procedure `f` will throw an error. In a roundabout way, it will try to apply the argument `2` to the procedure `2`, but `2` is a primitive number and not a procedure. Causing the error.

``````(define (f g)
(g 2))

;; Process shape
(f f)
(f 2)
(2 2)
``````

#### Exercise 1.35

Show that the golden ratio is a fixed point of the transformation ```x -> 1 + 1/x```, and use this fact to compute φ by means of the fixed-point procedure.

``````(fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0)
``````

#### Exercise 1.36

Print out the guess at every iteration.

``````(fixed-point (lambda (x) (/ (log 1000) (log x))) 1.5)
(fixed-point (lambda (x) (average x (/ (log 1000) (log x)))) 1.5)
``````

Results

``````(fixed-point (lambda (x) (/ (log 1000) (log x))) 1.5)
guess: 1.5
guess: 17.036620761802716
guess: 2.436284152826871
guess: 7.7573914048784065
guess: 3.3718636013068974
guess: 5.683217478018266
guess: 3.97564638093712
guess: 5.004940305230897
guess: 4.2893976408423535
guess: 4.743860707684508
guess: 4.437003894526853
guess: 4.6361416205906485
guess: 4.503444951269147
guess: 4.590350549476868
guess: 4.532777517802648
guess: 4.570631779772813
guess: 4.545618222336422
guess: 4.562092653795064
guess: 4.551218723744055
guess: 4.558385805707352
guess: 4.553657479516671
guess: 4.55677495241968
guess: 4.554718702465183
guess: 4.556074615314888
guess: 4.555180352768613
guess: 4.555770074687025
guess: 4.555381152108018
guess: 4.555637634081652
guess: 4.555468486740348
guess: 4.555580035270157
guess: 4.555506470667713
guess: 4.555554984963888
guess: 4.5555229906097905
guess: 4.555544090254035
guess: 4.555530175417048
;Value: 4.555539351985717

(fixed-point (lambda (x) (average x (/ (log 1000) (log x)))) 1.5)
guess: 1.5
guess: 9.268310380901358
guess: 6.185343522487719
guess: 4.988133688461795
guess: 4.643254620420954
guess: 4.571101497091747
guess: 4.5582061760763715
guess: 4.555990975858476
guess: 4.555613236666653
guess: 4.555548906156018
guess: 4.555537952796512
;Value: 4.555536087870658
``````

#### Exercise 1.37

Define a procedure `cont-frac` such that evaluating `(cont-frac n d k)` computes the value of the k-term finite continued fraction. Check your procedure by approximating 1/φ

``````;; Recursive
(define (cont-frac n d k)
(define (recurse i)
(if (= i k)
(/ (n i) (d i))
(/ (n i) (+ (d i) (recurse (+ i 1))))))
(recurse 1))

;; Iterative
(define (cont-frac-iter n d k)
(define (iter r i)
(if (= 0 i)
r
(iter (/ (n i) (+ (d i) r)) (- i 1))))
(iter 0 k))
``````

#### Exercise 1.38

Write a program that uses your `cont-frac` procedure from exercise 1.37 to approximate e, based on Euler’s expansion.

``````(define (e-minus-two k)
(cont-frac (lambda (i) 1.0)
(lambda (i) (if (= 0 (remainder (- i 5) 3))
(* 2 (+ 2 (/ (- i 5) 3)))
1))
k))

``````
``````;; Test
;; e - 2 = .71828
(e-minus-two 10)
;Value: .7182817182817183
``````

#### Exercise 1.39

Define a procedure `(tan-cf x k)` that computes an approximation to the tangent function based on Lambert’s formula.

``````(define (tan-cf x k)
(cont-frac (lambda (i) (if (= 1 i)
x
(- (square x))))
(lambda (i) (- (* 2 i) 1))
k))
``````

The trickiest part of this problem is subtraction of the next nk/dk. Noting that for all values of `k` except when `k = 1` this subtraction is needed, this is solved with a simple condition.

#### Exercise 1.40

Define a procedure `cubic` that can be used together with the `newtons-method` procedure to approximate zeros of the cubic x3 + ax2 + bx + c

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

#### 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

``````(define (double p)
(lambda (x) (p (p x))))
``````

#### Exercise 1.42

Define a procedure `compose` that implements composition. The composition `f` after `g` is defined to be the function `x -> f(g(x))`

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

#### Exercise 1.43

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`.

``````(define (repeated f n)
(if (< n 1)
(lambda (x) x)
(compose f (repeated f (- n 1)))))
``````

#### Exercise 1.44

Write a procedure `smooth` that takes as input a procedure that computes `f` and returns a procedure that computes the smoothed `f`

``````(define dx 0.0001)

(define (smooth f)
(lambda (x) (/ (+ (f (- x dx)) (f x) (f (+ x dx)))
3)))
``````

#### Exercise 1.45

Implement a simple procedure for computing nth roots using `fixed-point`, `average-damp`, and the `repeated` procedure of exercise 1.43.

The first thing I need to know is how many times to repeat `average-damp`. To do this I wrote most of my code for `nth-root`, with a hard-coded value of `2` for repeating `average-damp`. Then I started testing from the `4th` root onward.

``````(define (nth-root n)
(lambda (x) (fixed-point
((repeated average-damp 2) (lambda (y) (/ x (fast-expt y (- n 1)))))
1.0)))

((nth-root 4) 16)
;Value: 2.
((nth-root 5) 32)
;Value: 2.0000000945616985
((nth-root 6) 64)
;Value: 2.0000001833403775
((nth-root 7) 128)
;Value: 2.0000003557852426
((nth-root 8) 256) ;; Hangs here. We need to average-damp again.
``````

The repetition for `average-damp` is log2(n), so `nth-root` becomes:

``````(define (nth-root n)
(let ((r (/ (log n) (log 2))))
(lambda (x) (fixed-point
((repeated average-damp r) (lambda (y) (/ x (fast-expt y (- n 1)))))
1.0))))
``````

#### Exercise 1.46

Write a procedure `iterative-improve` that takes two procedures as arguments: a method for telling whether a guess is good enough and a method for improving a guess.

``````(define (iterative-improve good-enough? improve)
(lambda (guess)
(define (iter guess)
(if (good-enough? guess)
guess
(iter (improve guess))))
(iter guess)))
``````

First I redefined the `sqrt` procedure in terms of `iterative-improve`

``````(define (sqrt x)
(define (good-enough? guess)
(< (abs (- (square guess) x)) 0.001))
(define (improve guess)
(average guess (/ x guess)))
((iterative-improve good-enough? improve) 1.0))
``````

Then I rewrote `fixed-point` and wrote another version of `sqrt` to test it.

``````(define (fixed-point f first-guess)
(define (close-enough? guess)
(< (abs (- guess (f guess))) tolerance))
((iterative-improve close-enough? f) first-guess))

(define (sqrt x)
(fixed-point (lambda (y) (average y (/ x y))) 1.0))
``````