《SICP》读书笔记

因为图书角里恰好有这本书，我就借来看了。
《计算机程序的构造和解释》是 MIT 的教材，国内的高校也有相关的课程。英文名叫做《Structure and Interpretation of Computer Programs》，简称 SICP，搜索 SICP 可以获得很多资料。这本书以 Scheme 语言为例，讲解了“程序是如何解释执行的”这个问题。针对这个问题，它在每一章引入了一系列越来越精确的模型，这个模型可以理解为程序执行的规则。从“代换模型”，扩充为“环境模型”，然后用 Scheme 本身实现了一个 eval 函数，称为“元循环解释器”，最后用寄存器机器实现了一个 Scheme 解释器。同时，这本书也引入和讨论了很多话题，比如抽象的层次、函数式编程等等。很多人说这本书能塑造计算机程序的三观，确实有挺多点让我对“程序”有了新的思考。

网上很多人称这本书为“时间黑洞”。emm 确实，我自己看书的程度只能算得上是走马观花，尤其是由于这本书的学习曲线是比较陡峭的（理论上它是设计给大一学生看的，emm），所以我对这五章内容的消化程度是指数级下降（emm）。所以此文只是讲一些我得到的收获。

这本书是以 Scheme 语言举例的。此处，为了让大家不用去理解 Scheme 语言的语法，我会借用 Swift 语法。但是这仅仅只是借用了 Swift 语法，而不考虑 Swift 的真实实现，可以假设有人给 Swift 做了另外一种实现，甚至有人写了一个 Swift 解释器。所以下面的 Swift 我都用了引号。

一个简化的 "Swift"

首先，我们假设这个 "Swift" 只支持这几种语法：

1. 表达式

In computer science, an expression is a syntactic entity in a programming language that may be evaluated to determine its value.

486

1 + 100

2. 常量 -- let
3. 过程定义 -- func / clousure
4. 条件表达式 -- if

这个 "Swift" 没有变量（var），没有循环（for/while），但是它已经可以做比直观想象中更多的事情了。

先从一个简单的例子开始：求 n 的阶乘：

func factorial(_ n:Int) -> Int {
  if n == 1 {
    return 1
  }
  return n * factorial(n-1)
}

factorial(6);

代换模型

开头说过，这里举例的 "Swift" 代码，只是借用了 Swift 语法，可以认为是有人照着 Swift 语法实现了一个新的语言。所以当我们看着程序执行的时候，脑子里要抛弃掉内存、寄存器这样的概念。我们假设有一个机器，它能按照这样的规则执行 "Swift"：
To apply a compound procedure to arguments, evaluate the body of the procedure with each formal parameter replaced by the corresponding argument.
对于组合式，先求值其中的子表达式
找到要调用的过程的定义
将过程体中的每个形参用相应的实参取代之后，对过程体求值

所以，factorial(6) 的计算过程会是

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 

这种执行规则叫做“代换模型”。

递归 vs 迭代

我们很容易判断出，factorial 是一个递归过程。不管我们学习的是哪门语言，这个阶乘的实现都是讲“递归”时经典的例子。
但是当我们写完一个算法题后，面试官看到这个阶乘的实现，很可能会继续问：“有没有迭代的实现方案？”
如果我们用正常的 Swift 来回答这个问题，我们可以写

func factorial(_ n: Int) -> Int {
  var product = 1
  var count = 1
  while count <= n {
    product = count * product
    count = count + 1
  }
  return product
}

factorial(6)

但是 "Swift" 是没有循环的，没有 for，没有 while。但是我们能从上面的实现中得到阶乘函数的重点：维持一个变动的乘积 product，以及一个 1~n 的计数器 counter，每一步都按照下面的规则变化：

product ← counter * product
counter ← counter + 1 

因为 "Swift" 没有循环的，函数要达成循环的目的还是只能调用自己。所以在语法上，我们还是需要递归的形式（即自己调用自己），但是在计算过程中，我们可以仅用常数个状态变量来描述计算过程。所以我们这样重构了 factorial ：

func fact_iter(_ product: Int, _ counter: Int, _ n: Int) -> Int {
  if counter > n {
    return product
  }
  else {
    return fact_iter((product * counter), (counter + 1), n)
  }
}

func factorial(_ n: Int) -> Int {
  return fact_iter(1, 1, 6)
}

我们依然用代换模型去执行这段代码，它的计算过程会是：
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

这里我们会发现，这两个版本的阶乘，计算过程的“形状”是不一样的。
第一个版本中，总需要有存储空间去记忆“6(5(4(3(2*1))))”这样的信息，它的长度随着 n 线性增长。而在第二个版本中，虽然它在语法上仍然是递归的，但每一步需要的记忆的信息只有 product、counter 和 n。第二个版本的递归叫做尾递归。

因为第二个版本中，需要记忆的信息只有常数个，所以当这个语言引入了“循环”语法后，只要语言的实现者愿意，他就可以让循环和尾递归互为语法糖。比如 C 中，尾递归可以被编译器优化为循环。

数据结构

这个简化版的 "Swift" 能计算 n 的阶乘，好像挺好想象的。现在我们再进一步，用这个 "Swift" 来实现几个数据结构，比如 List。

这里，我们要引入数据结构的一个基本单元：序对。

序对会把两个元素组合在一起。
把多个序对组合，我们可以得到 List：

以此类推，我们也可以通过序对的组合，得到二叉树等数据结构。

如果我们把序对当作数据结构的单位，它必要有三个函数：
con、car、cdr
con 负责把两个元素组合成一个序对。
car 负责取出序对的第一个元素。
cdr 负责取出序对的第二个元素。

那么我们如何用 "Swift" 实现一个序对呢？一种方式是这样的：

func con(_ x: Any?, _ y: Any?) -> (Int) -> Any? {
  func dispatch(m: Int) -> Any? {
    if m == 0 {
      return x
    }
    else {
      return y
    }
  }
  return dispatch;
}

func car(_ z: (Int) -> Any?) -> Any? {
  return z(0)
}

func cdr(_ z: (Int) -> Any?) -> Any? {
  return z(1)
}

我们把序对拼接称为 List，利用序对的这三个函数，我们可以构建 List，可以求 List 的长度，可以遍历一个 List，可以在遍历的同时作出操作。稍微复杂一点，使用这个基于代换模型的 "Swift" 和它构建的数据结构，我们可以写一些算法题了，比如书中有一道题是求解八皇后。

函数式编程 vs 命令式编程

通过上面的几个程序，我们能明显感受到，这些程序的思维方式和我们以前学习的思维方式的不同。这源自于两种不同的“世界观”。

看起来，这个简化版的"Swift"，虽然连 var 也没有，但已经能做很多操作了。那有什么操作是这个 "Swift" 不能做的呢？

还是先从一个相对简单的例子看起：
现在我们想要做一个累加器：

func makeAccumulator(_ start: Int) {
...
}

let accumulator = makeAccumulator(100)
let q = accumulator(10) //110
let p = accumulator(10) //120

"Swift" 可以实现么？答案是不可以。
在之前的几个样例程序中，如果我们用同样的参数对同一过程两次求值，会产生同样的结果。但是这个累加器不是的。它的执行隐含着“时间流逝”这个因素，第一次调用和第二次调用返回的结果是不一样的。

如果我们确定了要通过计算机里的时间顺序去模拟实际系统里时间的流逝，那么我们必须构造起一些计算对象，使他们的行为随着程序的运行而改变。
如果我们希望模拟状态变量，那么语言里必须提供一个赋值运算符。

如果我们给 "Swift" 引入 var，那么 makeAccumulator 就可以实现了。

func makeAccumulator(_ start: Int) -> (Int) -> Int {
  var total = start
  func accumulator(_ added: Int) -> Int {
    total += added
    return total
  }
  return accumulator;
}

let accumulator = makeAccumulator(100)
let q = accumulator(10) //110
let p = accumulator(10) //120

只要我们不使用赋值，以同样的参数对同一过程的两次求值一定产生出同样的结果，因此就可以认为过程是在计算数学函数。不用任何赋值的程序设计称为“函数式程序设计”。
与之相对应的，广泛采用赋值的程序设计被称为“命令式程序设计”

环境模型

但在引入赋值之后，变量在程序运行的某些时刻代表一个值，在另一些时刻代表另外一个值。代换模型就不再有效了。
这时，"Swift" 需要引入更复杂的“环境模型”。

环境是什么呢？环境是一系列 frame，每一个 frame 是一个映射表。这个映射表把名字和值映射起来。每个 frame 还包含一个指针，指向外围环境。如果某个 frame 是全局的，它就没有外围环境。一个变量相对于某个环境的值，是这个环境中，包含该变量的第一个 frame 里这个变量的约束值。

比如这张图里，假设 x 是一个变量，在环境 B 里，x 的值是 3，在环境 A 里，x 的值是 7。

在环境模型里，一个过程是一个序对（Pair），由一些代码和一个指向环境的指针组成。过程只能通过 lambda 表达式创建。其中代码部分包含参数和过程体。

我们给 makeAccumulator 这段代码套上环境模型。

首先执行

func makeAccumulator(_ start: Int) -> (Int) -> Int {
  var total = start
  func accumulator(_ added: Int) -> Int {
    total += added
    return total
  }
  return accumulator;
}

（为了方便解释，这里先作弊一下，把 total 干掉，认为 start 是一个 var）

let makeAccumulator = {(_ start: Int) -> (Int) -> Int in
  return { (_ added: Int) -> Int in
    start += added
    return start
  }
}

我们按照过程的定义在环境模型中构造它。
由于这个过程是在全局环境中被定义的，所以它的环境指针指向全局。同时，全局环境中 makeAccumulator 这个名字成为了这一过程的变量名，于是我们把 makeAccumulator 这个名字约束到这一过程上。

然后执行

let accumulator = makeAccumulator(100)

这是一个过程调用。执行过程调用时有一个规则：
在将一个过程应用于一组实际参数时，会建立起一个新环境，其中包含了将所有形式参数约束于对应的实际参数的框架，该框架的外围环境就是所用的那个过程的环境，随后就在这个新环境下求值过程体。
这里我们首先建立了一个新环境，将形式参数 start 约束到实际参数 100。由于这个调用是在全局环境中发生的，所以新环境的外围环境是全局环境。

从新环境中，我们能获取到 makeAccumulator 对应的过程体：

{(_ start: Int) -> (Int) -> Int in
  return { (_ added: Int) -> Int in
    start += added
    return start
  }
}

把 start 代入后，求值的到

{ (_ added: Int) -> Int in
    start += added
    return start
}

同时，全局环境中会增加 accumulate 到这一过程体的约束。

接下来再执行
let q = accumulator(10) //110

这时，环境中的 start 从 100 变成了 110
当下一行代码再次需要使用到 start 时，它取到的值就是 110。

有了环境模型以后，"Swift" 可以支持 var 的赋值运算。

Eval & apply

回想刚刚，我们用环境模型执行了 accumulator 这个程序。我们会发现，在执行这个程序的过程中，我们用到了两个基本操作：

1、求值一个组合式时，先求值子表达式，然后将子表达式的结果代入，求出组合式的值（和代换模型一样）

2、当将参数应用到过程时，需要在一个新环境中求值这个过程体。为了构造这个新环境，我们需要用一个新的 frame 扩展当前的环境，在这个 frame 中，形式参数被约束到了实际参数（环境模型）

在将一个过程应用于一组实际参数时，会建立起一个新环境，其中包含了将所有形式参数约束于对应的实际参数的框架，该框架的外围环境就是所用的那个过程的环境，随后就在这个新环境下求值过程体。

这两个基本操作组成了一个循环，可以描述为 eval 和 apply 的循环。

Eval 的参数是一个表达式和一个环境，它返回这个表达式在环境中的求值结果。

Apply 的参数是一个过程和一个实际参数的表，他将实际参数应用于过程，相当于将过程转换成了表达式，返回出去，接着交给 Eval 处理。

这里我用伪代码来示意一下这个过程：

func eval(exp, env) {
    if (is-self-evaluating(exp)) return exp
    elseif (is-variable(exp)) return lookup-variable-value(exp, env)
    elseif (is-definition(exp)) return eval-definition(exp, env)
    ...
    elseif (is-application(exp)) 
        return apply(eval(operator(exp), env)), list-of-values(operator(exp), env))
    else error...
}

刚才我们讲到了函数，这是对过程的抽象；讲到了序对，这是对数据的抽象。现在世界上有了另一种抽象，是对语言的抽象。

这本书一步一步实现了一个 Scheme 的元循环解释器。最后大概 300 多行代码，可以调试着玩玩。因为 Scheme 代码本身就是 Scheme 语言的一个“内置对象”，即列表，所以用 Scheme，可以轻易取出函数名，函数体，形参列表等等，简化了 eval 的实现。

一个寄存器机器实现的解释器

刚才讲到的“代换模型”和“环境模型”都是理论上定义了一个规则。机器是怎么理解这个规则的呢？

还是用阶乘来举例

func factorial(_ n: Int) -> Int {
  func fact_iter(_ product: Int, _ counter: Int) -> Int {
   if counter > n {
    return product
   }
   else {
    return fact_iter((product * counter), (counter + 1))
   }
  }
  return fact_iter(1, 1)
}

factorial(6)

现在我们要来制造一个能计算阶乘的物理机器。
这个机器由两部分组成：

第一部分：

• 每个方框表示一个寄存器
• 梯形表示一个计算器
• 带叉叉的圆圈表示一个开关，平时是断开的，如果有人按了一下，数据就像电流一样流了过去
• 圆圈表示一个检测，counter > n 的时候会变成红色
  第二部分：
  我们告诉一个小朋友：如果检测圆圈没有变成红色，就按一下开关1，再按一下开关2。
  等开关变红色了，就从 product 的盒子里取出答案。

这两个图可以描述简单的程序，但是描述大型机器就会很不方便。但其实上图描述中，我们只是用到了几个指令。我们可以创造一个语言，一条指令可以是其中几种东西之一：

• 按一个开关，使得一个值被赋值给寄存器：assign
• 执行一个检测，亮一盏灯：test
• 根据灯的颜色，跳转到某条指令：branch
• 跳转到某条指令：goto
  这个机器便可以用指令来描述。

机器的抽象

上图中的 multi 元件，我们认为是现成的。但是如果世界上没有 multi 元件，而是需要用 add 元件构造，那可想而知，表示这个机器的图会更加复杂。
这时我们可以想象，如果我们把 multi 单独做成一个机器，放在一边。每次需要使用 multi 的时候，把输入先存放到固定的寄存器中，执行 multi，然后把结果也存入固定的寄存器，再拷贝到需要它的地方，我们就可以实现 multi 机器的抽象。
这时，指令集需要得到扩充。由于我们需要记录“结果需要被拷贝到哪”，我们需要扩充 assign 语句，使它能存放一个 label，也需要扩充 goto 语句，使它能从一个寄存器中读取 label，并跳转过去。

栈

在第一个递归版本的阶乘函数中，我们已知，执行这个阶乘函数，需要记忆的信息与 n 成正比。
由于寄存器只有常数个，为了执行递归的阶乘，我们需要引入新的数据存取的方式：栈。
于是指令集再次得到扩充：save 表示将一个值入栈，restore 表示从栈中恢复一个值。

func factorial(_ n:Int) -> Int {
  if n == 1 {
    return 1
  }
  return n * factorial(n-1)
}

factorial(6);

【待续】

参考资料：

SICP.pdf https://opendocs.github.io/sicp/sicp.pdf
SICP solutions http://community.schemewiki.org/?SICP-Solutions
如何准备 Scheme 环境 https://stackoverflow.com/questions/12322434/how-to-install-mit-scheme-on-mac/31601331#31601331
https://lfkdsk.github.io/