TableOfContents

Building Abstractions with Procedures

1. The Elements of Programming

1.1. Expressions

1. 486

      1 486
   

2. (+ 137 349)
   486
   (- 1000 334)
   666
   (* 5 99)
   495
   (/ 10 5)
   2
   (+ 2.7 10)
   12.7

      1 137 + 349
      2 1000 - 334
      3 5 * 99
      4 10 / 5
      5 2.7 + 10
   

3. (+ 21 35 12 7)
   75
   
   (* 25 4 12)
   1200

      1 21 + 35 + 12 + 7
      2 25 * 4 * 12
   

   或者

   reduce(int.__add__, [21, 35, 12, 7])
   reduce(int.__mul__, [25, 4, 12])

4. (+ (* 3 5) (- 10 6))
   19

      1 (3 * 5) + (10 - 6)
   

5. (+ (* 3
         (+ (* 2 4)
            (+ 3 5)))
      (+ (- 10 7)
         6))

      1 (3 * ((2*4)+(3+5)) ) + ((10-7)+6)
   

1.2. Naming and the Environment

1. (define size 2)

      1 size = 2
   

2. size
   2
   (* 5 size)
   10

      1 size
      2 5 * size
   

3. (define pi 3.14159)
   (define radius 10)
   (* pi (* radius radius))
   314.159
   (define circumference (* 2 pi radius))
   circumference
   62.8318

      1 pi = 3.14159
      2 radius = 10
      3 pi * (radius * radius)
      4 circumference = 2 * pi * radius
      5 circumference
   

1.3. Evaluating Combinations

1. (* (+ 2 (* 4 6))
      (+ 3 5 7))

      1 (2+(4*6)) * (3+5+7)
   

1.4. Compound Procedures

1. (define (square x) (* x x))

      1 square = lambda x: x*x
   

2. (square 21)
   441
   
   (square (+ 2 5))
   49
   
   (square (square 3))
   81

      1 square(21)
      2 square(2+5)
      3 square(square(3))
   

3. (define (sum-of-squares x y)
     (+ (square x) (square y)))
   
   (sum-of-squares 3 4)
   25

      1 sum_of_squares = lambda x, y: square(x) + square(y)
      2 sum_of_squares(3, 4)
   

4. (define (f a)
     (sum-of-squares (+ a 1) (* a 2)))
   
   (f 5)
   136

      1 f = lambda a:sum_of_squares(a+1, a*2)
      2 f(5)
   

1.5. The Substitution Model for Procedure Application

1.6. Conditional Expressions and Predicates

1. (define (abs x)
     (cond ((> x 0) x)
           ((= x 0) 0)
           ((< x 0) (- x))))

      1 abs = lambda x: x if x > 0 else ( 0 if x == 0 else (-x if x < 0 else 0))
   

   或者

      1 abs = lambda x: x if x > 0 else (0 if x == 0 else -x)
   

2. (define (abs x)
     (cond ((< x 0) (- x))
           (else x)))

      1 abs = lambda x: -x if x < 0 else x
   

3. (define (abs x)
     (if (< x 0)
         (- x)
         x))

   abs = lambda x: -x if x < 0 else x

4. (and (> x 5) (< x 10))

      1 x > 5 and x < 10
   

5. (define (>= x y)
     (or (> x y) (= x y)))

      1 greater_or_equal = lambda x, y: x>y or x==y
   

6. (define (>= x y)
     (not (< x y)))

      1 greater_or_equal = lambda x, y: not x < y
   

1.7. Example: Square Roots by Newton's Method

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

      1 sqrt_iter = lambda guess, x: guess if good_enough(guess, x) else sqrt_iter(improve(guess, x), x)
   

2. (define (improve guess x)
     (average guess (/ x guess)))

      1 improve = lambda guess, x: average(guess, x/guess)
   

3. (define (average x y)
     (/ (+ x y) 2))

      1 average = lambda x, y: (x+y)/2.0
   

4. (define (good-enough? guess x)
     (< (abs (- (square guess) x)) 0.001))

      1 good_enough = lambda guess, x: abs(square(guess)-x)< 0.001
   

5. (define (sqrt x)
     (sqrt-iter 1.0 x))

      1 sqrt = lambda x:sqrt_iter(1.0, x)
   

6. (sqrt 9)
   3.00009155413138
   (sqrt (+ 100 37))
   11.704699917758145
   (sqrt (+ (sqrt 2) (sqrt 3)))
   1.7739279023207892
   (square (sqrt 1000))
   1000.000369924366

      1 sqrt(9)
      2 sqrt(100+37)
      3 sqrt(sqrt(2)+sqrt(3))
      4 square(sqrt(1000))
   

1.8. Procedures as Black-Box Abstractions

1. (define (square x) (* x x))
   
   (define (square x) 
     (exp (double (log x))))
   
   (define (double x) (+ x x))

      1 square = lambda x: x*x
      2 from math import exp, log
      3 square = lambda x: exp(double(log(x)))
      4 double = lambda x: x+x
   

2. (define (square x) (* x x))
   
   (define (square y) (* y y))

      1 square = lambda x: x*x
      2 square = lambda y: y*y
   

3. (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))

      1 def sqrt(x):
      2     good_enough = lambda guess, x: abs(square(guess)-x)< 0.001
      3     improve = lambda guess, x: average(guess, x/guess)
      4     sqrt_iter = lambda guess, x: guess if good_enough(guess, x) else sqrt_iter(improve(guess, x), x)
      5     return sqrt_iter(1.0, x)
   

4. (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))

      1 def sqrt(x):
      2     good_enough = lambda guess: abs(square(guess)-x)< 0.001
      3     improve = lambda guess: average(guess, x/guess)
      4     sqrt_iter = lambda guess: guess if good_enough(guess) else sqrt_iter(improve(guess))
      5     return sqrt_iter(1.0)
   

2. Procedures and the Processes They Generate

• 1.2.1 Linear Recursion and Iteration 1.2.2 Tree Recursion 1.2.3 Orders of Growth 1.2.4 Exponentiation 1.2.5 Greatest Common Divisors 1.2.6 Example: Testing for Primality

• 1.3 Formulating Abstractions with Higher-Order Procedures
  • 1.3.1 Procedures as Arguments 1.3.2 Constructing Procedures Using Lambda 1.3.3 Procedures as General Methods 1.3.4 Procedures as Returned Values