即使在變化中，它也絲毫未變，
——赫拉克利特
吾猶昔人，非昔人也，
——僧肇
前面我們介紹了組成程式的各種基本元素，看到了如何把基本程序和基本資料組合起來，構造出復合的物體，不過對于設計程式而言，這些手段還不夠，我們還需要一些能夠幫助我們構造起模塊化（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.
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/545917.html
標籤：其他