程序设计的基本元素

这一部分主要是对 Lisp 语言（准确来说是用到的 Scheme 方言）的基本介绍。

• 数学表达式
• 变量的定义（将值与符号关联）
• 定义函数（复合过程）
• 条件表达式

以上部分与我们熟悉编程语言的相应内容相差不大，只是 Lisp 大量使用 S 表达式（前缀表达式）。需要适应一段时间。

程序设计的三种最基本的机制

• 基本表达形式：用于表示语言所关心的最简单的个体
• 组合的方法：它们可以从较简单的东西出发构造出复合的元素
• 抽象的方法：通过它们可以为复合对象命名，并将它们当作单元去操作

练习 1.1

(define a 3)
(define b (+ a 1))

(list 10
      (+ 5 3 4)
      (- 9 1)
      (/ 6 2)
      (+ (* 2 4) (- 4 6))
      (+ 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

将下面的表达式变换为前缀形式

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

练习 1.3

定义一个过程，它以三个数作为参数，返回这较大的两个数之和

(define (sum-of-max-two a b c)
  (if (>= a b)
      (if (>= b c) (+ a b) (+ a c))
      (if (> a c) (+ b a) (+ b c))))

(sum-of-max-two 1 2 3)

练习 1.4

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

(list (a-plus-abs-b 1 1)
      (a-plus-abs-b 1 -1))

这一过程中根据参数 b 的值来确定对参数 a b 应用的过程，如果 $b > 0$，则应用 + 过程；若 $b < 0$，则应用 - 过程。

代换模型

代换模型并不是对程序真实运行过程的描述。但是在引入赋值之前，代换模型能够很好地帮助我们领会过程调用的情况。

Substitution Rule

To evaluate an application

• Evaluate the operator to get procedure
• Evaluate the operands to get arguments
• Apply the procedure to the arguments
  • Copy the body of the procedure
    • substituting the arguments supplied for the formal parameters of the procedure
  • Evaluate the resulting new body

To evaluate an IF expression

• Evaluate the predicate expression
  • if it yields TRUE
    • evaluate the consequent expression
  • otherwise
    • evaluate the alternative expression

应用代换模型的例子

(sum-of-square 3 4)
(+ (suqare 3) (square 4))
(+ (square 3) (* 4 4))
(+ (square 3) 16)
(+ (* 3 3) 16)
(+ 9 16)

(define (+ x y)
  (if (= x 0)
    y
    (+ (-1 + x) (1 + y))

(+ 3 4)
(if (= 3 0) 4 (+ (-1 + 3) (1 + 4))
(+ (-1 + 3) (1 + 4))
(+ (-1 + 3) 5)
(+ 2 5)
(if (= 2 0) 5 (+ (-1 + 2) (1 + 5)))
(+ (-1 + 2) (1 + 5))
(+ (-1 + 2) 6)
(+ 1 6)
(if (= 1 0) 6 (+ (-1 + 1) (1 + 6))
(+ (-1 + 1) (1 + 6))
(+ (-1 + 1) 7)
(+ 0 7)
(if (= 0 0) 7 (+ (-1 + 0) (1 + 7)))
7

应用序和正则序

上文中代换模型中使用的“先求值参数而后应用”的方式称为 应用序。

此外，还有一种先将表达式完全展开而后归约的求值模型称为 正则序。

练习 1.5

判定解释器采用的是应用序还是正则序

(define (p) (p))

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

(test 0 (p))

p 是一个死循环。如果采用应用序，则 p 必定会被求值，因此程序一定会卡死。如果采用正则序求值，当 test 函数的输入为 0 时，if 的条件满足，过程 p 不会被执行，程序输出 0。

实例 牛顿法求平方根

如果对 $x$ 的平方根的值有了一个猜测 $y$，那么就可以得到一个更好的猜测： $\frac{y + x/y}{2}$

(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 (square x) (* x x))

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

(sqrt 9)

练习 1.6

(define (new-if predicate then-clause else-clause)
  (cond [predicate then-clause]
        [else else-clause]))

若采用应用序执行，无论判定条件如何， then-clause 和 else-clause 都一定会被执行，如果用 new-if 重写平方根程序，由于递归会无条件执行，程序永远无法终止。

练习 1.7

练习 1.8

牛顿法求立方根

如果 $y$ 是 $x$ 的立方根的一个近似值，那么下式将给出一个更好的近似值

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

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

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

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

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

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

(cube-root 27)

过程作为黑箱抽象

局部名

参数的的名字与外部环境无关，参数名实际上是将外部环境名称的重新绑定，它将函数的内部环境与外部环境隔离了。

这样的名字称为约束变量，因此我们说，一个过程的定义约束了它的所有形式参数。

如果在一个完整的过程定义里将某个约束变量统一换名，这一过程定义的意义将不会有任何改变。（让我想起了谓词逻辑的约束变量与自由变量）。如果一个变量不是被约束的，我们就称它为自由的。

内部定义和块结构

Scheme 允许我们定义内部函数，这中嵌套的定义称为 块结构

词法作用域：词法作用域要求过程中的自由变量实际引用外围过程定义中所出现的约束变量。

(define (sqrt x)
  (define (square x) (* x x))
  (define (average x y) (/ (+ x y) 2))
  (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))

(sqrt 9)