Skip to content

Latest commit

 

History

History
211 lines (174 loc) · 5.32 KB

ch1.org

File metadata and controls

211 lines (174 loc) · 5.32 KB

SICP Chapter 1

Building Abstractions with Procedures

The Elements of Programming

1.1

Determine the result of each expression

10 ;  10
(+ 5 3 4) ;  10
(- 9 1);  8
(/ 6 2);  3
(+ (* 2 4) (- 4 6));  6
(define a 3);  "unspecified" (but a is three!)
(define b (+ a 1));  "unspecified" (but b is four!)
(+ 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
(* (cond ((> a b) a)
         ((< a b) b)
         (else -1))
   (+ a 1));  16

1.2

Translate the following into prefix form:

\frac{5+4+(2-(3-(6+\frac{4}{5})))}{3(6-2)(2-7)}

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

1.3

Define a procedure that takes three numbers as arguments and returns the sum of the squares of the two larger numbers

(define (sum-of-squares-of-te-two-biggest a b c)
  (define (square x) (* x x))
  (define (min a b c)
    (cond ((< a b c) a)
          ((< b c) b)
          (else c)))
  (- (+ (square a) (square b) (square c))
     (square (min a b c))))

(sum-of-squares-of-te-two-biggest 3 5 10);  125

1.4

Describe the behavior of the following function in terms of combining compound expressions:

(define (a-plus-abs-b a b)
  ((if (> b 0) + -) a b))

As a result of the execution of the “if” procedure, one of the procedures “+” or “-” is returned and applied to the arguments “a” and “b”

1.5

Describe the difference in behavior of the following code for applicative-order and normal-order evaluation:

(define (p) (p))

(define (test x y)
  (if (= x 0)
      0
      y))

(test 0 (p))

In applicative order evaluation the call to “test” never completes, because executing “p” executes “p” which executes “p” (and so on). Under normal-order evaluation the application of “p” is never attempted because the test “x = 0” is true and the else branch is never executed.

1.6

Given the following replacement for the built-in special form “if” and the proceeding definition of an iterative square root calculator, what happens when sqrt-iter is applied?

(define (new-if condition then otherwise)
  (cond (condition then)
        (else otherwise)))

(define (sqrt-iter guess x)
  (new-if (good-enough? guess x) guess
          (sqrt-iter (improve guess x) x)))

Because new-if is not a special form, its “else” case is always evaluated in applicative order evaluation. The “escape clause” will never be able to end evaluation and the program will recurse infinitely (or have a stack overflow, depending on what happens inside “improve”).

1.7

The “good-enough?” procedure uses a fixed value (0.001) to test the guess. For very small numbers, the margin of error allowed by 0.001 is too large to get an accurate guess. For large numbers, the fixed value is too small and results in extremely long runtime when the guess was already accurate in the given scenario.

(define (sqrt-iter guess x)
  (if (good-enough? guess (improve guess x)) (exact->inexact guess)
      (sqrt-iter (improve guess x) x)))

(define (good-enough? guess improved-guess)
  (< (abs (- guess improved-guess)) 0.001))

(define (improve guess x)
  (let ((avg (lambda (a b) (/ (+ a b) 2))))
    (avg guess (/ x guess))))

The new set of procedures observes the diminishing value of “improve” and when the difference between the guess and an improved guess is small enough, considers it accurate.

1.8

Newton’s method for cube roots defines the improvement of a guess to be

\frac{\frac{x}{y^{2}}+2y}{3}

Use the formula to implement a cube-root procedure similar to the previous square root.

(define (cbrt-iter guess x)
  (if (good-enough? guess (improve guess x)) (exact->inexact guess)
      (cbrt-iter (improve guess x) x)))

(define (good-enough? guess improved-guess)
  (< (abs (- guess improved-guess)) 0.001))

(define (improve guess x)
  (/ (+ (/ x (* guess guess)) (* 2 guess))
     3))

1.9

Observe the two procedures below for implementing addition.

(define (inc x)
  (1+ x))

(define (dec x)
  (1- x))

(define (+ a b)
  (if (= a 0)
      b
      (inc (+ (dec a) b))))

(define (+' a b)
  (if (= a 0)
      b
      (+' (dec a) (inc b))))

;; (+ 3 3)
;; (inc (+ 2 3))
;; (inc (inc (+ 1 3)))
;; (inc (inc (inc (+ 0 3))))
;; (inc (inc (inc 3)))
;; (inc (inc 4))
;; (inc 5)
;; 6
;; (+' 3 3)
;; (+' 2 4)
;; (+' 1 5)
;; (+' 0 6)
;; 5
  • + is recursive and its execution space grows with a.
  • +’ is iterative and its execution space does not grow with a.

1.10

The following defines “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))))))

(A 1 10);  1024
(A 2 4);  65536
(A 3 3);  65536

(define (f n) (A 0 n)); f(n) = 2n
(define (g n) (A 1 n)); g(n) = 2n * 2(n-1) ... * 2
(define (h n) (A 2 n)); h(n) = 2^n
(define (k n) (* 5 n n)); k(n) = 5n^2