SICP Chapter3: Assignment and local state

Assignment and State

在之前的讨论中，我们并没有引入赋值这种在命令式语言中被广泛使用的语句，这是因为赋值会使得Lisp中的代换模型(Substitution Model)失效。在代换模型中，Lisp实现的是存粹的数学上的函数，也就是：给定相同的输入，保证会有相同的输出。这使得一个表达式可以通过将其中的函数调用替换为函数体，来求得最后的结果，这种代换并不会改变程序的语义，因为无论在何时对函数求值，得到的都是相同的结果。这种将表达式替换为值而不修改程序语义的特性，被称为reference transparency.

引入赋值的原因是我们想用编程世界来模拟现实世界，而不仅仅只是利用计算机来计算数学上的函数：数学上的函数，代表的是客观存在的真理，例如$since(\pi/2)=1$，因此它们可以很方便地利用代换模型计算；而现实世界的事物，增加了时间这一维度：一个函数在不同时刻的返回值可能会有所不同，因此只用代换模型模拟现实世界是不大可能的。

面向对象编程就是模拟现实世界的一种编程范式：现实世界的一个对象对应于编程世界中的一个“对象”。与之对应的是，我们也想模拟对象随时间的变化，也就是状态的概念。赋值操作为编程世界的状态模拟提供了手段，一旦一个赋值操作完成，那么就在时间上对这个对象进行了区分：赋值前的状态与赋值后的状态。

Assignment in Lisp

Lisp提供了对符号赋值的操作:(set! <name> <new-value>), 简单地说，set!操作对一个符号进行赋值，也就是在上述赋值完成之后，访问该符号，将得到刚刚的赋值。这一点与我们之前看到的很不一样，在代换模型中，一个符号拥有确定的值，直到程序结束都不会变；而在引入赋值之后，一个符号被引入了时间轴的概念，在某个时刻它是一个值，但在另一个时刻它是另一个值，正是赋值操作将这些时间节点分割开来。更确切地说，在引入赋值之后，符号关联的不是值，而是存储值的空间。

一个提款的例子:

(define balance 100)
(define (withdraw amount)
  (if (>= balance amount)
      (begin (set! balance (- balance amount))
             	balance)
      "Insufficient funds"))

当我们连续调用(withdraw 10)会得到不同的结果：

(withdraw 10)
=> 90
(withdraw 10)
=> 80
(withdraw 10)
=> 70

奇怪的是，我们对同一个函数使用相同的参数进行调用，但每次得到的结果却不同。因此这个函数并不是纯函数(Pure function), 因为它对于相同的输入，产生了不同的输出；并且它具有修改balance的副作用(Side-effect)。

Local State and OOP

我们在上面的例子中看到了一个提款的例子，每次调用withdraw函数都会减少账户的余额，并且当我们多次调用时结果也是合理的：账户余额是从前一次调用的余额减少而不是从初始值减少。

但问题在于上面的balance是一个“全局变量”，似乎所有定义的函数都有能力访问它。在这种情况下，我们很难模拟更多的账户：除非我们愿意定义更多的balance-1, balance-2...的变量，并且编写额外的withdraw-1, withdraw-2...函数，每个函数仅能操作自己对应的balance变量。

在现实世界中，每个对象都维系着与自己有关的状态，并通过与其他对象的交互来修改对方或者自己的状态。这些状态是局部 (local)的，因为它只与该对象本身有关。我们可以使用局部变量来表示这种特性，使用操作接口来修改状态。

(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)
  (define (dispatch m)
    (cond ((eq? m 'withdraw) withdraw)
      		((eq? m 'deposit) deposit)
          (else (error "Unknown request"))))
  dispatch)

上述函数定义了make-account函数，通过传入一个balance参数，该函数返回一个对象，该对象有balance数量的初始余额。该对象的实现是一个函数dispatch，它维护了一个局部状态balance。通过调用withdraw和deposit我们能修改这个局部状态：

(define acc (make-account 100))
((acc 'withdraw) 50)
=> 50
((acc 'withdraw) 60)
=> "Insufficient funds"

上述代码非常类似于C++或是JAVA中的OOP编程模式，通过make-XXX函数返回具有初始状态的对象，通过调用接口来修改对象的状态。调用对象接口的实现，得益于Lisp提供的符号处理能力，当'withdraw 这个符号被处理dispatch函数处理时，它返回实际的withdraw函数，这个函数以50为参数，执行修改balance的逻辑。

Benefit/Cost of assignment and state

An example of random

引入赋值和状态的原因在于一些操作几乎无法通过纯函数实现，例如随机函数rand, 我们期望每次对rand的调用都返回一个随机值，并且多次调用rand会生成不同的随机值：

(rand)
=> 9182
(rand)
=> 1307
(rand)
=> 15

显然，纯函数rand无法满足这个要求，如果rand是一个纯函数，那么每次对rand的调用将返回相同的值。实现rand的一个方法是保存一个内部状态rand-value, 每次调用rand时都使用当前存储的rand-value加上一个复杂的计算函数来生成下一个值：

(define rand
  (define (rand-update x)
    (modulo (+ (* a x) b) c))
  (let ((rand-value 0))
       (define (rand-func)
         (set! rand-value (rand-update rand-value))
         rand-value))
  rand-func)

这里我们使用一个多项式函数:$ax+b (\mbox{ mod } c)$ 来更新随机值。

使用上述随机值函数可以结合蒙特卡洛算法实现一个程序用于计算圆周率$\pi$的值，书上有详细的描述，这里省略。

The cost

引入赋值操作将使原先的代换模型失效，我们的表达式不再具有引用透明性(reference transparency)。而赋值操作也导致了两种截然不同的程序设计模式的产生：

函数式编程：指完全不使用赋值操作的编程模式
命令式编程：大量使用赋值操作和状态更新的编程模式

上述定义并不准确，但赋值操作的使用与否，确实是这两种编程范式的重要区别之一。

C/C++, Java等广泛使用的语言都属于命令式语言，赋值操作是这些语言的原子操作之一。而命令式编程广受诟病的一点在于：容易写出bug。正如前面所说，采用代换模型的Lisp，表达式的值无论在何时都是确定的，这使得debug相对容易，也提供了一些程序性能的优化可能：例如惰性求值(Lazy Evaluation), 记忆化(memorization)；而引入赋值的语言，则必须注意表达式的值在某个赋值前后的不同，这使得程序人员必须考虑赋值操作的前后顺序，尤其是在状态变量存在依赖关系时，而这些细节往往就是程序产生bug的根源。