3.1 赋值和局部状态
========================

我们可以用一个或几个状态变量刻画一个对象的状态, 在它们之间维持着有关这一对象的历史, 即能够确定该对象当前行为的的充分信息。

每一个计算对象必须有它自己的一些局部状态变量, 用于描述实际对象的状态。特别的, 我们希望通过赋值运算符去改变一个名字关联的值。

*3.1.1 局部状态变量*
-------------------------

使用 `withdraw` 模拟从银行账户支取现金

.. code-block:: scheme

  ;; 现金余额
  (define balance 100)

  ;; 使用 set! 在余额变化后对 balance 重新赋值
  (define (withdraw amount)
    (if (>= balance amount)
        (begin (set! balance (- balance amount))
               balance)
        "Insufficient funds"))

测试验证

::

  > (withdraw 25)
  75
  > (withdraw 25)
  50
  > (withdraw 60)
  "Insufficient funds"
  > (withdraw 15)
  35

为避免定义在全局环境中的 `balance` 被其它过程查看或修改, 应将其封装为 `withdraw` 过程的局部状态变量.

.. code-block:: scheme

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

测试验证

::

  > (new-withdraw 25)
  75
  > (new-withdraw 25)
  50
  > (new-withdraw 60)
  "Insufficient funds"
  > (new-withdraw 15)
  35

因为现在过程中使用了赋值操作, 因此之前对于过程求值的代换模型将不再适用。

`new-withdraw` 的一种变形

.. code-block:: scheme

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

测试验证

::

  > (define W1 (make-withdraw 100))
  > (define W2 (make-withdraw 100))
  > (W1 50)
  50
  > (W2 70)
  30
  > (W2 40)
  "Insufficient funds"
  > (W1 40)
  10

可以看到 `W1` 与 `W2` 为两个独立的对象, 两者拥有各自独立的 `balance` 。

构造即可以取款又可以存款的对象

.. code-block:: scheme

  (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: MAKE-ACCOUNT" m))))
    dispatch)

测试验证

::

  > (define acc (make-account 100))
  > ((acc 'withdraw) 50)
  50
  > ((acc 'withdraw) 60)
  "Insufficient funds"
  > ((acc 'deposit) 40)
  90
  > ((acc 'withdraw) 60)
  30

对于 `make-account` 的另一次调用将会产生出另一个完全独立的账户。

*练习 3.1*
---------------

.. code-block:: scheme

  (define (make-accumulator sum)
    (lambda (n)
      (set! sum (+ sum n))
      sum))

测试验证

::

  > (define A (make-accumulator 5))
  > (A 10)
  15
  > (A 10)
  25

*练习 3.2*
----------------

.. code-block:: scheme

  (define (make-monitored f)
    (let ((count 0))
      (define (how-many-call)
        count)
      (define (reset-count)
        (set! count 0))
      (define (dispatch m)
        (cond ((eq? m 'how-many-call?) (how-many-call))
              ((eq? m 'reset-count) (reset-count))
              (else (and (set! count (+ count 1))
                         (f m)))))
      dispatch))

测试验证

::

  > (define s (make-monitored sqrt))
  > (s 100)
  10
  > (s 'how-many-call?)
  1
  > (s 'reset-count)
  > (s 'how-many-call?)
  0
  > (s 36)
  6
  > (s 49)
  7
  > (s 64)
  8
  > (s 'how-many-call)
  3

*练习 3.3*
--------------

.. code-block:: scheme

  (define (make-account balance password)
    (define (withdraw amount)
      (if (>= balance amount)
          (begin (set! balance (- balance amount))
                 balance)
          "Insufficient funds"))
    (define (deposit amount)
      (set! balance (+ balance amount))
      balance)
    (define (dispatch p m)
      (if (eq? p password)
          (cond ((eq? m 'withdraw) withdraw)
                ((eq? m 'deposit) deposit)
                (else (error "UnKnown request: MAKE-ACCOUNT" m)))
          (lambda (amount) "Incorrect password")))
    dispatch)

测试验证

::

  > (define acc (make-account 100 'secret-password))
  > ((acc 'secret-password 'withdraw) 40)
  60
  > ((acc 'some-other-password 'deposit) 50)
  "Incorrect password"

*练习 3.4*
--------------

.. code-block:: scheme

  (define (make-account balance password)
    (define password-error-num 0)
    (define (call-the-cops)
      "call-the-cops")
    (define (withdraw amount)
      (if (>= balance amount)
          (begin (set! balance (- balance amount))
                 balance)
          "Insufficient funds"))
    (define (deposit amount)
      (set! balance (+ balance amount))
      balance)
    (define (alert amount)
      (begin (set! password-error-num (+ password-error-num 1))
             (if (>= password-error-num 7)
                 (call-the-cops)
                 "Incorrect password")))
    (define (dispatch p m)
      (if (eq? p password)
          ;; 密码正确则计数器归零
          (and (set! password-error-num 0)
               (cond ((eq? m 'withdraw) withdraw)
                     ((eq? m 'deposit) deposit)
                     (else (error "UnKnown request: MAKE-ACCOUNT" m))))
          alert))
    dispatch)

测试验证

::

  > (define acc (make-account 100 'secret-password))
  > ((acc 'secret-password 'withdraw) 40)
  60
  > ((acc 'some-other-password 'deposit) 50)
  "Incorrect password"
  > ((acc 'some-other-password 'deposit) 50)
  "Incorrect password"
  > ((acc 'some-other-password 'deposit) 50)
  "Incorrect password"
  > ((acc 'some-other-password 'deposit) 50)
  "Incorrect password"
  > ((acc 'some-other-password 'deposit) 50)
  "Incorrect password"
  > ((acc 'some-other-password 'deposit) 50)
  "Incorrect password"
  连续输错七次后报警
  > ((acc 'some-other-password 'deposit) 50)
  "call-the-cops"
  > ((acc 'some-other-password 'deposit) 50)
  "call-the-cops"
  输入正确密码后仍然需要连续输错七次才报警
  > ((acc 'secret-password 'withdraw) 40)
  20
  > ((acc 'some-other-password 'deposit) 50)
  "Incorrect password"
  > ((acc 'some-other-password 'deposit) 50)
  "Incorrect password"
  > ((acc 'some-other-password 'deposit) 50)
  "Incorrect password"
  > ((acc 'some-other-password 'deposit) 50)
  "Incorrect password"
  > ((acc 'some-other-password 'deposit) 50)
  "Incorrect password"
  > ((acc 'some-other-password 'deposit) 50)
  "Incorrect password"
  > ((acc 'some-other-password 'deposit) 50)
  "call-the-cops"
  > ((acc 'some-other-password 'deposit) 50)
  "call-the-cops"

*3.1.2 引进赋值带来的收益*
----------------------------

使用不同的方式来实现蒙特卡罗模拟, 以对比使用赋值和不使用赋值的差异。

使用赋值的方式实现蒙特卡罗方法, 基于 :math:`\frac{6}{\pi^2}` 是随机选取的两个整数之间没有公共因子的概率来计算 :math:`\pi` 的近似值。

.. code-block:: scheme

  ;; 根据以上的概率公式构建过程
  (define (estimate-pi trials)
    (sqrt (/ 6 (monte-carlo trials cesaro-test))))

  ;; 测试两个随机数是否互质
  (define (cesaro-test)
    (= (gcd (rand) (rand)) 1))

  ;; 这里 rand 的实现将局部状态变量 x 封装在过程之中
  ;; 初次调用时使用 random-init 对其初始化, 然后使其作为 rand-update 的参数获取新的随机数
  (define rand
    (let ((x random-init))
      (lambda ()
        (set! x (rand-update x))
        x)))

  ;; 蒙特卡罗方法
  ;; 传入指定的实验次数及实验本身
  ;; 在迭代过程中记录实验结果为真的次数
  ;; 当实验次数迭代到零时返回实验结果为真的次数占总次数的比值
  (define (monte-carlo trials experiment)
    (define (iter trials-remaining trials-passed)
      (cond ((= trials-remaining 0)
             (/ trials-passed trials))
            ((experiment)
             (iter (- trials-remaining 1)
                   (+ trials-passed 1)))
            (else
             (iter (- trials-remaining 1)
                   trials-passed))))
    (iter trials 0))

在上面的过程中因为将生成随机数的过程封装在 `rand` 过程中, 因此代码可以很好的体现出蒙特卡罗方法的思想, 而如果不采用上面的方式, 则会将生成随机数与蒙特卡罗方法掺杂在一起, 导致层层嵌套不便于改进也不具备兼容性的代码出现。

.. code-block:: scheme

  (define (estimate-pi trials)
    (sqrt (/ 6 (random-gcd-test trials random-init))))

  (define (random-gcd-test trials initial-x)
    (define (iter trials-remaining trials-passed x)
      (let ((x1 (rand-update x)))
        (let ((x2 (rand-update x1)))
          (cond ((= trials-remaining 0)
                 (/ trials-passed trials))
                ((= (gcd x1 x2) 1)
                 (iter (- trials-remaining 1)
                       (+ trials-passed 1)
                       x2))
                (else
                 (iter (- trials-remaining 1)
                       trials-passed
                       x2))))))
    (iter trials 0 initial-x))

与所有状态都必须显式的操作和传递额外参数的方式相比, 通过引进赋值和将状态隐藏在局部变量中的技术, 我们能以一种更模块化的方式构造系统。

*练习 3.5*
---------------

.. code-block:: scheme

  (define (random-in-range low high)
    (let ((range (- high low)))
      (+ low (random range))))

  ;; 直接用矩形面积乘以蒙特卡罗方法的结果即为积分的预估值
  (define (estimate-integral P x1 x2 y1 y2 trials)
    (define (experiment)
      (P (random-in-range x1 x2)
         (random-in-range y1 y2)))
    (* (* (- x2 x1)
          (- y2 y1))
       (monte-carlo trials experiment)))

  ;; 判断方法基于圆的方程式
  (define (P x y)
    (< (+ (expt (- x 5) 2)
          (expt (- y 7) 2))
       9))

  ;; 计算 pi 的预估值直接用积分预估值除以半径的评分即可
  (define (estimate-pi trials)
    (/ (estimate-integral P 2.0 8.0 4.0 10.0 trials)
       9.0))

测试验证

::

  > (estimate-pi 10000)
  3.1152
  > (estimate-pi 100000)
  3.13824
  > (estimate-pi 1000000)
  3.141092
  > (estimate-pi 10000000)
  3.1417688

*练习 3.6*
--------------

.. code-block:: scheme

  (define rand
    (let ((x random-init))
      (define (dispatch message)
        (cond ((eq? message 'generate)
               (begin (set! x (rand-update x))
                      x))
              ((eq? message 'reset)
               (lambda (new-value)
                 (set! x new-value)))
              (else
               (erro "Unknow mode -- RAND" message))))
      dispatch))

  (define random-init 1.0)
  ;; 暂时没有找到根据相同种子生成相同随机数的过程, 这里简单模拟一下
  (define (rand-update x)
    (+ x 1.23))


测试验证

::

  > (rand 'generate)
  2.23
  > (rand 'generate)
  3.46
  > (rand 'generate)
  4.6899999999999995
  > ((rand 'reset) 1.0)
  > (rand 'generate)
  2.23
  > (rand 'generate)
  3.46
  > (rand 'generate)
  4.6899999999999995

*3.1.3 引进赋值的代价*
-------------------------

不用任何赋值的程序设计称为函数式程序设计, 因为不使用赋值的情况下对于相同的参数对一个过程求值多次总会返回相同的结果。

对于它的理解可以参考下面的两个过程。

.. code-block:: scheme

  (define (make-simplified-withdraw balance)
    (lambda (amount)
      (set! balance (- balance amount))
      balance))

  (define W (make-simplified-withdraw 25))

测试

::

  > (W 20)
  5
  > (W 10)
  -5

可以看到传入的参数与返回的结果依赖于之前调用时传入的参数, 即这个过程返回的是一种累积的结果。

.. code-block:: scheme

  (define (make-decrementer balance)
    (lambda (amount)
      (- balance amount)))

  (define D (make-decrementer 25))

测试

::

  > (D 20)
  5
  > (D 10)
  15

可以看到在这个过程中对于每次调用都是用 25 减去传入的参数, 即并不是返回累积的结果。

对于上面两个过程使用代换模型推演一下两者的求值过程便能发现不同之处, 对于使用赋值的过程, 根本就不能使用代换模型。

由此也可以发现代换的基础在于变量名只是某个值的名字, 而一旦有了赋值功能, 则变量名将会索引一个可以保存值的位置, 而这个位置保存的值是可以变化的。

**同一和变化**

.. code-block:: scheme

  (define D1 (make-decrementer 25))
  (define D2 (make-decrementer 25))

基于 `make-decrementer` 过程构造的 `D1` 和 `D2` 具有相同的计算行为, 可以认为它们是 `同一` 的。

.. code-block:: scheme

  (define W1 (make-simplified-withdraw 25))
  (define W2 (make-simplified-withdraw 25))

而基于 `make-simplified-withdraw` 过程构造的 `W1` 和 `W2` 各自维护着自己的 `balance`, 它们并不是 `同一` 的。

如果某个语言支持在表达式里“同一的东西可以相互替换”的观念, 这样的替换不会改变有关表达式的值, 这个语言就称为是具有引用透明性。

当使用赋值语句打破了引用透明性后, 代换模型失效, 则此时已经不能再试图使用代换去简化表达式, 从而使得对于使用赋值的程序做推理变得极其困难。

一旦抛弃了引用透明性, “同一”的意义问题就很难形式的定义清楚了。因为要判断两个看起来是同一的事物是否为“同一个东西”, 最起码需要对其观察两次, 而在观察的过程中又要确定事物的某些用来判断同一的性质, 因此在判断同一之前, 首先要定义一些先验观念。

举例说明: 两个人的银行账户中各有100块钱, 以下是两种模拟方式。

.. code-block:: scheme

  (define peter-acc (make-account 100))
  (define paul-acc (make-account 100))

以上构建了两个不同的账户。

.. code-block:: scheme

  (define peter-acc (make-account 100))
  (define paul-acc peter-acc)

以上将两者定义成了同一个账户, 从而使两者共用了一个账户。这将会给这个账户的处理制造混乱, 因此此时不管是使用 `peter-acc` 还是 `paul-acc` 都会造成共用账户的修改。


**命令式程序设计的缺陷**

与函数式程序设计相对应的, 广泛采用赋值的程序设计被称为命令式程序设计。

命令式程序设计除了会导致计算模型的复杂性之外, 还会导致一些不容易在函数式程序设计中出现的错误。

以下是阶乘的函数式实现

.. code-block:: scheme

  (define (factorial n)
    (define (iter product counter)
      (if (> counter n)
          product
          (iter (* counter product)
                (+ counter 1))))
    (iter 1 1))

以下是阶乘的命令式实现

.. code-block:: scheme

  (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)))

单从代码行数上就能看出两者的差异, 在实现思路上函数式更接近人类思考的过程, 而命令式则过于机械化, 也正因为其机械化, 对于赋值语句的顺序要尤其注意。

*练习 3.7*
----------------

只需要对 `make-account` 过程做个封装即可

.. code-block:: scheme

  (define (make-joint acc password new-password)
    (lambda (p m)
      (if (eq? p new-password)
          (acc password m)
          (lambda (x)
            "Incorrect password"))))

测试验证:

::

  > (define peter-acc (make-account 100 'open-sesame))
  > (define paul-acc (make-joint peter-acc 'open-sesame 'rosebud))
  > ((peter-acc 'open-sesame 'withdraw) 40)
  60
  > ((paul-acc 'rosebud 'withdraw) 40)
  20
  > ((paul-acc 'rosebud1 'withdraw) 10)
  "Incorrect password"

*练习 3.8*
--------------

.. code-block:: scheme

  ;; 调用 f 将会设置 f 为一个始终返回 0 的过程
  ;; 而对于第一次调用将会返回其参数
  (define (f x)
    (set! f (lambda (y) 0))
    x)

测试验证:

::

  > (+ (f 0) (f 1))
  0
  调整调用顺序来模拟求值顺序, 注意这里需要重新编译 f
  > (+ (f 1) (f 0))
  1