Python如何實現SICP賦值和局部狀態

這篇文章主要講解了“Python如何實現SICP賦值和局部狀態”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“Python如何實現SICP賦值和局部狀態”吧！

所謂模塊化，也即使這些系統能夠“自然地”劃分為一些內聚（coherent）的部分，使這些部分可以分別進行開發和維護。

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

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

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

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

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

2 引進賦值帶來的利益

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

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

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

實現random_update的一種常見方法就是采用將xx更新為ax+bax+b取模mm的規則，其中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的每次調用算出當前xx值的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/π26/π2是隨機選取的兩個整數之間沒有公共因子（也即最大公因子為1）的概率。我們可以利用這一事實做出ππ的近似值（這個定理出自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 引進賦值的代價

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

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

要理解復制將怎樣使事情復雜化了，考慮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!

感謝各位的閱讀，以上就是“Python如何實現SICP賦值和局部狀態”的內容了，經過本文的學習后，相信大家對Python如何實現SICP賦值和局部狀態這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！