# 1.1 The Elements of Programming
# 1.1.1 Expressions
486 => 486
(+ 137 349) => 486
(- 1000 334) => 666
(* 5 99) => 495
(/ 10 5) => 2
(+ 2.7 10) => 12.7
(+ 21 35 12 7) => 75
(* 25 4 12) => 1200
(+ (* 3 5) (- 10 6)) => 19
(+ (* 3 (+ (* 2 4) (+ 3 5))) (+ (- 10 7) 6)) => 57# 1.1.2 Naming and the Environment
(define size 2)
size => 2
(* 5 size) => 10
(define pi 3.14159)
(define radius 10)
(* pi (* radius radius)) ~> 314.159
(define circumference (* 2 pi radius))
circumference ~> 62.8318# 1.1.3 Evaluating Combinations
(* (+ 2 (* 4 6))
(+ 3 5 7))
=> 390# 1.1.4 Compound Procedures
(define (square x) (* x x))
(square 21) => 441
(square (+ 2 5)) => 49
(square (square 3)) => 81
(define (sum-of-squares x y)
(+ (square x) (square y)))
(sum-of-squares 3 4) => 25
(define (f a)
(sum-of-squares (+ a 1) (* a 2)))
(f 5) => 136# 1.1.5 The Substitution Model for Procedure Application
Applicative-order evaluation:
(f 5)
=> (sum-of-squares (+ 5 1) (* 5 2))
=> (+ (square 6) (square 10))
=> (+ (* 6 6) (* 10 10))
=> (+ 36 100)
=> 136Normal-order evaluation:
(f 5)
=> (sum-of-squares (+ 5 1) (* 5 2))
=> (+ (square (+ 5 1)) (square (* 5 2)))
=> (+ (* (+ 5 1) (+ 5 1)) (* (* 5 2) (* 5 2)))
=> (+ (* 6 6) (* 10 10))
=> (+ 36 100)
=> 136# 1.1.6 Conditional Expressions and Predicates
(define (abs x)
(cond ((> x 0) x)
((= x 0) 0)
((< x 0) (- x))))
(define (abs x)
(cond ((< x 0) (- x))
(else x)))
(define (abs x)
(if (< x 0)
(- x)
x))
(define (>= x y) (or (> x y) (= x y)))
(define (>= x y) (not (< x y)))# Exercise 1.1
10 => 10
(+ 5 3 4) => 12
(- 9 1) => 8
(/ 6 2) => 3
(+ (* 2 4) (- 4 6)) => 6
(define a 3)
(define b (+ a 1))
(+ 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
(/ (+ 5 4 (- 2 (- 3 (+ 6 4/5))))
(* 3 (- 6 2) (- 2 7)))
=> -37/150# Exercise 1.3
(define (f a b c)
(cond ((and (<= a b) (<= a c))
(+ (* b b) (* c c)))
((and (<= b a) (<= b c))
(+ (* a a) (* c c)))
((and (<= c a) (<= c b))
(+ (* a a) (* b b)))))
(f 1 2 3) => 13
(f 3 2 1) => 13# Exercise 1.4
(define (a-plus-abs-b a b)
((if (> b 0) + -) a b))The operator evaluates to + (addition) when b is positive, and to - (subtraction) when b is negative. Subtracting a negative is equivalent to adding its absolute value, so this procedure returns in all cases.
# Exercise 1.5
(define (p) (p))
(define (test x y)
(if (= x 0) 0 y))
(test 0 (p)) =>...With applicative-order evaluation, the expression will never return a value because the interpreter tries to evaluate (p) and enters endless recursion.
With normal-order evaluation, the expression will evaluate to zero. The (p) expression is never evaluated because it is not necessary to do so.
# 1.1.7 Example: Square Roots by Newton’s Method
(define (sqrt-iter guess x)
(if (good-enough? guess x)
guess
(sqrt-iter (improve guess x) x)))
(define (improve guess x)
(average guess (/ x guess)))
(define (average x y)
(/ (+ x y) 2))
(define (good-enough? guess x)
(< (abs (- (square guess) x)) 0.001))
(define (sqrt x)
(sqrt-iter 1.0 x))
(sqrt 9)
~> 3.00009155413138
(sqrt (+ 100 37))
~> 11.704699917758145
(sqrt (+ (sqrt 2) (sqrt 3)))
~> 1.7739279023207892
(square (sqrt 1000))
~> 1000.000369924366# Exercise 1.6
(define (new-if predicate then-clause else-clause)
(cond (predicate then-clause)
(else else-clause)))
(new-if (= 2 3) 0 5) => 5
(new-if (= 1 1) 0 5) => 0
(define (sqrt-iter guess x)
(new-if (good-enough? guess x)
guess
(sqrt-iter (improve guess x) x)))
(paste (:1.1.7 sqrt))
(sqrt 9) =>...When Alyssa attempts to use this to compute square roots, it will not work. The sqrt-iter procedure gets stuck in infinite recursion because the new-if combination always evaluates both clauses, so it always evaluates the recursive call.
# Exercise 1.7
The good-enough? predicate does not work well for small numbers because the tolerance is fixed. If the number is smaller than the tolerance, the result will be hopelessly inaccurate, like measuring an atom with a yard stick.
(sqrt 0) ~> 0.03125 ; should be 0
(sqrt 1e-20) ~> 0.03125 ; should be 1e-10It is also inadequate for very large numbers. With limited precision, it is impossible to represent small differences between large numbers. This means the algorithm might never terminate, because the guess never satisfies good-enough? no matter how many times improve is called.
(sqrt 1e14) ~> 1e7
(sqrt 1e21) =>...Here is an alternative implementation of sqrt that watches how guess changes from one iteration to the next and stops when the change is a very small fraction of the guess.
(define (good-enough? g1 g2)
(or (zero? g2)
(< (/ (abs (- g2 g1)) g1)
0.001)))
(define (sqrt-iter guess x)
(let ((better (improve guess x)))
(if (good-enough? guess better)
guess
(sqrt-iter better x))))
(set! sqrt (lambda (x) (sqrt-iter 1.0 x)))(We use set! because shadowing imports with define is not allowed.)
The results for small numbers are much better. It works for zero even though the guess is always reduced by 50%, because eventually it reaches the smallest representable floating-point number and dividing that produces zero.
(sqrt 0) ~> 0
(sqrt 1e-20) ~> 1e-10For large numbers, it works better in that it always terminates. However, the results are less precise because “a small fraction” change in guess can be fairly large when the guesses themselves are very large.
(sqrt 1e14) ~> 1.0000029650278373e7
(sqrt 1e20) ~> 1.0000021484861237e10# Exercise 1.8
(define (cube x) (* x x x))
(define (cbrt-iter guess x)
(if (good-enough? guess x)
guess
(cbrt-iter (improve guess x) x)))
(define (improve guess x)
(/ (+ (/ x (square guess))
(* 2 guess))
3))
(define (good-enough? guess x)
(< (abs (- (cube guess) x)) 0.001))
(define (cbrt x)
(cbrt-iter 1.0 x))
(cbrt 8) ~> 2.000004911675504# 1.1.8 Procedures as Black-Box Abstractions
The following two procedures should be indistinguishable:
(define (square x) (* x x))
(define (square x) (exp (+ (log x) (log x))))These should be indistinguishable as well:
(define (square x) (* x x))
(define (square y) (* y y))Using block structure:
(define (sqrt x)
(define (good-enough? guess x)
(< (abs (- (square guess) x)) 0.001))
(define (improve guess x) (average guess (/ x guess)))
(define (sqrt-iter guess x)
(if (good-enough? guess x)
guess
(sqrt-iter (improve guess x) x)))
(sqrt-iter 1.0 x))Without passing x around:
(define (sqrt x)
(define (good-enough? guess)
(< (abs (- (square guess) x)) 0.001))
(define (improve guess)
(average guess (/ x guess)))
(define (sqrt-iter guess)
(if (good-enough? guess)
guess
(sqrt-iter (improve guess))))
(sqrt-iter 1.0))