Archive for August, 2010

Exercise 2.2

An implementation of the required procedures follows:

;; Point selectors and constructors.
(define (make-point x y)
  (cons x y))

(define (x-point p)
  (car p))

(define (y-point p)
  (cdr p))

;; Segment selectors and constructors.
(define (make-segment start end)
  (cons start end))

(define (start-segment s)
  (car s))

(define (end-segment s)
  (cdr s))

;; Calculates the midpoint of the segment s.
(define (midpoint-segment s)
  (make-point (/ (+ (x-point (start-segment s))
                    (x-point (end-segment s)))
              (/ (+ (y-point (start-segment s))
                    (y-point (end-segment s)))

Exercise 2.3

For the purposes of this exercise a rectangle will have two selectors width-rect, and height-rect for extracting the width and height respectively. Furthermore for sake of simplicity it is assumed that we are only interested in rectangles with sides parallel to the coordinate axes.

Having specified these selectors we can directly jump ahead and implement the perimeter-rect and area-rect procedures:

(define (perimeter-rect r)
  (+ (* 2 (width-rect  r))
     (* 2 (height-rect r))))

(define (area-rect r)
  (* (width-rect  r)
     (height-rect r)))

Now we can create different representations for a rectangle. The first representation treats a rectangle as a pair of points corresponding to diagonally opposite corners:

;; Representation 1
(define (make-rect p1 p2)
  (cons p1 p2))

(define (width-rect r)
  (abs (- (x-point (car r)) (x-point (cdr r)))))

(define (height-rect r)
  (abs (- (y-point (car r)) (y-point (cdr r)))))

The second representation considers a rectangle as a point corresponding to its lower left corner, a width, and a height:

;; Representation 2
(define (make-rect p width height)
  (cons p (cons width height)))

(define (width-rect r)
  (car (cdr r)))

(define (height-rect r)
  (cdr (cdr r)))

Changing the representation does not require changing the implementation of the perimeter-rect and area-rect procedures. This design technique is sometimes called programming to an interface, not an implementation.

Read Full Post »

Exercise 2.1

The “better version” of the make-rat constructor normalizes the sign of the rational number in addition to reducing the numerator and the denominator to lowest terms.

The let* special form is used. Let* is similar to let, but what makes it different is that it can be employed to define variables whose values depend on other variables previously defined in the same let* expression. To achieve the same result using let would require nesting which is not as convenient.

Instead of considering all 22 = 4 separate possibilities for the sign of the numerator and the denominator of a rational number, the case analysis can be tightly consolidated to just two.

(define (make-rat n d) 
  (let* ((g (gcd (abs n) (abs d)))
         (an (/ (abs n) g))
         (ad (/ (abs d) g)))
    (if (equal? (negative? n) (negative? d)) 
        (cons an ad)
        (cons (- an) ad))))

Read Full Post »

Exercise 1.40

Cubic creates and returns a procedure that takes an argument x and maps it to the value of x3 + ax2 + bx + c.

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

Even though this is a very simple example the smooth transition between algebraic notation and code is impressive.

Exercise 1.41

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

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

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

The evaluation of the expression above results in 21 = 5 + 16. This might seem strange at first because doubling something successively 3 times is equivalent to multiplying it by 23 = 8. So we could expect to get 13 = 5 + 8. But this is incorrect. The outermost double procedure creates 2 copies of the 2 inner double’s resulting in a “cascade” of 4 consecutive double’s, for a total of 24 = 16 applications of the procedure f. This can be clearly seen by applying the substitution model of evaluation.

Exercise 1.42

The capability of a procedure to take another procedure(s) as argument and to return a procedure as a value makes the implementation of compose simple and elegant:

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

Exercise 1.43

The returned procedure can in turn be passed as an argument to a procedure which returns a procedure. This “closure property” (in the mathematical sense) adds additional power to the language as can be seen in this and the next exercise.

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

Exercise 1.44

(define (average-3 x y z)
  (/ (+ x y z) 3.0))

(define dx 0.001)

(define (smooth f)
  (lambda (x)
    (average-3 (f (- x dx))
               (f x)
               (f (+ x dx)))))

(define (n-fold-smooth n)
  (repeated smooth n))

Exercise 1.45

As an experimental tool we can define a procedure n-th-root-test:

;; Tries to compute the n'th root of x using t average-damps.
(define (n-th-root-test n x t)
  (fixed-point ((repeated average-damp t) 
                (lambda (y) (/ x (expt y (- n 1)))))

It takes three arguments – n, x, and t. N determines the order of the root we want to compute, x is the number whose root we are computing, and t is the number of damping operations to be applied.

Running tests for n’s from 2 to 16 on x = 42 and taking t to be as small as possible we get:

;; Tests
(n-th-root-test 2 42 1)
(n-th-root-test 3 42 1)
(n-th-root-test 4 42 2) ; does not terminate with t = 1

(n-th-root-test 5 42 2)
(n-th-root-test 6 42 2)
(n-th-root-test 7 42 2)
(n-th-root-test 8 42 3) ; does not terminate with t = 2

(n-th-root-test 9 42 3)
(n-th-root-test 10 42 3)
(n-th-root-test 11 42 3)
(n-th-root-test 12 42 3)
(n-th-root-test 13 42 3) 
(n-th-root-test 14 42 3)
(n-th-root-test 15 42 3)
(n-th-root-test 16 42 4) ; does not terminate with t = 3

A clear pattern emerges. Each time n reaches the next power of 2 one more average damping operation is needed to achieve convergence. In other words to compute the n-th root of x we need to apply ⌊ log2n⌋ damping operations. Embedding this knowledge into a new n-th-root procedure we get:

(define (n-th-root n x)
  (fixed-point ((repeated average-damp 
                          (floor (/ (log n) (log 2.0))))
                (lambda (y) (/ x (expt y (- n 1)))))

Exercise 1.46

Iterative-improve is slightly different from the procedures we saw so far. It can not return a lambda expression in the most straight forward manner. The reason is that the procedure returned is syntactically recursive (even though it generates an iterative process). So it must have a name:

(define (iterative-improve good-enough? improve)
  (define (p guess)
    (if (good-enough? guess)
        (p (improve guess))))

(define (my-sqrt x)
  (define (average x y)
    (/ (+ x y) 2))
  (define (good-enough? guess)
    (< (abs (- (* guess guess) x)) 0.00001))
  (define (improve guess)
    (average guess (/ x guess)))
  ((iterative-improve good-enough? improve) x))

(define (fixed-point f first-guess)
  (define (good-enough? guess)
    (< (abs (- guess (f guess))) 0.00001))
  (define (improve guess)
    (f guess))
  ((iterative-improve good-enough? improve) first-guess))

Read Full Post »

Exercise 1.35

Indeed φ is a fixed point of the transformation

x \mapsto 1 + \dfrac{1}{x}

This is a direct consequence of the fact that φ is a root of the equation:

x^2 - x - 1 = 0

Using the fixed-point procedure we get a good approximation of φ:

(fixed-point (lambda (x) (+ 1.0 (/ 1.0 x))) 1.0) 
=> 1.6180327868852458

Exercise 1.36

(define (average x y)
  (/ (+ x y) 2.0))

(define (tolerance) 0.00001)
(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) (tolerance)))
  (define (try guess)
    (display "guess: ")
    (display guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          (try next))))
  (try first-guess))

(fixed-point (lambda (x) (/ (log 1000.0) (log x))) 2.0)
=> 4.555532270803653 ; 34 guesses

(fixed-point (lambda (x) (average x (/ (log 1000.0) (log x))) 2.0))
=> 4.555537551999825 ; 9 guesses

The computation that uses average damping converges much faster. It takes only 9 guesses as opposed to the 34 needed for the non-damped one.

Exercise 1.37

Computing continued fractions turns out to be very cool. The recursive version is straight forward as usual. However the iterative implementation requires computing the continued fraction backwards! See the code below for more details:

(define (cont-frac n d k)
  ;; Recursive implementation
  (define (rec i)
    (if (> i k)
        (/ (n i)
           (+ (d i) (rec (+ i 1))))))
  ;; Iterative implementation
  (define (iter i result)
    (if (= i 0)
        (iter (- i 1)
              (/ (n i)
                 (+ (d i) result)))))
  (iter k 0))

Experimenting a little we see that for the 12-term finite continued fraction with Ni = 1 and Di = 1 we get an approximation of 1 / φ accurate to 4 decimal places:

(cont-frac (lambda (i) 1.0)
           (lambda (i) 1.0)
=> 0.6180257510729613

Exercise 1.38

(define (den i)
  (if (< (remainder i 3) 2) 
      (* 2 (/ (+ i 1) 3))))

(define e (+ 2 (cont-frac (lambda (i) 1.0)

=> 2.7182818284590455

This 100-term continued fraction approximation for e is accurate to 14 decimal places.

Exercise 1.39

(define (tan-cf x k)
  (define (num i)
    (if (= i 1)
        (- (* x x))))
  (define (den i)
    (- (* 2 i) 1))
  (cont-frac num den k))

(tan-cf 3.0 100)
=> -0.14254654307427775

Read Full Post »

Exercise 1.34

Applying the substitution model of evaluation we get:

(f f) =>
(f 2) =>
(2 2)

The attempt to evaluate the last expression will result in an error since 2 is not a procedure the interpreter knows how to apply.

Read Full Post »

Older Posts »