SICP 笔记（三）：赋值的代价、mutex 的实现、流与时间
赋值的引入
之前提到的所有 scheme 语法，都不会对一个已经有的值进行修改。比如如果我们使用 define 对一个 identifier 定义两次，就会出现报错：
(define x 1)
(define x 2)
; module: identifier already defined
但是在一些场景下，我们确实需要去改变一个已有的值。这种情况下，scheme 提供了 set! 函数，于是我们可以借此来实现一个 bank account：
(define balance 100)
(define (withdraw amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
"Insufficient funds"))
更合理的设计是 balance 应该只是 withdraw 的内部变量，我们可以使用 let 来构造一个局部的变量：
(define new-withdraw
(let ((balance 100))
(lambda (amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
"Insufficient funds"))))
与这种用 let 的方式类似，一个函数的形参也可以用来作为一个局部变量：
(define (make-withdraw balance)
(lambda (amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
"Insufficient funds")))
在这种情况下，我们就可以得到独立局部变量的两个用来 withdraw 的账户：
(define W1 (make-withdraw 100))
(define W2 (make-withdraw 200))
赋值的带来的好处是显而易见的，我们可以实现一些本来没法实现的场景。
还有一个典型的例子是 rand 函数的实现。在 Scheme 中，我们使用 rand-update 函数来对一个随机数种子做变换，从而生成一个随机数。如果我们可以赋值，我们就可以将这个种子作为一个局部状态变量，使得外部不需要每次都传一个种子进来：
(define rand
(let ((x random-init))
(lambda () (set! x (rand-update x)) x)))
注意这里的 rand-update 实际上是一个非常普通的函数，只是把一个数转换成另一个数，结果是确定的。比如一个根据书中注释里面介绍的，常见的做法是可以用将 \(x\) 更新为 $(ax+b)\mod m$：
(define (rand-update x)
(remainder (+ (* a x) c) m))
这样之后，我们就可以直接使用 rand 来得到一个随机数了。否则，如果在外部显式地去操作随机数种子，会使得外部代码的逻辑结构不够清晰。外部算法在实现算法本身之外还要同时完成种子的更新操作，而且实现上比较容易出错，比如误用了相同的种子。书中使用的例子是一个 Monte Carlo simulation 算法的实现，他被迫在算法实现的结构中多添加一个参数来接受每次迭代使用的种子。
总体来说，必须要有 set! ，才能使一个函数在对自己的局部状态变量进行更新，从而对外隐藏自己随时间变化的内部状态。这样的情况下，整个系统的构建就可以更加模块化。
在没有赋值的情况下，我们程序中的函数与数学上的函数是类似的，固定的输入一定会得到固定的输出。我们称这种不使用赋值操作的程序设计为「函数式编程」(functional programming)，而使用了赋值操作的为「命令式编程」(imperative programming)。
两种编程范式最突出的一个习惯上的区别可能就是如何实现迭代，后者就和我们平时使用 C 的 while 比较类似：
; functional programming
(define (factorial n)
(define (iter product counter)
(if (> counter n)
product
(iter (* counter product)
(+ counter 1))))
(iter 1 1))
; imperative programming
(define (factorial n)
(let ((product 1)
(counter 1))
(define (iter)
(if (> counter n)
product
(begin (set! product (* counter product))
(set! counter (+ counter 1))
(iter))))
(iter)))
赋值的代价
命令式编程固然带来了更多的灵活性，但是其代价也是巨大的。
我们会发现我们在解释一个运算的时候，无法再使用代换模型了。因为代换模型要求语言中符号只是作为值的名字，如果使用了赋值操作，则值是可以改变的，则一个变量不再只是一个简单的名字而已，变量实际上索引着一个保存了值的位置。于是，我们在使用符号的时候，必须加入时间维度，去区分这个符号的运算是在 set! 之前还是之后，这是代换模型做不到的。 我们可以说这是破坏了一种「引用透明性」，即一个表达式在被替换的时候能够不改变其值的性质。
在没有引用透明性的情况下，我们会很难判断两个对象是不是「同一」的。即使两个符号可能是通过完全相同的表达式创建出来的，他们也可能是完全不同的对象。比如下面的情况，因为有可变的局部变量 balance 的存在，W1 和 W2 很可能是不同一的：
(define (make-simplified-withdraw balance)
(lambda (amount)
(set! balance (- balance amount))
balance))
(define W1 (make-simplified-withdraw 25))
(define W2 (make-simplified-withdraw 25))
作为对比，这里的 D1 和 D2 一定是同一的：
(define (make-decrementer balance)
(lambda (amount) (- balance amount)))
(define D1 (make-decrementer 25))
(define D2 (make-decrementer 25))
变动数据对象
通过赋值，我们也可以构造更加灵活的数据对象。
一个最简单的例子，比如我们知道一个典型的 list 的结构是这样的：
(define x (cons 1 (cons 2 (cons 3 (cons 4 nil)))))
即有一个个 pair，pair 的 car 指向一个值，而 cdr 指向下一个 pair。所以当我们对某个 pair 使用 set-car! 和 set-cdr! 就可以改变这种指向关系，比如让 car 变成另一个值，让 cdr 变成另一个 pair，甚至是让 car 同样指向一个 pair 从而让 x 变成一个二维的 list。
另外，赋值的引入还让这种指向有了更复杂的情况。比如我们可以通过 set-cdr! 让 x 的 cdr 指向另一个 list 的中间：
(define y (list a b c d))
(set-cdr! x b)
如此一来，x 和 y 就会共享 list 的 (b c d) 部分，这是我们在 functional programming 范式下不会出现的情况。
书中还列举了使用赋值来实现 queue, table 等数据结构，方法都是类似的。同时还可以通过这种手段来模拟电路（因为需要改变输入的 signal），并且来构建一个 constraint system。
并发和 mutex 的实现
一旦有了赋值的操作，我们就为整个系统引入了时间这个维度。即在我们去运算一个符号的时候，需要关心这个运算是什么发生的，因为时间可能会使得结果不同。
如果程序是单线程的，那这个问题还不那么严重，因为我们可以很清楚地就知道运算之间的先后关系。而并发的场景就完全不同了，操作的先后是有随机性的，而且不同的线程也可能会共享相同的 local value， 这自然会带来极大的麻烦。
一个简单的例子就是之前实现过的 withdraw，是这样定义的：
(define (withdraw amount)
(if (>= balance amount)
(begin
(set! balance
(- balance amount))
balance)
"Insufficient funds"))
我们可以看到，这里面的关键一步是 (set! balance (- balance amount)) ， 这一步可以被分解为三小步：
- 读取 balance
- 计算 balance 和 amount 的差值
- 将计算出来的差值赋值给 balance
可以看到这里面第一步是对 balance 的读，第三步是对 balance 的写。那么此时如果有两个并发的线程 A 和 B，它们的执行顺序如下是 A1-B1-A3-B3，则 B 就将覆盖掉 A 的写入。因为 B 读取到的 balance 值是 A 写入之前的，因此其计算结果和 A 的操作完全无关。
很自然得，我们可以想到使用 serializer 这样的方式来对过程做限制，即一个被经过了 serializer 处理的过程同一个时间只能有一个在运行。
我们可以用这样的方式定义出更改后的账户系统，它对 withdraw, deposit 以及直接查询余额的 balance 操作都进行了限制：
(define (make-account balance)
(define (withdraw amount)
(if (>= balance amount)
(begin (set! balance
(- balance amount))
balance)
"Insufficient funds"))
(define (deposit amount)
(set! balance (+ balance amount))
balance)
(let ((protected (make-serializer)))
(define (dispatch m)
(cond ((eq? m 'withdraw)
(protected withdraw))
((eq? m 'deposit)
(protected deposit))
((eq? m 'balance)
balance)
(else (error "Unknown request:
MAKE-ACCOUNT"
m))))
dispatch))
我们可以使用一种叫做 mutex 的对象来实现 serializer:
(define (make-serializer)
(let ((mutex (make-mutex)))
(lambda (p)
(define (serialized-p . args)
(mutex 'acquire)
(let ((val (apply p args)))
(mutex 'release)
val))
serialized-p)))
mutex 本身是一种只包含单个元素的 list，我们在此称之为 cell ，它可以表示一个布尔值，我们可以如此构造 mutex：
(define (make-mutex)
(let ((cell (list false)))
(define (the-mutex m)
(cond ((eq? m 'acquire)
(if (test-and-set! cell)
(the-mutex 'acquire))) ; retry
((eq? m 'release) (clear! cell))))
the-mutex))
(define (clear! cell) (set-car! cell false))
其中， test-and-set! 会去检查 cell 的状态，如果它是 false 的，就立即将其变为 true，同时返回 false，从而让 the-mutex 函数完成对 mutex 的 acquire：
(define (test-and-set! cell)
(if (car cell)
true
(begin (set-car! cell true)
false)))
仅仅是这样当然是不足以保证 mutex 实现的有效性的，我们必须要确信 test-and-set! 的执行具有原子性，即要保证当我们检测到 cell 是 false 之后，一定会将其 set 成 true。否则这里的实现就和前面提到的 withdraw 的场景类似了。
这个的保证就有赖于操作系统的实现了，并不是程序语言这个层面可以解决的。一个简单的例子，我们知道很多操作系统使用时间片机制来调度进程，那对于这种需要原子操作的函数我们可以在其运行期间 block 中断，从而保证其自始至终的执行。而 multi-core 的 CPU 应该会支持硬件级别的原子操作指令。
这里还有一个很有意思的问题就是 arbiter ，即如果两个进程同时使用这种硬件级别的原子操作指令，我们需要一个 arbiter (仲裁器) 来决定哪个进程能获得资源的控制权。但是不幸的是，我们可以证明一个 100% 有效的仲裁器是不可能被构建出来的。这个问题最早由 14 世纪的法国哲学家 Jean Buridan 提出，称为 Buridan’s ass ，他描述了一个一只驴子因为无法决定去吃左右两边哪堆干草而饿死。也就是说，如果一个选择没有明显的理由优于另一个选择，那么一个完全理性的决策者就非常难以做出选择。
流
我们看到，赋值的引入产生了非常多的副作用。而之所以我们需要赋值，是因为真实世界中真的有这样的场景，即一个对象的状态是会改变的。 但是除了用变量，我们还可以使用其他的方式来描述这种状态的变化。
比如我们可以把这个状态看成是一个随时间变化的函数 \(f(t)\)，那么只要我们在调用的时候同时给出了时间的信息，其值就一定是固定的。可以把这个函数的历史看成是一个非常长的 list，其中的每个元素就是一个时间点对应的值。
但是看成 list 显然是存在一些问题的，最主要的是两个：
- 时间所对应的值应该是无限的，但是不可能构造出一个无限长的 list 来
- 就算 list 不是无限的，在一些场景下它的构建和存在都是需要消耗很多的计算和存储资源的
我们可以用一个非常极端的例子来说明 list 的问题。比如用下面这个方法来找出从 10000 到 1000000 的第二个素数：
(car (cdr
(filter
prime?
(enumerate-interval 10000 1000000))))
我们将会找出所有 10000 到 1000000 的所有整数，然后挨个判断是否是素数，但是最后抛弃几乎所有的结果，只取其中的一个。这种写法固然不合理，但是使用 list 来表示就是会存在这样的问题。
在此我们引入新的数据结构，称为 stream (流)。流在使用上与 list 类似，但是并不是在构造的时候就生成出所有的元素，而是真正需要被用到了采取计算。可以简单得认为，stream 就是一种 delayed list。
与 list 一样，一个 stream 的开头同样是一个 pair，但是结构是这样的：
(cons ⟨a⟩ (delay ⟨b⟩))
它的 car 部分是一个正常的表达式，但是 cdr 部分却是经过了 delay 的表达式，我们称后面这部分为一个 promise 。
所以自然得，去取这个 stream 的 cdr 部分，需要强制把 promise 变成真正的表达式：
(define (stream-cdr stream)
(force (cdr stream)))
所以如果我们用 stream 来实现之前那个极端的例子：
(stream-car
(stream-cdr
(stream-filter
prime? (stream-enumerate-interval
10000 1000000))))
(define (stream-enumerate-interval low high)
(if (> low high)
the-empty-stream
(cons-stream
low
(stream-enumerate-interval (+ low 1)
high))))
(define (stream-filter pred stream)
(cond ((stream-null? stream)
the-empty-stream)
((pred (stream-car stream))
(cons-stream
(stream-car stream)
(stream-filter
pred
(stream-cdr stream))))
(else (stream-filter
pred
(stream-cdr stream)))))
stream-filter 在开始的时候会发现 10000 不是 prime，从而执行 (stream-filter pred (stream-cdr stream)) ，于是 stream-cdr 就会强制转换一个 promise，让 stream-enumerate-interval 给出这样的返回：
(cons 10001
(delay
(stream-enumerate-interval
10002
1000000)))
然后 stream-filter 使用 stream-car 直接取到了这个 10001，重复进行这样的流程。直到取到了 10007，发现它是一个素数，然后将其 cons 起来，此时的整个返回：
(cons 10007
(delay
(stream-filter
prime?
(cons 10008
(delay
(stream-enumerate-interval
10009 1000000))))))
后面再找到 10009 也是类似，然后就能得到整个表达式的结果是 10009。整个过程执行的运算数量和使用 list 时是差了几个数量级的。
而这里面 delay 和 force 的实现其实都是非常直接的， delay 一个表达式的方式就是将其放到一个函数中去返回，而 force 执行就是将这个函数执行一下而已：
(define (delay exp)
(lambda () exp))
(define (force delayed-object)
(delayed-object))
不过值得注意的是我们可以想见 delay 一定是一个 special form 而不是一个普通的函数（所以上面的函数定义只是一个参考，实际上这种定义并不存在），因为在 applicative order 下，普通函数的参数必然要被先运算。
另外，为了让流的使用更加高效，我们还可以用一个 memo-proc 函数将一个流中已经计算过的值存起来。这样，如果流中的元素是依赖于前值的，需要计算的步骤就会大大减少：
(define (memo-proc proc)
(let ((already-run? false) (result false))
(lambda ()
(if (not already-run?)
(begin (set! result (proc))
(set! already-run? true)
result)
result))))
(define (delay exp)
(memo-proc (lambda () exp)))
流的一个重要 feature 就是可以构造出无穷的流，比如我们可以如此定义包含了所有 integer 的流：
(define (integers-starting-from n)
(cons-stream
n (integers-starting-from (+ n 1))))
(define integers (integers-starting-from 1))
这是一种比较直接的定义方式，即用 integers-start-from 这个函数来递归生成下一个值。我们还可以用一种比较隐晦的定义方式：
(define ones (cons-stream 1 ones))
(define (add-streams s1 s2)
(stream-map + s1 s2))
(define integers
(cons-stream 1 (add-streams ones integers)))
至此，我们可以尝试回看之前的 rand 了，在流的眼光中，我们没有一个随机数生成器，但是可以有一个包含了无穷的随机数的流：
(define random-numbers
(cons-stream random-init
(stream-map rand-update
random-numbers)))
在使用这个随机数流的时候，我们同样可以将其很好的抽象出来，不影响上层算法的逻辑结构。
函数式编程视角下的时间
在现实中，对象拥有自己的状态，并且这种状态是会随着时间而变化的。我们此前正是为了试图去模拟这种现实中的情况，才为程序语言引入了赋值的机制。但是赋值的引入有太多的代价，因此我们尝试另寻出路。
借助流这种特殊的数据结构，我们得以显式得将变量随着时间变化的历史表现出来，从而松开了模拟的世界中时间与运算过程之间的紧密联系。
我们可以用 withdraw 的例子再来对比一下二者，这是赋值形式的 withdraw：
(define (make-simplified-withdraw balance)
(lambda (amount)
(set! balance (- balance amount))
balance))
这是流形式的，我们可以得到一个包含了表现 balance 历史的流：
(define (stream-withdraw balance amount-stream)
(cons-stream
balance
(stream-withdraw
(- balance (stream-car amount-stream))
(stream-cdr amount-stream))))
这里的 stream-withdraw 不仅实现了需要的功能，而且它本身仍然是定义良好的、数学意义上的函数，其返回值永远只取决于其参数。
也就是说，对于这个流来说，从来就没有什么时间的概念，它本身也是没有所谓的状态的。但是对于其用户来说，看到的却是正在和一个系统进行交互，而且存在着一个交互形成的状态。之所以会形成这样的认识上的区别，是因为用户本身是具有时态的，类似于将参数代入一个函数，用户本身将他的时态信息代入了系统，从而将一个无状态的流看成了有状态的。