SICP Section 2.1 Introduction to Data Abstraction

Exercise 2.1. Define a better version of make-rat that handles both positive and negative arguments. Make-rat should normalize the sign so that if the rational number is positive, both the numerator and denominator are positive, and if the rational number is negative, only the numerator is negative.

Answer:
(define (make-rat n d) (let ((g (gcd n d)) (ratio (/ n d))) (if (> ratio 0.0) (cons (/ n g) (/ d g)) (cons (- (abs (/ n g))) (abs (/ d g))))))
Exercise 2.2. Consider the problem of representing line segments in a plane. Each segment is represented as a pair of points: a starting point and an ending point. Define a constructor make-segment and selectors start-segment and end-segment that define the representation of segments in terms of points. Furthermore, a point can be represented as a pair of numbers: the x coordinate and the y coordinate. Accordingly, specify a constructor make-point and selectors x-point and y-point that define this representation. Finally, using your selectors and constructors, define a procedure midpoint-segment that takes a line segment as argument and returns its midpoint (the point whose coordinates are the average of the coordinates of the endpoints). To try your procedures, you'll need a way to print points:
(define (print-point p) (newline) (display "(") (display (x-point p)) (display ",") (display (y-point p)) (display ")"))
Answer:
;; Point (define (make-point x y) (cons x y)) (define (x-point p) (car p)) (define (y-point p) (cdr p)) ;; Line segment (define (make-segment start end) (cons start end)) (define (start-segment seg) (car seg)) (define (end-segment seg) (cdr seg)) (define (print-point p) (display "(") (display (x-point p)) (display ",") (display (y-point p)) (display ")")) (define (midpoint-segment seg) (let ((start (start-segment seg)) (end (end-segment seg))) (let ((x1 (x-point start)) (y1 (y-point start)) (x2 (x-point end)) (y2 (y-point end))) (make-point (average x1 x2) (average y1 y2))))) ;; (define seg (make-segment (make-point 0 1) (make-point 2 1))) ;; (print-point (midpoint-segment seg)) ;; (1,1)
Exercise 2.3. Implement a representation for rectangles in a plane. (Hint: You may want to make use of exercise 2.2.) In terms of your constructors and selectors, create procedures that compute the perimeter and the area of a given rectangle. Now implement a different representation for rectangles. Can you design your system with suitable abstraction barriers, so that the same perimeter and area procedures will work using either representation?

Answer:
(define (make-rect p1 p2 p3 p4) (cons (cons p1 p2) (cons p3 p4))) (define (length-seg seg) (let ((start (start-segment seg)) (end (end-segment seg))) (let ((x1 (x-point start)) (y1 (y-point start)) (x2 (x-point end)) (y2 (y-point end))) (sqrt (+ (square (- x2 x1)) (square (- y2 y1))))))) (define (rect-length r) (let ((p1 (car (car r))) (p2 (cdr (car r)))) (let ((side (make-segment p1 p2))) (length-seg side)))) (define (rect-breadth r) (let ((p1 (car (car r))) (p4 (cdr (cdr r)))) (let ((side (make-segment p1 p4))) (length-seg side)))) (define (perimeter r) (* 2 (+ (rect-length r) (rect-breadth r)))) (define (area r) (* (rect-length r) (rect-breadth r))) ;; (define r (make-rect ;; (make-point 0 0) ;; (make-point 0 1) ;; (make-point 2 1) ;; (make-point 2 0))) ;; (perimeter r) ;; 6 ;; (area r) ;; 2
Exercise 2.4. Here is an alternative procedural representation of pairs. For this representation, verify that (car (cons x y)) yields x for any objects x and y.
(define (cons x y) (lambda (m) (m x y))) (define (car z) (z (lambda (p q) p)))
What is the corresponding definition of cdr? (Hint: To verify that this works, make use of the substitution model of section 1.1.5.)

Answer:
(define (cons1 x y) (lambda (m) (m x y))) (define (car1 z) (z (lambda (p q) p))) ;; cdr (define (cdr1 z) (z (lambda (p q) q))) ;; (car1 (cons1 2 1)) ;; 2 ;; (cdr1 (cons1 2 1)) ;; 1
Exercise 2.5. Show that we can represent pairs of nonnegative integers using only numbers and arithmetic operations if we represent the pair a and b as the integer that is the product 2a 3b. Give the corresponding definitions of the procedures cons, car, and cdr.

Answer:
(define (count-powers-of-n number n) (define (iter count number) (if (and (= (remainder number n) 0) (>= number n)) (iter (+ 1 count) (/ number n)) count)) (iter 0 number)) (define (count-powers-of-2 number) (count-powers-of-n number 2)) (define (count-powers-of-3 number) (count-powers-of-n number 3)) (define (n-cons a b) (* (expt 2 a) (expt 3 b))) (define (n-car z) (count-powers-of-2 z)) (define (n-cdr z) (count-powers-of-3 z)) ;; (n-car (n-cons 10 11)) ;; 10 ;; (n-cdr (n-cons 10 11)) ;; 11
Exercise 2.6. In case representing pairs as procedures wasn't mind-boggling enough, consider that, in a language that can manipulate procedures, we can get by without numbers (at least insofar as nonnegative integers are concerned) by implementing 0 and the operation of adding 1 as
(define zero (lambda (f) (lambda (x) x))) (define (add-1 n) (lambda (f) (lambda (x) (f ((n f) x)))))
This representation is known as Church numerals, after its inventor, Alonzo Church, the logician who invented the calculus.

Define one and two directly (not in terms of zero and add-1). (Hint: Use substitution to evaluate (add-1 zero)). Give a direct definition of the addition procedure + (not in terms of repeated application of add-1).

Answer:
(define zero (lambda (f) (lambda (x) x))) (define (add-1 n) (lambda (f) (lambda (x) (f ((n f) x))))) ;; one (define one (lambda (f) (lambda (x) (f x)))) ;; two (define two (lambda (f) (lambda (x) (f (f x))))) ;; + (define (church+ m n) (lambda (f) (lambda (x) ((m f) ((n f) x)))))
Exercise 2.7. Alyssa's program is incomplete because she has not specified the implementation of the interval abstraction. Here is a definition of the interval constructor:
(define (make-interval a b) (cons a b))
Define selectors upper-bound and lower-bound to complete the implementation.

Answer:
;; selectors (define (lower-bound interval) (car interval)) (define (upper-bound interval) (cdr interval))
Exercise 2.8. Using reasoning analogous to Alyssa's, describe how the difference of two intervals may be computed. Define a corresponding subtraction procedure, called sub-interval.

Answer:
(define (sub-interval x y) (make-interval (- (lower-bound x) (upper-bound y)) (- (upper-bound x) (lower-bound y))))
Exercise 2.10. Ben Bitdiddle, an expert systems programmer, looks over Alyssa's shoulder and comments that it is not clear what it means to divide by an interval that spans zero. Modify Alyssa's code to check for this condition and to signal an error if it occurs.


(define (spans-zero? interval) (and (< (lower-bound interval) 0) (> (upper-bound interval) 0))) (define (div-interval x y) (if (spans-zero? y) (error "Denominator interval spans zero" y) (mul-interval x (make-interval (/ 1.0 (upper-bound y)) (/ 1.0 (lower-bound y))))))
Exercise 2.11. In passing, Ben also cryptically comments: ``By testing the signs of the endpoints of the intervals, it is possible to break mul-interval into nine cases, only one of which requires more than two multiplications.'' Rewrite this procedure using Ben's suggestion.

After debugging her program, Alyssa shows it to a potential user, who complains that her program solves the wrong problem. He wants a program that can deal with numbers represented as a center value and an additive tolerance; for example, he wants to work with intervals such as 3.5± 0.15 rather than [3.35, 3.65]. Alyssa returns to her desk and fixes this problem by supplying an alternate constructor and alternate selectors:
(define (make-center-width c w) (make-interval (- c w) (+ c w))) (define (center i) (/ (+ (lower-bound i) (upper-bound i)) 2)) (define (width i) (/ (- (upper-bound i) (lower-bound i)) 2))
Unfortunately, most of Alyssa's users are engineers. Real engineering situations usually involve measurements with only a small uncertainty, measured as the ratio of the width of the interval to the midpoint of the interval. Engineers usually specify percentage tolerances on the parameters of devices, as in the resistor specifications given earlier.

Answer:
(define (above-zero? interval) (and (> (lower-bound interval) 0) (> (upper-bound interval) 0))) (define (below-zero? interval) (and (< (lower-bound interval) 0) (< (upper-bound interval) 0))) (define (mul-interval x y) (let ((l1l2 (* (lower-bound x) (lower-bound y))) (l1u2 (* (lower-bound x) (upper-bound y))) (u1l2 (* (upper-bound x) (lower-bound y))) (u1u2 (* (upper-bound x) (upper-bound y)))) (cond ((and (above-zero? x) (above-zero? y)) (make-interval l1l2 u1u2)) ((and (above-zero? x) (spans-zero? y)) (make-interval u1l2 u1u2)) ((and (spans-zero? x) (above-zero? y)) (make-interval l1u2 u1u2)) ((and (above-zero? x) (below-zero? y)) (make-interval u1u2 l1l2)) ((and (below-zero? x) (above-zero? y)) (make-interval u1u2 l1l2)) ((and (below-zero? x) (spans-zero? y)) (make-interval l1u2 l1l2)) ((and (spans-zero? x) (below-zero? y)) (make-interval u1l2 l1l2)) ((and (below-zero? x) (below-zero? y)) (make-interval u1u2 l1l2)) ((and (spans-zero? x) (spans-zero? y)) (make-interval (min l1u2 u1l2) (min l1l2 u1u2))))))
Exercise 2.12. Define a constructor make-center-percent that takes a center and a percentage tolerance and produces the desired interval. You must also define a selector percent that produces the percentage tolerance for a given interval. The center selector is the same as the one shown above.

Answer:
(define (center i) (/ (+ (lower-bound i) (upper-bound i)) 2)) (define (make-center-percent c p) (let ((p-value (/ (* c p) 100))) (make-interval (- c p-value) (+ c p-value))))
Exercise 2.13. Show that under the assumption of small percentage tolerances there is a simple formula for the approximate percentage tolerance of the product of two intervals in terms of the tolerances of the factors. You may simplify the problem by assuming that all numbers are positive.

After considerable work, Alyssa P. Hacker delivers her finished system. Several years later, after she has forgotten all about it, she gets a frenzied call from an irate user, Lem E. Tweakit. It seems that Lem has noticed that the formula for parallel resistors can be written in two algebraically equivalent ways:

and

He has written the following two programs, each of which computes the parallel-resistors formula differently:
(define (par1 r1 r2) (div-interval (mul-interval r1 r2) (add-interval r1 r2))) (define (par2 r1 r2) (let ((one (make-interval 1 1))) (div-interval one (add-interval (div-interval one r1) (div-interval one r2)))))
Lem complains that Alyssa's program gives different answers for the two ways of computing. This is a serious complaint.

Answer: Let x and y be two intervals and dx and dy their respective tolerances. Their product can be calculated as (x + dx) * (y + dy). Expanding this we get xy + xdy + ydx + dxdy. As dx and dy are small to begin with their product will be very small and can be ignored without losing much accuracy. The equation then becomes xy + xdy + ydx.

If we call the product z, with a tolerance dz, then z + dz = xy + xdy + ydx. Separating z and dz, we get dz = xdy + ydx. This is the relation between the tolerance of the product the individual tolerances.

Exercise 2.14. Demonstrate that Lem is right. Investigate the behavior of the system on a variety of arithmetic expressions. Make some intervals A and B, and use them in computing the expressions A/A and A/B. You will get the most insight by using intervals whose width is a small percentage of the center value. Examine the results of the computation in center-percent form (see exercise 2.12).

Answer: Lem's hypothesis is easily proven right. Take the example below.
(define (par1 r1 r2) (div-interval (mul-interval r1 r2) (add-interval r1 r2))) (define (par2 r1 r2) (let ((one (make-interval 1 1))) (div-interval one (add-interval (div-interval one r1) (div-interval one r2))))) (define x (make-center-percent 3 0.1)) (define y (make-center-percent 7 0.1)) (par1 x y) ;; (2.0937083916083914 . 2.1063084084084083) (par2 x y) ;; (2.0979 . 2.1021)
The problem stems from the fact that the formulae do not take intervals into consideration whereas the code does. For instance the interval one implicitly assumes that R1/R1 = R2/R2 = 1. However this is only true when intervals are not involved. Hence the two formulae give two different results.

Exercise 2.15. Eva Lu Ator, another user, has also noticed the different intervals computed by different but algebraically equivalent expressions. She says that a formula to compute with intervals using Alyssa's system will produce tighter error bounds if it can be written in such a form that no variable that represents an uncertain number is repeated. Thus, she says, par2 is a ``better'' program for parallel resistances than par1. Is she right? Why?

Answer: Eva is correct. As we are operating with intervals rather than whole numbers it is better to reduce the "occurrence" of intervals in any given formula to a minimum. This reduces the number of ways in which errors can creep in and thereby produces tighter bounds. As the second formula has fewer occurrences of the intervals it will produce tighter bounds.

Exercise 2.16. Explain, in general, why equivalent algebraic expressions may lead to different answers. Can you devise an interval-arithmetic package that does not have this shortcoming, or is this task impossible? (Warning: This problem is very difficult.)

Answer: The answer is similar those of the two previous questions. The main reason is the difference between using whole numbers and intervals. Normal properties and rules of algebra that apply to whole numbers do not hold true when intervals are used. For instance, while x/x = 1 when x and y are non zero whole numbers this is not so for cases when x is an interval. Likewise x - x need not be zero and so on.

It *might* be possible to develop a package provided such concepts as inverse can be defined for an interval. I am not sure how to go about the definitions though.

SICP Section 1.3 Formulating Abstractions with Higher-Order Procedures

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.

Answer:
(define (sum term a next b) (if (> a b) 0 (+ (term a) (sum term (next a) next b)))) (define (integral f a b dx) (define (add-dx x) (+ x dx)) (* (sum f (+ a (/ dx 2.0)) add-dx b) dx)) ;; solution (define (s-integral f a b n) (define h (/ (- b a) n)) (define (factor x) (cond ((or (= x 0) (= x n)) 1) ((= (modulo x 2) 0) 2) (else 4))) (define (s-term k) (define a-plus-kh (+ a (* k h))) (* (factor k) (f a-plus-kh))) (define (s-next x) (+ 1 x)) (* (/ h 3) (sum s-term a s-next n)))
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 <??> <??>))
Answer:
(define (sum term a next b) (define (iter a result) (if (= a b) (+ result (term a)) (iter (next a) (+ result (term a))))) (iter a 0))
Exercise 1.31. a. 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. Show how to define factorial in terms of product. Also use product to compute approximations to using the formula
b. 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.

Answer:
;; product similar to sum (define (product term a next b) (if (> a b) 1 (* (term a) (product term (next a) next b)))) ;; Factorial using product defined above. (define (identity x) x) (define (factorial-1 n) (product identity 1 inc n)) ;; Calculating pi using John Wallis' formula. (define (pi n) (define b (* 2 n)) (define (add2 x) (+ x 2)) (define (num-term x) (if (or (= x 2) (= x b)) x (square x))) (* 4.0 (/ (product num-term 2 add2 b) (product square 3 add2 (- b 1))))) ;; Product as iterative. (define (i-product term a next b) (define (iter a result) (if (= a b) (* result (term a)) (iter (next a) (* result (term a))))) (iter a 1))
Exercise 1.32. a. 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.
b. 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.

Answer
;; Accumulate (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)))) ;; sum and product defined using accumulate (define (a-sum term a next b) (accumulate + 0 term a next b)) (define (a-product term a next b) (accumulate * 1 term a next b)) ;; Iterative accumulate (define (i-accumulate combiner null-value term a next b) (define (iter a result) (if (= a b) (combiner result (term a)) (iter (next a) (combiner result (term a))))) (iter a null-value)) (define (i-sum term a next b) (i-accumulate + 0 term a next b)) (define (i-product term a next b) (i-accumulate * 1 term a next b))
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:

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

b. 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).

Answer:
(define (filtered-accumulate combiner filter null-value term a next b) (define (_combine result x) (if (filter x) (combiner result (term x)) result)) (define (iter a result) (if (= a b) (_combine result a) (iter (next a) (_combine result a)))) (iter a null-value)) (define (sum-even term a next b) (define (even? x) (= 0 (modulo x 2))) (filtered-accumulate + even? 0 term a next b))
Exercise 1.34. Suppose we define the procedure
(define (f g) (g 2))
Then we have
(f square) 4 (f (lambda (z) (* z (+ z 1)))) 6
What happens if we (perversely) ask the interpreter to evaluate the combination (f f)? Explain.

Answer: f is a procedure that accepts another procedure g as its argument. When executed f calls g, passing 2 as argument. In the first example the argument procedure is square. When square is called with 2 as its argument the result is naturally 4.

When we try to call f passing itself as an argument the following things happen:

1. The first time f receives a procedure, f, as its argument.
2. The argument is then invoked, passing 2 as a parameter. As the argument is f itself, this means invoking (f 2)
3. The argument to f now is 2, leading to (2 2) being invoked. This causes as the interpreter expects the first item in the expression to be a procedure but instead gets 2.

Exercise 1.35. Show that the golden ratio (section 1.2.2) is a fixed point of the transformation x 1 + 1/x, and use this fact to compute by means of the fixed-point procedure.

Answer:
(define tolerance 0.00001) (define (fixed-point f first-guess) (define (close-enough? v1 v2) (< (abs (- v1 v2)) tolerance)) (define (try guess count) (let ((next (f guess))) (if (close-enough? guess next) next (try next (+ count 1))))) (try first-guess 1)) ;; Calculating golden ratio phi ;; (fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0) ;; Requires 14 steps ;; = 1.6180327868852458 ;; (fixed-point (lambda (x) (average x (+ 1 (/ 1 x)))) 2.0) ;; Requires 10 steps ;; = 1.6180311591702674
Exercise 1.36. Modify fixed-point so that it prints the sequence of approximations it generates, using the newline and display primitives shown in exercise 1.22. Then find a solution to xx = 1000 by finding a fixed point of x log(1000)/log(x). (Use Scheme's primitive log procedure, which computes natural logarithms.) Compare the number of steps this takes with and without average damping. (Note that you cannot start fixed-point with a guess of 1, as this would cause division by log(1) = 0.)

Answer:
(define (fixed-point f first-guess) (define (close-enough? v1 v2) (< (abs (- v1 v2)) tolerance)) (define (try guess count) (let ((next (f guess))) (display count) (display ": ") (display guess) (newline) (if (close-enough? guess next) next (try next (+ count 1))))) (try first-guess 1)) ;; Calculating fp for x^x = 1000 without damping ;; Requires 34 steps ;; (fixed-point (lambda (x) (/ (log 1000) (log x))) 2.0) ;; = 4.555532270803653 ;; Calculating fp for x^x = 1000 with damping ;; Requires 9 steps ;; (fixed-point (lambda (x) (average x (/ (log 1000) (log x)))) 2.0) ;; = 4.555537551999825
Exercise 1.37. a. An infinite continued fraction is an expression of the form



As an example, one can show that the infinite continued fraction expansion with the Ni and the Di all equal to 1 produces 1/, where is the golden ratio (described in section 1.2.2). One way to approximate an infinite continued fraction is to truncate the expansion after a given number of terms. Such a truncation -- a so-called k-term finite continued fraction -- has the form



Suppose that n and d are procedures of one argument (the term index i) that return the Ni and Di of the terms of the continued fraction. 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/ using
(cont-frac (lambda (i) 1.0) (lambda (i) 1.0) k)
for successive values of k. How large must you make k in order to get an approximation that is accurate to 4 decimal places?

b. If your cont-frac 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.

Answer:
;; phi ~= 1.6180 (define (cont-frac n d k) (define (fraction i) (if (= i k) (/ (n i) (d i)) (/ (n i) (+ (d i) (fraction (+ i 1)))))) (fraction 1)) (define (phi k) (/ 1 (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) k))) ;; For k >= 12 accuracy of four decimal places is obtained. ;; (phi 12) = 1.6180555555555558 ;; (phi 1000000) = 1.618033988749895 ;; Iterative version (define (i-cont-frac n d k) (define (iter i fraction) (if (= i 0) fraction (iter (- i 1) (/ (n i) (+ (d i) fraction))))) (iter k (/ (n k) (d k)))) (define (i-phi k) (/ 1 (i-cont-frac (lambda (i) 1.0) (lambda (i) 1.0) k))) ;; (i-phi 1000000) = 1.618033988749895
Exercise 1.38. In 1737, the Swiss mathematician Leonhard Euler published a memoir De Fractionibus Continuis, which included a continued fraction expansion for e - 2, where e is the base of the natural logarithms. In this fraction, the Ni are all 1, and the Di are successively 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, .... Write a program that uses your cont-frac procedure from exercise 1.37 to approximate e, based on Euler's expansion.

Answer:
;; Exercise 1.38 (define (calc-euler-e k) (define (euler-d i) (if (= (modulo (+ i 1) 3) 0) (* 2 (+ 1 (quotient i 3))) 1)) (+ 2 (i-cont-frac (lambda (i) 1.0) euler-d k))) ;; Expected e: ;; 2.71828 18284 59045 23536 ;; (calc-euler-e 10000) ;; 2.71828 18284 59045 5
Exercise 1.39. A continued fraction representation of the tangent function was published in 1770 by the German mathematician J.H. Lambert:



where x is in radians. Define a procedure (tan-cf x k) that computes an approximation to the tangent function based on Lambert's formula. K specifies the number of terms to compute, as in exercise 1.37.

Answer:
(define (tan-frac n d k) (define (iter i fraction) (if (= i 0) fraction (iter (- i 1) (/ (n i) (- (d i) fraction))))) (iter k (/ (n k) (d k)))) (define (tan-cf x k) (define (n i) (if (= i 1) x (square x))) (define (d i) (if (= i 1) 1 (- (* 2 i) 1))) (tan-frac n d k))
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³ + ax² + bx + c.

Answer:
;; Cubic (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. 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)
Answer:
(define (double f) (lambda (x) (f (f x)))) ;; (((double (double double)) inc) 5) = 21
Double is a function that takes an input function and returns another function which applies the input twice. Therefore (double double) returns a function that applies its input 4 times. (double (double double)) therefore leads to a function that applies its input 4 * 4, or 16 times. Applying inc 16 times to 5 yields 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) 49
Answer:
(define (compose f g) (lambda (x) (f (g x))))
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 2nth 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
Hint: You may find it convenient to use compose from exercise 1.42.

Answer:
(define (repeated f n) (define (iter g i) (if (= i 1) g (iter (compose f g) (- i 1)))) (iter f n))
Exercise 1.44. The idea of smoothing a function is an important concept in signal processing. If f is a function and dx is some small number, then the smoothed version of f is the function whose value at a point x is the average of f(x - dx), f(x), and f(x + dx). Write a procedure smooth that takes as input a procedure that computes f and returns a procedure that computes the smoothed f. It is sometimes valuable to repeatedly smooth a function (that is, smooth the smoothed function, and so on) to obtained the n-fold smoothed function. Show how to generate the n-fold smoothed function of any given function using smooth and repeated from exercise 1.43.
(define (smooth f) (define dx 0.00001) (lambda (x) (/ (+ (f x) (f (+ x dx)) (f (- x dx))) 3))) (define (n-fold-smooth f n) (repeated smooth n) f)
Exercise 1.46. Several of the numerical methods described in this chapter are instances of an extremely general computational strategy known as iterative improvement. Iterative improvement says that, to compute something, we start with an initial guess for the answer, test if the guess is good enough, and otherwise improve the guess and continue the process using the improved guess as the new guess. 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. Iterative-improve should return as its value a procedure that takes a guess as argument and keeps improving the guess until it is good enough. Rewrite the sqrt procedure of section 1.1.7 and the fixed-point procedure of section 1.3.3 in terms of iterative-improve.

Answer:
(define (iterative-improve good-enough? improve) (lambda (guess) (define (iter guess) (let ((next (improve guess))) (if (good-enough? guess next) next (iter next)))) (iter guess))) ;; sqrt using iterative-improve (define (ii-sqrt x) ((iterative-improve (lambda (guess next) (< (abs (- guess next)) tolerance)) (lambda (guess) (average guess (/ x guess)))) 1.0)) ;; fixed-point using iterative-improve (define (ii-fixed-point f first-guess) ((iterative-improve (lambda (guess next) (< (abs (- guess next)) tolerance)) (lambda (guess) (f guess))) first-guess)) ;; Calculating golden ratio phi ;; (fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0) ;; Requires 14 steps ;; = 1.6180327868852458

SICP Section 1.2 Procedures and the Processes They Generate

Exercise 1.9. Each of the following two procedures defines a method for adding two positive integers in terms of the procedures inc, which increments its argument by 1, and dec, which decrements its argument by 1.
(define (+ a b) (if (= a 0) b (inc (+ (dec a) b)))) (define (+ a b) (if (= a 0) b (+ (dec a) (inc b))))
Using the substitution model, illustrate the process generated by each procedure in evaluating (+ 4 5). Are these processes iterative or recursive?

Answer: First version is recursive; second is iterative. Exercise 1.10. The following procedure computes a mathematical function called Ackermann's function.
(define (A x y) (cond ((= y 0) 0) ((= x 0) (* 2 y)) ((= y 1) 2) (else (A (- x 1) (A x (- y 1))))))
What are the values of the following expressions?
(A 1 10) (A 2 4) (A 3 3)
Consider the following procedures, where A is the procedure defined above:
(define (f n) (A 0 n)) (define (g n) (A 1 n)) (define (h n) (A 2 n)) (define (k n) (* 5 n n))
Give concise mathematical definitions for the functions computed by the procedures f, g, and h for positive integer values of n. For example, (k n) computes 5n2.

Answer:
(A 1 10) ;; 2^10 = 1024 (A 2 4) ;; 65536 (A 3 3) ;; 65536 (define (f n) (A 0 n)) ;; (f n) computes 2n (define (g n) (A 1 n)) ;; (g n) computes 2^n (define (h n) (A 2 n)) ;; (h n) computes 0 if n = 0; 2 if n = 1; 2^h(n-1) for n > 1
Exercise 1.11. A function f is defined by the rule that f(n) = n if n<3 and f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) if n> 3. Write a procedure that computes f by means of a recursive process. Write a procedure that computes f by means of an iterative process.
;; Recursive version (define (f n) (cond ((< n 3) n) (else (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))))) ;; Iterative version (define (g n) (cond ((< n 3) n) (else (g-iter 2 1 0 (- n 2))))) (define (g-iter a b c count) (if (= count 1) (g-sum a b c) (g-iter (g-sum a b c) a b (- count 1)))) (define (g-sum a b c) (+ a (* 2 b) (* 3 c)))
Exercise 1.12. The following pattern of numbers is called Pascal's triangle. The numbers at the edge of the triangle are all 1, and each number inside the triangle is the sum of the two numbers above it.35 Write a procedure that computes elements of Pascal's triangle by means of a recursive process.

Answer:
(define (pascal row column) (cond ((= row 1) 1) ((= column 1) 1) ((= row column) 1) (else (+ (pascal (- row 1) (- column 1)) (pascal (- row 1) column)))))
Exercise 1.14. Draw the tree illustrating the process generated by the count-change procedure of section 1.2.2 in making change for 11 cents. What are the orders of growth of the space and number of steps used by this process as the amount to be changed increases?

Answer: Amount (steps and space) are respectively 1 (10), 2 (12), 3 (14) etc. Therefore space and # of steps grows linearly with amount. O(n).

SICP section 1.1 The Elements of Programming

Exercise 1.1. Below is a sequence of expressions. What is the result printed by the interpreter in response to each expression? Assume that the sequence is to be evaluated in the order in which it is presented.
10 ;; 10 (+ 5 3 4) ;; 12 (- 9 1) ;; 8 (/ 6 2) ;; 3 (+ (* 2 4) (- 4 6)) ;; 6 (define a 3) ;; <nothing is printed> (define b (+ a 1)) ;; <nothing is printed> (+ a b (* a b)) ;; 19 (= a b) ;; #f (if (and (> b a) (< b (* a b)) ) b a) ;; 4 (cond ((= a 4) 6) ((= b 4) (+ 6 7 a)) (else 25) ) ;; 16 (+ 2 (if (> b a) b a)) ;; 6 (* (cond ((> a b) a) ((< a b) b) (else -1)) (+ a 1) ) ;; 16
Exercise 1.2. Translate the following expression into prefix form

(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5))))) (* 3 (- 6 2) (- 2 7)) )
Exercise 1.3. Define a procedure that takes three numbers as arguments and returns the sum of the squares of the two larger numbers. (define (smallest x y z) (cond ((and (>= x z) (>= y z)) z) ((and (>= y x) (>= z x)) x) ((and (>= z y) (>= x y)) y) ) ) (define (square x) (* x x)) (define (sum_of_squares x y) (+ (square x) (square y) ) ) (define (sum_of_squares_of_larger_two x y z) (cond ((= (smallest x y z) x) (sum_of_squares y z)) ((= (smallest x y z) y) (sum_of_squares x z)) ((= (smallest x y z) z) (sum_of_squares x y)) ) )
Exercise 1.4. Observe that our model of evaluation allows for combinations whose operators are compound expressions. Use this observation to describe the behavior of the following procedure: (define (a-plus-abs-b a b) ((if (> b 0) + -) a b))
Answer: The procedure a_plus_abs_b takes two arguments, a and b. It evaluates the expression (operator a b) where operator is chosen as either + or - depending on whether b is greater than zero or not. The key is that operator itself is the value of evaluating the if expression.

Exercise 1.5. Ben Bitdiddle has invented a test to determine whether the interpreter he is faced with is using applicative-order evaluation or normal-order evaluation. He defines the following two procedures: (define (p) (p)) (define (test x y) (if (= x 0) 0 y))
Then he evaluates the expression (test 0 (p))
What behavior will Ben observe with an interpreter that uses applicative-order evaluation? What behavior will he observe with an interpreter that uses normal-order evaluation? Explain your answer. (Assume that the evaluation rule for the special form if is the same whether the interpreter is using normal or applicative order: The predicate expression is evaluated first, and the result determines whether to evaluate the consequent or the alternative expression.)

Answer: If applicative order is used for evaluation the arguments to test are evaluated first. This means (p) is evaluated, leading to an infinite loop. On the other hand with normal order evaluation (p) is not evaluated until it is actually needed. Since the if is designed in such a way that this never happens, there is no infinite loop and the call returns 0.

Exercise 1.6. Alyssa P. Hacker doesn't see why if needs to be provided as a special form. ``Why can't I just define it as an ordinary procedure in terms of cond?'' she asks. Alyssa's friend Eva Lu Ator claims this can indeed be done, and she defines a new version of if: (define (new-if predicate then-clause else-clause) (cond (predicate then-clause) (else else-clause)))
Eva demonstrates the program for Alyssa: (new-if (= 2 3) 0 5) 5 (new-if (= 1 1) 0 5) 0
Delighted, Alyssa uses new-if to rewrite the square-root program: (define (sqrt-iter guess x) (new-if (good-enough? guess x) guess (sqrt-iter (improve guess x) x)))
What happens when Alyssa attempts to use this to compute square roots? Explain.

Answer: Normally if evaluates the alternative only if the predicate is false. This is why it is a special form. Since Alyssa's version is not a special form the alternative is evaluated irrespective of the result of the predicate. In the case of square roots this means calling sqrt-iter again, leading to an infinite loop.

SICP: Solutions to Exercises and Notes

I started my sabbatical in early July 2008 with the aim of working through the Structure and Interpretation of Computer Programs, exercises and all. I have completed the first three chapters at the time of writing this. So far I have been posting notes at the end of each chapter. I'll now start putting up my solutions to the exercises and any notes/questions I have.

All the exercises have been written in MzScheme using DrScheme. DrScheme's implementation of MzScheme worked straight out of the box for most purposes. The only serious tweaking I had to do so far was to add a macro for the cons-stream operation required in chapter 3. The code for this macro was borrowed from the PLT Scheme mailing list.

Testing Code Highlighting Redux

I have been playing around with adding syntax highlighting for Scheme using syntaxhighlighter (albeit an old version of the tool). Here is a little test to see if it worked. (define (probe name connector) ;; comment (define (print-probe value) (newline) (display "Probe: ") (display name) (display " = ") (display value)) (define (process-new-value) (print-probe (get-value connector))) (define (process-forget-value) (print-probe "?")) (define (me request) (cond ((eq? request 'I-have-a-value) (process-new-value)) ((eq? request 'I-lost-my-value) (process-forget-value)) (else (error "Unknown request -- PROBE" request)))) (connect connector me) me)

Sabbatical Update #3

I completed Chapter 3 of SICP today. It took longer than expected but was worth the effort I put in.

Chapter 3 started off by introducing state variables. This was quite new for chapters 1 and 2 used stateless procedures to solve problems. With the introduction of state came new problems. The substitution model of evaluation was no longer adequate to figure out how a given procedure would work. The authors introduced what is called the Environment Model as a better suited means of evaluation. The new model made good use of environment diagrams to help the process. In fact many exercise problems require the student to come up with environment diagrams along with the actual procedures.

The authors then focused on a prominent outcome of using assignment - mutable data. This involved learning to work with mutable lists and designing implementations of queues and tables. The understanding of mutable data and data structures were put to use in solving problems related to simulating digital circuits and constraint propagation.

The next section demonstrated the problems created when assignment and concurrency collide. Serialization was discussed in some depth as one possible way to control problems related to concurrency. I learned to implement simple mutexes and serializers.

The last section of the chapter - Streams - proved to be the most interesting and conceptually difficult to understand. In general streams are data structures used to represent sequences. They are distinct from lists in that they make use of delayed evaluation. What makes them fascinating is how such a powerful concept is built using such simple ingredients as force and delay.

Streams proved to be difficult to tackle in the beginning. The breakthrough came when I learned to ignore the syntax (the force and delay bits in particular) and look at streams purely as sequences, sometimes mathematical ones. Understanding stream operations became easier once I visualized these operations as "machinery working on moving assembly lines".