SICP：賦值和局部狀態（Python實現）

即使在變化中，它也絲毫未變。

——希拉克利特

吾猶昔人，非昔人也。

——僧肇

前面我們介紹了組成程式的各種基本元素，看到瞭如何把基本過程和基本數據組合起來，構造出複合的實體。不過對於設計程式而言，這些手段還不夠，我們還需要一些能夠幫助我們構造起模塊化（modular）的大型系統的策略。所謂模塊化，也即使這些系統能夠“自然地”劃分為一些內聚（coherent）的部分，使這些部分可以分別進行開發和維護。

在哲學上，組織程式的方式與我們對被模擬系統的認識息息相關。接下來我們要研究兩種特色很鮮明的組織策略，它們源自於對於系統結構的兩種非常不同的“世界觀”（world views）。

• 第一種策略將註意力集中在對象（objects）上，將一個大型系統看成不同對象的集合，它們的狀態和行為可能隨著時間不斷變化。

• 另一種組織策略將註意力集中在流過系統的信息流（streams of information）上，非常像EE工程師觀察一個信號處理系統。

這兩種策略都對程式設計提出了具有重要意義的語言要求。對於對象途徑而言，我們必須關註對象可以怎樣變化而又保持其標識（identity）。這將迫使我們拋棄前面說講過的計算的代換模型，轉向更機械式的，理論上也更不容易把握的計算的環境模型(environment model)。在處理對象、變化和標識時，各種困難的根源在於我們需要在這一計算模型中與時間搏鬥，如果引入併發後還將變得更糟糕。流方式將我們的模型中的模擬時間與求值過程中的事件發生順序進行解耦，我們將通過一種稱為延時求值(lazy evaluation)的技術做到這一點。

本節我們先介紹第一種對象世界觀。

3.1.1 局部狀態變數

在對象世界觀里，我們想讓計算對象具有隨著時間變化的狀態，而這就需要讓每個計算對象有自己的一些局部狀態變數。現在讓我們來對一個銀行賬戶支取現金的情況做一個模擬。我們將用一個過程withdraw完成此事，它有一個參數amount表示支取的現金量。如果餘額足夠則withdraw返回支取之後賬戶里剩餘的款額，否則返回消息Insufficient funds(金額不足)。假設開始時賬戶有100元錢，在不斷使用withdraw的過程中我們可能得到下麵的響應序列：

withdraw(25) # 70
withdraw(25) # 50
withdraw(60) # "In sufficient funds"
withdraw(15) # 35

在這裡可以看到表達式widthdraw(25)求值了兩次，但它產生的值卻不同，這是過程的一種新的行為方式。之前我們看到的過程都可以看做是一些可計算的數學函數的描述，兩次調用一個同一個過程，總會產生出相同的結果。

為了實現withdraw，我們可以用一個全局變數balance表示賬戶里的現金金額，並將withdraw定義為一個訪問balance的過程。下麵是balance和widthdraw的定義：

balance = 100
def withdraw(amount):
    global balance
    if balance > amount:
        balance = balance - amount
        return balance
    else: 
        return "Insufficient funds"

雖然withdraw能像我們期望的那樣工作，變數balance卻表現出一個問題。如上所示，balance是定義在全局環境中的一個名字，因此可以被任何過程檢查或修改。我們希望將balance做成withdraw內部的東西，因為這將使withdraw成為唯一能直接訪問balance的過程，而其他過程只能間接地（通過對withdraw的調用）訪問balance。這樣才能準確地模擬有關的概念：balance是一個只有withdraw使用的局部狀態變數，用於保存賬戶狀態的變化軌跡。

我們可以通過下麵的方式重寫出withdraw，使balance成為它內部的東西：

def new_withdraw():
    balance = 100
    def inner(amount):
        nonlocal balance
        if balance > amount:
            balance = balance - amount
            return balance
        else:
            return "Insufficient funds"
    return inner

W = new_withdraw()
print(W(25)) # 70
print(W(25)) # 50
print(W(60)) # "In sufficient funds"
print(W(15)) # 35

這裡的做法是用創建起一個包含局部變數balance的環境，並使它初始值為100。在這個環境里，我們創建了一個過程inner，它以amount作為一個參數，其行為就像是前面的withdraw過程。這樣最終返回的過程就是new_withdraw，它的行為方式就像是withdraw，但其中的變數確實其他任何過程都不能訪問的。用程式設計語言的行話，我們說變數balance被稱為是封裝在new_withedraw過程裡面。

將賦值語句與局部變數相結合，形成了一種具有一般性的程式設計技術，我們將一直使用這種技術區構造帶有局部狀態的計算對象。但這一技術也帶來了麻煩，我們之前在代換模型中說，應用（apply）一個過程應該解釋為在將過程的形式參數用對應的值取代之後再求值這一過程。但現在出現了麻煩，一旦在語言中引進了賦值，代換就不再適合作為過程應用的模型了（我們將在3.1.3節中看到其中的原因）。我們需要為過程應用開發一個新模型，這一模型將在3.2節中介紹。現在我們要首先檢查new_withdraw所提出的問題的幾種變形。

下麵過程make_withdraw能創建出一種“提款處理器”。make_withdraw的形式參數balance描述了有關賬戶的初始餘額值。

def make_withdraw(balance):
    def withdraw(amount):
        nonlocal balance
        if balance > amount:
            balance = balance - amount
            return balance
        else:
            return "Insufficient funds"
    return withdraw

下麵用make_withdraw創建了兩個對象：

W1 = make_withdraw(100)
W2 = make_withdraw(100)
print(W1(50)) # 50
print(W2(70)) # 30
print(W2(40)) # Insufficient funds
print(W1(40)) # 10

我們可以看到，W1和W2是相互完全獨立的對象，每一個都有自己的局部狀態變數balance，從一個對象提款與另一個毫無關係。

我們還可以創建出除了提款還能夠存入款項的對象，這樣就可以表示簡單的銀行賬戶了。下麵是一個過程，它返回一個具有給點初始餘額的“銀行賬戶對象”：

def make_account(balance):
    def withdraw(amount):
        nonlocal balance
        if balance >= amount:
            balance = balance - amount
            return balance
        else:
            return "In sufficient funds"
    def deposit(amount):
        nonlocal balance
        balance = balance + amount
        return balance
    def dispatch(m):
        nonlocal balance
        if m == "withdraw":
            return withdraw
        if m == "deposit":
            return deposit
        else:
            raise ValueError("Unkown request -- MAKE_ACOUNT %s" % m)
    return dispatch

對於make_acount的每次調用將設置好一個帶有局部狀態變數balance的環境，在這個環境里，make_account定義了能夠訪問balance過程deposit和withdraw，另外還有一個過程dispatch，它以一個“消息”做為輸入，返回這兩個局部過程之一。過程dispatch本身將會被返回，做為表示有關銀行賬戶對象的值。這正好是我們在2.4.3節中看到過的程式設計的消息傳遞風格，當然這裡將它與修改局部變數的功能一起使用。

acc = make_account(100)
print(acc("withdraw")(50)) # 50
print(acc("withdraw")(60)) # In sufficient funds
print(acc("deposit")(40)) # 90
print(acc("withdraw")(60)) # 30

對acc的每次調用將返回局部定義的deposit或者withdraw過程，這個過程隨後被應用於給定的amount。就像make_withdraw一樣，對make_amount的另一次調用

acc2 = make_acount(100)

將產生出另一個完全獨立的賬戶對象，維持著它自己的局部balance。

這裡再舉一個實現累加器的例子（事實上該例子在《黑客與畫家》^[2]第13章中也有出現，被用來說明不同編程語言編程能力的差異）。累加器是一個過程，反覆用數值參數調用它，就會使得它的各個參數累加到一個和中。每次調用時累加器將返回當前的累加和。請寫出一個生成累加器的過程make_accumulator，它所生成的每個累加器維持著一個獨立的和。傳給make_accumulator的輸入描述了和的初始值。其Python實現代碼如下：

def make_accumulator(sum_value):
    def accumulator(number):
        nonlocal sum_value
        sum_value += number
        return sum_value
    return accumulator

A =  make_accumulator(5)
print(A(10)) # 15
print(A(10)) # 25

當然，Common Lisp的寫法將更為簡單：

(defun make_accumulator (sum_value)
   (lambda (number) (incf sum_value number)))

Ruby的寫法與Lisp幾乎完全相同：

def make_accumulator (sum_value)
    lambda {|number| sum_value += number } end

《黑客與畫家》中作者還展示了Perl、Smalltalk、JavaScript等語言的寫法，感興趣的朋友可以去看下這本書（劇透一下：作者這兒把Java黑慘了233）。

3.1.2 引進賦值帶來的利益

正如下麵將要看到的，將賦值引進所用的程式設計語言中，將會使我們陷入困難概念問題的叢林之中。但無論如何，將系統看做是帶有局部狀態的對象的集合，也是一種維護模塊化設計的強有力技術。先讓我們看一個簡單的例子：如何設計出一個過程rand，每次它被調用就會返回一個隨機選出的整數。這裡的“隨機選擇”的意思並不清楚，其實我們希望的就是對rand的反覆調用將產生一個具有均勻分佈統計性質的序列。假定我們已經有一個過程rand-update，它的性質就是，如果從一個給點的數x1開始，執行下麵操作

x2 = random_update(x1)
x3 = random_update(x2)

得到的值序列x1、x2，x3，...將具有我們所希望的性質。

實現random_update的一種常見方法就是採用將\(x\)更新為\(ax+b\)取模\(m\)的規則，其中a、b和m都是適當選出的整數。比如：

def rand_update(x):
    a = int(pow(7, 5))
    b = 0
    m = int(pow(2, 31)) - 1
    return (a * x + b) % m

Knuth的TAOCP第二捲(半數值演算法)^[3]中包含了有關隨機數序列和建立起統計性質的深入討論。註意，random_update是計算一個數學函數，兩次給它同一個輸入，它將產生同一個輸出。這樣，如果“隨機”強調的事序列中每個數與前面的數無關的話，由random_update生成的數序列肯定不是“隨機的”。在“真正的隨機性”與所謂偽隨機序列（由定義良好的確定性計算產生出的但又具有適當統計性質的序列）之間的關係是一個非常複雜的問題，涉及到數學和哲學中的一些困難問題，Kolmogorov、Solomonoff、Chaitin為這些問題做出了很多貢獻，從Chaitin 1975^[4]可以找到有關討論。

現在回到當前的話題來。我們已經實現好了random_update，接下來在此基礎上實現rand。我們可以將rand實現為一個帶有局部狀態變數x的過程，其中將這個變數初始化為某個固定值rand_init。對rand的每次調用算出當前\(x\)值的random_update值：

def make_rand(random_init):
    x = random_init
    def inner():
        nonlocal x
        x  = rand_update(x)
        return x
    return inner

rand = make_rand(42)
print(rand()) # 705894
print(rand()) # 1126542223

當然，即使不用賦值，我們也可以通過簡單地調用rand_update，生成同樣的隨機序列。但是這意味著程式中任何使用隨機數的部分都必須顯式地記住，需要將x的當前值傳給rand_update作為參數，這樣會徒增煩惱。

接下來，我們考慮用隨機數實現一種稱為蒙特卡羅模擬的技術。

蒙特卡羅方法包括從一個大集合里隨機選擇試驗樣本，併在對這些試驗結果的統計估計的基礎上做出推斷。例如，\(6/\pi^2\)是隨機選取的兩個整數之間沒有公共因數（也即最大公因數為1）的概率。我們可以利用這一事實做出\(\pi\)的近似值（這個定理出自Cesaro，見TAOCP第二捲^[3]4.5.2的討論和證明）。

這一程式的核心是過程monte_carlo，它以某個試驗的次數（trails）以及這個試驗本身（experiment）作為參數。試驗用一個無參過程cesaro_test表示，返回的是每次運行的結果為真或假。monte_carlo運行指定次數的這個試驗，它返回所做的這些試驗中得到真的比例。

rand = make_rand(42)
import math
def estimate_pi(trials):
    return math.sqrt(6 / monte_carlo(trials, cesaro_test))

def cesaro_test():
    return math.gcd(rand(), rand()) == 1

def monte_carlo(trials, experiment):
    def iter(trials_remaining, trials_passed):
        if trials_remaining == 0:
            return trials_passed / trials
        elif cesaro_test():
            return iter(trials_remaining - 1, trials_passed + 1)
        else:
            return iter(trials_remaining - 1, trials_passed)
    return iter(trials, 0)

print(estimate_pi(500)) # 3.178208630818641

現在讓我們試一試不用rand，直接用rand_update完成同一個計算。如果我們不使用賦值去模擬局部狀態，那麼將不得不採取下麵的做法：

random_init = 42
def estimate_pi(trials):
    return math.sqrt(6 / random_gcd_test(trials, random_init))

def random_gcd_test(trials, initial_x):
    def iter(trials_remaining, trials_passed, x):
        x1 = rand_update(x)
        x2 = rand_update(x1)
        if trials_remaining == 0:
            return trials_passed / trials
        elif math.gcd(x1, x2) == 1:
            return iter(trials_remaining - 1, trials_passed + 1, x2)
        else:
            return iter(trials_remaining - 1, trials_passed, x2)
    return iter(trials, 0, initial_x)

print(estimate_pi(500)) # 3.178208630818641

雖然這個程式還是比較簡單的，但它卻在模塊化上打開了一些令人痛苦的缺口，因為它需要顯式地去操作隨機數x1和x2，並通過一個迭代過程將x2傳給random_update作為新的輸入。這種對於隨機數的顯式處理與積累檢查結果的結構交織在一起。此外，就連上層的過程estimate_pi也必須關心提供隨機數的問題。由於內部的隨機數生成器被暴露了出來，進入了程式的其它部分，我們很難將蒙特卡羅方法的思想隔離出來了。反觀我們在程式的第一個版本中，由於通過賦值將隨機數生成器的狀態隔離在過程rand的內部，因此就使隨機數生成的細節完全獨立於程式的其它部分了。

由上面的蒙特卡洛方法實例體現的一種普遍性系統設計原則就是：對於行為隨時間變化的計算對象（如銀行賬戶和隨機數生成器），我們需要設置局部狀態變數，並用對這些變數的賦值去模擬狀態的變化。

3.1.3 引進賦值的代價

正如上面所看到的，賦值操作使我們可以模擬帶有局部狀態的對象。然而，這一獲益也有一個代價，也即使我們的程式設計語言不能再用前面所提到過的代換模型解釋了。進一步說，任何具有“漂亮”數學性質的簡單模型，都不可能繼續適合作為處理程式設計語言里的對象和賦值的框架了。

只要我們不適用賦值，以同樣參數對同一過程的兩次求值一定產生出同樣的結果，因此就可以認為過程是在計算數學函數。就像我們在之前的章節中所提到的那樣，不用任何複製的程式設計稱為函數式程式設計。

要理解複製將怎樣使事情複雜化了，考慮3.1.1節中make_withdraw過程的一個簡化版本，其中不再關註是否有足夠餘額的問題：

def make_simplified_withdraw(balance):
    def simplified_withdraw(amount):
        nonlocal balance
        balance = balance - amount
        return balance
    return simplified_withdraw

W = make_simplified_withdraw(25)
print(W(20)) # 5
print(W(10)) # -5

請將這一過程與下麵make_decrementer過程做一個比較，該過程里沒有用賦值運算：

def make_decrementer(balance):
    return lambda amount: balance - amount

make_decrementer返回的是一個過程，該過程從指定的量balance中減去其輸入，但順序調用時卻不會像make_simplifed_withdraw那樣產生累積的結果。

D = make_decrementer(25)
print(D(20)) # 5
print(D(10)) # 15

我們可以用代換模型解釋make_decrementer如何工作。例如，讓我們分析一下下麵表達式的求值過程：

make_decrementer(25)(20)

首先簡化組合式中的操作符，用25代換make_decrementer體里的balance，這樣就規約出了下麵的表達式：

(lambda amount: 25 - amount) (20)

隨後應用運算符，用20代換lambda表達體里的amount：

25 - 20

最後結果是5。

現在再來看看，如果將類似的代換分析用於make_simplifed_withdraw，會出現什麼情況：

make_simplified_withdraw(25)(20)

先簡化其中的運算符，用25代換make_simplified_withdraw體里的balance，這樣就規約出了下麵的表達式（註意，Python的lambda表達式里不能進行賦值運算（據Guido說是故意加以限制從而防止Python成為一門函數式編程語言），下麵這個式子不能在Python解釋器中運行，只是為了方便大家理解）：

(lambda amount： balance = 25 - amount)(25)(20)

這裡我們沒有代換賦值表達式里的balance，因為賦值符號=的左邊部分並不會進行求值，如果代換掉它，得到的25 = 25 - amount根本就沒有意義。

現在用20代換lambda表達式體里的amount：

(balance = 25 - 20)(25)

如果我們堅持使用代換模型，那麼就必須說，這個過程應用的結果是首先將balance設置為5，而後返回25作為表達式的值。這樣得到的結果當然是錯誤的。為了得到正確答案，我們不得不對balance的第一次出現（在=作用之前）和它的第二次出現(在=作用之後)加以區分，而代換模型根本無法完成這件事情。

這裡的麻煩在於，從本質上說代換的最終基礎就是，這一語言里的符號不過是作為值的名字。而一旦引入了賦值運算=和變數的值可以變化的想法，一個變數就不再是一個簡單的名字了。現在的一個變數索引著一個可以保存值的位置（place），而存儲再那裡的值也是可以改變的。在3.2節里將會看到，在我們的計算模型里，環境將怎樣扮演者“位置”的角色。

同一和變化

這裡暴露出的問題遠遠不是簡單地打破了一個特定計算模型，它還使得以前非常簡單明瞭的概念現在都變得有問題了。首先考慮兩個物體實際上“同一”（“the same”）的概念。

假定我們用同樣的參數調用make_decrementer兩次，就會創建出兩個過程：

D1 = make_decrementer(25)
D2 = make_decrementer(25)

D1和D2是同一的嗎？“是”是一個可接受的回答，因為D1和D2具有同樣的計算行為——都是同樣的將會從其輸入里減去25點過程。事實上，我們確實可以在任何計算中用D1代替D2而不會改變結果，如下所示：

print(D1(20)) # 5
print(D1(20)) # 5
print(D2(20)) # 5

於此相對應的是調用make_simplified_withdraw兩次：

W1 = make_simplified_withdraw(25)
W2 = make_simplified_withdraw(25)

W1和W2是同一的嗎？顯然不是，因為對W1和W2的調用會有不同的效果，下麵的調用顯示出這方面的情況：

print(W1(20)) # 5
print(W1(20)) # -15
print(W2(20)) # 5

雖然W1和W2都是通過對同樣表達式make_simplified_withdraw(25)求值創建起來的東西，從這個角度可以說它們“同一”。但如果說在任何表達式里都可以用W1代替W2，而不會改變表達式的求值結果，那就不對了。

如果一個語言支持在表達式里“同一的東西可以相互替換”的觀念，這樣替換不會改變有關表達式的值，這個語言就稱為是具有引用透明性。而當我們的電腦語言包含賦值運算之後，就打破了引用透明性。

一旦我們拋棄了引用透明性，有關計算對象“同一”的意義問題就很難形式地定義清楚了。事實上，在我們企圖用電腦程式去模擬的現實世界里，“同一”的意義本身就很難搞清楚的，這是由於“同一”和“變化”的迴圈定義所致：我們想要確定兩個看起來同一的事物是否確實是“同一個東西”，我們一般只能去改變其中一個對象，看另一個對象是否也同樣改變；但如果不觀察“同一個”對象兩次，看看對象的性質是否與另一次不同，我們就能確定對象是否“變化”。由是觀之，我們必須要將“同一”作為一個先驗觀念引入（PS：這裡可以參見康德的思想），否則我們就不可能確定“變化”。

現在舉例說明這一問題會如何出現在程式設計里。現在考慮一種新情況，假定Peter和Paul有銀行賬戶，其中有100塊錢。關於這一事實的如下模擬：

peter_acc = make_account(100)
paul_acc = make_account(100)

和如下模擬之間有著實質性的不同：

peter_acc = make_account(100)
paul_acc = peter_acc

在前一種情況里，有關的兩個銀行賬戶互不相同。Peter所做的交易將不會影響Paul的賬戶，反之亦然。比如，當Peter取10塊，Paul取10塊，則Paul賬戶里還有90塊：

peter_acc("withdraw")(10)
print(paul_acc("withdraw")(10)) # 90

而對於後一種情況，這裡把paul_acc定義為與peter_acc是同一個東西，結果就使現在Peter和Paul共有一個共同的賬戶，此時當Peter取10塊錢，Paul再取10塊錢後，Paul就只剩80塊錢了：

peter_acc("withdraw")(10)
print(paul_acc("withdraw")(10)) # 80

這裡一個計算對象可以通過多於一個名字訪問的現象稱為別名（aliasing）。這裡的銀行賬戶例子是最簡單的，我們在3.3節里還將看到一些更複雜的例子，例如“不同”的數據結構共用某些部分，如果對某一個對象的修改可能由於“副作用”而修改了另一“不同的”的對象，因為這兩個“不同”對象實際上只是同一個對象的不同別名，當我們忘記這一情況程式就可能出現錯誤。這種錯誤被稱為副作用錯誤，特別難以定位和分析。因此某些人（如分散式計算大佬Lampson）就建議說，程式設計語言的設計不允許副作用或者別名。

命令式程式設計的缺陷

與函數式程式設計相對應的，廣泛採用賦值的程式設計被稱為命令式程式設計(imperative programming)。除了會導致計算模型的複雜性之外，以命令式風格寫出的程式還容易出現一些不會在函數式程式中出現的錯誤。舉例來說，現在重看一下在1.2.1節里的迭代求階乘程式：

def factorial(n):
    def iter(product, counter):
        if counter > n:
            return product
        else:
            return iter(counter * product, counter + 1)
    return iter(1, 1)

print(factorial(4)) # 24

我們也可以不通過內部迭代迴圈（這裡假設Python支持尾遞歸）傳遞參數，而是採用更命令的風格，顯式地通過賦值去更新變數product和counter的值：

def factorial(n):
    product, counter = 1, 1
    def iter():
        nonlocal product, counter
        if counter > n:
            return product
        else:
            product = counter * product
            counter = counter + 1
            return iter()
    return iter()

print(factorial(4)) # 24

這樣做不會改變程式的結果，但卻會引進一個很微妙的陷阱。我們應該如何確定兩個賦值的順序呢？像上面的程式雖然是正確的，但如果以相反的順序寫出這兩個賦值：

counter = counter + 1 
product = counter * product

就會產生出與上面不同的錯誤結果：

print(factorial(4)) # 120， Wrong!

一般而言，帶有賦值的程式將強迫人們去考慮賦值的相對順序，以保證每個語句所用的是被修改變數的正確版本。在函數式程式設計中，這類問題根本就不會出現。事實上這種看法也說明，大部分的引論性程式設計課程採用高度命令式風格講授，這確實是意見令人啼笑皆非的事情。這一情況可能源自20世紀70年代中流行的一種常見看法的殘存遺跡，這種看法說調用過程的程式一定比執行賦值的程式效率更低（Steele(1977)^[6]批駁了這一論斷）。還有，這種情況也可能反應了另一種觀點，認為初學者一步步的看賦值比觀察過程調用更容易。無論出於什麼原因，它總是給初學程式設計的人們增加了關註“我應該把這個變數的賦值放在另一個之前呢還是之後”的負擔，這會使程式設計複雜化，也使其中的主要思想變模糊了。

如果考慮有多個併發執行的進程的應用程式，命令式程式設計的複雜性還會變得更糟糕。我們將在3.4節回到這個問題。

參考

• [1] Abelson H, Sussman G J. Structure and interpretation of computer programs[M]. The MIT Press, 1996.
• [2] Graham P. Hackers & painters: big ideas from the computer age[M]. " O'Reilly Media, Inc.", 2004
• [3] MacLaren M D. The art of computer programming. Volume 2: Seminumerical algorithms (Donald E. Knuth)[J]. SIAM Review, 1970, 12(2): 306-308.
• [4] Chaitin G J. Randomness and mathematical proof[J]. Scientific American, 1975, 232(5): 47-53.
• [5] Lampson B W, Horning J J, London R L, et al. Report on the programming language Euclid[J]. ACM Sigplan Notices, 1977, 12(2): 1-79.
• [6] Steele Jr G L. Debunking the “expensive procedure call” myth or, procedure call implementations considered harmful or, lambda: The ultimate goto[C]//Proceedings of the 1977 annual conference. 1977: 153-162.