摘要：操作函數(shù)的函數(shù)叫做高階函數(shù)。這一節(jié)展示了高階函數(shù)可用作強大的抽象機制，極大提升語言的表現(xiàn)力。新的環(huán)境特性高階函數(shù)。這是因為局部函數(shù)的函數(shù)體的求值環(huán)境擴展于定義處的求值環(huán)境。這種命名慣例并不由解釋器強制，只是函數(shù)名稱的一部分。

來源：1.6   Higher-Order Functions
譯者：飛龍
協(xié)議：CC BY-NC-SA 4.0

我們已經(jīng)看到，函數(shù)實際上是描述復(fù)合操作的抽象，這些操作不依賴于它們的參數(shù)值。在square中，

>>> def square(x):
        return x * x

我們不會談?wù)撎囟〝?shù)值的平方，而是一個獲得任何數(shù)值平方的方法。當(dāng)然，我們可以不定義這個函數(shù)來使用它，通過始終編寫這樣的表達式：

>>> 3 * 3
9
>>> 5 * 5
25

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

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

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

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

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

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

>>> 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

第三個，計算這個級數(shù)中式子的和：

它會慢慢收斂于pi。

>>> 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

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

def (n):
    total, k = 0, 1
    while k <= n:
        total, k = total + (k), (k)
    return total

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

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

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

>>> 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

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

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

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

>>> 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

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

盡管函數(shù)的意義在概念上擴展了，我們對于如何求解調(diào)用表達式的環(huán)境模型也優(yōu)雅地延伸到了高階函數(shù)，沒有任何改變。當(dāng)一個用戶定義函數(shù)以一些實參調(diào)用時，形式參數(shù)會在最新的局部幀中綁定實參的值（它們可能是函數(shù)）。

考慮下面的例子，它實現(xiàn)了迭代改進的一般方法，并且可以用于計算黃金比例。迭代改進算法以一個方程的解的guess（推測值）開始。它重復(fù)調(diào)用update函數(shù)來改進這個推測值，并且調(diào)用test來檢查是否當(dāng)前的guess“足夠接近”所認為的正確值。

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

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

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

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

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

黃金比例，通常叫做phi，是經(jīng)常出現(xiàn)在自然、藝術(shù)、和建筑中的數(shù)值。它可以通過iter_improve使用golden_update來計算，并且在它的后繼等于它的平方時收斂。

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

這里，我們已經(jīng)向全局幀添加了多個綁定。函數(shù)值的描述為了簡短而有所刪節(jié)：

使用golden_update和golden_test參數(shù)來調(diào)用iter_improve會計算出黃金比例的近似值。

>>> iter_improve(golden_update, golden_test)
1.6180371352785146

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

完成near的求值之后，我們看到golden_test為False，因為 1 并不非常接近于 2。所以，while子句代碼組內(nèi)的求值過程，以及這個機制的過程會重復(fù)多次。

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

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

>>> 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"

新的環(huán)境特性：高階函數(shù)。

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

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

讓我們考慮一個新問題：計算一個數(shù)的平方根。重復(fù)調(diào)用下面的更新操作會收斂于x的平方根：

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

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

>>> 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)

就像局部賦值，局部的def語句僅僅影響當(dāng)前的局部幀。這些函數(shù)僅僅當(dāng)square_root求值時在作用域內(nèi)。和求值過程一致，局部的def語句在square_root調(diào)用之前并不會求值。

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

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

每個用戶定義的函數(shù)都有一個關(guān)聯(lián)環(huán)境：它的定義所在的環(huán)境。

當(dāng)一個用戶定義的函數(shù)調(diào)用時，它的局部幀擴展于函數(shù)所關(guān)聯(lián)的環(huán)境。

回到square_root，所有函數(shù)都在全局環(huán)境中定義，所以它們都關(guān)聯(lián)到全局環(huán)境，當(dāng)我們求解square_root的前兩個子句時，我們創(chuàng)建了關(guān)聯(lián)到局部環(huán)境的函數(shù)。在

>>> square_root(256)
16.00000000000039

的調(diào)用中，環(huán)境首先添加了square_root的局部幀，并且求出def語句update和test（只展示了update）：

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

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

以這種方式，update的函數(shù)體能夠解析名稱x。所以我們意識到了詞法作用域的兩個關(guān)鍵優(yōu)勢。

局部函數(shù)的名稱并不影響定義所在函數(shù)外部的名稱，因為局部函數(shù)的名稱綁定到了定義處的當(dāng)前局部環(huán)境中，而不是全局環(huán)境。

局部函數(shù)可以訪問外層函數(shù)的環(huán)境。這是因為局部函數(shù)的函數(shù)體的求值環(huán)境擴展于定義處的求值環(huán)境。

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

新的環(huán)境特性：局部函數(shù)定義。

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

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

>>> 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

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

這里，我們開始觀察我們在計算的復(fù)雜模型中投入的回報。我們的環(huán)境模型不需要任何修改就能支持以這種方式返回函數(shù)的能力。

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

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

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

我們可以通過構(gòu)造相應(yīng)的英文語句來理解 Lambda 表達式：

     lambda            x            :          f(g(x))
"A function that    takes x    and returns     f(g(x))"

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

>>> compose1 = lambda f,g: lambda x: f(g(x))

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

這種風(fēng)格規(guī)范不是準則，你可以想怎么寫就怎么寫，但是，在你編寫程序時，要考慮某一天可能會閱讀你的程序的人們。如果你可以讓你的程序更易于理解，你就幫了人們一個忙。

Lambda 的術(shù)語是一個歷史的偶然結(jié)果，來源于手寫的數(shù)學(xué)符號和早期打字系統(tǒng)限制的不兼容。

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

盡管它的詞源不同尋常，Lambda 表達式和函數(shù)調(diào)用相應(yīng)的形式語言，以及 Lambda 演算都成為了計算機科學(xué)概念的基礎(chǔ)，并在 Python 編程社區(qū)廣泛傳播。當(dāng)我們學(xué)習(xí)解釋器的設(shè)計時，我們將會在第三章中重新碰到這個話題。

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

牛頓法是一個傳統(tǒng)的迭代方法，用于尋找使數(shù)學(xué)函數(shù)返回值為零的參數(shù)。這些值叫做一元數(shù)學(xué)函數(shù)的根。尋找一個函數(shù)的根通常等價于求解一個相關(guān)的數(shù)學(xué)方程。

16 的平方根是滿足square(x) - 16 = 0的x值。

以 2 為底 32 的對數(shù)（例如 2 與某個指數(shù)的冪為 32）是滿足pow(2, x) - 32 = 0的x值。

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

在我們繼續(xù)之前有個注解：我們知道如何計算平方根和對數(shù)，這個事實很容易當(dāng)做自然的事情。并不只是 Python，你的手機和計算機，可能甚至你的手表都可以為你做這件事。但是，學(xué)習(xí)計算機科學(xué)的一部分是弄懂這些數(shù)如何計算，而且，這里展示的通用方法可以用于求解大量方程，而不僅僅是內(nèi)建于 Python 的東西。

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

>>> 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)

當(dāng)然，在我們定義find_root之前，現(xiàn)在還不能調(diào)用任何函數(shù)，所以我們需要理解牛頓法如何工作。

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

f(x) = square(x) - 16（細線）

f(x) = pow(2, x) - 32（粗線）

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

由于它們是光滑的（可導(dǎo)的），這些曲線可以通過任何點上的直線來近似。牛頓法根據(jù)這些線性的近似值來尋找函數(shù)的根。

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

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

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

>>> 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

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

>>> 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

當(dāng)你實驗牛頓法時，要注意它不總是收斂的。iter_improve的初始推測值必須足夠接近于根，而且函數(shù)必須滿足各種條件。雖然具有這些缺陷，牛頓法是一個用于解決微分方程的強大的通用計算方法。實際上，非?？焖俚膶?shù)算法和大整數(shù)除法也采用這個技巧的變體。

這一節(jié)的開始，我們以觀察用戶定義函數(shù)作為關(guān)鍵的抽象技巧，因為它們讓我們能夠?qū)⒂嬎愕耐ㄓ梅椒ū磉_為編程語言中的顯式元素。現(xiàn)在我們已經(jīng)看到了高階函數(shù)如何讓我們操作這些通用方法來進一步創(chuàng)建抽象。

作為程序員，我們應(yīng)該留意識別程序中低級抽象的機會，在它們之上構(gòu)建，并泛化它們來創(chuàng)建更加強大的抽象。這并不是說，一個人應(yīng)該總是盡可能以最抽象的方式來編程；專家級程序員知道如何選擇合適于他們?nèi)蝿?wù)的抽象級別。但是能夠基于這些抽象來思考，以便我們在新的上下文中能使用它們十分重要。高階函數(shù)的重要性是，它允許我們更加明顯地將這些抽象表達為編程語言中的元素，使它們能夠處理其它的計算元素。

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

它們可以綁定到名稱。

它們可以作為參數(shù)向函數(shù)傳遞。

它們可以作為函數(shù)的返回值返回。

它們可以包含在好素具結(jié)構(gòu)中。

Python 總是給予函數(shù)一等地位，所產(chǎn)生的表現(xiàn)力的收益是巨大的。另一方面，控制結(jié)構(gòu)不能做到：你不能像使用sum那樣將if傳給一個函數(shù)。

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

>>> def trace1(fn):
        def wrapped(x):
            print("-> ", fn, "(", x, ")")
            return fn(x)
        return wrapped
>>> @trace1
    def triple(x):
        return 3 * x
>>> triple(12)
->   ( 12 )
36

這個例子中，定義了高階函數(shù)trace1，它返回一個函數(shù)，這個函數(shù)在調(diào)用它的參數(shù)之前執(zhí)行print語句來輸出參數(shù)。triple的def語句擁有一個注解，@trace1，它會影響def的執(zhí)行規(guī)則。像通常一樣，函數(shù)triple被創(chuàng)建了，但是，triple的名稱并沒有綁定到這個函數(shù)上，而是綁定到了在新定義的函數(shù)triple上調(diào)用trace1的返回函數(shù)值上。在代碼中，這個裝飾器等價于：

>>> def triple(x):
        return 3 * x
>>> triple = trace1(triple)

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