开新坑啦！

前言

很早之前就已经接触 《计算机程序的构造和解释》（Structure and Interpretation of Computer Programs，SICP），也曾经大致看完，不过只是单纯的看，没有做习题。所以过后很快就忘了。这次开坑目的是希望能一字一句仔细阅读，完成课后练习，加深对书中概念的理解。

目前暂定为一个小节如 1.1 的笔记和所有习题解答为一篇文章。因为是自己做的，所以不保证答案正确。

目测深坑，可能弃坑，请勿尾随。

笔记

三种方式

  1. 基本表达式，用于展现语言所关注的最简单的元素。
  2. 组合的方式，用于组合最基本的元素。
  3. 抽象的方式，用于组合和操作命名的元素。

这里说的比较抽象。个人理解是第一个基本表达式就是程序的保留字，操作符和内置函数等，如 if while int = 。第二个组合的方式说的是用第一个基本表达式之间的组合。比如 if 和 while 组合可以实现绝大部分的逻辑。第三个抽象的方式就是第二个组合之后的结果，可以将其命名，形成一个个单元，比如函数。这样编写函数的过程本质就是抽象的过程。

数据和过程

数据和过程并不是那么严格区分的。在面向过程式编程中，通常数据和过程比较容易区分。程序的输入可以算作一种数据。函数是一种很典型的过程。例如计算阶乘的程序，接收一个 n 作为输入，n 被视为数据。之后计算出 n 的阶乘，返回结果。计算的步骤就是一个过程。在面向对象中也差不多，只不过数据变成了属性，过程变成了成员函数。函数的参数是一种数据，但如果把过程当作参数传递，那么传递的是过程还是数据呢？也就是说当传递函数指针（或者回调）的时候，数据和过程的界限就不是那么清晰了。在 Lisp 系列的语言中，所有的程序都是 S 表达式，也就是列表。过程是一个列表，数据也是一个列表。所以过程和数据在语言看来是一样的。因此在 Lisp 系列的语言中，编写操作数据的过程和编写操作过程的过程难度差不多。元编程，或者说宏，就是自然而然的思想。

表达式

书中约定了教学语言是 Lisp 方言 Scheme 。语言所用的表达式是 S 表达式。S 表达式使用前缀表示法，操作符放在操作数前面。例如 1 + 2 是这么表示

表示方式 表达式
前缀表达式 + 1 2
中缀表达式 1 + 2
后缀表达式 1 2 +

为什么不用更常用的中缀表达式呢。因为中缀表达式的计算规则有两条，一是先计算优先级大的，二是从左往右计算。你也许听过那个很烂熟的哏：

「一加二乘三等于多少？」

「九啊」

「你个傻〇！是七！」

这个很无聊的哏中展现了 (1 + 2) * 3 = 9 ， 1 + 2 * 3 = 7 。也就是说如果想要改变计算的顺序，就必须使用优先级更高的括号操作符括住表达式。

如果是使用前缀表达式就只需要一条规则，从左往右计算。没有优先级的说法，自然也不需要有括号。比如 1 + 2 * 3 的前缀表达式是 + 1 * 2 3 。

从左往右扫描，看到 + 1 知道要用 1 和其他数字相加，这个数字是多少呢？再看到 * 2 3，原来这个数字是 * 2 3 ，也就是 6，最后就是 + 1 6 也就是 7 。有一点递归返回的感觉。

如果要计算 (1 + 2) * 3 ，那么相应的前缀表达式是 * + 1 2 3 。

计算过程也很简单

* + 1 2 3 ⇒ * 3 3 ⇒ 9

那为什么不用后缀表达式呢？

S 表达式为什么不用不了解。个人觉得后缀表达式真的很丧心病狂，非常反直觉。例如 1 2 + 3 * 是怎么计算的呢？

它不是 1 + 2 * 3 ，也不是从右往左计算的 (3 + 2) * 1 ，而是 (1 + 2) * 3 。

虽说不用中缀表达式可以节省括号，但是 S 表达式里面全是括号啊！摔！

不使用中缀表达式另外一个优点是可以天然地支持多参数。

例如 1 + 2 + 3 的 S 表达式是 (+ (+ 1 2) 3) 。可以写成 (+ 1 2 3) 。

因为中缀表达式操作符两边要有操作数，所以不能很方便的表达多参数的情况。

好好写代码

S 表达式无脑嵌套会非常辣眼睛。比如看到 (+ (* 3 (+ (* 2 4) (+ 3 5))) (+ (- 10 7) 6)) 会一脸懵 X，写成这样就会好很多

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

也就是操作符在前，操作数垂直对齐。

变量绑定与环境

Scheme 使用 define 绑定全局变量。如果不允许声明和绑定变量，那就只能用递归来写程序了，也就是「纯函数式」编程（大雾）。

出现在函数参数列表中的变量称为绑定变量。如 (define (square x) (* x x)) 中的 x 称为绑定变量。

没有被绑定的变量称为自由变量。如 (define (cube x) (* (square x) x)) 中的 square 是自由变量。因为参数列表 cube x 中只有 x ，没有 square 。这意味着 x 的值由调用函数 cube 传入的参数决定，与 cube 死死的绑在了一起。而 square 的值则需要去上下文环境查找。

上下文环境可以简单的理解为储存变量的地方。既然有储存肯定有读取，读取的时候按规则区分为词法作用域和动态作用域。

词法作用域，也称为动态作用域，是大部分语言常用的查找规则。

动态作用域，有些反直觉，早期语言使用的规则。因为环境创建的时候什么事都不用干就是天然的动态作用域。熟悉 JavaScript 的都知道 this关键字吧。这个家伙有很多的异常表现就是因为它是动态作用域。还好 Scheme 出现解决了动态作用域的问题。

词法作用域和动态作用域的区别可以用两句话解释清楚。

替换绑定的变量不影响结果。也就是

(define (square x) (* x x)) 和 (define (square y) (* y y)) 结果是一样的。其实这是 $\alpha$ 变换（大雾）。

函数的定义也是一个变量绑定的过程。在 Scheme 中函数默认返回最后一个计算结果，不需要显式地 return 。

还有一个语法细节，定义变量是 (define a 1) ，定义函数是 (define (square x) (* x x)) 。

语法看似不一致，其实是统一的。可以把 define 看作 = 。式子可以这么理解。

(define a 1) ⇒ a = 1

(define (square x) (* x x)) ⇒ (square x) = (* x x)

求值规则

To evaluate a combination, do the following:

  1. Evaluate the subexpressions of the combination.
  2. Apply the procedure that is the value of the leftmost subexpression (the operator) to the arguments that are the values of the other subexpressions (the operands)

求值表达式，按以下规则进行

  1. 求值子表达式
  2. 应用其操作符于该子表达式

所以这是一个嵌套的求值过程。嵌套结构用树结构很容易表示。如果用树来表示，那么求值的时候相当于树的遍历。

这里没有似乎没有说清楚参数求值是从左往右还是从右往左。

这种求值方式是传值调用（Call by value），这里说的传值调用强调的是求值的时机。

传值调用，也就是在函数调用前，求出每个参数的值。例如平方函数 (define (square x) (* x x)) 在接收参数 5 的调用时是这么求值的。

(square 5) ⇒ (* 5 5) ⇒ 25

在接收参数为 (square 2) 时是这么求值的

(square (square 2)) ⇒ (square (* 2 2)) ⇒ (square 4) ⇒ (* 4 4) ⇒ 16

传值调用在书中被称为 Applicative-order 。

还有一种求值方式是传名调用（Call by name），在书中被称为 Normal-order 。

简单地说是把所有表达式中命名的变量求值完成后，再对整个表达式求值。

比如 (square (square (+ 1 2))) 按传名调用是这样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(square (square (+ 1 2)))

(* (square (+ 1 2)
   (square (+ 1 2))))

(* (* (+ 1 2)
      (+ 1 2)
   (* (+ 1 2)
      (+ 1 2))))
(* (* 3 3)
   (* 3 3))

(* 9 9)

81

如果是传值调用是这样

1
2
3
4
5
6
7
8
9
10
11
(square (square (+ 1 2)))

(square (square 3))

(square (* 3 3))

(square 9)

(* 9 9)

81

在这里两种方式最后的结果一致。但是在参数求值有副作用或者有求值短路等现象出现时，结果就会不一样。习题 1.5 会给出这样的情况。

递归与循环

平方根函数 sqrt-iter 在最后调用了sqrt-iter。也就是自己调用自己。这种方式称为递归。

与递归对应的是迭代。实际上递归更符合人类思维，迭代更符合计算机思维。

递归很容易给人一种计算效率低的印象。但并不是所有的递归都是这样。

像平方根函数这种在函数最后一句只调用自身的递归称为尾递归。

普通的递归在计算到出口后会将结果一层层向上返回，所以需要在堆栈中记录返回地址等相关信息，层数一多很可能就爆栈。

而尾递归因为递归放在尾部，返回后也没有后续可执行内容（continuation），所以可以直接抛弃之前的调用信息。也就是尾递归通过抛弃之前的调用信息而防止爆栈。常见的现代编译器都会将尾递归优化为循环。所以尾递归的效率并不低。

然而并不是所有的递归都能转化为循环。

封装与面向对象

Scheme 允许在函数定义中定义函数，所以通常会看到一个函数，内部定义不少小函数和常量，之后调用这些小函数。

这样把数据和过程包装在一个函数的手段称为封装。

说到封装，很自然就想到了面向对象。毕竟面向对象的三大特性是封装，继承，多态。

说到对象就会想到 class，实际上面向对象跟 class 一点关系都没有。

class是实现面向对象的一种方式但不是唯一方式。 原型链也是一种实现面向对象方式。

现在的面向对象跟 Alan Kay 的面向对象已经不是同一个东西了。

Alan Kay 的面向对象强调封装与消息发送。他认为每一个对象都要有一个 IP 。

如果按照 Alan Kay 的观点大家的面向对象都跑偏了（逃

习题

习题 1.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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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))

这道题所有表达式都不存在命名的函数，所以直接求值，不用考虑求值方式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
10
;; 10 规则 1.1.3 第一条：字面量的值为它们相应的值
(+ 5 3 4)
;; 12 规则 1.1.3 第二条：内置操作符为它们相应的操作符
(- 9 1)
;; 8 是 9 - 1 不是 1 - 9 。参考前缀表达式定义
(/ 6 2)
;; 6/2 = 3
(+ (* 2 4) (- 4 6))
;; (+ 8 (- 2)) = 6
(define a 3)
(define b (+ a 1))
;; 注意此时 b 已经被赋值为 a + 1 = 3 + 1 = 4
(+ a b (* a b))
;;规则 1.1.3 第三条：命名的符号值从环境中获取
;;这里使用了参数从左往右求值的顺序
;;(+ 3 b (* a b))
;;(+ 3 4 (* a b))
;;(+ 3 4 (* 3 b))
;;(+ 3 4 (* 3 4))
;;(+ 3 4 12)
;;19
(= a b)
;;(= 3 b)
;;(= 3 4)
;; #f Scheme 用 #t 和 #f 表示 true 和 false。在脚注 17 中有提到
(if (and (> b a) (< b (* a b)))
    b
    a)
;;(if (and (> 4 3) (< b (* a b))) b a)
;;(if (and #t (< b (* a b))) b a)
;;(if (and #t (< 4 (* a b))) b a)
;;(if (and #t (< 4 (* 3 4))) b a)
;;(if (and #t (< 4 12)) b a)
;;(if (and #t #t) b a)
;;b
;;4
(cond ((= a 4) 6)
      ((= b 4) (+ 6 7 a))
      (else 25))
;;(cond ((= 3 4) 6) ((= b 4) (+ 6 7 a)) (else 25))
;;(cond (#f 6) ((= b 4) (+ 6 7 a)) (else 25))
;;(cond (#f 6) (#t (+ 6 7 a)) (else 25))
;;(+ 6 7 a)
;;(+ 6 7 3)
;;16
(+ 2 (if (> b a) b a))
;;(+ 2 (if (> 4 a) b a))
;;(+ 2 (if (> 4 3) b a))
;;(+ 2 (if #t b a))
;;(+ 2 b)
;;(+ 2 4)
;;6
(* (cond ((> a b) a)
         ((< a b) b)
         (else -1))
   (+ a 1))
;;(* (cond ((> 3 4) a) ((< a b) b) (else -1)) (+ a 1))
;;(* (cond (#f a) ((< a b) b) (else -1)) (+ a 1))
;;(* (cond (#f a) ((< 3 4) b) (else -1)) (+ a 1))
;;(* (cond (#f a) (#t b) (else -1)) (+ a 1))
;;(* (cond (#f a) (#t b) (else -1)) (+ a 1))
;;(* b (+ a 1))
;;(* 4 (+ a 1))
;;(* 4 (+ 3 1))
;;(* 4 4)
;;16

习题 1.2

Exercise 1.2. Translate the following expression into prefix form
$$
\frac {5+4+(2-(3-(6+ \frac 4 3)))} {3(6-2)(2-7)}
$$

先把分子和分母转成前缀表达式，利用前缀表达式支持多参数的特性简化式子，再用 (/ 分子 分母) 连起来即可。

这里说明中缀表达式转前缀表达式的过程

分子

1
2
3
4
5
6
7
(+ 5 
   4
   (- 2
      (- 3
         (+ 6
            (/ 4
               3)))))

分母

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

所以答案是

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

习题 1.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.

从动词可以判断有多少个函数

  1. a procedure that take … return ..
  2. sum of …
  3. squares…

从下往上一个个写回去，square

1
2
(define (square x)
  (* x x))

sum求和

1
2
(define (sum a b)
  (+ a b))

接收三个参数返回最大和次大的两个数。因为加法满足交换律 a + b = b + a 所以只需要确定出最小的数，把比较大的两个数求平方和即可。

1
2
3
4
5
6
7
8
(define (sum-larger-square a b c)
  (if (> a b)
      (if (> b c)
          (sum (square a) (square b))
          (sum (square a) (square c)))
      (if (> a c)
          (sum (square b) (square a))
          (sum (square b) (square c)))))

测试

1
2
3
4
5
6
7
8
(sum-larger-square 1 2 3)
;; 13
(sum-larger-square 6 5 4)
;; 61
(sum-larger-square 7 9 8)
;; 145
(sum-larger-square 1 1 1)
;; 2

习题 1.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:

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

描述函数行为。按语句翻译即可。首先看到函数定义 (define (a-plus-abs-b a b) (...) 这是一个接收两个参数的函数，再看函数体 ((if (> b 0) + -) a b) 如果 b 大于 0 则结果为 + 操作符，否则为 - 操作符。然后将该操作符应用到参数 a b 上。所以答案是

a 加上 b 的绝对值。 （虽然函数名字已经提示得够明显了。）

这道题展示了过程（函数）是可以作为结果返回的。根据b 的正负，返回+ 或 - 。这种做法在 Scheme 中很常见。因为过程（函数）和数据在语言看来没有区别。既然可以返回数字（典型的数据），也自然可以返回函数（典型的过程）。

习题 1.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:

1
2
3
4
5
(define (p) (p))
(define (test x y)
  (if (= x 0)
      0
      y))

Then he evaluates the expression

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

先回顾一下概念

Applicative-order: evaluate the arguments and then apply. 求值参数并应用。

Normal-order: fully expand and then reduce. 完全展开后规约。

先按 applicative-order 展开

1
2
3
4
5
6
7
8
9
10
11
;; applicative-order
(test 0 (p))
;; 挨个求值参数 0 (p)
;; 求值 0 结果为 0 1.1.3 第一条：字面量的值为它们相应的值
(test 0 (p))
;; 求值 (p) 规则 1.1.3 第三条：命名的符号值从环境中获取
;; 环境中 (define (p) (p))
(test 0 ((p)))
;; 求值后又出现 p ，再次对 p 求值
(test 0 (((p))))
;; 递归，没有办法获得具体的值。无限循环

按 normal-order 展开

1
2
3
4
5
6
7
;; normal-order
(test 0 (p))
;; 先完全展开定义的函数，在规约求值
(if (= 0 0) 0 (p))
(if #t 0 (p))
;; 题目中提到 if 语句中的条件判断优先执行，结果只执行相应的分支
0

所以答案是按 applicative-order 执行会无限循环，按 normal-order 执行结果是 0 。

习题 1.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:

1
2
3
(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
        (else else-clause)))

Eva demonstrates the program for Alyssa:

1
2
3
4
(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:

1
2
3
4
5
(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.

按默认的 applicative-order 展开

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
(sqrt-iter 1 2)
;; 根据 applicative-order 先求参数的值
(new-if (good-enough? 1 2)
        1
        (sqrt-iter (improve 1 2)
                   2))
;; 求 (good-enough 1 2) 的值
(new-if (< (abs (- (square 1) 2) 0.001))
        1
        (sqrt-iter (improve 1 2)
                   2))
;; 2 - 1 > 0.001 所以结果是 #f
(new-if #f
        1
        (sqrt-iter (improve 1 2)
                   2))
;;接着求 (sqrt-iter (improve 1 2)2)
(new-if #f
        1
        (sqrt-iter (average 1 (/ 2 1))
                   2))
;;1 和 2 的平均值为 1.5
(new-if #f
        1
        (sqrt-iter 1.5 
                   2))
;; 求值 (sqrt-iter 1.5 2)
(new-if #f
        1
        (new-if (good-enough? 1.5 2)
                1
                (sqrt-iter (improve 1.5 2)
                           2)))
;; 又回到开始的地方。无穷无尽的求值

所以答案是会一直递归下去。无穷无尽。

解决方法是使用宏，宏在求值会先展开后求参数的值。这个后面章节应该会讲。

习题 1.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?

这道题有两个问题。

第一个问题是解释为什么遇到特别小的数和特别大的数时候 good-enough 失效？第二个问题是请设计一个 good-enough

先来看第一个问题。

在遇到特别小的数如0.0001的时候

1
2
3
4
5
6
7
8
9
(sqrt 0.0004)
;;(guess next-guess)
;;(1 0.5002)
;;(0.5002 0.2504998400639744)
;;(0.2504998400639744 0.12604832373535454)
;;(0.12604832373535454 0.06461085492374607)
;;(0.06461085492374607 0.0354008825558513)
;;(0.0354008825558513 0.023350017942701275)
;;0.0354008825558513

正确结果应该是 0.01。那为什么结果是 0.03 呢。

因为在 (if good-enough? guess x) 中 $|0.035^2 - 0.0004| = 0.0008 < 0.001$

也就是误差范围太大了。

在遇到特别大的数$10^{50}$的时候

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
(sqrt 1000000000000000000000000000000000000000000000000000)
;;(guess next-guess)
;;(1 5e+50)
;;(5e+50 2.5e+50)
;;(2.5e+50 1.25e+50)
;;(1.25e+50 6.25e+49)
;;(6.25e+49 3.125e+49)
;;......
;;(8.275835485684287e+26 4.143959428915591e+26)
;;(4.143959428915591e+26 2.084045469651032e+26)
;;(2.084045469651032e+26 1.066014533818449e+26)
;;(1.066014533818449e+26 5.799109426226321e+25)
;;(5.799109426226321e+25 3.7617560672361973e+25)
;;(3.7617560672361973e+25 3.2100444948749963e+25)
;;(3.2100444948749963e+25 3.1626330556312044e+25)
;;(3.1626330556312044e+25 3.1622776801368567e+25)
;;(3.1622776801368567e+25 3.1622776601683795e+25) 
;;(3.1622776601683795e+25 3.1622776601683795e+25)
;;(3.1622776601683795e+25 3.1622776601683795e+25)
;;(3.1622776601683795e+25 3.1622776601683795e+25)
;;(3.1622776601683795e+25 3.1622776601683795e+25)

可以发现某个时刻开始猜测的下一个更好的值和原来是同一个值。

这是因为如果要精确的话应该在3.1622…3795e25 的 …3795继续精确下去。但是浮点数的精确度不够用了，不能再表示更长的小数了。

所以这就是出错的原因。

接下来第二个问题是怎么改进。题目中已经提示观察近似值和下一个近似值之间的变化，当变化足够小的时候停止。

变化足够小可以考虑用差来表示，但是考虑到遇到特别小的数时会出现问题。

所以使用比值判断是否变化足够小，也就是只需要改进 good-enough? 即可

1
2
3
4
(define (good-enough? guess x)
 (< (abs (- 1 
            (/ guess (improve guess x)))) 
    0.001))

判断近似值的比值是否足够靠近 1 。也就是两个近似值是否足够接近。

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
(sqrt 4)
;;(1 2.5)
;;(2.5 2.05)
;;(2.05 2.000609756097561)
;;(2.000609756097561 2.0000000929222947)
;;2.000609756097561
(sqrt 0.0004)
;;(1 0.5002)
;;(0.5002 0.2504998400639744)
;;(0.2504998400639744 0.12604832373535454)
;;(0.12604832373535454 0.06461085492374607)
;;(0.06461085492374607 0.0354008825558513)
;;(0.0354008825558513 0.023350017942701275)
;;(0.023350017942701275 0.02024031288207058)
;;(0.02024031288207058 0.020001426615330147)
;;(0.020001426615330147 0.020000000050877154)
;;0.020001426615330147
(sqrt 1000000000000000000000000000000000000000000000000000)
;;(1 5e+50)
;;(5e+50 2.5e+50)
;;(2.5e+50 1.25e+50)
;;(1.25e+50 6.25e+49)
;;(6.25e+49 3.125e+49)
;;(3.125e+49 1.5625e+49)
;;(1.5625e+49 7.8125e+48)
;;(7.8125e+48 3.90625e+48)
;;(3.90625e+48 1.953125e+48)
;;(1.953125e+48 9.765625e+47)
;;......
;;(8.275835485684287e+26 4.143959428915591e+26)
;;(4.143959428915591e+26 2.084045469651032e+26)
;;(2.084045469651032e+26 1.066014533818449e+26)
;;(1.066014533818449e+26 5.799109426226321e+25)
;;(5.799109426226321e+25 3.7617560672361973e+25)
;;(3.7617560672361973e+25 3.2100444948749963e+25)
;;(3.2100444948749963e+25 3.1626330556312044e+25)
;;(3.1626330556312044e+25 3.1622776801368567e+25)
;;3.1626330556312044e+25

程序没有卡死，也能求出近似值。现在程序还有问题吗？有的，很明显是 (sqrt 0)，千万不要轻易尝试后果很严重（认真脸）

习题 1.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. (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.)

题目中已经给出从一个近似值得到更好的近似值的式子。仿造 sqrt 函数，修改 improve 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
(define (square x) (* x x))

(define (cube x) (* (square x) x))

(define tolerance 0.0001)

(define (good-enough? guess x)
  (< (abs (- (cube guess) x)) tolerance))

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

(define (cube-root-iter guess x)
  (if (good-enough? guess x)
      guess
      (cube-root-iter (improve guess x) x)))

(define (cube-root x)
  (cube-root-iter 1.0 x))

测试

1
2
3
4
5
6
(cube-root 8)
;; 2
(cube-root 27)
;; 3
(cube-root (cube 27))
;; 27

也可以写成封装的形式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(define (cube-root x)
  (define (square x) (* x x))
  (define (cube x) (* (square x) x))
  (define tolerance 0.0001)
  (define (good-enough? guess)
    (< (abs (- (cube guess) x)) tolerance))
  (define (improve guess)
    (/ (+ (/ x (square guess))
          (* 2 guess))
       3))
  (define (cube-root-iter guess)
    (if (good-enough? guess)
        guess
        (cube-root-iter (improve guess))))
  (cube-root-iter 1.0))

注意到第二行 (define (square x) (* x x)) 中的 x 产生了变量覆盖（shadowing），所以(* x x) 的 x其实是 square 的 x 而不是 cube-root 的 x 。编译器会正确区分，不会混淆。

总结

本小节讲述了编程的几个要素。一是语言所关注的最基本元素，例如数字，算数操作符，变量定义等。二是元素的组合。如求平方，求平方根等都是最基本元素的组合。最后是抽象，阐述了一个问题是如何拆分成几个小问题，又是如何用基本元素组合解决。