文档：1.6 Elements of Programming
参考：cs61a.org/spring2018

1.6 高阶函数

我们已经看到，函数是一种抽象方法，它用于描述独立于它们的参数的复合运算。比如函数square，

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

我们不是在谈论特定值的平方，而是在讨论一个能获得任何数值平方数的方法。 当然，我们可以不去定义这个函数，总是编写诸如以下的表达式：

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

并且永远不会明确地提到square。这种做法对于诸如square的简单计算就足够了，但是对于更复杂的例子，例如abs或fib就将变得很困难。一般来说，缺乏函数定义将使我们处于不利之地，它迫使我们始终工作在非常原始的操作层面（这个例子中是乘法）而不是在较高级别操作。我们的程序能够计算平方，但是我们的语言将缺乏表达平方概念的能力。

我们应从强大的编程语言中索求的事情之一，就是通过将名称分配给常用模式来构建抽象的能力。函数提供这种能力。正如我们将在下面的例子中看到的，代码中会反复出现一些常见的编程模式，但是使用一些不同函数来实现。这些模式也可以被抽象和给予名称。

为了将特定的常用模式表达为具名概念，我们将需要构造可以接受其他函数作为参数或将函数作为返回值的函数。操纵函数的函数称为高阶函数。本节介绍了高阶函数如何作为强大的抽象机制，极大增加了语言的表现力。

1.6.1 作为参数的函数

以下三个函数都能计算总和。第一个函数sum_naturals，计算 n个自然数的和:

>>> 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个自然数的立方和:

>>> def sum_cubes(n):
        total, k = 0, 1
        while k <= n:
            total, k = total + k*k*k, k + 1
        return total
>>> sum_cubes(100)
25502500

第三个函数pi_sum,计算以下一系列项的总和:

>>> def pi_sum(n):
        total, k = 0, 1
        while k <= n:
            total, k = total + 8 / ((4*k-3) * (4*k-1)), k + 1
        return total
>>> pi_sum(100)
3.1365926848388144

明显地，这三个函数拥有一个相同的模式。 它们大部分是相同的，仅在函数名和用于计算被加项的k的方法有所不同。 我们可以通过填写相同模板中的槽位来生成每个函数：

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

这种相同模板的存在是实用抽象出现的有力证据。 这些函数中的每一个都是求和术语。 作为程序的设计者，我们希望我们的语言足够强大，以便我们可以编写一个表达求和概念的函数，而不是对特定的值进行求和。在Python里，我们可以通过使用上面所示的通用模板，将“槽位”转换为形式参数：

在下面的例子中，summation求和有两个参数，上限n以及用来计算第k次值的函数term。 我们能像使用任何函数一样使用summation,并简洁地表示结果。 您可以多花点时间来执行这个例子，请注意到cube是如何绑定到局部名称term上的并且如何确保1 * 1 * 1 + 2 * 2 * 2 + 3 * 3 * 3 = 36的计算正确的。 在此示例中，不再需要的帧会被删除以节省空间。

使用`identity`函数来返回其参数，我们还可以使用完全相同的`summation`求和函数来计算自然数之和。
>>> def summation(n, term):
        total, k = 0, 1
        while k <= n:
            total, k = total + term(k), k + 1
        return total
>>> def identity(x):
        return x
>>> def sum_naturals(n):
        return summation(n, identity)
>>> sum_naturals(10)
55

summation求和函数也可以直接调用，而不需要为特定序列定义另一个函数。

>>> summation(10, square)
385

我们可以使用我们的summation函数来抽象定义pi_sum函数。 我们传递参数1e6，这是1 * 10 ^ 6 = 1000000的简称，结果会慢慢收敛于pi。

>>> def pi_term(x):
        return 8 / ((4*x-3) * (4*x-1))
>>> def pi_sum(n):
        return summation(n, pi_term)
>>> pi_sum(1e6)
3.141592153589902

1.6.2 作为一般方法的函数

我们引入用户定义函数作为抽象机制，对数值运算进行抽象以使它们独立于特定数值。对于高阶函数，我们开始寻找一种更强大的抽象类型：一些能表达一般计算方法的函数，独立于它们调用的特定函数。

函数的意义发生了扩展，我们求解调用表达式的环境模型也可以适度地扩展到高阶函数的情况。当用户定义函数调用参数时，形式参数将会在最新的局部帧中绑定实参（可能是函数）的值。

思考接下来的示例，其实现了迭代改进的一般方法，并可以来计算golden ratio (黄金比例)。黄金比例，通常被称为phi，是一个与1.6近似，经常出现在自然、艺术、和建筑中的数值。

迭代改进算法开始于对方程的解的guess（猜测值）。它重复调用update更新功能来改进guess，并调用test来检查当前guess猜测值是否“足够接近”预想的正确值。

>>> def improve(update, close, guess=1):
        while not close(guess):
            guess = update(guess)
        return guess

improve改进函数是重复细化的通用表达。 它不会具体指定要解决的问题：这些细节都留给update更新函数和close关闭函数来解决。

黄金比例的众所周知的特性之一是可以通过反复叠加任何正数的倒数加上1来计算，而这个黄金比例属性是一个小于它平方的数字。 我们可以将这些属性表达为improve函数。

>>> def golden_update(guess):
        return 1/guess + 1
>>> def square_close_to_successor(guess):
        return approx_eq(guess * guess, guess + 1)

以上，我们调用了approx_eq：如果它的参数大致相等，则返回True。 我们可以将两个数字差值的绝对值与一个很小的tolerance value(公差值)进行比较。

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

使用golden_update和square_close_to_successor作为参数来调用improve，将会计算出黄金比例的近似值。

>>> improve(golden_update, square_close_to_successor)
1.6180339887498951

通过跟踪求值的步骤，我们可以看到结果是如何计算出来的。 首先，improve的局部环境被构建起来，并为update 、test 和 guess 这三个参数绑定值。 在improve的函数体中,名字close被绑定到square_close_to_successor上，用于被初始值guess调用。 我们继续跟踪接下来的步骤来看看计算黄金比例的具体过程。

一如以往，我们新的一般函数improve需要一个测试来检查其正确性。 黄金比例可以提供这样的测试，因为它也有一个精确的闭式解，我们可以将它与迭代结果进行比较。

>>> from math import sqrt
>>> phi = 1/2 + sqrt(5)/2
>>> def improve_test():
        approx_phi = improve(golden_update, square_close_to_successor)
        assert approx_eq(phi, approx_phi), 'phi differs from its approximation'
>>> improve_test()

对于这个测试，没有反馈消息就证明是好的：在执行成功的assert语句之后，improve_test返回的是None。

1.6.3 定义函数 III:嵌套定义

上面的例子演示了函数作为参数传递而显著提高了编程语言的效率的能力。 每个通用概念或方程都能映射为小型函数。 这种方式的一个负面后果是，全局帧会变得混乱。 另一个问题是我们被特定函数的签名所约束：improve的update参数必须只接受一个参数。 嵌套函数的定义解决了这两个问题，但要求我们重新调整环境模型。

让我们考虑一个新问题：计算一个数的平方根。 在编程语言中，“平方根”通常缩写为sqrt。 重复调用下面的更新操作会收敛于a的平方根：

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

这个带有两个参数的更新函数和improve不兼容（它需要接受两个参数，而不是一个参数）。我们实际上只关心最后的平方根。这些问题的解决方案是把函数放到其他定义的函数体中。

>>> def sqrt(a):
        def sqrt_update(x):
            return average(x, a/x)
        def sqrt_close(x):
            return approx_eq(x * x, a)
        return improve(sqrt_update, sqrt_close)

像局部赋值一样，局部的def语句仅影响当前的局部帧。这些函数仅仅当sqrt求值时在作用域内。和求值过程一致, 局部的def语句在sqrt调用之前并不会求值。

词法作用域。局部定义的函数可以访问定义作用域中的名称绑定。在此示例中，sqrt_update引用名称a，它是外层函数sqrt的形式参数。这种在嵌套函数中共享名称的规则称为词法作用域。最重要的是，内部函数可以访问它们被定义的环境中的名称（而不是它们被调用的位置）。

我们需要对我们的环境模型进行两个扩展，以实现词法作用域。

1.每个用户定义的函数都有父环境：它的定义所在的环境。
2.当用户定义的函数被调用时，其局部帧扩展于其父环境。
在sqrt之前，所有函数都是在全局环境中定义的，所以它们都关联到全局环境。相比之下，当Python运行sqrt的前两个子句时，它创建了与本地环境相关联的函数。在

>>> sqrt(256)
16.0

的调用中，环境首先为sqrt添加一个局部帧，并为sqrt_update和sqrt_close的def语句求值。

随后，sqrt_update的名称解析到新定义的函数上，该函数是向improve传入的参数。 在improve的函数体中，我们必须以初始值 1 调用update函数（绑定到sqrt_update）。最后这个调用创建一个sqrt_update的环境，该环境一开始仅包含x的局部帧，但是之前的sqrt帧仍然包含一个a的绑定。

扩展环境。环境可以由任意多的帧组成，总是以全局框架结束。在此sqrt示例之前，环境最多有两帧：局部帧和全局帧。通过调用在其他函数中定义的函数，通过嵌套的def语句，我们可以创建更多的帧。对sqrt_update调用的环境由三个帧组成：局部帧sqrt_update，定义sqrt_update的sqrt帧（标记为f1）和全局帧。

sqrt_update函数体中的返回表达式可以通过跟随这一系列帧来解析值。我们可以通过查找在当前环境的名称找到绑定到该名称的第一个值。 Python首先在sqrt_update帧中检查 -- 不存在。接下来，Python检查父帧中f1，并找到a绑定到256。

因此，我们意识到了Python中词法作用域的两个主要优点。

1. 局部函数的名称不会影响到定义函数外部的名称，因为局部函数名称将绑定到了定义处的当前局部环境中,而不是全局环境中。
2. 局部函数可以访问外层函数的环境，这是因为局部函数的函数体的求值环境扩展于定义处的求值环境。

sqrt_update函数自带有一些数据：在定义它的环境中引用的值。因为它以这种方式“封装”信息，所以局部定义的函数通常被称为闭包。

1.6.4 作为返回值的函数

我们可以通过创建返回值本身是函数的函数提高效率。 带有词法作用域的编程语言的一个重要特性就是，局部定义函数在它们返回时仍旧持有所关联的环境。 以下示例展示了这一特性。

在定义了许多简单函数之后，composition函数就是包含在我们的编程语言中的自然组合方法。 也就是说，给定两个函数f(x)和g(x)，我们可能想要定义h(x)= f(g(x))。 我们可以使用我们现有的工具来定义复合函数：

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

此示例的环境图显示了f和g是如何正确解析的，即使它们存在冲突的名称。

在这里，我们开始观察我们努力在计算的复杂模型中投入的回报。我们的环境模型不需要任何修改就能支持以这种方式返回函数的能力。

1.6.5 例子:牛顿法

这个扩展示例显示了函数返回值和局部定义如何一起工作来简明扼要地表达通常概念。我们将实现一种能广泛应用于机器学习，科学计算，硬件设计和优化的算法。

牛顿法是一种经典的迭代方法，用于查找使数学函数返回值为零的参数。这些值称为函数的根。找到一个函数的根通常等价于解决一些有意思的问题，例如计算平方根。

开始前的激励：您当然知道该如何计算平方根。不只是Python，您的手机，网络浏览器或计算器都可以为您做到这一点。然而，学习计算机科学的一部分是弄懂这些数如何计算,而且,这里展示的通用方法可以用于求解 大量方程,而不仅仅是内建于 Python 的东西。

牛顿的方法是一种迭代改进算法：它可以改进任何可导函数的根的推测值，这意味着它可以在任何点被直线逼近。牛顿的方法遵循这些线性近似来找到函数根。

想象经过点 (x, f(x)) 的一条直线,它与函数 f(x) 的曲线在这一点的斜率相同。这样的直线叫做tangent切线,它的斜率叫做 f 在 x 上的derivative导数。

这条直线的斜率是函数值改变量与函数参数改变量的比值。所以,按照 f(x) 除以这个斜率来 平移 x ,就会得到切线到达 0 时的 x 值。

>>> def newton_update(f, df):
        def update(x):
            return x - f(x) / df(x)
        return update

最后，我们可以定义基于newton_update（我们的迭代改进算法）的find_root函数和比较测试以查看f(x)是否接近0。

>>> def find_zero(f, df):
        def near_zero(x):
            return approx_eq(f(x), 0)
        return improve(newton_update(f, df), near_zero)

计算根.使用牛顿法，我们可以计算任意度n的根。 a的n次方根为x，使得x·x·x ... x = a，其中x重复n次。 例如，

1. 64的平方根为8，因为8·8 = 64。
2. 64的立方根为4，因为4·4·4 = 64。
3. 64的六次方根是2，因为2⋅2⋅2⋅2⋅2⋅2= 64。

通过绘制n等于2, 3和6以及a等于64的曲线，我们可以看出以下关系。

>>> def square_root_newton(a):
        def f(x):
            return x * x- a
        def df(x):
            return 2 * x
        return find_zero(f, df)
>>> square_root_newton(64)
8.0

以下是n次方根的情况：

>>> def power(x, n):
        """Return x * x * x * ... * x for x repeated n times."""
        product, k = 1, 0
        while k < n:
            product, k = product * x, k + 1
        return product
>>> def nth_root_of_a(n, a):
        def f(x):
            return power(x, n) - a
        def df(x):
            return n * power(x, n-1)
        return find_zero(f, df)
>>> nth_root_of_a(2, 64)
8.0
>>> nth_root_of_a(3, 64)
4.0
>>> nth_root_of_a(6, 64)
2.0

所有这些计算中的近似误差可以通过减少approx_eq的tolerance而降低。

当您尝试使用牛顿法时，请注意它不总是收敛的。improve的初始猜测值必须足够接近根，并且必须满足函数的各种条件。 尽管有这个缺点，牛顿法是一个能解决微分方程的强大的通用计算方法。 在现代计算机中，非常快速的对数算法和大整数除法也使用了该技巧的变体。

1.6.6 函数柯里化

我们可以使用高阶函数将一个接受多参数的函数转换成接受一个单一参数（最初函数的第一个参数）的函数。 具体地说，给定函数f(x，y)，我们可以定义函数g，使得g(x)(y)等价于f(x，y)。 这里，g是一个高阶函数，它接受单个参数x，并返回另一个接受单个参数y的函数。 这种转变叫做currying函数柯里化。
例如，我们可以定义一个pow函数的柯里化版本：

>>> def curried_pow(x):
        def h(y):
            return pow(x, y)
        return h
>>> curried_pow(2)(3)
8

一些编程语言（如Haskell）只允许函数接受单个参数的，因此程序员必须对所有多参数程序进行currying柯里化。 在更通用的语言（如Python）中，当我们需要只接受一个参数的函数时，currying很有用。 例如，map模式将单参数函数应用于一系列值。 在随后的章节中，我们将看到更多的map模式的例子。至于现在，我们可以在一个函数中实现这个模式：

>>> def map_to_range(start, end, f):
        while start < end:
            print(f(start))
            start = start + 1

我们可以使用map_to_range和curried_pow来计算2的前10个幂，而不是专门写一个函数：

>>> map_to_range(0, 10, curried_pow(2))
1
2
4
8
16
32
64
128
256
512

我们可以类似地使用相同的两个函数来计算其他数字的幂函数。 currying可以让我们做到，它不需要为我们希望计算的幂的每一个数写一个特定的函数。

在上面的例子中，我们手动对pow函数进行currying转换，得到curried_pow。 相反，我们可以定义自动化currying的函数，以及反向currying的转换：

>>> def curry2(f):
        """Return a curried version of the given two-argument function."""
        def g(x):
            def h(y):
                return f(x, y)
            return h
        return g
>>> def uncurry2(g):
        """Return a two-argument version of the given curried function."""
        def f(x, y):
            return g(x)(y)
        return f
>>> pow_curried = curry2(pow)
>>> pow_curried(2)(5)
32
>>> map_to_range(0, 10, pow_curried(2))
1
2
4
8
16
32
64
128
256
512

curry2函数使用了双参数函数f，并返回单参数函数g。 当g接受参数x时，它返回一个单参数函数h。 当h接受参数y时，它调用了f(x，y)。 因此，curry2(f)(x)(y)等价于f(x，y)。 uncurry2函数反转currying变换，使得uncurry2(curry2(f))等效于f。

>>> uncurry2(pow_curried)(2, 5)
32

1.6.7 Lambda 表达式

到目前为止，每当我们想要定义新的函数时，我们都需要给它一个名字。 但是对于其他类型的表达式，我们不需要将中间值关联到名称上。 也就是说，我们可以计算a * b + c * d，而不用命名子表达式a * b或c * d。 在Python中，我们可以使用lambda表达式创建函数，该表达式会求值为匿名函数。 lambda表达式是函数体具有单个返回表达式的函数,不允许出现赋值和控制语句。

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

我们可以通过构建相应的英文句子来理解lambda表达式的结构：

lambda表达式的结果称为lambda函数。 它没有内在名称（因此Python为该名称打印<lambda>），但它的行为就像任何其他函数一样。

>>> s = lambda x: x * x
>>> s
<function <lambda> at 0xf3f490>
>>> s(12)
144

在环境图示中，lambda表达式的结果也是用希腊字母λ（lambda）命名的函数。 我们的示例可以用lambda表达式表达得相当简洁紧凑。

一些程序员发现使用lambda表达式的匿名函数更简短直接。 但是复合的lambda表达式是非常难以辨认的，尽管它们很简洁。 以下定义是正确的，但很多程序员很难理解它。

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

一般来说，Python代码风格倾向于显式的def语句而不是 Lambda 表达式，但是允许它们在简单函数作为参数或返回值的情况下使用。

这样的风格规则只是指导; 你可以按你想要的方式进行编程。 但是,在你编写程序时,要考虑某一天可能会阅读你的程序的人们。如果你可以让你的程序更易于理解,你就帮了人们一个忙。
术语lambda是一个历史的偶然结果, 来源于手写的数学符号和早期打字系统限制的不兼容。

It may seem perverse to use lambda to introduce a procedure/function. The notation goes back to Alonzo Church, who in the 1930's started with a "hat" symbol; he wrote the square function as "ŷ . y × y". But frustrated typographers moved the hat to the left of the parameter and changed it to a capital lambda: "Λy . y × y"; from there the capital lambda was changed to lowercase, and now we see "λy . y × y" in math books and (lambda (y) (* y y)) in Lisp.

                                     —Peter Norvig (norvig.com/lispy2.html)

尽管它们具有不寻常的词源，lambda表达式和函数调用相应形式的语言，以及lambda演算都成为了计算机科学概念的基础,并在 Python编程社区广泛传播。 当我们在第3章研究解释器的设计时，我们将重新讨论这个话题。

1.6.8 抽象和一等函数

用户定义函数是一个关键的抽象机制，因为它们允许我们将计算的通用方法表达为编程语言中的显式元素。现在我们已经看到了高阶函数如何让我们操纵这些通用方法来创建进一步的抽象。

作为程序员，我们应该留意程序中的低级抽象，在它们之上构架并将其概括为更强大的抽象。这不是说应该总以最抽象的方式编写程序; 专家程序员知道如何选择适合他们任务的抽象级别。但是，重要的是能够从这些抽象的角度思考，以便我们可以在新的环境中应用它们。高阶函数的意义，在于它们使我们能够将这些抽象明确地表示为编程元素，以便像处理其他计算元素那样处理它们。

通常，编程语言会对计算元素被操纵的方式施加限制。具有最少限制的要素具有一等的地位。一等元素的一些“权利和特权”是：

1. 它们可以被绑定到名字。
2. 它们可以作为参数传递给函数。
3. 它们可以作为函数的返回值返回。
4. 它们可以被包括在数据结构中。

Python 总是给予函数一等地位, 所产生的表现力的收益是巨大的。

1.6.9 函数装饰器

Python提供了特殊的语法, 将高阶函数用作执行def语句的一部分,叫做装饰器。 也许最常见的例子是trace跟踪。

>>> def trace(fn):
        def wrapped(x):
            print('-> ', fn, '(', x, ')')
            return fn(x)
        return wrapped
>>> @trace
    def triple(x):
        return 3 * x
>>> triple(12)
->  <function triple at 0x102a39848> ( 12 )
36

在这个例子中，定义了一个高阶函数trace跟踪，它返回一个函数，该函数在调用它的参数之前执行print语句来输出参数。triple的def语句有一个注释，@trace，它影响了def的执行规则。 像往常一样，函数triple被创建。 但是，triple名称没有绑定在此函数上。 相反，triple名称绑定到新定义的triple上的调用trace的返回函数值上。 在代码中，这个装饰器相当于：

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

在与此文本相关的项目中，装饰器用于跟踪，以及选择在命令行运行程序时要调用哪些函数。

附加部分。 装饰器符号@后可以跟随一个调用表达式。 首先求解@之后的表达式，然后是def语句，最后求解出的装饰器表达式的结果被应用于新定义的函数，结果绑定到def声明的名称上。 如果您感兴趣的话，可以阅读Ariel Ortiz编写的装饰器简短教程。

下一节：SICP 第一章 使用函数抽象概念 1.7 递归函数