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
(+ 5 3 4)
(- 9 1)
(/ 6 2)
(+ (* 2 4) (- 4 6))
(define a 3)
(define b (+ a 1))
(+ a b (* a b))
(= a b)
(if (and (> b a) (< b (* a b)))
b
a)
(cond ((= a 4) 6)
((= b 4) (+ 6 7 a))
(else 25))
(+ 2 (if (> b a) b a))
(* (cond ((> a b) a)
((< a b) b)
(else -1))
(+ a 1))
Solution
10
12
8
3
19
4
16
6
16
Exercise 1.2.
Translate the following expression into prefix form
5 + ⅓ + (2 - (3 - (6 + ⅓)))
————————————————————————————
3(6 - 2)(3 - 7)
Solution
(/
(+ 5
1/3
(- 2
(- 3
(+ 6 1/3))))
(* 3
(- 6 2)
(- 3 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.
Solution
(define (sum-squares-largest-two a b c)
(if (> a b)
(if (> b c)
(+ (sq a) (sq b))
(+ (sq a) (sq c)))
(if (> a c)
(+ (sq a) (sq b))
(+ (sq b) (sq c)))))
(define (sq x)
(* x x))
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))
Solution
If b is larger than zero, the + operation is used to combine a and b, otherwise the - operation is used. The latter operation negates the negative (or zero) value of b, and, in effect, adds the absolute value of b to a.
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.)
Solution
In the case of normal-order evaluation, (test 0 (p)) is evaluated as follows:
(test 0 (p))
(if (= 0 0)
0
(p)
(if (= 0 0)
0
(p)
(if #t
0
(p)
0
In the applicative order, (test 0 (p)) is evaluated as follows:
(test 0 (p))
(test 0 (p))
(test 0 ((p)))
(test 0 (((p))))
...
The interpreter keeps adding parentheses around (p) until infinity, and there will never be a result printed, because it will take forever to evaluate the expression (test 0 (p)).
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.
Solution
The program goes into an endless loop, because it keeps evaluating (sqrt-iter (improve guess x) x) with new values for guess, adding a new-if in each iteration after the existing new-if.
The reason that this happens is because if is a keyword and
(if predicate consequent alternative)
is a special case, instead of a regular combination or a procedure (like new-if). This means the order in which terms are evaluated in the if special form is different than in the new-if procedure.
The special form if evaluates the predicate first and if it returns a non-false value (everything else than #f), it evaluates the consequence, never evaluating the alternative. This means that if there is a base case, the recursion will end at some point. In the original definition there is such a base case, namely when the absolute value of the difference between the square of the guess and the number value the sqrt-iter definition consumes is less than a certain constant value.
When the new-if procedure is used, the three argument expressions of the procedure call are evaluated before new-if is applied to the evaluated expressions. In order to evaluate the third argument expression, which is a recurvive call to sqrt-iter, the new-if of that recursive call has to be evaluated first. Of course, this recursive call also has a third argument expression, with the same consequence of calling new-if for that successive recursive call, and so on. The result is that new-if calls are being added to the evaluation process and there is never going to be a base case that ends this. The program gets into an endless loop until the user halt it.
Exercise 1.7.
The good-enough? test used in computing square roots will not be very effective for finding the square roots of very small numbers. Also, in real computers, arithmetic operations are almost always performed with limited precision. This makes our test inadequate for very large numbers. Explain these statements, with examples showing how the test fails for small and large numbers. An alternative strategy for implementing good-enough? is to watch how guess changes from one iteration to the next and to stop when the change is a very small fraction of the guess. Design a square-root procedure that uses this kind of end test. Does this work better for small and large numbers?
Solution
For x < 1e-6, the square root of x is always smaller than 0.001, so the absolute value of the difference between the square of guess and x will always be smaller than 0.001, and the result of good-enough? will always be a true value.
In real computers, if x is sufficiently large, the number of decimal places will be too small to hold enough precision to let guess² close in on x.
(define (sqrt x)
(sqrt-iter 2.0 1.0 x))
(define (sqrt-iter old-guess guess x)
(if (good-enough? old-guess guess)
guess
(sqrt-iter guess (improve guess x)
x)))
(define (good-enough? old-guess guess)
(<
(if (< old-guess guess)
(/ guess old-guess)
(/ old-guess guess))
1.001))
(define (improve guess x)
(average guess (/ x guess)))
(define (average x y)
(/ (+ x y) 2))
Exercise 1.8.
Newton's method for cube roots is based on the fact that if y is an approximation to the cube root of x, then a better approximation is given by the value
x/y2 + 2y
—————————
3
Use this formula to implement a cube-root procedure analogous to the square-root procedure. (In section 1.3.4 we will see how to implement Newton's method in general as an abstraction of these square-root and cube-root procedures.)
Solution
(define (cube-root x)
(cube-root-iter 2.0 1.0 x))
(define (cube-root-iter old-guess guess x)
(if (good-enough? old-guess guess)
guess
(cube-root-iter guess (improve guess x)
x)))
(define (good-enough? old-guess guess)
(<
(if (< old-guess guess)
(/ guess old-guess)
(/ old-guess guess))
1.001))
(define (improve guess x)
(/ (+ (/ x (sqr guess)) (* 2 guess)) 3))
No comments:
Post a Comment