緒論

我們在第一章引進復合程序時，采用了求值的代換模型定義了將程序應用于實參（arguments）的意義：

• 將一個復合程序應用于一些實參，也就意味著用實參替換程序體里對應的形參（formal parameters）之后，求值這個程序體，

但正如我們在上一章博客《SICP：賦值和區域狀態（Python實作）》中所講的，一旦我們把賦值引入程式設計語言之后，這一定義就不再合適了，由于賦值的存在，變數已經不能再看作僅僅是某個值的名字，此時的變數必須以某種方式指定了一個“位置”（place），相應的值可以存盤再那里， 在我們新求值模型里，這種位置將維持在稱為環境的結構中，

一個環境就是幀（frame） 的一個序列，每個幀是包含著一些系結（bindings） 的表格，這些約束將一些變數名字關聯于對應的值（在一個幀內，任何變數至多只有一個系結），

每個幀還包含一個指標，指向這個幀的外圍環境（enclosing environment），如果由于當前討論的目的，將相應的幀看做是全域（global） 的，那么它將沒有外圍環境，一個變數相對于某個特定環境的值，也就是在這一環境中，包含著該變數的第一個幀里這個變數的系結值，如果在幀序列中不存在這一變數的系結，則稱這個變數在特定環境下是未系結（unbound） 的，

下圖展示了一個簡單的環境結構，其中包含了三個幀，分別用Ⅰ、Ⅱ、Ⅲ標記，

在這個圖里，A、B、C和D都是環境指標，其中C和D指向同一個環境，變數z和x在幀Ⅱ里系結，變數y和x在幀Ⅰ里系結，x在環境D里的值是3，x相對于環境B的值也是3，后一種情況是因為我們先檢測幀序列中的第一個幀（幀Ⅲ），在這里沒有找到x的系結，因此繼續前進到外圍環境D并在幀Ⅰ里找到了相應的系結，另一方面，x在環境A中的值就是7，因為幀序列中第一個幀（幀Ⅱ）里包含x與7的系結，對于環境A，我們說在幀Ⅱ里x與7的系結遮蔽了幀1里x與3的系結(這里可以聯想一下Python中區域變數對全域變數的遮蔽)，

環境對于求值是至關重要的，因為它確定了運算式求值的背景關系（context），實際上，我們完全可以說在一個程式設計語言里的一個運算式本身沒有任何意義，因為即使像1+1這樣簡單的運算式，其解釋也要依賴于+是表示加法符號的背景關系，這樣，在現在討論的求值模型中，我們將總說某個運算式相對于某個環境的求值，為了描述與解釋器的互動作用，我們將始終假定存在著一個全域環境，它只包含著一個幀（沒有外圍環境），這個環境里包含著所有關聯于基本程序的符號值，例如，我們說+是表示加法的符號，也就意味著符號+在全域環境中被系結到基本的加法程序，

3.2.1 求值規則

關于解釋器如何求值一個組合式的問題，其整體描述仍然與我們在1.1.3節第一次介紹時完全一樣，

在1.1.3節中的代換模型中，我們如果要對一個組合運算式求值，需要：
(1) 求值這一組合式里的各個子運算式，
(2) 將運算子（operator）子運算式的值應用于運算物件（operand）子運算式的值，

PS：賦值的存在給求值規則的步驟 (1) 引入了一個微妙問題，即以不同的順序對組合式中各個子運算式求值，它們就會產出不同的值（想想在C語言中被(++i)+(++i)支配的恐懼^[2]），然而，這種順序應該看做是一個實作細節，我們永遠不要去寫依賴于特定順序的程式，比如，如果一個復雜的編譯器去做程式的優化，它完全可能改變其中各子運算式的求值順序，

現在我們要用求值的環境模型代替求值的代換模型，在這一模型中我們將會討論當定義一個復合程序以及當一個復合程序應用于實參究竟意味著什么，

我們來看一個例子，考慮在全域環境里求值下面的程序定義：

def square(x):
    return x * x

下圖展示的是在全域環境中求值這一def運算式而產生的環境結構：

這里的程序物件是一個序對（pair），其代碼部分描述的是一個帶有形參x的程序，程序體是return x * x，程序物件的環境部分是一個指向全域環境的指標（因為這個程序的定義是在全域環境中求值的），這個定義在全域幀中加入了一個新系結，將上述程序物件系結于符號square，一般而言，用def建立定義的方式（Python的話用=也可表示變數定義）就是將新的系結加入到幀中，

這樣，程序物件創建的環境模型可總結定為：

• 對于一個給定環境求值一個程序的定義，將創建起一個程序物件，這個程序物件是一個序對，由該程序的正文和一個指向環境的指標組成，這一指標指向的就是創建這個程序物件時的環境，

接下來我們來描述程序物件的應用，環境模型說明，將一個程序物件應用于一組實參時，將會建立起一個新的環境，其中包含了將所有形參系結到對應實參的一個幀，該幀的外圍環境就是創建該程序物件時的環境（在這個例子中即全域環境），隨后就在這個新環境下求值該程序的體，

下面我們來演示這一規則的實施情況，下圖展示了在全域環境里對運算式square(5)求值而創建起來的環境結構，其中square即上圖中生成的程序，這一程序應用的結果是創建了一個新環境E1，這個環境從一個幀開始，幀中包含著將這個程序的形參x約束到實參5，這個幀引出的指標說明這個幀的外圍環境就是全域環境，現在我們要在E1里求值程序的體return x * x，因為在E1里x的值是5，所以求值結果是return 5 * 5，也就是return 25，

這樣，程序物件的應用的環境模型可總結為：

• 將一個程序物件應用于一集實參，將造出一個新幀，其中將程序的形參系結到呼叫時的實參，而后在構造起的這一新環境的背景關系中求值程序體，這個新幀的外圍環境就是創建該程序物件時的環境（這個例子中即全域環境），

PS：所謂定義一個符號(包括用def foo()定義程序或用foo = 1定義變數），也就是在當前環境frame里建一個系結，并賦予這個符號指定的值，而賦值運算=則會要求我們首先在環境中確定有關變數的系結位置，然后再修改這個系結，使之表示為這個新值，這也就是說，首先需要找到包括這個變數系結的第一個幀，然后修改這個幀，如果該變數在環境中沒有系結，賦值將報一個錯誤，當然由于Python語法的緣故，x = ...可同時表示變數定義和賦值，故此處注意例外，

此外，眾所周知，Python的基礎資料型別(如整形、字串等)是不可變（immutable）的，故對基礎資料型別而言，所謂賦值運算其實就等同于我們前面說的拿符號去系結新的物件），

3.2.2 簡單程序的應用

在1.1.5節里介紹代換模型時，我們展示了在有下面程序的定義之后，組合式f(5)，怎樣求值得到135：

def square(x):
    return x * x

def sum_of_squares(x, y):
    return square(x) + square(y)

def f(a):
    return sum_of_squares(a + 1, a * 2)

print(f(5)) # 136

現在我們用環境模型來分析同一個實體，下圖中展示出在全域環境里對f、square和sum_of_squares的定義求值后創建起的三個程序物件，每個程序物件都由一些代碼和一個指向全域環境的指標組成，

而在下圖中，我們看到的是對f(5)求值創建起的環境結構，

對于f的呼叫創建了一個新環境E1，它開始于一個幀，其中f的形參a被系結到實參5，我們需要在E1里求值f的體：

return sum_of_squares(a + 1, a * 2)

求值sum_of_squares這個組合式時，正如我們前面所說的，首先需要求值其中的子運算式，第一個子運算式sum_of_squares以一個程序物件為值（請注意看這個值是如何找到的：首先在E1的第一個幀里找，這里沒有包含sum_of_squares的系結，而后進入有關的外圍環境，即全域環境，并在那里找到了創建程序物件時確立好的系結），對另外兩個子運算式的求值是應用兩個基本運算子+和*，通過求職組合式a + 1和a * 2分別得到6和10，

現在需要把程序物件sum_of_squares應用于實參6和10，這時得到的是一個新環境E2，形式引數x和y在其中系結與其對應的實際引數6和10，然后繼續在E2里求值組合式square(x) + square(y)，以此類推，

這里需要注意的是，對square的每個呼叫都會創建起一個包含著x的系結的新環境，事實上這就是通過不同的幀去維護所有名字為x的區域變數互不相同，還請注意，由square創建的每個幀都指向全域環境，因為square程序物件需要從全域環境中找到，

各個子運算式求值后回傳得到的值，對square的兩個呼叫產生的值被sum_of_squares加起來，作為求值的結果回傳，因為我們在這里關心的是環境結構，因此將不仔細考察這些回傳值在呼叫之間傳遞的問題，留到第5章討論（將會涉及到堆疊結構），

3.2.3 將幀看作區域狀態的存盤庫（repository）

現在可以從環境模型出發，看看怎樣用程序和賦值表示帶有區域狀態的物件，作為一個例子，還是考慮取自3.1.1節的由呼叫下面程序創建的“提款處理器”：

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

讓我們仔細看看下式的求值：

W1 = make_withdraw(100)

而后做：

print(W1(50)) # 50

下圖展示了在全域環境里定義make_withdraw程序的結果，這一求值產生出一個程序物件，其中包含著一個指向全域環境的指標，

到目前為止，這個實體中還沒出現于前面看過的實體不同的東西，除了程序體中內置一個閉包函式withdraw之外，

計算中有趣的現象出現在將程序make_withdraw應用于一個實參的時候：

W1 = make_withdraw(100)

與往常一樣，我們在開始時設定了環境E1，其中將形參balance系結到實參100，并接著在這一環境里求值make_withdraw的體，也即內置閉包函式withdraw的定義，然后有趣之處來了，這一求值構造起一個新程序物件，其代碼由這個閉包函式所描述，而它的環境就是E1，這樣做出程序物件被作為呼叫make_withdraw的回傳值，在全域環境里系結于符號W1，因為W1 = ...這個變數定義本身的求值是在全域環境里進行的，下圖顯示出這樣的結果得到的環境結構，

PS：上圖make_withdraw中之所以要加nonlocal，乃是在因為Python中想要修改外圍環境中的自由變數，必須要加nonlocal/global將其先系結到內層環境，而Lisp則不需要人工系結，

Python的作用域規則和SML、Lisp一樣，采用詞法作用域（lexical scope）^[3]規則，所謂詞法作用域規則，即在程序中遇到自由變數（不是形參也不是函式內部定義的區域變數）時，要去參考外圍程序定義中所出現的系結，也即去本程序定義的環境中查詢（這里的順序即是著名的LEGB規則^[4]：Local scopes -> Enclosing -> Global -> Built-in）；與之相反的是動態作用域，即在程序中遇到自由變數時，去函式呼叫時的環境中查詢， 欲了解更多詞法作用域和動態作用域的知識，可參見知乎問題[5]，

現在讓我們來分析將W1應用于一個引數時所發生的情況：

print(W1(50)) # 50

此時首先要構造出一個幀，W1的形參amount在其中系結到實參50，需要注意的最關鍵的一點是，這個幀的外圍環境并不是全域環境，而是環境E1，因為它才是由程序物件W1所指定的外圍環境，現在我們需要在這個新環境中求值下面的程序體：

    nonlocal balance
    if balance > amount:
        balance = balance - amount
        return balance
    else:
        return "Insufficient funds"

這樣做得到的環境結構如下圖所示，在被求值的運算式里參考了amount和balance，其中amount在環境里的第一個幀中就能找到，而balance則沿著外圍環境指標向前在E1里找到，

在執行賦值運算=時，位于E1里balance的系結就被修改了，對W1的呼叫完成時，balance是50，而包含著這個balance的幀仍由程序物件W1指著，系結amount的那個幀（即執行修改balance的代碼的那個幀）現在已經無關緊要了，因為構造它的程序已經結束，在下次W1被呼叫時，這一程序又會構造另一個幀，其中建立起amount的一個新系結，這個幀的外圍環境還是E1，根據上面的分析，我們可以看到E1怎樣起著保存程序物件的區域狀態變數的“位置”的作用，下圖展示的便是呼叫W1之后的情景，

現在來看我們通過再次呼叫make_withdraw，創建起第二個“提款”物件的情況：

W2 = make_withdraw(100)

這樣做產生出的環境結構如下圖所示，其中顯示了W2是另一個程序物件，通過呼叫make_withdraw為W2創建起的環境是E2，它包含了一個幀，其中包含著它自己對balance的區域系結，在另一方面，W1和W2擁有相同的代碼，也就是在make_withdraw體內的那個閉包函式withdraw所確定的代碼（這里究竟W1和W2是共享計算機里保存的同一段物理代碼，還是各自維持自己的一份拷貝，則完全是一種實作細節，我們在第4章實作的解釋器里采用共享代碼的方式），這里對W1呼叫參考的是保存在E1里的狀態變數balance，對W2的呼叫參考的是在E2里的balance，故 W1和W2在行為上是完全獨立的物件，

3.2.4 內部定義

1.1.8節里我們介紹了程序可以有內部定義的思想，這樣就引入了塊結構（block structure），就像下面計算平方根的程序里的情況：

def sqrt(x):
    def is_good_enough(guess):
        return abs(guess**2 - x) < 0.001

    def improve(guess):
        return (guess + x/guess)/2

    def sqrt_iter(guess):
        if is_good_enough(guess):
            return guess
        else:
            return sqrt_iter(improve(guess))
        
    return  sqrt_iter(1.0)

print(sqrt(2)) # 1.4142156862745097

這也是一個詞法作用域的經典例子，現在我們可以利用上面的環境模型，去考察為什么這些內部定義具有所需要的行為，下圖所示的是運算式sqrt(2)求值中的一個時刻，此時內部程序is_good_enough被第一次呼叫，其中的guess等于1.

注意這時的環境結構，sqrt是全域環境里的一個符號，它被系結到一個程序物件，與之關聯的環境就是全域環境，在sqrt被呼叫時，形成了一個新的環境E1，它將成為全域環境的下屬，在E1中，引數x被系結到2，而后在E1里求值sqrt的體，由于sqrt體中的第一個運算式是：

def is_good_enough(guess):
    return abs(guess**2 - x) < 0.001

對這一運算式在環境E1里求值并定義出程序is_good_enough，更準確地說，符號is_good_enough被加入到E1的第一個幀中，并被系結于一個程序物件，其關聯的環境是E1（注意這里程序物件和其符號不在全域環境中系結，這點和我們之前講的閉包有鮮明區別，在閉包中雖然閉包函式雖然有自己的外圍環境，但閉包函式物件和其符號卻仍然是在全域環境中系結的），與此類似，improve和sqrt_iter也在E1里定義為程序，為了簡潔起見，在上圖中只顯示了系結于is_good_enough的程序物件，

在定義好各個區域程序物件之后，運算式sqrt_iter(1.0)被求值，還是在環境E1里，因此，呼叫在E1里系結于符號sqrt_iter的程序物件時，我們以1作為實參，然后這一呼叫創建了另一個環境E2，在其中sqrt_iter的形參guess被系結到1，sqrt_iter轉而（在E2里）以guess作為實參呼叫is_good_enough，這就建立了另一個環境E3，此時雖然sqrt_iter和is_good_enough都有名字為guess的形參，但它們是兩個不同的區域變數，位于不同的幀中，與之相對地，E2和E3都以E1作為其外圍環境，這樣出現在sqrt_iter和is_good_enough體內部的符號x都將參考出現在E1里x的系結，也就是原來sqrt被呼叫時的那個x值，

這樣，環境模型已經解釋清楚了以前區域程序定義作為程式化模塊技術的兩個關鍵性質：

• 區域程序的名字不會與它們外圍程序之外的名字互相干擾，這是因為這些區域程序的名字都是在他們的外圍程序運行時所創建的幀里系結的，而不是在全域環境中系結的，

• 區域程序只需要將它們外圍程序的形參作為自由變數，就可以訪問外圍程序的實參，這是因為對于區域程序體的求值所在的環境是它們外圍程序求值所在的環境的下屬，

參考

• [1] Abelson H, Sussman G J. Structure and interpretation of computer programs[M]. The MIT Press, 1996.

• [2] 知乎：i＝1，為什么 (++i)+(++i)＝6？

• [3] Stackoverflow：Does Python scoping rule fits the definition of lexical scoping? [duplicate]

• [4] Real Python Tutorials: Python Scope & the LEGB Rule: Resolving Names in Your Code

• [5] 知乎：動態作用域和詞法域的區別是什么？

標籤：Python

上一篇：chatgpt寫程式-python小游戲-2048-pygame

下一篇：Python工具箱系列(二十九)