程序的构造元素

为了构建复杂的程序，程序语言会提供不同层级的元素：

  • primitive expressions，也就是程序所关心的最小的个体
  • means of combinations，将上面的最小个体进行简单的组合形成的东西
  • means of abstractions，为上面组合形成的东西进行命名，从而在进行整体调用，这就是抽象，是本书的核心

求值顺序

对于 combinations，求值 (eval) 的规则都是一定的，比如在 scheme 中：

(+ 1 2)

这里的 + 我们称为 operator ，而 1 和 2 是它的 operands ，求值也就是将前者的过程作用于后者。

在稍微复杂一些的 combination 中，我们还会意识到求值顺序是可以有所区别的，比如我们定义一个过程 sum-of-squares ，然后调用它进行求值：

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

(define (sum-of-squares x y)
  (+ (square x) (square y)))

(sum-of-squares (+ 5 1) (* 5 2))

可以看到应该会有两种展开方式，第一种是表达式在求值的时候先求值所有的 operands：

(sum-of-squares (+ 5 1) (* 5 2))

(sum-of-squares 6 10)

(+ (square 6) (square 10))

(+ 36 100)

136

第二种是先展开 operator，直到没什么可展开了，再进行 reduce：

(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

我们把前者称为 aplicative order (eager evaluation)，后者称为 normal order (lazy evaluation) 。当今流行的绝大多数语言采用的都是 aplicative order，包括 C, Java, Python 等等，而 normal order 最知名的代表语言就是 Haskell。SICP 中使用的 Scheme 也是使用 applicative order 的。

我们很容易就能想到 applicative order 的优势，因为真正的计算都尽早被执行了，所以通常程序的内存开销会更小，效率更高，而其劣势则自然就是做不到 normal order 能做的一些事情。 一个很有意思的问题是：我们能否自己定义一个函数来实现 if 的功能？

比如我们将条件、表达式 A 和表达式 B 都作为参数来传入：

(define (my-if predicate exp-a exp-b) ... )

可以想见的是，如果语言采用的是 applicative order 方式，那么这种实现就是不可能的。因为在执行该函数的时候，所有的参数都会被执行，包括不符合条件的那种。

因此在 Scheme 中， if 这个 operator 的执行一定不是遵循普通的求值规则的，我们称这种元素为 special forms 。很明显的是我们上面使用的 define 也一定是一种 special form。

递归过程与递归运算

我不确定我使用的这个中文名称是否准确，书中的说法是 recursive procedure 和 recursive process 。前者就是我们一般常说的递归调用，即在 procedure 的定义里面 refer 了它本身。而 recursive process 则是描述了一个持续进行递归调用，同时 defer 了很多处理的情况。

以 factorial 为例：

(define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (- n 1)))))

(factorial 6)
(* 6 (factorial 5))
(* 6 (* 5 (factorial 4)))
(* 6 (* 5 (* 4 (factorial 3))))
(* 6 (* 5 (* 4 (* 3 (factorial 2)))))
(* 6 (* 5 (* 4 (* 3 (* 2 (factorial 1))))))
(* 6 (* 5 (* 4 (* 3 (* 2 1)))))
(* 6 (* 5 (* 4 (* 3 2))))
(* 6 (* 5 (* 4 6)))
(* 6 (* 5 24))
(* 6 120)
720

这里的运算过程形成了一个「弧线形」，可以看到每次的返回中包含了 defer 了的运算，这些运算要等到所有的递归过程结束之后才会进行。而这个过程，是要在每一层的调用中都占用内存空间的。这种情况就称之为 recursive process。

而同时，我们可以换一种做法，把运算的结果放到 function 的 argument 中，使得这些运算不再被 defer：

(define (factorial n)
  (define (fact-iter product counter max-count)
    (if (> counter max-count)
	product
	(fact-iter (* counter product)
		   (+ counter 1)
		   max-count)))
  (fact-iter 1 1 n))

(factorial 6)
(fact-iter 1 1 6)
(fact-iter 1 2 6)
(fact-iter 2 3 6)
(fact-iter 6 4 6)
(fact-iter 24 5 6)
(fact-iter 120 6 6)
(fact-iter 720 7 6)
720

在这种时候，实际上 factorial 的运算是 iterative process 的，其过程和我们在其他语言里面使用 for loop 之类的结构实现的并没有区别。和之前那个 recursive process 的情况相比，最突出的区别就是函数递归调用时的返回结果就是以该函数为 operator 的 (self-called)，而运算过程是一个 operand。那么对于一个 applicative order 的语言来说，这个运算部分自然是先被执行的。这种递归的方式我们也就称为 tail recursion 尾递归。

高阶函数和 Lambda

在 Scheme 中，我们不仅可以将普通的变量作为参数传入函数，还可以将函数作为参数传入函数，同时也可以将函数作为返回值，这就是我们说的 higher-order procedures 。除了 Lisp 之外，有很多其他拥有 functional programming 特性的语言也同样支持这一点，比如 Javascript, Python, Swift 等，而以 C, Java 这些则并不支持。

而在使用 higher-order procedures 时，我们会意识到给所有的 procedure 都取一个名字是完全没必要的，这时候我们就可以使用 lambda 关键字。lambda 表达式脱胎于 λ 演算，本身就是一套变量绑定和替换的规则，从而来在一个形式系统中实现函数的抽象化定义和应用。在 scheme 中使用 lambda 的方式和 λ 是几乎一样的：

; variable
x

; abstraction
(lambda (x) (+ x 1))

; application
((lambda (x) (+ x 1)) 1)
=> 2

当然我们也可以将这个函数绑定到一个名字上

(define add-1 (lambda (x) (+ x 1)))

(add-1 1)
=> 2

实际上面的定义方式和这种特殊的用 define 的方式是完全等价的，这种用法可以看成是 scheme 的语法糖：

(define (add-1 x) (+ x 1))

除此之外，其实还有 let 也是只是 lambda 包装的语法糖，用来方便得定义有清晰的作用域的变量，下面两个表达是等价的：

(let ((x 1)
      (y 2))
  (+ x y))

((lambda (x y)
   (+ x y))
 1 2)

总结

第一章这部分主要是介绍了计算的基础构成和求值规则，我们看到经过 recursive procudure，这些非常基础的规则可以组合出复杂的、功能强大的程序，而其中的关键就是利用一层一层得在基础的功能之上叠加抽象层级。在这个过程中，我们可以看到 lambda 表达式可以非常灵活得构筑抽象，尤其是作为 higher-order procedure 的参数或返回值的时候。