SICP Section 2.2 Hierarchical Data and the Closure Property - Part 2

Exercise 2.44. Define the procedure up-split used by corner-split. It is similar to right-split, except that it switches the roles of below and beside.
(define (up-split painter n) (if (= n 0) painter (let ((up (up-split painter (- n 1)))) (below painter (beside up up)))))
Exercise 2.45. Right-split and up-split can be expressed as instances of a general splitting operation. Define a procedure split with the property that evaluating
(define right-split (split beside below)) (define up-split (split below beside))
produces procedures right-split and up-split with the same behaviors as the ones already defined.

Answer:
(define (split orig-placer split-placer) (lambda (painter n) (if (= n 0) painter (let ((smaller ((split orig-placer split-placer) painter (- n 1)))) (orig-placer smaller (split-placer smaller smaller))))))
Exercise 2.46. A two-dimensional vector v running from the origin to a point can be represented as a pair consisting of an x-coordinate and a y-coordinate. Implement a data abstraction for vectors by giving a constructor make-vect and corresponding selectors xcor-vect and ycor-vect. In terms of your selectors and constructor, implement procedures add-vect, sub-vect, and scale-vect that perform the operations vector addition, vector subtraction, and multiplying a vector by a scalar:



Answer:
(define (make-vect x-cord y-cord) (cons x-cord y-cord)) (define (xcor-vect vector) (car vector)) (define (ycor-vect vector) (cdr vector)) (define (add-vect v1 v2) (make-vect (+ (xcor-vect v1) (xcor-vect v2)) (+ (ycor-vect v1) (ycor-vect v2)))) (define (sub-vect v1 v2) (make-vect (- (xcor-vect v1) (xcor-vect v2)) (- (ycor-vect v1) (ycor-vect v2)))) (define (scale-vect s v) (make-vect (* s (xcor-vect v)) (* s (ycor-vect v))))
Exercise 2.47. Here are two possible constructors for frames:
(define (make-frame origin edge1 edge2) (list origin edge1 edge2)) (define (make-frame origin edge1 edge2) (cons origin (cons edge1 edge2)))
For each constructor supply the appropriate selectors to produce an implementation for frames.

Answer:
;; Option 1 and selectors (define (make-frame origin edge1 edge2) (list origin edge1 edge2)) (define (origin-frame frame) (car frame)) (define (edge1-frame frame) (cadr frame)) (define (edge2-frame frame) (caddr frame)) ;; Option 2 and selectors (define (make-frame origin edge1 edge2) (cons origin (cons edge1 edge2))) (define (origin-frame frame) (car frame)) (define (edge1-frame frame) (cadr frame)) (define (edge2-frame frame) (cddr frame))
Exercise 2.48. A directed line segment in the plane can be represented as a pair of vectors -- the vector running from the origin to the start-point of the segment, and the vector running from the origin to the end-point of the segment. Use your vector representation from exercise 2.46 to define a representation for segments with a constructor make-segment and selectors start-segment and end-segment.

Answer:
(define (make-segment start-point-vector end-point-vector) (cons start-point-vector end-point-vector)) (define (start-segment segment) (car segment)) (define (end-segment segment) (cdr segment))
Exercise 2.49. Use segments->painter to define the following primitive painters:

a. The painter that draws the outline of the designated frame.

b. The painter that draws an ``X'' by connecting opposite corners of the frame.

c. The painter that draws a diamond shape by connecting the midpoints of the sides of the frame.

d. The wave painter.

Answer: a. The painter that draws the outline of the designated frame. This is done by connecting the four corners of the frame. Translated to the unit frame the corners are the points (0, 0), (1, 0), (0, 1) and (1, 1).
(define outline-segments (let ((origin (make-vect 0.0 0.0)) (one-zero (make-vect 1.0 0.0)) (zero-one (make-vect 0.0 1.0)) (one-one (make-vect 1.0 1.0))) (list (make-segment origin zero-one) (make-segment origin one-zero) (make-segment one-zero one-one) (make-segment one-one zero-one)))) (define outline-painter (segments->painter outline-segments))
b. Painting an x is accomplished by connecting opposite corners of the frame. This means drawing a line connecting (0, 0) to (1, 1) and (0, 1) to (1, 0) respectively.
(define diagonal-segments (let ((origin (make-vect 0.0 0.0)) (one-zero (make-vect 1.0 0.0)) (zero-one (make-vect 0.0 1.0)) (one-one (make-vect 1.0 1.0))) (list (make-segment origin one-one) (make-segment zero-one one-zero)))) (define x-painter (segments->painter diagonal-segments))
c. A diamond shape is created by connecting the midpoints of the sides of the unit square.
(define midpoint-segments (let ((m1 (make-vect 0.5 0.0)) (m2 (make-vect 1.0 0.5)) (m3 (make-vect 0.5 1.0)) (m4 (make-vect 0.0 0.5))) (list (make-segment m1 m2) (make-segment m2 m3) (make-segment m3 m4) (make-segment m4 m1)))) (define diamond-painter (segments->painter midpoint-segments))
d. I'll skip the wave painter. Too many line segments!

Exercise 2.50. Define the transformation flip-horiz, which flips painters horizontally, and transformations that rotate painters counterclockwise by 180 degrees and 270 degrees.

Answer:
(define (flip-horiz painter) (transform-painter painter (make-vect 1.0 0.0) (make-vect 0.0 0.0) (make-vect 1.0 1.0))) (define (rotate-ccw-180 painter) (transform-painter painter (make-vect 1.0 1.0) (make-vect 0.0 1.0) (make-vect 1.0 0.0))) (define (rotate-ccw-270 painter) (transform-painter painter (make-vect 0.0 1.0) (make-vect 0.0 0.0) (make-vect 1.0 1.0)))
Exercise 2.51. Define the below operation for painters. Below takes two painters as arguments. The resulting painter, given a frame, draws with the first painter in the bottom of the frame and with the second painter in the top. Define below in two different ways -- first by writing a procedure that is analogous to the beside procedure given above, and again in terms of beside and suitable rotation operations (from exercise 2.50).

Answer:
;; below - analogous to beside (define (below painter-bottom painter-top) (let ((split-point (make-vect 0 0.5))) (let ((paint-top (transform-painter painter-top split-point (make-vect 1.0 0.5) (make-vect 0.0 1.0))) (paint-bottom (transform-painter painter-bottom (make-vect 0.0 0.0) (make-vect 1.0 0.0) split-point))) (lambda (frame) (paint-top frame) (paint-bottom frame))))) ;; below in terms of beside and rotation operations from Exercise 2.50 (define (below painter-bottom painter-top) (lambda (frame) (rotate-ccw-90 (beside (rotate-ccw-270 painter-bottom) (rotate-ccw-270 painter-top))) frame))
Exercise 2.52. Make changes to the square limit of wave shown in figure 2.9 by working at each of the levels described above. In particular:

a. Add some segments to the primitive wave painter of exercise 2.49 (to add a smile, for example).

b. Change the pattern constructed by corner-split (for example, by using only one copy of the up-split and right-split images instead of two).

c. Modify the version of square-limit that uses square-of-four so as to assemble the corners in a different pattern. (For example, you might make the big Mr. Rogers look outward from each corner of the square.)

Answer: I am skipping the smiley part.
;; b. change pattern used by corner-split (define (corner-split painter n) (if (= n 0) painter (let ((up (up-split painter (- n 1))) (right (right-split painter (- n 1)))) (let ((corner (corner-split (painter (- n 1))))) (beside (below painter up) (below right corner)))))) ;; c. modify square-limit (define (square-limit painter n) (let ((quarter (corner-split painter n))) (let ((half (beside quarter (flip-horiz quarter)))) (below (flip-vert half) half))))

SICP Section 2.2 Hierarchical Data and the Closure Property - Part 1

Exercise 2.17. Define a procedure last-pair that returns the list that contains only the last element of a given (nonempty) list:
(last-pair (list 23 72 149 34)) (34)
Answer: This solution uses the length and list-ref functions described in the text. Here is a simpler solution which does not use length or list-ref.
(define (last-pair items) (cond ((null? items) '()) ((null? (cdr items)) items) (else (last-pair (cdr items)))))
Exercise 2.18. Define a procedure reverse that takes a list as argument and returns a list of the same elements in reverse order:
(reverse (list 1 4 9 16 25)) (25 16 9 4 1)
Answer:
(define (reverse items) (if (null? items) '() (append (reverse (cdr items)) (list (car items)))))
Exercise 2.19. Consider the change-counting program of section 1.2.2. It would be nice to be able to easily change the currency used by the program, so that we could compute the number of ways to change a British pound, for example. As the program is written, the knowledge of the currency is distributed partly into the procedure first-denomination and partly into the procedure count-change (which knows that there are five kinds of U.S. coins). It would be nicer to be able to supply a list of coins to be used for making change.

We want to rewrite the procedure cc so that its second argument is a list of the values of the coins to use rather than an integer specifying which coins to use. We could then have lists that defined each kind of currency:
(define us-coins (list 50 25 10 5 1)) (define uk-coins (list 100 50 20 10 5 2 1 0.5))
We could then call cc as follows:
(cc 100 us-coins) 292
To do this will require changing the program cc somewhat. It will still have the same form, but it will access its second argument differently, as follows:
(define (cc amount coin-values) (cond ((= amount 0) 1) ((or (< amount 0) (no-more? coin-values)) 0) (else (+ (cc amount (except-first-denomination coin-values)) (cc (- amount (first-denomination coin-values)) coin-values)))))
Define the procedures first-denomination, except-first-denomination, and no-more? in terms of primitive operations on list structures. Does the order of the list coin-values affect the answer produced by cc? Why or why not?

Answer:
(define (first-denomination coin-values) (car coin-values)) (define (except-first-denomination coin-values) (cdr coin-values)) (define (no-more? coin-values) (null? coin-values))
Order of the list coin-values will not matter. This owes to the way cc is structured. The first recursive call to cc tries to compare the amount with *all* denominations irrespective of their order in the list.

Exercise 2.20. The procedures +, *, and list take arbitrary numbers of arguments. One way to define such procedures is to use define with dotted-tail notation. In a procedure definition, a parameter list that has a dot before the last parameter name indicates that, when the procedure is called, the initial parameters (if any) will have as values the initial arguments, as usual, but the final parameter's value will be a list of any remaining arguments. For instance, given the definition
(define (f x y . z) <body>)
the procedure f can be called with two or more arguments. If we evaluate
(f 1 2 3 4 5 6)
then in the body of f, x will be 1, y will be 2, and z will be the list (3 4 5 6). Given the definition
(define (g . w) <body>)
the procedure g can be called with zero or more arguments. If we evaluate
(g 1 2 3 4 5 6)
then in the body of g, w will be the list (1 2 3 4 5 6).

Use this notation to write a procedure same-parity that takes one or more integers and returns a list of all the arguments that have the same even-odd parity as the first argument. For example,
(same-parity 1 2 3 4 5 6 7) (1 3 5 7) (same-parity 2 3 4 5 6 7) (2 4 6)
Answer:
(define (same-parity . items) (define (parity-type n) (if (= (modulo n 2) 0) even? odd?)) (define (iter has-expected-parity? items result) (if (null? items) result (let ((first (car items)) (rest (cdr items))) (if (has-expected-parity? first) (iter has-expected-parity? rest (append result (list first))) (iter has-expected-parity? rest result))))) (iter (parity-type (car items)) items '()))
Exercise 2.21. The procedure square-list takes a list of numbers as argument and returns a list of the squares of those numbers.
(square-list (list 1 2 3 4)) (1 4 9 16)
Here are two different definitions of square-list. Complete both of them by filling in the missing expressions:
(define (square-list items) (if (null? items) nil (cons <??> <??>))) (define (square-list items) (map <??> <??>))
Answer:
(define (square-list items) (if (null? items) '() (cons (* (car items) (car items)) (square-list (cdr items))))) (define (square-list items) (map (lambda (x) (* x x)) items))
Exercise 2.22. Louis Reasoner tries to rewrite the first square-list procedure of exercise 2.21 so that it evolves an iterative process:
(define (square-list items) (define (iter things answer) (if (null? things) answer (iter (cdr things) (cons (square (car things)) answer)))) (iter items nil))
Unfortunately, defining square-list this way produces the answer list in the reverse order of the one desired. Why?

Louis then tries to fix his bug by interchanging the arguments to cons:
(define (square-list items) (define (iter things answer) (if (null? things) answer (iter (cdr things) (cons answer (square (car things)))))) (iter items nil))
This doesn't work either. Explain.

Answer: In the first procedure iter starts by attaching the first item from the input list to answers. Subsequent items are consed to answers, thereby ending up *before* the first. Hence answers ends up having the square of the items in reverse order.

The second approach tried by Louis gets the order right. However the end result is not a plain list as he expects. Here the cons operation starts by attaching the empty answer list to the square of the first item. This yields (() . 1) and not (1). Further iterations repeat the same operation with similar results.

Exercise 2.23. The procedure for-each is similar to map. It takes as arguments a procedure and a list of elements. However, rather than forming a list of the results, for-each just applies the procedure to each of the elements in turn, from left to right. The values returned by applying the procedure to the elements are not used at all -- for-each is used with procedures that perform an action, such as printing. For example,
(for-each (lambda (x) (newline) (display x)) (list 57 321 88)) 57 321 88
The value returned by the call to for-each (not illustrated above) can be something arbitrary, such as true. Give an implementation of for-each.

Answer:
(define (for-each proc items) (cond ((not (null? items)) (proc (car items)) (for-each proc (cdr items)))))
Exercise 2.24. Suppose we evaluate the expression (list 1 (list 2 (list 3 4))). Give the result printed by the interpreter, the corresponding box-and-pointer structure, and the interpretation of this as a tree (as in figure 2.6). Answer: The interpreter prints (1 (2 (3 4))). I'll add the pictures once I draw them out using GIMP.

Exercise 2.25. Give combinations of cars and cdrs that will pick 7 from each of the following lists:
(1 3 (5 7) 9) ((7)) (1 (2 (3 (4 (5 (6 7))))))
Answer:
(define x '(1 3 (5 7) 9)) (car (cdr (car (cdr (cdr x))))) 7 (define x '((7))) (car (car x)) 7 (define x '(1 (2 (3 (4 (5 (6 7))))))) (cadr (cadr (cadr (cadr (cadr (cadr x)))))) 7
Exercise 2.26. Suppose we define x and y to be two lists:
(define x (list 1 2 3)) (define y (list 4 5 6))
What result is printed by the interpreter in response to evaluating each of the following expressions:
(append x y) (cons x y) (list x y)
Answer:
(append x y) (1 2 3 4 5 6) (cons x y) ((1 2 3) 4 5 6) (list x y) ((1 2 3) (4 5 6))
Exercise 2.27. Modify your reverse procedure of exercise 2.18 to produce a deep-reverse procedure that takes a list as argument and returns as its value the list with its elements reversed and with all sublists deep-reversed as well. For example,
(define x (list (list 1 2) (list 3 4))) x ((1 2) (3 4)) (reverse x) ((3 4) (1 2)) (deep-reverse x) ((4 3) (2 1))
Answer:
(define (deep-reverse tree) (cond ((null? tree) nil) ((pair? (car tree)) (append (deep-reverse (cdr tree)) (list (deep-reverse (car tree))))) (else (append (deep-reverse (cdr tree)) (list (car tree)))))) (deep-reverse (list (list 1 2) (list 3 4))) ((4 3) (2 1))
Exercise 2.28. Write a procedure fringe that takes as argument a tree (represented as a list) and returns a list whose elements are all the leaves of the tree arranged in left-to-right order. For example,
(define x (list (list 1 2) (list 3 4))) (fringe x) (1 2 3 4) (fringe (list x x)) (1 2 3 4 1 2 3 4)
Answer:
(define (fringe tree) (cond ((null? tree) nil) ((pair? (car tree)) (append (fringe (car tree)) (fringe (cdr tree)))) (else (append (list (car tree)) (fringe (cdr tree))))))
Exercise 2.29. A binary mobile consists of two branches, a left branch and a right branch. Each branch is a rod of a certain length, from which hangs either a weight or another binary mobile. We can represent a binary mobile using compound data by constructing it from two branches (for example, using list):
(define (make-mobile left right) (list left right))
A branch is constructed from a length (which must be a number) together with a structure, which may be either a number (representing a simple weight) or another mobile:
(define (make-branch length structure) (list length structure))
a. Write the corresponding selectors left-branch and right-branch, which return the branches of a mobile, and branch-length and branch-structure, which return the components of a branch.

b. Using your selectors, define a procedure total-weight that returns the total weight of a mobile.

c. A mobile is said to be balanced if the torque applied by its top-left branch is equal to that applied by its top-right branch (that is, if the length of the left rod multiplied by the weight hanging from that rod is equal to the corresponding product for the right side) and if each of the submobiles hanging off its branches is balanced. Design a predicate that tests whether a binary mobile is balanced.

d. Suppose we change the representation of mobiles so that the constructors are
(define (make-mobile left right) (cons left right)) (define (make-branch length structure) (cons length structure))
How much do you need to change your programs to convert to the new representation?

Answer: a. As the mobile is represented as a list the selectors are straight forward to implement.
;; (a) Selectors (define (left-branch mobile) (car mobile)) (define (right-branch mobile) (car (cdr mobile))) (define (branch-length branch) (car branch)) (define (branch-structure branch) (car (cdr branch)))
b. Calculation of total weight is made easier by an utility procedure which calculates the weight of a given branch. These procedure use mutual recursion to calculate the total weight of a given mobile.
;; (b) total-weight (define (branch-weight branch) (if (pair? (branch-structure branch)) (total-weight (branch-structure branch)) (branch-structure branch))) (define (total-weight mobile) (+ (branch-weight (left-branch mobile)) (branch-weight (right-branch mobile))))
c. The test to find out if a mobile is balanced can be similarly written with the help of an utility procedure to find out if its sub-mobiles are balanced.
;; (c) balanced? (define (balanced? mobile) (let ((left (left-branch mobile)) (right (right-branch mobile))) (and (= (torque left) (torque right)) (submobiles-balanced? left) (submobiles-balanced? right)))) (define (torque branch) (* (branch-length branch) (branch-weight branch))) (define (submobiles-balanced? branch) (let ((structure (branch-structure branch))) (or (not (pair? structure)) (balanced? structure))))
d. Only the selectors need to be changed. For instance the right-branch can use (cdr mobile) instead of (car (cadr mobile)).

Exercise 2.30. Define a procedure square-tree analogous to the square-list procedure of exercise 2.21. That is, square-list should behave as follows:
(square-tree (list 1 (list 2 (list 3 4) 5) (list 6 7))) (1 (4 (9 16) 25) (36 49))
Define square-tree both directly (i.e., without using any higher-order procedures) and also by using map and recursion.

Answer:
(define (square-tree tree) (cond ((null? tree) nil) ((not (pair? tree)) (* tree tree)) (else (cons (square-tree (car tree)) (square-tree (cdr tree)))))) ;; using map (define (square-tree tree) (map (lambda (sub-tree) (if (pair? sub-tree) (square-tree sub-tree) (* sub-tree sub-tree))) tree))
Exercise 2.31. Abstract your answer to exercise 2.30 to produce a procedure tree-map with the property that square-tree could be defined as
(define (square-tree tree) (tree-map square tree))
Answer:
(define (tree-map proc tree) (map (lambda (sub-tree) (if (pair? sub-tree) (tree-map proc sub-tree) (proc sub-tree))) tree)) (define (square-tree tree) (tree-map square tree)) ;; another use (define (inc-tree tree) (tree-map inc tree))
Exercise 2.32. We can represent a set as a list of distinct elements, and we can represent the set of all subsets of the set as a list of lists. For example, if the set is (1 2 3), then the set of all subsets is (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3)). Complete the following definition of a procedure that generates the set of subsets of a set and give a clear explanation of why it works:
(define (subsets s) (if (null? s) (list nil) (let ((rest (subsets (cdr s)))) (append rest (map <??> rest)))))
Answer:
(define (subsets s) (if (null? s) (list nil) (let ((rest (subsets (cdr s)))) (append rest (map (lambda (x) (cons (car s) x)) rest)))))
Exercise 2.33. Fill in the missing expressions to complete the following definitions of some basic list-manipulation operations as accumulations:
(define (map p sequence) (accumulate (lambda (x y) <??>) nil sequence)) (define (append seq1 seq2) (accumulate cons <??> <??>)) (define (length sequence) (accumulate <??> 0 sequence))
Answer:
(define (a-map p sequence) (accumulate (lambda (x y) (cons (p x) y)) nil sequence)) (a-map inc (list 1 2 3 4)) (2 3 4 5) (define (a-append seq1 seq2) (accumulate cons seq2 seq1)) (a-append (list 1) (list 3 4)) (1 3 4) (define (length sequence) (accumulate (lambda (x y) (+ y 1)) 0 sequence)) (length (list 1 (list 3 4))) 2
Exercise 2.34. Evaluating a polynomial in x at a given value of x can be formulated as an accumulation. We evaluate the polynomial

using a well-known algorithm called Horner's rule, which structures the computation as

In other words, we start with an, multiply by x, add an-1, multiply by x, and so on, until we reach a0.16 Fill in the following template to produce a procedure that evaluates a polynomial using Horner's rule. Assume that the coefficients of the polynomial are arranged in a sequence, from a0 through an.
(define (horner-eval x coefficient-sequence) (accumulate (lambda (this-coeff higher-terms) <??>) 0 coefficient-sequence))
For example, to compute 1 + 3x + 5x³ + x⁵ at x = 2 you would evaluate
(horner-eval 2 (list 1 3 0 5 0 1))
Answer:
(define (horner-eval x coefficient-sequence) (accumulate (lambda (this-coeff higher-terms) (+ this-coeff (* higher-terms x))) 0 coefficient-sequence))
Exercise 2.35. Redefine count-leaves from section 2.2.2 as an accumulation:
(define (count-leaves t) (accumulate <??> <??> (map <??> <??>)))
Answer:
(define (count-leaves t) (accumulate + 0 (map (lambda (x) 1) (fringe t))))
Exercise 2.36. The procedure accumulate-n is similar to accumulate except that it takes as its third argument a sequence of sequences, which are all assumed to have the same number of elements. It applies the designated accumulation procedure to combine all the first elements of the sequences, all the second elements of the sequences, and so on, and returns a sequence of the results. For instance, if s is a sequence containing four sequences, ((1 2 3) (4 5 6) (7 8 9) (10 11 12)), then the value of (accumulate-n + 0 s) should be the sequence (22 26 30). Fill in the missing expressions in the following definition of accumulate-n:
(define (accumulate-n op init seqs) (if (null? (car seqs)) nil (cons (accumulate op init <??>) (accumulate-n op init <??>))))
Answer:
(define (accumulate-n op init seqs) (if (null? (car seqs)) nil (cons (accumulate op init (map (lambda (x) (car x)) seqs)) (accumulate-n op init (map (lambda (x) (cdr x)) seqs)))))
Exercise 2.37. Suppose we represent vectors v = (vi) as sequences of numbers, and matrices m = (mij) as sequences of vectors (the rows of the matrix). For example, the matrix

is represented as the sequence ((1 2 3 4) (4 5 6 6) (6 7 8 9)). With this representation, we can use sequence operations to concisely express the basic matrix and vector operations. These operations (which are described in any book on matrix algebra) are the following:

We can define the dot product as
(define (dot-product v w) (accumulate + 0 (map * v w)))
Fill in the missing expressions in the following procedures for computing the other matrix operations. (The procedure accumulate-n is defined in exercise 2.36.)
(define (matrix-*-vector m v) (map <??> m)) (define (transpose mat) (accumulate-n <??> <??> mat)) (define (matrix-*-matrix m n) (let ((cols (transpose n))) (map <??> m)))
Answer:
;; Matrix * Vector (define (matrix-*-vector m v) (map (lambda (x) (dot-product x v)) m)) ;; Transpose Matrix (define (transpose mat) (accumulate-n cons nil mat)) ;; Matrix * Matrix (define (matrix-*-matrix m n) (let ((cols (transpose n))) (map (lambda (x) (map (lambda (y) (accumulate + 0 (accumulate-n * 1 (list x y)))) cols)) m)))
Exercise 2.38. The accumulate procedure is also known as fold-right, because it combines the first element of the sequence with the result of combining all the elements to the right. There is also a fold-left, which is similar to fold-right, except that it combines elements working in the opposite direction:
(define (fold-left op initial sequence) (define (iter result rest) (if (null? rest) result (iter (op result (car rest)) (cdr rest)))) (iter initial sequence))
What are the values of
(fold-right / 1 (list 1 2 3)) (fold-left / 1 (list 1 2 3)) (fold-right list nil (list 1 2 3)) (fold-left list nil (list 1 2 3))
Give a property that op should satisfy to guarantee that fold-right and fold-left will produce the same values for any sequence.

Answer:
(fold-right / 1 (list 1 2 3)) 1 1/2 (fold-left / 1 (list 1 2 3)) 1/6 (fold-right list nil (list 1 2 3)) (1 (2 (3 ()))) (fold-left list nil (list 1 2 3)) (((() 1) 2) 3)
In order for fold-right and fold-left to yield identical results op should be associative. For instance take the + operator.
(fold-right + 1 (list 1 2 3)) 7 (fold-left + 1 (list 1 2 3)) 7
Exercise 2.39. Complete the following definitions of reverse (exercise 2.18) in terms of fold-right and fold-left from exercise 2.38:
(define (reverse sequence) (fold-right (lambda (x y) <??>) nil sequence)) (define (reverse sequence) (fold-left (lambda (x y) <??>) nil sequence))
Answer:
(define (reverse sequence) (fold-right (lambda (x y) (if (null? y) (list x) (append y (list x)))) nil sequence)) (define (reverse sequence) (fold-left (lambda (x y) (if (null? x) (list y) (append (list y) x))) nil sequence))
Exercise 2.40. Define a procedure unique-pairs that, given an integer n, generates the sequence of pairs (i,j) with 1< j< i< n. Use unique-pairs to simplify the definition of prime-sum-pairs given above.

Answer:
(define (unique-pairs n) (flatmap (lambda (i) (map (lambda (j) (list i j)) (enumerate-interval 1 (- i 1)))) (enumerate-interval 1 n)))
Exercise 2.41. Write a procedure to find all ordered triples of distinct positive integers i, j, and k less than or equal to a given integer n that sum to a given integer s.

Answer:
(define (generate-triples n) (flatmap (lambda (i) (flatmap (lambda (j) (map (lambda (k) (list i j k)) (enumerate-interval 1 (- j 1)))) (enumerate-interval 1 (- i 1)))) (enumerate-interval 1 n))) (define (find-triples n s) (define (sum-equal-s? triple) (let ((a (car triple)) (b (cadr triple)) (c (caddr triple))) (= (+ a b c) s))) (filter sum-equal-s? (generate-triples n)))
Exercise 2.42.

Figure 2.8: A solution to the eight-queens puzzle.

The ``eight-queens puzzle'' asks how to place eight queens on a chessboard so that no queen is in check from any other (i.e., no two queens are in the same row, column, or diagonal). One possible solution is shown in figure 2.8. One way to solve the puzzle is to work across the board, placing a queen in each column. Once we have placed k - 1 queens, we must place the kth queen in a position where it does not check any of the queens already on the board. We can formulate this approach recursively: Assume that we have already generated the sequence of all possible ways to place k - 1 queens in the first k - 1 columns of the board. For each of these ways, generate an extended set of positions by placing a queen in each row of the kth column. Now filter these, keeping only the positions for which the queen in the kth column is safe with respect to the other queens. This produces the sequence of all ways to place k queens in the first k columns. By continuing this process, we will produce not only one solution, but all solutions to the puzzle.

We implement this solution as a procedure queens, which returns a sequence of all solutions to the problem of placing n queens on an n× n chessboard. Queens has an internal procedure queen-cols that returns the sequence of all ways to place queens in the first k columns of the board.
(define (queens board-size) (define (queen-cols k) (if (= k 0) (list empty-board) (filter (lambda (positions) (safe? k positions)) (flatmap (lambda (rest-of-queens) (map (lambda (new-row) (adjoin-position new-row k rest-of-queens)) (enumerate-interval 1 board-size))) (queen-cols (- k 1)))))) (queen-cols board-size))
In this procedure rest-of-queens is a way to place k - 1 queens in the first k - 1 columns, and new-row is a proposed row in which to place the queen for the kth column. Complete the program by implementing the representation for sets of board positions, including the procedure adjoin-position, which adjoins a new row-column position to a set of positions, and empty-board, which represents an empty set of positions. You must also write the procedure safe?, which determines for a set of positions, whether the queen in the kth column is safe with respect to the others. (Note that we need only check whether the new queen is safe -- the other queens are already guaranteed safe with respect to each other.)

Answer:
(define empty-board (list nil)) (define (adjoin-position new-row k rest-of-queens) (if (null? (car rest-of-queens)) (list (list k new-row)) (cons (list k new-row) rest-of-queens))) (define (safe? k positions) (define (iter new-pos others) (if (null? others) #t (let ((other-pos (car others))) (if (row-col-or-dia-matches? new-pos other-pos) #f (iter new-pos (cdr others)))))) (if (= k 1) #t (iter (car positions) (cdr positions)))) (define (row-col-or-dia-matches? new-position other-position) (or (same-row? new-position other-position) (same-col? new-position other-position) (same-diagonal? new-position other-position))) (define (same-row? pos1 pos2) (= (cadr pos1) (cadr pos2))) (define (same-col? pos1 pos2) (= (car pos1) (car pos2))) (define (same-diagonal? pos1 pos2) (let ((k1 (car pos1)) (k2 (car pos2)) (r1 (cadr pos1)) (r2 (cadr pos2))) (= (abs (- k1 k2)) (abs (- r1 r2)))))
Exercise 2.43. Louis Reasoner is having a terrible time doing exercise 2.42. His queens procedure seems to work, but it runs extremely slowly. (Louis never does manage to wait long enough for it to solve even the 6× 6 case.) When Louis asks Eva Lu Ator for help, she points out that he has interchanged the order of the nested mappings in the flatmap, writing it as
(flatmap (lambda (new-row) (map (lambda (rest-of-queens) (adjoin-position new-row k rest-of-queens)) (queen-cols (- k 1)))) (enumerate-interval 1 board-size))
Explain why this interchange makes the program run slowly. Estimate how long it will take Louis's program to solve the eight-queens puzzle, assuming that the program in exercise 2.42 solves the puzzle in time T.

Answer: Louis is breaking a well known rule of thumb in programming - namely to avoid expensive operations in inner loops. His code is calling the expensive recursive call to queen-cols in the inner loop.

I am not able to figure out how much time Louis' procedure will take to run in terms of T. If you have an answer/explanation do let me know.

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