【計算機程序的構造和解釋】使用函數構建抽象——5. 高階函數

我們已經看到，函數實際上是描述複合操作的抽象，這些操作不依賴於它們的參數值。在 square 中，

<code>>>> def square(x):
        return x * x
/<code>

我們不會談論特定數值的平方，而是一個獲得任何數值平方的方法。當然，我們可以不定義這個函數來使用它，通過始終編寫這樣的表達式：

<code>>>> 3 * 3
9
>>> 5 * 5
25
/<code>

並且永遠不會顯式提及square。這種實踐適合類似square的簡單操作。但是對於更加複雜的操作會變得困難。通常，缺少函數定義會對我們非常不利，它會強迫我們始終工作在特定操作的層級上，這在語言中非常原始（這個例子中是乘法），而不是高級操作。我們應該從強大的編程語言索取的東西之一，是通過將名稱賦為常用模式來構建抽象的能力，以及之後直接使用抽象的能力。函數提供了這種能力。

我們將會在下個例子中看到，代碼中會反覆出現一些常見的編程模式，但是使用一些不同函數來實現。這些模式也可以被抽象和給予名稱。

為了將特定的通用模式表達為具名概念，我們需要構造可以接受其他函數作為參數的函數，或者將函數作為返回值的函數。操作函數的函數叫做高階函數。這一節展示了高階函數可用作強大的抽象機制，極大提升語言的表現力。

作為參數的函數

考慮下面三個函數，它們都計算總和。第一個，sum_naturals，計算截至n的自然數的和：

<code>>>> def sum_naturals(n):
        total, k = 0, 1
        while k <= n: 
            total, k = total + k, k + 1
        return total
>>> sum_naturals(100)
5050
/<code>

第二個，sum_cubes，計算截至n的自然數的立方和：

<code>>>> def sum_cubes(n): 
        total, k = 0, 1
        while k <= n: 
            total, k = total + pow(k, 3), k + 1
        return total
>>> sum_cubes(100)
25502500
/<code>

第三個，計算這個級數中式子的和：

它會慢慢收斂於pi。

<code>>>> def pi_sum(n): 
        total, k = 0, 1
        while k <= n: 
            total, k = total + 8 / (k * (k + 2)), k + 4
        return total
>>> pi_sum(100)
3.121594652591009
/<code>

這三個函數在背後都具有相同模式。它們大部分相同，只是名字、用於計算被加項的 k 的函數，以及提供 k 的下一個值的函數不同。我們可以通過向相同的模板中填充槽位來生成每個函數：

<code>def <name>(n): 
    total, k = 0, 1
    while k <= n: 
        total, k = total + <term>(k), <next>(k)
    return total
/<next>/<term>/<name>/<code>

這個通用模板的出現是一個強有力的證據，證明有一個實用抽象正在等著我們表現出來。這些函數的每一個都是式子的求和。作為程序的設計者，我們希望我們的語言足夠強大，便於我們編寫函數來自我表達求和的概念，而不僅僅是計算特定和的函數。我們可以在 Python 中使用上面展示的通用模板，並且把槽位變成形式參數來輕易完成它。

<code>>>> def summation(n, term, next):
        total, k = 0, 1
        while k <= n:  

            total, k = total + term(k), next(k)
        return total
/<code>

要注意summation接受上界n，以及函數term和next作為參數。我們可以像任何函數那樣使用summation，它簡潔地表達了求和。

<code>>>> def cube(k):
        return pow(k, 3)
>>> def successor(k):
        return k + 1
>>> def sum_cubes(n):
        return summation(n, cube, successor)
>>> sum_cubes(3)
36
/<code>

使用identity函數來返回參數自己，我們就可以對整數求和：

<code>>>> def identity(k):
        return k
>>> def sum_naturals(n):
        return summation(n, identity, successor)
>>> sum_naturals(10)
55
/<code>

我們也可以逐步定義pi_sum，使用我們的summation抽象來組合組件。

<code>>>> def pi_term(k): 
        denominator = k * (k + 2)
        return 8 / denominator
>>> def pi_next(k):
        return k + 4
>>> def pi_sum(n):
        return summation(n, pi_term, pi_next)
>>> pi_sum(1e6)
3.1415906535898936
/<code>

作為一般方法的函數

我們引入的用戶定義函數作為一種數值運算的抽象模式，便於使它們獨立於涉及到的特定數值。使用高階函數，我們開始尋找更強大的抽象類型：一些函數表達了計算的一般方法，獨立於它們調用的特定函數。

儘管函數的意義在概念上擴展了，我們對於如何求解調用表達式的環境模型也優雅地延伸到了高階函數，沒有任何改變。當一個用戶定義函數以一些實參調用時，形式參數會在最新的局部幀中綁定實參的值（它們可能是函數）。

考慮下面的例子，它實現了迭代改進的一般方法，並且可以用於計算黃金比例。迭代改進算法以一個方程的解的guess（推測值）開始。它重複調用update函數來改進這個推測值，並且調用 test 來檢查是否當前的guess“足夠接近”所認為的正確值。

<code>>>> def iter_improve(update, test, guess=1):
        while not test(guess): 
            guess = update(guess)
        return guess
/<code>

test函數通常檢查兩個函數f和g在guess值上是否彼此接近。測試f(x)是否接近於g(x)也是計算的一般方法。

<code>>>> def near(x, f, g):
        return approx_eq(f(x), g(x))
/<code>

程序中測試相似性的一個常見方式是將數值差的絕對值與一個微小的公差值相比：

<code>>>> def approx_eq(x, y, tolerance=1e-5):
        return abs(x - y) < tolerance
/<code>

黃金比例，通常叫做phi，是經常出現在自然、藝術、和建築中的數值。它可以通過iter_improve使用golden_update來計算，並且在它的後繼等於它的平方時收斂。

<code>>>> def golden_update(guess):
        return 1 / guess + 1
>>> def golden_test(guess):
        return near(guess, square, successor)
/<code>

這裡，我們已經向全局幀添加了多個綁定。函數值的描述為了簡短而有所刪節：

使用golden_update和golden_test參數來調用iter_improve會計算出黃金比例的近似值。

<code>>>> iter_improve(golden_update, golden_test)
1.6180371352785146
/<code>

通過跟蹤我們的求值過程的步驟，我們就可以觀察結果如何計算。首先，iter_improve的局部幀以update、test和guess構建。在iter_improve的函數體中，名稱test綁定到golden_test上，它在初始值guess上調用。之後，golden_test調用near，創建第三個局部幀，它將形式參數f和g綁定到square和successor上。

完成near的求值之後，我們看到golden_test為False，因為 1 並不非常接近於 2。所以，while子句代碼組內的求值過程，以及這個機制的過程會重複多次。

這個擴展後的例子展示了計算機科學中兩個相關的重要概念。首先，命名和函數允許我們抽象而遠離大量的複雜性。當每個函數定義不重要時，由求值過程觸發的計算過程是相當複雜的，並且我們甚至不能展示所有東西。其次，基於事實，我們擁有了非常通用的求值過程，小的組件組合在複雜的過程中。理解這個過程便於我們驗證和檢查我們創建的程序。

像通常一樣，我們的新的一般方法iter_improve需要測試來檢查正確性。黃金比例可以提供這樣一個測試，因為它也有一個閉式解，我們可以將它與迭代結果進行比較。

<code>>>> phi = 1 / 2 + pow(5, 1 / 2) / 2
>>> def near_test():
        assert near(phi, square, successor), 'phi * phi is not near phi + 1'
>>> def iter_improve_test(): 
        approx_phi = iter_improve(golden_update, golden_test)
        assert approx_eq(phi, approx_phi), 'phi differs from its approximation'
/<code>

新的環境特性：高階函數。

附加部分：我們在測試的證明中遺漏了一步。求出公差值e的範圍，使得如果tolerance為e的near(x, square, successor)值為真，那麼使用相同公差值的approx_eq(phi, x)值為真。

定義函數Ⅲ：嵌套定義

上面的例子演示了將函數作為參數傳遞的能力如何提高了編程語言的表現力。每個通用的概念或方程都能映射為自己的小型函數，這一方式的一個負面效果是全局幀會被小型函數弄亂。另一個問題是我們限制於特定函數的簽名：iter_improve的update參數必須只接受一個參數。Python 中，嵌套函數的定義解決了這些問題，但是需要我們重新修改我們的模型。

讓我們考慮一個新問題：計算一個數的平方根。重複調用下面的更新操作會收斂於x的平方根：

<code>>>> def average(x, y):
        return (x + y) / 2
>>> def sqrt_update(guess, x):
        return average(guess, x / guess)
/<code>

這個帶有兩個參數的更新函數和iter_improve不兼容，並且它只提供了一個介值。我們實際上只關心最後的平方根。這些問題的解決方案是把函數放到其他定義的函數體中。

<code>>>> def square_root(x):
        def update(guess):
            return average(guess, x / guess)
        def test(guess):
            return approx_eq(square(guess), x)
        return iter_improve(update, test)
/<code>

就像局部賦值，局部的def語句僅僅影響當前的局部幀。這些函數僅僅當square_root求值時在作用域內。和求值過程一致，局部的def語句在square_root調用之前並不會求值。

詞法作用域。局部定義的函數也可以訪問它們定義所在作用域的名稱綁定。這個例子中，update引用了名稱x，它是外層函數square_root的一個形參。這種在嵌套函數中共享名稱的規則叫做詞法作用域。嚴格來說，內部函數能夠訪問定義所在環境（而不是調用所在位置）的名稱。

我們需要兩個對我們環境的擴展來兼容詞法作用域。

1. 每個用戶定義的函數都有一個關聯環境：它的定義所在的環境。
2. 當一個用戶定義的函數調用時，它的局部幀擴展於函數所關聯的環境。

回到square_root，所有函數都在全局環境中定義，所以它們都關聯到全局環境，當我們求解square_root的前兩個子句時，我們創建了關聯到局部環境的函數。在

<code>>>> square_root(256)
16.00000000000039
/<code>

的調用中，環境首先添加了square_root的局部幀，並且求出def語句update和test（只展示了update）：

隨後，update的名稱解析到這個新定義的函數上，它是向iter_improve傳入的參數。在iter_improve的函數體中，我們必須以初始值 1 調用update函數。最後的這個調用以一開始只含有g的局部幀創建了update的環境，但是之前的square_root幀上仍舊含有x的綁定。

這個求值過程中，最重要的部分是函數所關聯的環境變成了局部幀，它是函數求值的地方。這個改變在圖中以藍色箭頭高亮。

以這種方式，update的函數體能夠解析名稱x。所以我們意識到了詞法作用域的兩個關鍵優勢。

• 局部函數的名稱並不影響定義所在函數外部的名稱，因為局部函數的名稱綁定到了定義處的當前局部環境中，而不是全局環境。
• 局部函數可以訪問外層函數的環境。這是因為局部函數的函數體的求值環境擴展於定義處的求值環境。

update函數自帶了一些數據：也就是在定義處環境中的數據。因為它以這種方式封裝信息，局部定義的函數通常叫做閉包。

新的環境特性：局部函數定義。

作為返回值的函數

我們的程序可以通過創建返回值是它們本身的函數，獲得更高的表現力。帶有詞法作用域的編程語言的一個重要特性就是，局部定義函數在它們返回時仍舊持有所關聯的環境。下面的例子展示了這一特性的作用。

在定義了許多簡單函數之後，composition是包含在我們的編程語言中的自然組合法。也就是說，提供兩個函數f(x)和g(x)，我們可能希望定義h(x) = f(g(x))。我們可以使用現有工具來定義複合函數：

<code>>>> def compose1(f, g):
        def h(x):
            return f(g(x))
        return h
>>> add_one_and_square = compose1(square, successor)
>>> add_one_and_square(12)
169
/<code>

compose1中的1表明複合函數和返回值都只接受一個參數。這種命名慣例並不由解釋器強制，1只是函數名稱的一部分。

這裡，我們開始觀察我們在計算的複雜模型中投入的回報。我們的環境模型不需要任何修改就能支持以這種方式返回函數的能力。

Lambda 表達式

目前為止，每次我們打算定義新的函數時，我們都會給它一個名稱。但是對於其它類型的表達式，我們不需要將一個間接產物關聯到名稱上。也就是說，我們可以計算a*b + c*d，而不需要給子表達式a*b或c*d，或者整個表達式來命名。Python 中，我們可以使用 Lambda 表達式憑空創建函數，它會求值為匿名函數。Lambda 表達式是函數體具有單個返回表達式的函數，不允許出現賦值和控制語句。

Lambda 表達式十分受限：它們僅僅可用於簡單的單行函數，求解和返回一個表達式。在它們適用的特殊情形中，Lambda 表達式具有強大的表現力。

<code>>>> def compose1(f,g):
        return lambda x: f(g(x))
/<code>

我們可以通過構造相應的英文語句來理解 Lambda 表達式：

<code>     lambda            x            :         f(g(x))
"A function that    takes x    and returns    f(g(x))"
/<code>

一些程序員發現使用 Lambda 表達式作為匿名函數非常簡短和直接。但是，複合的 Lambda 表達式非常難以辨認，儘管它們很簡潔。下面的定義是是正確的，但是許多程序員不能很快地理解它：

<code>>>> compose1 = lambda f, g: lambda x: f(g(x))
/<code>

通常，Python 的代碼風格傾向於顯式的def語句而不是 Lambda 表達式，但是允許它們在簡單函數作為參數或返回值的情況下使用。

這種風格規範不是準則，你可以想怎麼寫就怎麼寫，但是，在你編寫程序時，要考慮某一天可能會閱讀你的程序的人們。如果你可以讓你的程序更易於理解，你就幫了人們一個忙。

Lambda 的術語是一個歷史的偶然結果，來源於手寫的數學符號和早期打字系統限制的不兼容。

使用 lambda 來引入過程或函數看起來是不正當的。這個符號要追溯到 Alonzo Church，他在 20 世紀 30 年代開始使用“帽子”符號；他把平方函數記為ŷ . y × y。但是失敗的打字員將這個帽子移到了參數左邊，並且把它改成了大寫的 lambda：Λy . y × y；之後大寫的 lambda 就變成了小寫，現在我們就會在數學書裡看到λy . y × y，以及在 Lisp 裡看到(lambda (y) (* y y))。– Peter Norvig (norvig.com/lispy2.html)

儘管它的詞源不同尋常，Lambda 表達式和函數調用相應的形式語言，以及 Lambda 演算都成為了計算機科學概念的基礎，並在 Python 編程社區廣泛傳播。當我們學習解釋器的設計時，我們將會重新碰到這個話題。

示例：牛頓法

最後的擴展示例展示了函數值、局部定義和 Lambda 表達式如何一起工作來簡明地表達通常的概念。

牛頓法是一個傳統的迭代方法，用於尋找使數學函數返回值為零的參數。這些值叫做一元數學函數的根。尋找一個函數的根通常等價於求解一個相關的數學方程。

• 16 的平方根是滿足square(x) - 16 = 0的x值。
• 以 2 為底 32 的對數（例如 2 與某個指數的冪為 32）是滿足pow(2, x) - 32 = 0的x值。

所以，求根的通用方法會向我們提供算法來計算平方根和對數。而且，我們想要計算根的等式只包含簡單操作：平法和乘方。

在我們繼續之前有個註解：我們知道如何計算平方根和對數，這個事實很容易當做自然的事情。並不只是 Python，你的手機和計算機，可能甚至你的手錶都可以為你做這件事。但是，學習計算機科學的一部分是弄懂這些數如何計算，而且，這裡展示的通用方法可以用於求解大量方程，而不僅僅是內建於 Python 的東西。

在開始理解牛頓法之前，我們可以開始編程了。這就是函數抽象的威力。我們簡單地將之前的語句翻譯成代碼：

<code>>>> def square_root(a):
        return find_root(lambda x: square(x) - a)
>>> def logarithm(a, base=2):
        return find_root(lambda x: pow(base, x) - a)
/<code>

當然，在我們定義find_root之前，現在還不能調用任何函數，所以我們需要理解牛頓法如何工作。

牛頓法也是一個迭代改進算法：它會改進任何可導函數的根的推測值。要注意我們感興趣的兩個函數都是平滑的。對於

• f(x) = square(x) - 16（細線）
• f(x) = pow(2, x) - 32（粗線）

在二維平面上畫出x對f(x)的圖像，它展示了兩個函數都產生了光滑的曲線，它們在某個點穿過了 0。

由於它們是光滑的（可導的），這些曲線可以通過任何點上的直線來近似。牛頓法根據這些線性的近似值來尋找函數的根。

想象經過點(x, f(x))的一條直線，它與函數f(x)的曲線在這一點的斜率相同。這樣的直線叫做切線，它的斜率叫做f在x上的導數。

這條直線的斜率是函數值改變量與函數參數改變量的比值。所以，按照f(x)除以這個斜率來平移x，就會得到切線到達 0 時的x值。

我們的牛頓更新操作表達了跟隨這條切線到零的計算過程。我們通過在非常小的區間上計算函數斜率來近似得到函數的導數。

<code>>>> def approx_derivative(f, x, delta=1e-5): 
        df = f(x + delta) - f(x)
        return df / delta
>>> def newton_update(f):
        def update(x):
            return x - f(x) / approx_derivative(f, x)
        return update
/<code>

最後，我們可以定義基於newton_update（我們的迭代改進算法）的find_root函數，以及一個測試來觀察f(x)是否接近於 0。我們提供了一個較大的初始推測值來提升logarithm的性能。

<code>>>> def find_root(f, initial_guess=10):
        def test(x):
            return approx_eq(f(x), 0)
        return iter_improve(newton_update(f), test, initial_guess)
>>> square_root(16)
4.000000000026422
>>> logarithm(32, 2)
5.000000094858201
/<code>

當你實驗牛頓法時，要注意它不總是收斂的。iter_improve的初始推測值必須足夠接近於根，而且函數必須滿足各種條件。雖然具有這些缺陷，牛頓法是一個用於解決微分方程的強大的通用計算方法。實際上，非常快速的對數算法和大整數除法也採用這個技巧的變體。

抽象和一等函數

這一節的開始，我們以觀察用戶定義函數作為關鍵的抽象技巧，因為它們讓我們能夠將計算的通用方法表達為編程語言中的顯式元素。現在我們已經看到了高階函數如何讓我們操作這些通用方法來進一步創建抽象。

作為程序員，我們應該留意識別程序中低級抽象的機會，在它們之上構建，並泛化它們來創建更加強大的抽象。這並不是說，一個人應該總是儘可能以最抽象的方式來編程；專家級程序員知道如何選擇合適於他們任務的抽象級別。但是能夠基於這些抽象來思考，以便我們在新的上下文中能使用它們十分重要。高階函數的重要性是，它允許我們更加明顯地將這些抽象表達為編程語言中的元素，使它們能夠處理其它的計算元素。

通常，編程語言會限制操作計算元素的途徑。帶有最少限制的元素被稱為具有一等地位。一些一等元素的“權利和特權”是：

1. 它們可以綁定到名稱。
2. 它們可以作為參數向函數傳遞。
3. 它們可以作為函數的返回值返回。
4. 它們可以包含在數據結構中。

Python 總是給予函數一等地位，所產生的表現力的收益是巨大的。另一方面，控制結構不能做到：你不能像使用sum那樣將if傳給一個函數。

函數裝飾器

Python 提供了特殊的語法，將高階函數用作執行def語句的一部分，叫做裝飾器。

<code>>>> def trace1(fn): 
        def wrapped(x): 
            print('-> ', fn, '(', x, ')') 
            return fn(x) 
        return wrapped
>>> @trace1 
    def triple(x): 
        return 3 * x
>>> triple(12)
-> <function> ( 12 )
36
/<function>/<code>

這個例子中，定義了高階函數trace1，它返回一個函數，這個函數在調用它的參數之前執行print語句來輸出參數。triple的def語句擁有一個註解，@trace1，它會影響def的執行規則。像通常一樣，函數triple被創建了，但是，triple的名稱並沒有綁定到這個函數上，而是綁定到了在新定義的函數triple上調用trace1的返回函數值上。在代碼中，這個裝飾器等價於：

<code>>>> def triple(x): 

        return 3 * x
>>> triple = trace1(triple)
/<code>

附加部分：實際規則是，裝飾器符號@可以放在表達式前面（@trace1僅僅是一個簡單的表達式，由單一名稱組成）。任何產生合適的值的表達式都可以。例如，使用合適的值，你可以定義裝飾器check_range，使用@check_range(1, 10)來裝飾函數定義，這會檢查函數的結果來確保它們是 1 到 10 的整數。調用check_range(1,10)會返回一個函數，之後它會用在新定義的函數上，在新定義的函數綁定到def語句中的名稱之前。感興趣的同學可以閱讀 ArielOrtiz 編寫的一篇裝飾器的簡短教程來了解更多的例子。

閱讀更多 藝賽旗RPA 的文章

關鍵字: 參數值 抽象 Square