1 Chapter 1. Building Abstractions with Procedures
1.1 The Elements of Programming
1.1.1 Expressions
...
1.1.2 Naming and Environment
...
1.1.3 Evaluating Combinations
...
1.1.4 The Substitution Model for Procedure Application
The Substitution Model:
To apply a compound procedure to arguments, evaluate the body of the procedure with each formal parameter replaced by the corresponding argument.
Application Order versus Normal Order:
Application Order: fully expand and then reduce
Normal Order: evaluate the arguments and then apply
1.1.5 Conditional Expressions and Predicates
1.1.5.1 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.
Solution:
#lang racket/base (module+ test (require akari-sicp/lib/testing) (define a 3) (define b (+ a 1)) (run-tests (describe "Exercise 1.1" (it.eqv? 10 10 "10") (it.eqv? (+ 5 3 4) 12 "(+ 5 3 4)") (it.eqv? (- 9 1) 8 "(- 9 1)") (it.eqv? (/ 6 2) 3 "(/ 6 2)") (it.eqv? (/ 6 2) 3 "(/ 6 2)") (it.eqv? (+ (* 2 4) (- 4 6)) 6 "(+ (* 2 4) (- 4 6))") (it.eqv? (+ a b (* a b)) 19 "(+ a b (* a b))") (it.false (= a b) "(= a b)") (it.eqv? (if (and (> b a) (< b (* a b))) b a) b "(if (and (> b a) (< b (* a b))) b a)") (it.eqv? (cond [(= a 4) 6] [(= b 4) (+ 6 7 a)] [else 25]) 16 "(cond [(= a 4) 6] [(= b 4) (+ 6 7 a)] [else 25])") (it.eqv? (+ 2 (if (> b a) b a)) 6 "(+ 2 (if (> b a) b a))") (it.eqv? (* (cond [(> a b) a] [(< a b) b] [else -1]) (+ a 1)) 16 "(* (cond [(> a b) a] [(< a b) b] [else -1]) (+ a 1))"))))
1.1.5.2 Exercise 1.2
Translate the following expression into prefix form
\frac{5 + 4 + (2 - (3 - (6 + \frac{4}{5})))}{3 (6 - 2) (2 - 7)}
Solution:
#lang racket/base (define x (/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5))))) (* 3 (- 6 2) (- 2 7)))) (module+ test (require akari-sicp/lib/testing) (expect [x => (- (/ 37 150))]))
1.1.5.3 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:
1.1.5.4 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 > 0, then apply the parameters a and b to the function +, produce the result of a + b
if b < 0, then apply the parameters a and b to the function -, produce the result of a - b
1.1.5.5 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:
Applicative-order evaluation: the interpreter evaluate the arguments first, which means it will evaluate (p) first, producing an infinite loop
Normal-order evaluation: the interpreter will evaluate the predicate first, which is 0, and then return 0 without evaluating (p)
1.1.5.6 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:
Scheme uses applicative-order evaluation by default, so the then-clause and else-clause of new-if are evaluated when passing them to new-if before the predicate is evaluated, which leads to an infinite loop.
1.1.5.7 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:
#lang racket/base (define (average x y) (/ (+ x y) 2)) (define (improve guess x) (average guess (/ x guess))) (define (good-enough? last-guess guess) (< (/ (abs (- guess last-guess)) last-guess) 0.00000001)) (define (sqrt-iter last-guess x) (let ([guess (improve last-guess x)]) (if (good-enough? last-guess guess) guess (sqrt-iter guess x)))) (define (sqrt x) (when (< x 0) (error 'sqrt "negative number")) (if (= x 0) 0 (sqrt-iter 1.0 x))) (module+ test (require akari-sicp/lib/testing) (run-tests (describe "test sqrt" (it "should handle perfect squares" (expect [(sqrt 4) ~> 2] [(sqrt 9) ~> 3] [(sqrt 16) ~> 4] [(sqrt 100) ~> 10])) (it "should handle irrational square roots" (expect [(sqrt 2) ~> 1.4142135623730951] [(sqrt 3) ~> 1.7320508075688772] [(sqrt 5) ~> 2.23606797749979])) (it "should handle extreme large numbers" (expect [(sqrt 1e20) ~> 1e10] [(sqrt 1e50) ~> 1e25] [(sqrt 1e100) ~> 1e50] [(sqrt 1e200) ~> 1e100])) (it "should handle extreme small numbers" (expect [(sqrt 1e-20) ~> 1e-10] [(sqrt 1e-50) ~> 1e-25] [(sqrt 1e-100) ~> 1e-50] [(sqrt 1e-200) ~> 1e-100])) (it "should handle special cases" (expect [(sqrt 0) => 0] [(sqrt 1) ~> 1])) (it "should throw an error for negative numbers" (expect [(sqrt -1) =!> exn:fail?] [(sqrt -100) =!> exn:fail?])) (it "should handle numbers very close to perfect squares" (expect [(sqrt 4.000001) ~> 2.0000002] [(sqrt 3.999999) ~> 1.9999998])))))
1.1.5.8 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
\frac{x/y^2 + 2y}{3}
Use this formula to implement a cube-root procedure analogous to the square-root procedure.
Solution:
#lang racket/base (define (cube-root x) (define (square x) (* x x)) (define (good-enough? last-guess guess) (< (/ (abs (- guess last-guess)) last-guess) 0.001)) (define (improve guess x) (/ (+ (/ x (square guess)) (* 2 guess)) 3)) (define (cube-root-iter last-guess x) (let ([guess (improve last-guess x)]) (if (good-enough? last-guess guess) guess (cube-root-iter guess x)))) (cube-root-iter 1.0 x)) (module+ test (require akari-sicp/lib/testing) (run-tests (describe "cube-root" (it "should return the cube root of a number" (expect [(cube-root 1) => 1] [(cube-root 0) => 0] [(cube-root -1) => -1] [(cube-root 2) ~> 1.2599210498948732] [(cube-root 3) ~> 1.4422495703074083] [(cube-root 4) ~> 1.5874010519681994] [(cube-root 5) ~> 1.7099759474226504] [(cube-root 6) ~> 1.8171205928321397] [(cube-root 7) ~> 1.9129311827745818])))))