My solutions to the exercises in SICP …

10 12 8 3 6 undefined undefined 19 #f 4 16 6 16

(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5) ) ) ) ) (* 3 (- 6 2) (- 2 7) ) )

Alternative formatting:

(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5 ) ) ) ) ) (* 3 (- 6 2 ) (- 2 7 ) ) )

The exercise didn't say what to do if all three numbers are equal, or two numbers are equal and one is bigger. I decided to return *#f* in that case.

(define (a-smaller-b-and-c a b c) (and (< a b) (< a c) ) ) (define (square a) (* a a)) (define (sum-of-two-squares a b) (+ (square a) (square b) ) ) (define (sum-of-squares-of-largest a b c) (cond ( (a-smaller-b-and-c a b c) (sum-of-two-squares b c) ) ( (a-smaller-b-and-c b c a) (sum-of-two-squares c a) ) ( (a-smaller-b-and-c c a b) (sum-of-two-squares a b) ) (#t #f) ) )

*a-plus-abs-b* returns the sum of *a* and the absolute value of *b*. It does so by choosing either *+* or *-* as the operator on the two operands *a* and *b*, *+* if *b* greater zero and therefore positive, and *-* otherwise.

In normal-order evaluation, *p* will not by evaluated by the interpreter. In applicative-order evaluation, it will. The latter spells trouble, for *p* is defined as nothing but a reference to itself, recursively. According to the evaluation rules defined so far, evaluating *p* should send the interpreter into an infinite loop.

At first, I could not come up with any reason why *srqt* should not work as before. I then tested the new code in my Scheme interpreter (does that count as cheating?) and got a "No memory!" error. That meant something was working differently (and fatally so).

I reasoned that something like in 1.5 was happening: some kind of recursion having to do with the evaluation order. But my reasonings did not get much closer to a solution. Surely consequent expressions in the *cond* special form should only be evaluated conditionally, even in applicate-order evaluation? I then got (this surely counts as cheating!) some hints by a friend: *new-if* may encapsulate *cond*, but it is not *cond*. If *new-if* is called on any operators, those operators are therefore evaluated first by ordinary applicate order before being put to use in the encapsulated *cond* statement.

In other words: Evaluation of the special form *if* may leave out evaluation of clauses the condition for which is not met. But the clauses of *new-if* are evaluated completely, no matter whether they get put to use, if applicate-order evaluation is the rule. Calls to a *sqrt* that uses *new-if* therefore lead to an infinite loop.

Failure of *good_enough?* for very small numbers:

> (sqrt 4) 2.000000093 > (sqrt 0.04) 0.2006099041 > (sqrt 0.0004) 0.03540088256

What happens here is *good_enough?* returning *#t* too early. With *x* 0.001 or smaller, this happens for any *guess* the square of which is below 0.001, no matter how precise it is in the digits further to the right. Furthermore, the smaller *x*, the more *improve* converges towards merely dividing *guess* by 2 during its first runs. Only few such divisions are needed to make *guess* fall below the root of 0.001. As a result, *sqrt* on *x* below 0.001 converges towards a single value the smaller *x* becomes: 0.03125, or the first *guess* of 1.00 divided by 2 as often as necessary (five times) to have it fall below the root of 0.001.

Failure of *good_enough?* for very large numbers:

> (sqrt 40000000000000000) 200000000 > (sqrt 4000000000000000000) 2000000000 > (sqrt 400000000000000000000)

(At this point, the interpreter freezes.)

The value 400000000000000000000 confuses all kinds of operations. If put into *good_enough?*, for example, with the start *guess* of 1.00, the sub-expression *(- (square guess) x)*, evaluated first to *(- 1.00 400000000000000000000)*, evaluates not to -399999999999999999999 as expected, but rather to *-9.223372037e+18*. The probable explanation is that the interpreter only works sanely for values the binary machine representations of which fit into 64 bit. Greater values overflow.

The failure on small numbers is repaired by following the *good_enough?* redefinition proposed in the exercise text; the failure on large numbers is not:

(define (good-enough? guess x) (< (prop-diff guess (improve guess x)) 0.001)) (define (prop-diff-a-greater-b a b) (/ 1 (/ a (- a b)))) (define (prop-diff a b) (cond ((> a b) (prop-diff-a-greater-b a b)) ((< a b) (prop-diff-a-greater-b b a)) (#t 0)))

(define (average x y) (/ (+ x y) 2)) (define (abs x) (if (< x 0) (- x) x)) (define (square x) (* x x)) (define (prop-diff-a-greater-b a b) (/ 1 (/ a (- a b)))) (define (prop-diff a b) (cond ((> a b) (prop-diff-a-greater-b a b)) ((< a b) (prop-diff-a-greater-b b a)) (#t 0))) (define (curt x) (curt-iter 1.0 x)) (define (curt-iter guess x) (if (curt-good-enough? guess x) guess (curt-iter (curt-improve guess x) x))) (define (curt-improve guess x) (/ (+ (/ x (square guess)) (* 2 guess)) 3)) (define (curt-good-enough? guess x) (< (prop-diff guess (curt-improve guess x)) 0.001))

(+ 4 5) (if (= 4 0) 5 (inc (+ (dec 4) 5))) (if (#false) 5 (inc (+ (dec 4) 5))) (inc (+ (dec 4) 5)) (inc (+ 3 5)) (inc (if (= 3 0) 5 (inc (+ (dec 3) 5)))) (inc (if (#false) 5 (inc (+ (dec 3) 5)))) (inc (inc (+ (dec 3) 5))) (inc (inc (+ 2 5))) (inc (inc (if (= 2 0) 5 (inc (+ (dec 2) 5))))) (inc (inc (if (#false) 5 (inc (+ (dec 2) 5))))) (inc (inc (inc (+ (dec 2) 5))))) (inc (inc (inc (+ 1 5)))) (inc (inc (inc (if (= 1 0) 5 (inc (+ (dec 1) 5)))))) (inc (inc (inc (if (#false) 5 (inc (+ (dec 1) 5)))))) (inc (inc (inc (inc (+ (dec 1) 5)))))) (inc (inc (inc (inc (+ 0 5))))) (inc (inc (inc (inc (if (= 0 0) 5 (inc (+ (dec 0) 5))))))) (inc (inc (inc (inc (if (#true) 5 (inc (+ (dec 0) 5))))))) (inc (inc (inc (inc 5)))) (inc (inc (inc 6))) (inc (inc 7)) (inc 8) 9

(+ 4 5) (if (= 4 0) 5 (+ (dec 4) (inc 5))) (if (#false) 5 (+ (dec 4) (inc 5))) (+ (dec 4) (inc 5)) (+ 3 6) (if (= 3 0) 6 (+ (dec 3) (inc 6))) (if (#false) 6 (+ (dec 3) (inc 6))) (+ (dec 3) (inc 6)) (+ 2 7) (if (= 2 0) 7 (+ (dec 2) (inc 7))) (if (#false) 7 (+ (dec 2) (inc 7))) (+ (dec 2) (inc 7)) (+ 1 8) (if (= 1 0) 8 (+ (dec 1) (inc 8))) (if (#false) 8 (+ (dec 1) (inc 8))) (+ (dec 1) (inc 8)) (+ 0 9) (if (= 0 0) 9 (+ (dec 0) (inc 9))) (if (#true) 9 (+ (dec 0) (inc 9))) 9

The first procedure's process is recursive: With each recursion, another inc operation is deferred. The second procedure's process is iterative: The number of state variables stays fixed to the initial two (a, b).

(A 1 10) (A (- 1 1) (A 1 (- 10 1))) (A (- 1 1) (A 1 9)) (A 0 (A (- 1 1) (A 1 (- 9 1)))) (A 0 (A (- 1 1) (A 1 8)))) (A 0 (A 0 (A (- 1 1) (A 1 (- 8 1))))) (A 0 (A 0 (A (- 1 1) (A 1 7)))) (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 7 1)))))) (A 0 (A 0 (A 0 (A 0 (A 1 6))))) (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 6 1))))))) (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 5)))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 5 1)))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 4))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 4))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 4 1))))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 3)))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 3 1)))))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 2))))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 2 1))))))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 1)))))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2))))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4)))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16)))))) (A 0 (A 0 (A 0 (A 0 (A 0 32))))) (A 0 (A 0 (A 0 (A 0 64)))) (A 0 (A 0 (A 0 128))) (A 0 (A 0 256)) (A 0 512) 1024 = 2^10

Next one:

(A 2 4) (A (- 2 1) (A 2 (- 4 1))) (A (- 2 1) (A 2 3)) (A 1 (A (- 2 1) (A 2 (- 3 1)))) (A 1 (A (- 2 1) (A 2 2))) (A 1 (A 1 (A (- 2 1) (A 2 (- 2 1))))) (A 1 (A 1 (A (- 2 1) (A 2 1)))) (A 1 (A 1 (A 1 2))) (A 1 (A 1 (A 1 2))) (A 1 (A 1 (A (- 1 1) (A 1 (- 2 1))))) (A 1 (A 1 (A (- 1 1) (A 1 1)))) (A 1 (A 1 (A 0 2))) (A 1 (A 1 4)) (A 1 (A (- 1 1) (A 1 (- 4 1)))) (A 1 (A (- 1 1) (A 1 3))) (A 1 (A 0 (A 1 3))) (A 1 (A 0 (A (- 1 1) (A 1 (- 3 1))))) (A 1 (A 0 (A (- 1 1) (A 1 2)))) (A 1 (A 0 (A 0 (A (- 1 1) (A 1 (- 2 1)))))) (A 1 (A 0 (A 0 (A (- 1 1) (A 1 1))))) (A 1 (A 0 (A 0 (A 0 2)))) (A 1 (A 0 (A 0 4))) (A 1 (A 0 8)) (A 1 16) (A (- 1 1) (A 1 (- 16 1))) (A (- 1 1) (A 1 15)) (A 0 (A 1 15)) (A 0 (A (- 1 1) (A 1 (- 15 1)))) (A 0 (A (- 1 1) (A 1 14))) (A 0 (A 0 (A 1 14)))

(at this point, I get too lazy to go on; I know the pattern from above, y-1 times "(A 0 " followed by "2" followed by the necessary closing brackets …)

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2))))))))))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4)))))))))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8))))))))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16)))))))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 32))))))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 64)))))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 128))))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 256)))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 512))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 1024)))))) (A 0 (A 0 (A 0 (A 0 (A 0 2048))))) (A 0 (A 0 (A 0 (A 0 4096)))) (A 0 (A 0 (A 0 8192))) (A 0 (A 0 16384)) (A 0 32768) 65536 = 2^16

Next one:

(A 3 3) (A (- 3 1) (A 3 (- 3 1))) (A (- 3 1) (A 3 2)) (A 2 (A (- 3 1) (A 3 (- 2 1)))) (A 2 (A (- 3 1) (A 3 1))) (A 2 (A 2 2)) (A 2 (A (- 2 1) (A 2 (- 2 1)))) (A 2 (A (- 2 1) (A 2 1))) (A 2 (A 1 2)) (A 2 (A (- 1 1) (A 1 (- 2 1)))) (A 2 (A (- 1 1) (A 1 1))) (A 2 (A 0 2)) (A 2 4)

(I know from the last evaluation what this leads too …)

65536 = 2^16

f(n) = 2n

g(n) = 2^n

h(n) = 2^(h(n-1)) (the question only dealt with n>=1 – this solution is valid with h(0)=1 as per the Scheme code; alternative notation: "2" followed by n-1 times "^2")

Procedure that leads to a recursive process:

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

Procedure that leads to an iterative process:

(define (f x) (define (iter a b c n) (if (= n 0) a (iter (+ a (* 2 b) (* 3 c)) a b (- n 1)))) (if (< x 3) x (iter 2 1 0 (- x 2))))

This computes the value of the x-th element of the y-th row of Pascal's triangle:

(define (p y x) (cond ((< x 1) 0) ((= 1 x) 1) ((< y x) 0) (else (+ (p (- y 1) x) (p (- y 1) (- x 1))))))

Spent quite some time on this one, without success. Seems my algebra is too bad. Here's some solutions by others:

- https://wizardbook.wordpress.com/2010/11/24/exercise-1-13/
- http://wqzhang.wordpress.com/2009/06/09/sicp-exercise-1-13/
- http://www.kendyck.com/math/sicp/ex1-13.xml
- http://www.billthelizard.com/2009/12/sicp-exercise-113-fibonacci-and-golden.html
- https://www.evernote.com/shard/s100/sh/6a4b59d5-e99f-417c-9ef3-bcf03a4efecd/7e030d4602a0bef5df0d6dd4c2ad47bf

StructureAndInterpretationOfComputerPrograms Facebook20140908-Scheme PlomLerntScheme 2014-09-07 2014-09-08 SICP

Keine Kommentare zu dieser Seite.

Kommentar-Schreiben derzeit nicht möglich: Kein Captcha gesetzt.

PlomWiki-Engine lizensiert unter der AGPLv3. Quellcode verfügbar auf GitHub.