Exercises 2.38 & 2.39: fold-left and fold-right

These exercises didn't take too long to complete, but I'm still not sure I understand the implications of it, so I'm going to work through it here.

The accumulate procedure in the text is the same as a Scheme procedure called fold-right. There's a similar procedure called fold-left that can be defined like this:

(define (fold-left op initial sequence)
  (define (iter result rest)
    (if (null? rest)
        result
        (iter (op result (car rest))
              (cdr rest))))
  (iter initial sequence))

The first exercise has you work through some sample expressions to see how the two differ. Here are my expansions, using the substitution model we've been using in the text so far.

(fold-right / 1 (list 1 2 3))
(/ 1 (fold-right / 1 (list 2 3)))
(/ 1 (/ 2 (/ 3 (fold-right / 1 (list)))))
(/ 1 (/ 2 (/ 3 1)))
(/ 1 (/ 2 3))
(/ 1 2/3)
3/2


(fold-left / 1 (list 1 2 3))
(iter 1 (list 1 2 3))
(iter (/ 1 1) (list 2 3))
(iter 1 (list 2 3))
(iter (/ 1 2) (list 3))
(iter 1/2 (list 3))
(iter (/ 1/2 3) (list))
(iter 1/6 (list))
1/6

;; or:
(/ (/ (/ 1 1) 2) 3)

Just in case having the initial parameter the same as the first term of the list (i.e., the two 1's) is hiding an error, I'm going to do it again with my own list where every number is unique.

(fold-right / 1 (list 2 3 4))
(/ 2 (fold-right / 1 (list 3 4)))
(/ 2 (/ 3 (/ 4 (fold-right / 1 (list)))))
(/ 2 (/ 3 (/ 4 1)))
(/ 2 (/ 3 4))
(/ 2 3/4)
8/3


(fold-left / 1 (list 2 3 4))
(iter 1 (list 2 3 4))
(iter (/ 1 2) (list 3 4))
(iter 1/2 (list 3 44))
(iter (/ 1/2 3) (list 4))
(iter 1/6 (list 4))
(iter (/ 1/6 4) (list))
(iter 1/24 (list))
1/24

;; or:
(/ (/ (/ 1 2) 3) 4)

With infix notation I could describe these as:

(((1 ÷ 2) ÷ 3) ÷ 4) for fold-left and

(2 ÷ (3 ÷ (4 ÷ 1))) for fold-right.

For the mathematical operators above, fold-left conforms to what you would get if you were to work your way through the list from left to right with a calculator, as 1 ÷ 2 ÷ 3 ÷ 4 =.

Moving on to the list operator:

;;fold-right
(fold-right list nil (list 1 2 3))
(list 1 (fold-right list nil (list 2 3))
(list 1 (list 2 (fold-right list nil (list 3))))
(list 1 (list 2 (list 3 (fold-right list nil (list)))))
(list 1 (list 2 (list 3 '())))
(list 1 (list 2 (3 ())))
(list 1 (2 (3 ())))
(1 (2 (3 ())))

;;fold-left
(fold-left list nil (list 1 2 3))
(iter nil (list 1 2 3))
(iter (list nil 1) (list 2 3))
(iter (() 1) (list 2 3))
(iter (list (() 1) 2) (list 3))
(iter ((() 1) 2) (list 3))
(iter (list ((() 1) 2) 3) (list))
(iter (((() 1) 2) 3) (list))
(((() 1) 2) 3)
;; or:
(list (list (list nil 3) 2) 1)

fold-right seems clear as a recursive process. You take the first item from the list and apply the operator to it and the fold-right of the remainder of the list. One confusing thing is that the initial term provided to the procedure feels like a terminal term when I work through the substitution: it's the last thing the operator works on when it reaches the end of the list. It is, I suppose, the first thing the get evaluated in the chain of deferred recursive expressions.

I have a harder time describing fold-left. As noted above, it feels natural with mathematical operators and conforms to what I get from a calculator. As explained in this Stack Exchange question, these operators are left-associative, so fold-left feels natural. With other operators (like cons), fold-right starts feeling more natural. If your operator is commutative, like addition and multiplication, your result will be the same with either fold-left or fold-right.

Exercise 2.39 has you define reverse in terms of both fold-left and fold-right. First, fold-right:

Given a list (1 2 3), you need an operator (I'll call it op) such that

(op 1 (op 2 (op 3 nil)))

results in

(3 2 1)

(define (reverse sequence)
  (fold-right (lambda (x y) (append y (list x))) nil sequence))

For fold-left, you need an operator such that, given a list (1 2 3),

(op (op (op nil 3) 2) 1)

Evaluates to

(3 2 1)

(define (reverse sequence)
  (fold-left (lambda (x y) (cons y x)) nil sequence))

It was easiest to look at the innermost expression and figure out a way to build the term I want.

Working through these definitely helped my understanding, but it would take a lot more practice before either fold-left or fold-right feels natural, and before it's immediately obvious whether a left fold or right fold is the best fit for a given operation.

Sequences as Conventional Interfaces

map can be combined with other procedures accumulate and filter to build up a conventional way of dealing with sequenced data. Two examples from the text:

Example 1 This program takes a tree, goes through it to find all leaves containing an odd number, and squares those odd leaves, and adds the squares together.

(define (sum-odd-squares tree)
  (cond ((null? tree) 0)
        ((not (pair? tree))
         (if (odd? tree) (square tree) 0))
        (else (+ (sum-odd-squares (car tree))
                 (sum-odd-squares (cdr tree))))))

Program 2 This procedure takes a number n and produces a list of even Fibonacci numbers equal to or less than Fib(n).

(define (even-fibs n)
  (define (next k)
    (if (> k n)
        nil
        (let ((f (fib k)))
          (if (even? f)
              (cons f (next (+ k 1)))
              (next (+ k 1))))))
  (next 0))

The programs don't seem to have a lot in common, but they can be understood like this:

Program 1
Enumerate tree leaves -> Filter odd leaves -> map square procedure -> Accumulate with +

Program 2
Enumerate integers -> map fib procdure -> filter even results -> accumulate with cons.

Seen this way you can abstact out the notions of filtering and accumulating, and the two actually look very similar.

To filter we can define

(define (filter predicate sequence)
  (cond ((null? sequence) nil)
        ((predicate (car sequence))
         (cons (car sequence)
               (filter predicate (cdr sequence))))
        (else (filter predicate (cdr sequence)))))

(filter odd? (list 1 2 3 4 5))
;Value: (1 3 5)

and to accumulate

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))

(accumulate + 0 (list 1 2 3 4 5))
;Value: 15

(accumulate * 1 (list 1 2 3 4 5))
;Value: 120

(accumulate cons nil (list 1 2 3 4 5))
;Value: (1 2 3 4 5)

We can now define the above procedures in terms of map, filter, and accumulate.

(define (sum-odd-squares tree)
  (accumulate +
              0
              (map square
                   (filter odd?
                           (enumerate-tree tree)))))

(define (even-fibs n)
  (accumulate cons
              nil
              (filter even?
                      (map fib
                           (enumerate-interval 0 n)))))

Mapping Over Lists and Trees

The procedure map takes a procedure and a list, applies the procedure to each element of the list, and returns a list of the results. One way to define map could be

(define (map proc items)
  (if (null? items)
      nil
      (cons (proc (car items))
            (map proc (cdr items)))))

(map square (list 1 2 3 4))
;; (1 4 9)

You can also pass anonymous functions with lambda:

(map (lambda (x) (* x 2)) (list 1 2 3))
;Value 7: (2 4 6)

Then use this for more general procedures.

(define (scale-list items factor)
  (map (lambda (x) (* x factor))
       items))

(scale-list (list 1 2 3) 10)
;Value 8: (10 20 30)

You can use recursion to map over trees. Check for leaves as the terminating condition.

(define (scale-tree tree factor)
  (map (lambda (sub-tree)
         (if (pair? sub-tree)
             (scale-tree sub-tree factor)
             (* sub-tree factor)))
       tree))

(scale-tree (list 1 2 (list 4 5) 5) 10)

;Value 15: (10 20 (40 50) 50)

The built-in map is more general. If the procedure passed in takes multiple arguments, you can also supply multiple lists. The procedure is applied to all the first elements of the lists, then all the second elements of the list, and so on.

(map + (list 1 2 3 4) (list 10 20 30 40))
;Value 3: (11 22 33 44)

Exercise 2.30 Implement square-tree both directly and by using map and recursion.

;;Direct implementation
(define (square-tree tree)
  (cond ((null? tree) nil)
        ((not (pair? (car tree))) (cons (square (car tree))
                                        (square-tree (cdr tree))))
        (else (cons (square-tree (car tree))
                    (square-tree (cdr tree))))))

;;Using map
(define (square-tree tree)
  (map (lambda (x)
  (if (pair? x)
      (square-tree x)
      (square x)))
       tree))

The version using map is much shorter and easier to grok.

Exercise 2.31 Abstract previous exercise to use a procedure tree-map.

(define (tree-map proc tree)
  (map (lambda (x)
         (if (pair? x)
         (tree-map proc x)
         (proc x)))
   tree))

(define (square-tree tree) (tree-map square tree))

Exercise 2.6: Church Numerals

Exercise 2.6 Define one and two directly (not in terms of zero and add-1).

The exercise gives the following definitions of zero and add-1

(define zero (lambda (f) (lambda (x) x)))

(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

OK. Not that I understand how these represent zero and add-1, because trying to evaluate them just returns a procedure.

zero

;Value 22: #[compound-procedure 22 zero]

(add-1 zero)

;Value 23: #[compound-procedure 23]

Still, I'll play along. I'll use the substitution rules to figure out one and two.

(add-1 zero)
(lambda (f) (lambda (x) (f ((zero f) x))))
(lambda (f) (lambda (x) (f (lambda (x1) x1) x)))
(lambda (f) (lambda (x) (f x)))

(define one
  (lambda (f) (lambda (x) (f x)))

(add-1 one)
(lambda (f) (lambda (x) (f ((one f) x))))
(lambda (f) (lambda (x) (f ((lambda (x) f x) x))))
(lambda (f) (lambda (x) (f (f x))))

(define two
    (lambda (f) (lambda (x) (f (f x))))

At this point i can see a pattern emerge. I'm going to venture a guess that three would look like this:

(define three
    (lambda (f) (lambda (x) (f (f (f x)))))

So I don't really know what I did or how to verify whether its right. A little googling reveals a great page on this exercise by Bill the Lizard. And (surprise!) it looks like my substitutions above came out OK.

Reading over Bill's solution, I realize I forgot to define add. So I try not to look at Bill's solution, and work on my own. I do crib Bill's suggestion on how to test these numbers with inc.

So, I start looking at the pattern closer. I know that

(add zero one)

should result in

(lambda (f) (lambda (x) (f x)))

and that

(add one one)

should result in

(lambda (f) (lambda (x) (f (f x))))

And just to make sure I understand what's going on, I define add-2

(define (add-2 n)
  (lambda (f) (lambda (x) (f (f ((n f) x))))))

This seems to work based on my
inc test.

(((add-2 zero) inc) 0)

;Value: 2

I have a procedure to increase the value of a number. I need to generalize it so that I can increase it value of a number a b times. As it turns out, this "number" b is a procedure which repeats another procedure. So I'll just apply b to (a f) like this.

(define (add a b)
  (lambda (f)
    (lambda (x)
      (f ((b (a f)) x)))))

This look promising at first, but, until I get to adding two and two.

(((add zero one) inc) 0)

;Value: 1

(((add one one) inc) 0)

;Value: 2

(((add one two) inc) 0)

;Value: 3

(((add two two) inc) 0)

;Value: 5

(((add two zero) inc) 0)

;Value: 1

(((add two one) inc) 0)

;Value: 3

So I played around with it until my head hurt. In the end, I read the end of Bill's article. The final solution is this.

(define (add a b)
  (lambda (f)
    (lambda (x)
      ((b f) ((a f) x)))))

Now that I see it, it makes sense. I need b applications of f to ((a f) x), and the way to do this is with the procedure(b f), which will result in the application of procedure f b times. The repeated application of this procedure should be applied to ((a f) x).

Definitely one of the hardest problems I've encountered. I'll have to do some study on church numbers and come back to it.

Exercise 2.5: Yet another definition of cons, car, cdr

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 2^a3^b. Give the corresponding definitions of the procedures cons, car, and cdr.

This is possible because any number 2ⁿ will not contain 3 as a factor. Similarly, any number 3ⁿ will not contain 2 as a factor.

cons is a straightforward application of what the exercise describes.

(define (cons3 a b)
  (* (expt 2 a) (expt 3 b)))

car and cdr just repeatedly divide by 2 (car) or 3 (cdr) until the number no longer divides evenly. Count the number of even divisions, and return the count as the result.

(define (cdr3 c)
  (define (helper x count)
    (if (= 0 (remainder x 3))
        (helper (/ x 3) (+ 1 count))
        count))
  (helper c 0))

(define (car3 c)
  (define (helper x count)
    (if (= 0 (remainder x 2))
        (helper (/ x 2) (+ 1 count))
        count))
  (helper c 0))

;;tests
(car3 (cons3 23 67))
;Value: 23

(cdr3 (cons3 23 67))
;Value: 67

Exercises 2.1 - 2.4

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.

The main trick in this problem was to get the signs to line up after your number comes through the gcd procedure. I could have redefined gcd to return only a positive number, but that seemed to be cheating. So I came up with the method below which calls make-rat again. I could have added more conditional checking to get the signs to work, but somehow this was the first solution to come to me.

;;;from chapter 1
(define (square x) (* x x))

;;;from section 1.2.5, for Section 2.1.1
(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

;; from section 2.1
(define (numer x) (car x))

(define (denom x) (cdr x))

(define (print-rat x)
  (newline)
  (display (numer x))
  (display "/")
  (display (denom x)))

;; original make-rat
(define (make-rat n d)
  (let ((g (gcd n d)))
    (cons (/ n g) (/ d g))))

;;new, improved make-rat
(define (make-rat n d)
  (let ((g (abs (gcd n d))))
    (cond
     ((and (< n 0) (< d 0)) (make-rat (abs n) (abs d)))
     ((and (> n 0) (< d 0)) (make-rat (- n) (- d)))
     (else (cons (/ n g) (/ d g))))))

Exercise 2.2 Specify a constructor make-point and selectors x-point and y-point that define this representation (of a line segment).

;; Exercise 2.2

(define (make-segment a b) (cons a b))

(define (start-segment a) (car a))

(define (end-segment b) (cdr b))

(define (make-point x y) (cons x y))

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

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

(define (midpoint-segment s)
  (make-point (/ (+ (x-point (start-segment s)) (x-point (end-segment s))) 2)
              (/ (+ (y-point (start-segment s)) (y-point (end-segment s))) 2)))

(define (print-point p)
  (newline)
  (display "(")
  (display (x-point p))
  (display ",")
  (display (y-point p))
  (display ")"))

;;; test out the procedure

(define s1 (make-point 0 0) (make-point 2 4)

(print-point (midpoing s1))

(1,2)
;Unspecified return value

Exercise 2.3 Implement a representation for rectangles in a plane.

I wasn't sure what I was supposed to provide in term of "abstraction barriers." I decided that was the selectors for the width and height of the rectangles. The first definition of rectangle is defined in terms of two points: the top left and the bottom right. Then I define height and width to calculate those values based on the two points.

;; exercise 2.3
;;first definition
(define (make-rect tl br) (cons tl br))

(define (top-left-rect r) (car r))
(define (bottom-right-rect r) (cdr r))

(define (width-rect r)
    (- (x-point (bottom-right-rect r))
       (x-point (top-left-rect r))))

(define (height-rect r)
    (- (y-point (top-left-rect r))
       (y-point (bottom-right-rect r))))

The second definition of rectangle is defined in terms of an origin point and the size. I use coordinates to represent size, which isn't ideal. The data matches up, but it isn't quite right to talk about the x-point of the width. Still, I didn't think it was necessary to define a new kind of size pair for the purpose of this exercise. Height and width selectors return the values of height and width from the size pair.

;; exercise 2.3

;;second definition
(define (make-rect origin size) (cons origin size))
(define (origin-rect r) (car r))
(define (size-rect r) (cdr r))
(define (width-rect r) (x-point (size-rect r)))
(define (height-rect r) (y-point (size-rect r)))

Finally, calculating area and perimeter in terms of size.

;; these procedures work on either representation of rectangle above
(define (perimeter-rect r) (+ (* 2 (width-rect r)) (* 2 (height-rect r))))
(define (area-rect r) (* (width-rect r) (height-rect r)))

Exercise 2.4 What is the corresponding definition of cdr?

This I just worked through with standard substitution rules until the application became clear.

;;exercise 2.4

(define (cons2 x y)
  (lambda (m) (m x y)))

(define (car2 z)
  (z (lambda (p q) p)))

;;substitution for (car (cons 1 2))

(car (cons 1 2))
(car (lambda (m) (m 1 2)))
((lambda (m) (m 1 2)) (lambda (p q) p))
((lambda (p q) p) 1 2)
(lambda (1 2) 1)
1
;; resulting definition of cdr

(define (cdr2 z)
  (z (lambda (p q) q)))

Section 2.1: Intro Data Abstraction

Notes from Book section 2.1 and Youtube lecture 2B.

Compound data. So far we've been operating on numbers for a lack of other data types to work on. This chapter introduces data. The basic datatype in Scheme is the pair.

Make pairs with cons.

(cons x y) -> pair (x, y)

Retrieve the first element with car. Retrieve the second element with cdr.

(car (cons x y)) -> x

(cdr (cons x y)) -> y

This is true for any x and y, even if x and y are themselves pairs. The ability to combine not just primitives (like numbers) but also compound data is called closure. Pairs would be limited an uninteresting if we could only crate them with a limited set of primitive data.

Suppose you have a data type of point, defined as a pair created by cons.

(define (make-point x y) (cons x y))

(define (x-coordinate p) (car p))

(define (y-coordinate p) (cdr p))

You can combine the points into a pair to define the endpoints of a line segment...

(define (make-segment a b) (cons a b))

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

(define (end-segmenet s) (cdr s))

...and then define computations based on the points.

(define (midpoint s)
    (make-point (average (x-coordinate (start-segment))
                         (x-coordinate (end-segment)))
                (average (y-coordinate (start-segment))
                         (y-coordinate (end-segment)))))

This definition also make a layered approach to the problem of lines, something like this:

Segments
------------
make-seg, seg-start, seg-end
------------
Points
------------
make-point, x-coordinate, y-coordinate
------------
Pairs, Numbers

The definition of points could change, and as long as the constructors and accessors make-point, x-coordinate, y-coordinate are updated to match the new definition, the line segment procedures don't need to change.

The pair data structure can be represented as procedures:

(define (cons x y)
    (lambda (pick)
        (cond ((= pick 1) x)
              ((= pick 2) y))))

(define (car z) (z 1))

(define (cdr z) (z 2))

Mind-blowing! There is no data, just procedures. Still, it's a valid representation of pairs because it fulfills the contract

(car (cons a b)) -> a

(cdr (cons a b)) -> b

So in some sense you can build data abstractions without data.

Chapter 1 Review

I haven't had much time to work on SICP in the last couple of weeks, but I consider chapter 1 finished. I have a couple of observations.

I love Scheme. Its a great learning tool. I've spent very little time learning some special syntax and a lot of time learning the underlying concepts. It is remarkably well-suited to thinking recursively. Oddly, it is difficult to do iterative looping. Part of that might have been that the exercises were trying to make me write an iterative algorithm for a problem that was recursive in nature.

The course starts out with no data types other than numbers. This leads to problems and exercises that are very math-heavy. One claim I see often is that you don't need much math beyond high school precalculus for this text. Technically that's true, because the text gives you any formulas you need. I hadn't had any experience with the concept of fixed points o Newton's method, and I completed those sections. Still, I was glad I had studied Simpons' formula in calculus. Moreover, studying infinite series gave me a sense of familiarity with many of the exercises. SICP doesn't require you to solve calculus problems, but I can't help but think that my confusion would be increased greatly if I didn't understand the math behind the exercises.

On to Chapter 2.

Exercises 1.40 - 1.44

These were exercises on writing procedures which return procedures. They went pretty quick, and I don't have a lot to write up for them. I have sample output that verifies the solution for most of them.

Exercise 1.40 Define a procedure cubic to approximate zeros of the cubic x³ + ax² + bx + c.

(define (cube x) (* x x x))
(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 f)
  (lambda (x)
    (f (f x))))

((double square) 2)
;Value: 16

(((double (double double)) inc) 5)
;Value: 21

Exercise 1.42 Define a procedure compose that implements composition.

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

((compose square inc) 6)
;Value: 49

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 x)
  (lambda (y)
    (if (= x 1)
        (f y)
        ((compose f (repeated f (- x 1))) y))))

((repeated square 2) 5)
;Value: 625

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 (smooth f)
  (lambda (x)
    (let ((dx .00001))
      (/ (+ (f (+ x dx)) (f x) (f (- x dx))) 3.0))))

(sqrt 4)
;Value: 2.0000000944796694

(((repeated smooth 10) sqrt) 4)
;Value: 2.0000000944692538

I'm not sure whether sqrt doesn't respond to smoothing, the dx is too large, or this solution isn't right. But I think it's right.

Exercises 1.38, 1.39: More Continued Fraction Fun

Exercise 1.38

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

The main challenge with this exercise is how to caputure the series 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, .... as a procedure.

• f(x) = x for 1 and 2
• For x > 2, every third term is part of the series 4, 6, 8, ...
• For every other x, f(x) = 1

So I use remainder to check whether the argument is one of those third terms. If it is, its value is 2 greater than the term for x - 3. Or to put it another way, f(x) = 2 + f(x - 3), for x = 5, 8, 11....

;; Exercise 1.38

(define (d x)
  (cond ((< x 3) x)
    ((= 0 (remainder (- x 2) 3)) (+ 2 (d (- x 3))))
    (else 1)))

(+ 2 (cont-frac d (lambda (x) 1.0) 100))

;Value: 2.7182818284590455

Exercise 1.39

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

A few points I had to keep in mind:

• Procedure n has to operate on the argument x, but n should still take only one value, which is the term for that portion of the contiued fraction.
• Procedure n returns a number, which is the value of an appropriate procedure applied to x.
• Procedure n should return a negative number for values of k greater than 1.

;; Exercise 1.38
(define (tan-cf x k)
  (define (d i)
    (if (= i 1)
        1.0
        (+ 2 (d (- i 1)))))
  (define (n i)
    (if (= i 1)
        x
        (- (* x x))))
  (cont-frac d n k))

Comparing my results with the calculator result of tan(3) = -0.142546543074278:

;; Using recursive version of cont-frac
(tan-cf 3 10)

;Value: -.1425465438397583

; Using iterative Version of cont-frac
(tan-cf 3 10)

;Value: -.14254654300801906

Finally, testing these two exercises revealed an error in my solution for exercise 1.37 (since corrected).

Exercise 1.37: Continued Fraction

Write a procedure to calculate a continued fraction, such as:

In approaching the problem I think of the expression like this:

This lends itself naturally to a recursive definition. "The Rest" is just the next procedure call. The terminating case is when you have called the procedure k times.

I had to define a helper procedure so that I could keep track of the index. The only way I see to avoid this is to define the procedure to take four arguments, like (define cont-frac d n a b), which starts at a and ends at b. Since the exercise specifically asks for a procedure with three arguments, I chose to create a helper function.

(define (cont-frac d n k)
  (define (cont-frac-helper index)
    (if (= index k)
        (/ (n index) (d index))
        (/ (n index) (+ (d index) (cont-frac-helper (+ index 1))))))
  (cont-frac-helper 1))

;; Estimate of golden ratio
(/ 1 (cont-frac (lambda (x) 1.0) (lambda (x) 1.0) 10))

The iterative version is a little harder, but by now I'm getting the hang of this. I know I need a results variable to store the results of my work from one iteration to the next. The steps are

• Start with the final term N_k/D_k
• Check whether you're done.
• If you're not done, the new result is N_k-1 / (D_k-1 + Result_k)
• You're done after you've calculated the step with N₁ and D₁. Repeat until k=0

;; Iterative version
(define (cont-frac d n k)
  (define (iter k result)
    (if (= k 0)
        result
        (iter (- k 1) (/ (n k) (+ (d k) result)))))
  (iter k (/ (n k) (d k))))

;; Estimate of golden ratio
(/ 1 (cont-frac (lambda (x) 1.0) (lambda (x) 1.0) 10))

---

Update: Fixed an off-by-one error in the iterative version.

Exercise 1.29: Simpson's Rule

Use the sum procedure from the chapter to estimate the definite integral of a procedure based on Simpson's rule.

Here's the summation procedure from the chapter:

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

My function definition should look like: (define (simpsons f a b n) ... where f is the function to integrate (defined as a procedure), a is the upper bound, b is the lower bound, and n is the number of subdivisions on the interval [a, b].

To get it straight in my head, I rewrote Simpson's rule in a way that was more clearly applicable for this problem.

Writing it down this way made two things clearer:

1. The argument of the function in the series changes in a straightforward manner. I just need to add h to get the next argument.
2. The procedure applied is different in each term. Sometimes it's f, sometimes it's 2f, and sometimes it's 4f

First, just to make things easier on myself, I'll define h.

(define h (/ (- b a) n))

Based on the way the sum procedure is defined, I know I need to pass it two procedures. I'll call them simp-term and simp-next.

As mentioned above, it's easy to see how the the function argument changes from term to term. I define simp-next like this.

(define (simp-next x)
    (+ x h))

Figuring out how to apply one of three different procedures to the terms of the summation is a little more puzzling. I start out with some pseudocode:

(define (simp-term x)
    (decide on a procedure)(apply the right procedure to x))

How do I decide on a procedure? With a cond statement, naturally. Something like.

(cond (or (first?) (last?) (f x))
      (even? (* 4 (f x)))
      (odd? (* 2 (f x))))

Next I need to figure out how to recognize the first, last, even, and odd terms. The parameters at my disposal are bounds a, b, total number of intervals n, and the specific function argument x. Looking at my rewritten equation above, I can see the coefficient of h has the pattern 0, 1, 2, 3, ... , n. I can see how to use this to write a test.

• If the coefficient of h = 0, it is the first term.
• If the coefficient = n, it is the last term.
• If the coefficient is odd, multiply the function results by 4.
• If the coefficient is even, multiply the function results by 2.

The parameter x is equal to a + n_kh. I can't get the coefficient directly, but together with a and h, I have enough elements to solve for for the coefficent, n_k.

So my test becomes

(define (simp-term x)
  (cond ((or (= x a) (= x b))(f x))
        ((even? (/ (- x a) h)) (* 2 (f x)))
        ((odd? (/ (- x a) h))(* 4 (f x)))))

I should note that in reality I'm doing a lot of trial-and-error coding at this point. The DrRacket stepper was a godsend, also. In hindsight, I can see why what I came up with is correct, but I don't really approach the problem like a math proof. I approach it more of a jigsaw puzzle, trying to put things together until it works.

Putting it all together I end up with:

(define (simpsons f a b n)
  (define h
    (/ (- b a) n))
  (define (simp-next x)
    (+ x h))
  (define (simp-term x)
    (cond ((or (= x a) (= x b))(f x))
          ((even? (/ (- x a) h)) (* 2 (f x)))
          ((odd? (/ (- x a) h))(* 4 (f x)))))
  (* (/ h 3)
     (sum simp-term a simp-next b)))

I spent a lot of time on this problem. It just about killed me. Working on this blog post was hugely helpful (I started it long before I was finished with the problem). My reasoning was not quite as methodical as this blog post appears. Some things that tripped me up:

• I was confused about data vs. procedures. At one point I was trying to make simp-next and simp-term return procedures. Wrong. The names represent a procedure, but they evaluate to a number.
• I was confused about what simp-next should return. It needs to return the argument to f(x), not the result of f(x).
• It wasn't clear what data I would have available when evaluating simp-term. I was getting hung up that I was defining simp-term inside simpsons, but it would be evaluated in sum. Sum doesn't have access to a, b, and n. Turns out I didn't need to worry where it would be evaluated.

I hope that reading this post help you as much as writing it helped me.

Higher-Order Procedures

This is a long-winded set of notes on section 1.3.1. I've tried to make it through SICP before, and this section is the place I usually stopped. This time, I'm pushing through until I make it. I may belabor points you find obvious, but I needed to make it excruciatingly explicit to understand it thoroughly.

Consider how similar the following three procedures are.

Sum integers from a to b

(define (sum-integers a b)
  (if (> a b)
      0
      (+ a (sum-integers (+ a 1) b))))

Sum the cube of integers from a to b

(define (sum-cubes a b)
  (if (> a b)
      0
      (+ (cube a) (sum-cubes (+ a 1) b))))

Estimate π with the series

(define (pi-sum a b)
  (if (> a b)
      0
      (+ (/ 1.0 (* a (+ a 2))) (pi-sum (+ a 4) b))))

Each of these procedures is a specific instance of a more general idea of summation.

For the first procedure, sum-integers, the function is f(x) = x, and the argument x increase by 1 each term.

For the second procedure, sub-cubes, the function is f(x) = x³. The argument x increase by 1 each term here too.

Finally, the series for ^π⁄₈. The function is a bit more complicated.

Which means the terms increase by a + 4

This particular sum also assumes we are starting with a = 1 and b is even.

So, for each summation we have

• A function f that we apply to each term
• A method for finding each subsequent argument x to supply our function f.

Saying the same thing a different way: to sum a series

We need a procedure that, given x₁, can calculate x₂. Given x₂, it calculates x₃, and so on. We feed the results of that procedure into a second procedure that calculates our function f(x).

Now you can see how you might generalize the original three procedures above by having two additional procedures, term and next. term calculates the function and gives you the numerical result you will be adding. next advances the series and gets the next value of x, which f will operate on.

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

In the case of sum-integers, the helper procedures are pretty easy. We saw above that f(x) = x, so we need an identity procedure

(define (identity x) x)

And we see that x should increase by on each term, so we make an increment procedure.

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

So defining sum-integers in terms of sum we have

(define (sum-integers a b)
  (sum identity a inc b))

For sum-cubes, f(x) = x³, and x increases by one each term. Since we already have cube and inc

(define (sum-cubes a b)
  (sum cube a inc b))

Finally, our estimate for π/8. I define two new procedures for term and next, both of which are straightforward implementations of the observations made above about the function f(x) and how the function argument increases by x + 4.

(define (pi-sum a b)
  (define (pi-term x)
    (/ 1.0 (* x (+ x 2))))
  (define (pi-next x)
    (+ x 4))
  (sum pi-term a pi-next b))

The examples above provided specific implementations for the function f(x), which is always the same for every procedure call. We can design a procedure to take a function as an argument, so the function f(x) isn't hard-coded into the implementation. Suppose we want to estimate a definite integral with the following sum.

This method for estimating definite integrals is valid for lots of functions: x², x³, sin(x), log(x) etc. We can define our procedure to take a procedure as an argument. That procedure argument calculates some function f(x). This way, our procedure can calculate the definite integral for any function expressed as a procedure.

We advance to the next x by adding dx each time. The procedure for this estimate is

(define (integral f a b dx)
  (define (add-dx x) (+ x dx))
  (* (sum f (+ a (/ dx 2)) add-dx b)
     dx))

Another notable difference is that the first x to operate on is (a + ^dx⁄₂). Previous procedures started at x = a.

Exercises 1.16, 1.17, 1.18

1.16 Design a procedure that evolves an iterative exponentiation process that uses successive squaring and uses a logarithmic number of steps, as does fast-expt.

From the hints

• (b^n/2)² = (b²)^n/2
• abⁿ should have the same value through the transition.

I want to decrease the exponent until it equals zero, at which point the result variable, a, will have the result. So the question is, when I halve the exponent n, how can I modify a and b so that abⁿ is unchanged, and that we're somehow closer to the result?

So my strategy is:

• If n is even, halve n, square b, and leave a alone
• If n is odd, decrement n by 1, and multiply a by b.

Here is the procedure.

(define (fast-iter-expt x y)
  (define (fast-helper a b n)
    (cond ((= 0 n) a)
          ((odd? n) (fast-helper (* b a) b (- n 1)))
          ((even? n) (fast-helper a (* b b) (/ n 2)))))
  (fast-helper 1 x y))

1.17 Design a multiplication procedure analogous to fast-expt that uses a logarithmic number of steps.

Referring back to the text for the exponent procedure, I come up with a method for determining multiplication, analogous to the exponentiation method in the text.

• ab = 2(a x ^b⁄₂), if b is even
• ab = a + a(b-1) if b is odd

This translates to the procedure.

(define (double n)
  (+ n n))

(define (halve n)
  (if (even? n)
      (/ n 2)
      (error "Tried to halve an odd number" n)))

(define (mult-r a b)
  (cond ((= b 0) 0)
        ((odd? b) (+ a (mult-r a (- b 1))))
        ((even? b) (double (mult-r a (halve b))))))

1.18 An iterative version of 1.17.

I came up with an invariant quantity, as described in the hint for 1.14

• ab+r = 2a⋅^b⁄₂ + r, when b is even
• ab+r = a(b-1) + (result + a), when b is odd

This translates to the procedure:

(define (mult-i a b)
  (define (multi-helper a b result)
    (cond ((= b 0) result)
          ((odd? b) (multi-helper a (- b 1) (+ result a)))
          ((even? b) (multi-helper (double a) (halve b) result))))
  (multi-helper a b 0))

Exercise 1.12: Pascal's Triangle

The following pattern of numbers is called Pascal's Triangle

    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1

Write a procedure the computes elements of Pascal's triangle by means of a recursive process.

My biggest problem with this exercise was that I didn't understand what it was asking. What input is the procedure supposed to take? I originally thought that I should take a number, and print out that many rows of the triangle. Then I realized I don't really know how to print out data like that in Scheme. So I peeked at a solution online, and realized the procedure is supposed to take the row and column, and return the number. The following procedure does that. The terminating condition for the recursion is when the column is either the first one, or the last one in the row. In both those cases the result is 1.

(define (pascal row column)
  (if (or (= 1 column)
          (= row column))
      1
      (+ (pascal (- row 1) column)
  (pascal (- row 1) (- column 1)))))

Exercise 1.11: Iterative and Recursive Procedures

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.

First, the recursive process.

(define (fun-r n)
  (if (< n 3)
      n
      (+ (* 3 (fun-r (- n 3)))
         (* 2 (fun-r (- n 2)))
         (fun-r (- n 1)))))

This was surprisingly straightforward. I thought recursion was hard, but this felt natural. Even more surprising was how hard the iterative version was. I puzzled on it for a while. I finally figured it out aftter I referred back to the discussion of the iterative Fibonnacci procedure in the text.

I'll need to keep three variables and apply the following transformations in each step of the iteration:

a ← a + b + c
b ← a
c ← b

After applying the transformation n times, the results will be

a = f (n + 2)
b = f (n + 1)
c = f (n)

I'll start the process off by initializing the first three terms at 2, 1, 0. The final procedure follows.

(define (fun-iter a b c count)
  (if (= count 0)
      c
      (fun-iter (+ a (* 2 b) (* 3 c)) a b (- count 1))))

(define (fun n)
  (fun-iter 2 1 0 n))

Iteration, Recursion, and Orders of Growth

This is my notes on section 1.2

Recursion

Many functions can be defined in terms of themselves. The factorial function is an exampe:

$$ n! = n * (n-1)! \\ 0! = 1 $$

It's easy to define a procedure from this definition.

(define (factorial n)
    (if (= n 0)
        1
        (* n (factorial (- n 1)))))

The procedure follows directly from the definition of factorial.

Iteration

The factorial function can also be calculated iteratively. Calculate it by starting with 1, and multiplying each successive integer until we reach our target. For example.

$$ n! = 1 \times 2 \times 3 \times 4 \times ... \times n $$

Translating this to a procedure is often more difficult.

(define (factorial n)
  (define (iter product counter)
    (if (> counter n)
        product
        (iter (* counter product)
              (+ counter 1))))
  (iter 1 1))

Iterative processes carry all their state with them from one step of the iteration to the next. Every time the procedure iter is called, all the information necessary to evaluate iter is passed on. Compare to the recursive procedure above, where the expression (* n (factorial (- n 1)) can't be fully evaluated until the the last factorial call reaches the base case of n = 0.

The fact that the Scheme procedure above calls itself doesn't mean that the process is recursive. The key differentiator is whether the procedure call contains all the information it needs to evalute, or whether evaluation is deferred to a future call to the procedure.

Tree recursion

The Fibonacci numbers are another function which can be naturally defined recursively

$$ Fib(0) = 0 \\ Fib(1) = 1 \\ Fib(n) = Fib (n-1) + Fib(n-2) \\ $$

The procedure for this is

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 0))))))

Each call to to Fib where n > 1 generates two more calls to Fib. The + operator has to wait for both of those calls to return before it can evaluate its arguments.

The tree recursive definition of this procedure results in a lot of duplicate work. Figure 1.5 on page 38 illustrates that (fib 3) is computed twice.

Orders of Growth

We're simplifying resources to mean the number of steps taken to solve a given problem, and the amount of space required to solve the problem.

For the recursive factorial procedure above, as the input grows, the number of steps to solve the problem grows at the same rate. The steps grow as Θ(n).

For the iterative factorial procedure, the steps grow as Θ(n), but the space required to calculate is fully capture by the state variables in each iteration, and never grows. The growth of the space is Θ(1).

The tree-recursive Fibonacci sequence requires Θ(φⁿ) steps (where φ is the golden ratio) and space Θ(n).

Some problems can be halved. For example, exponentiation. b⁸ can be calculated as:

$$ b \times b \times b \times b \times b \times b \times b \times b $$

but it can also be calculated as

$$ b^4 \times b^4 $$

\( b^4 \) can be reduced to \( b^2 \times b^2 \) and so on. The steps for calulating exponents this way grow at Θ(log n).

Substitution Model

These are my notes on the discussion from 1.1.3 - 1.1.5 of the text.

The substitution model of process evaluation, as described on page 9 of the text.

To evaluate a combination

1. Evaluate the subexpressions of the combination
2. Apply the procedure that is the value of the leftmost subexpression (the operator) to the arguments that are the values of the other subexpressions (the operands).

Define does not follow the rules above. It is one of several special forms.

To apply a compound procedure: evaluate the body of the procedure with each formal parameter replaced by the corresponding argument.

Given the procedures

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

(define (sum-of-squares x y)
  (+ (square x) (square y)))

(define (f n)
  (sum-of-squares (+ n 1) (* n 2)))

We would evaluate (f 5) by the following substitutions
(sum-of-squares (+ n 1) (* n 2)
(sum-of-squares (+ 5 1) (* 5 2)
(+ (square 6) (square 10))
(+ 36 100)
136


This substitution model above uses applicative-order evaluation. An alternative is normal-order evaluation. Normal order evaluation fully expands all arguments before applying procedures.

(f 5)
(sum-of-squares (+ 5 1) (* 5 2)
(+ (square (+ 5 1)) (square (* 5 2)))
(+ (* (+ 5 1) (+ 5 1)) (* (* 5 2) (* 5 2)))
(+ (* 6 6) (* 10 10))
(+ 36 100)
136

The interpreter actually uses applicative order evaluation, but the substitution model as described here does not accurately capture how the interpreter works.

Structure and Interpretation of Computer Programs

I'm going through Structure and Interpretation of Computer Programs (SICP) on my own. I'm going to use this blog document the materials I use, as well as for my notes and assignments. Here's the resources I'm starting out with:

• The Online Book (Amazon Link for hard copy)
• A YouTube playlist of the lectures
• MIT OpenCourseWare page for 6.001.
• Online Tutor

The videos are from a different delivery than the materals in the OCW site. I'm not sure how closely they'll match up in terms of readings and assignments. Nor am I sure how the online tutor matches.

I'm hardly the first person to blog his way through SICP. Eli Bandersky and Ken Dyck did a similar project. They did a fine job. The only reason I'm repeating is that I think it will help me learn the material. The best way to test your knowledge is to try to explain it to somebody else.