# 《Composing Programs》第三版 · 中文版
> 原书：*Composing Programs (3rd Edition)* — John DeNero（Berkeley CS61A 教材）
> 本译本覆盖 **第 1 章 Functions** 与 **第 2 章 Building Abstractions with Data**
>
> 译注：原文中的专有名词（语言名、工具名、人名、网址、代码标识符）一律保留原样，
> 以保证与官方文档、cs61a.org 作业和代码示例对得上。
## 翻译进度
| 小节 | 原文词数 | 状态 |
|---|---|---|
| 1.1 Getting Started | 1,419 | ✅ 已完成 |
| 1.2 Elements of Programming | 2,586 | ✅ 已译（编程的基本要素） |
| 1.3 Defining New Functions | 3,440 | ✅ 已译（定义新函数） |
| 1.4 Designing Functions | 770 | ✅ 已译（设计函数） |
| 1.5 Control | 2,623 | ✅ 已译（控制） |
| 1.6 Higher-Order Functions | 4,899 | ✅ 已译（高阶函数） |
| 1.7 Recursive Functions | 2,676 | ✅ 已译（递归函数） |
| Functions Reference 函数参考 | 1,160 | ✅ 已译 |
| 2.1 Introduction | 1,606 | ✅ 已译（引言） |
| 2.2 Sequences | 4,255 | ✅ 已译（序列） |
| 2.3 Compound Data | 3,844 | ✅ 已译（复合数据） |
| 2.4 Mutable Data | 3,061 | ✅ 已译（可变数据） |
| 2.5 Object-Oriented Programming | 4,798 | ✅ 已译（面向对象编程） |
| 2.6 Implementing Classes and Objects | 1,408 | ✅ 已译（实现类与对象） |
| 2.7 Object Abstraction | 1,396 | ✅ 已译（对象抽象） |
| 2.8 Lazy Evaluation | 3,100 | ✅ 已译（惰性求值） |
---
# 第 1 章 函数
## 1.1 起步
计算机科学是一门范围广阔的学科。全球分布式系统、理论、机器人、图形学、安全、计算机体系结构，以及数十个新兴子领域，每年都在涌现新的技术与发现。计算机科学的高速进展几乎触及人类生活的方方面面，而人工智能的进步正在进一步加快这一变化的速度。商业、通信、科学、艺术、休闲与政治，如今都已成为计算的主场。
计算机科学之所以影响深远，很大程度上源于一组优雅而强大的基本思想：一切计算都始于**表示信息**，进而**指定处理这些信息的求解逻辑**，再**创建抽象**以驾驭这份逻辑的复杂度。编程语言是人类最聪慧、最灵活的发明之一，也正是这些思想得以表达的载体。理解计算机程序如何书写与组织、计算机又如何运行程序来完成计算过程，正是创造新程序、进一步拓展计算机科学影响力的必备基础。
长期以来，这些基本思想都是借助经典教材《计算机程序的构造和解释》（*Structure and Interpretation of Computer Programs*，简称 SICP）来传授的。该书由 Harold Abelson 与 Gerald Jay Sussman 主笔、Julie Sussman 参与，于 1984 年首次出版。本书大量借鉴了这本教材，原作者也已慷慨授权改编与复用。
《Composing Programs》第三版关注的是：如何借助人工智能（AI）工具来编写、扩展和理解计算机程序。若只是让 AI 写出一个已被完整、精确描述的程序，根本不需要任何人类技能。然而，要创造出新颖而有用的程序，总得有人去构思并把它描述出来——而在今天，这往往仍需要与从零编写程序同样扎实的理解：对表示、逻辑、抽象和编程语言的透彻掌握。有了 AI，一个简短的描述就能生成或改写大段程序，创造的效率因此大幅提升；但设想程序的设计、准确地描述它、并改进 AI 给出的产物，这份人类的专业能力依旧是造程序的核心。**学习如何有效地用 AI 开发程序，最好的时机正是掌握了这些核心理解之后**——这也正是本书把该主题放在末尾的原因。
### 用 Python 编程
> 语言与其说是你学会的东西，不如说是你加入的共同体。
> —— Arika Okrent
本书主要使用 Python 语言。
Python 是一门广泛使用的编程语言，拥趸来自各行各业：Web 程序员、游戏工程师、科学家、学者，乃至新编程语言的设计者。学会 Python，你就加入了一个规模达百万级的开发者社区。开发者社区是极其重要的机构：成员互相帮忙解决问题，分享自己的项目与经验，共同打造软件与工具。其中热忱的成员常常因其贡献而赢得名声与广泛敬重。
Python 语言本身就是一大群志愿者的产物，他们以贡献者的多元为傲。这门语言由 Guido van Rossum 于 1980 年代末构思并首次实现。在其 *Python 3 教程* 的第一章里，他解释了在如今众多语言之中，Python 为何如此受欢迎。
作为教学语言，Python 表现优异，因为纵观其历史，Python 的开发者一直强调 Python 代码的**人可读性**，并以《Python 之禅》（*Zen of Python*）中美、简洁、易读的指导原则加以强化。本书之所以格外适合用 Python，是因为它丰富的特性支持多种不同的编程风格，我们将在书中逐一探索。
开始学 Python 编程最好的方式，就是直接与解释器互动。本节介绍如何安装 Python 3 与 Visual Studio Code 编辑器，随后启动一次交互式会话、开始写程序。这些软件全部免费，全球数百万程序员日常都在使用。
### 安装 Python 3
请使用适用于你操作系统的官方安装程序来安装 Python。始终选择版本号以 3 开头、且标注为 stable 的版本，例如 3.14.7。版本号越大越好。
**Windows。** 从 Windows 下载页面下载 64 位安装程序并运行。在安装程序的第一个界面上，先勾选标注为 **Add python.exe to PATH** 的复选框，再点击 **Install Now**。
**Mac。** 从 macOS 下载页面下载 64 位 universal2 安装程序，打开下载好的 `.pkg` 文件，按安装程序的提示操作。
### 安装与配置 Visual Studio Code
编辑器是用来编写和修改程序的应用程序。Visual Studio Code（通常简称 VS Code）是目前全球最流行的编辑器。
请使用适用于你操作系统的官方安装程序安装 Visual Studio Code，可从 Visual Studio Code 下载页面获取。
**Windows。** 下载 Windows x64 User Installer 并运行。
**Mac。** 下载 Mac Universal 归档包，打开下载的文件，把 Visual Studio Code 应用拖进「应用程序」文件夹。
首次打开 VS Code 时，如果它要求你登录以使用 GitHub Copilot 的 AI 功能或其他功能，直接关掉登录窗口即可——无需登录 VS Code。
VS Code 安装并打开后，还有两个重要步骤。如果你打开的是本版教材的配套作业（例如 cs61a.org 上的 lab、homework 或 project），这些步骤应当会自动完成。如果只是想自己写程序，请手动完成这两步：
* **添加 Python 支持**：点击左侧边栏的扩展图标，搜索 `python`，安装名为 **Python**、发布者为 Microsoft 的扩展。它应排在第一位，描述以「Python language support」开头。
* **关闭 GitHub Copilot**：搜索 `copilot`，点击预装的 **GitHub Copilot Chat** 扩展。在打开的扩展说明页顶部附近，点击「Disable AI Features」，然后关闭扩展页面。
### 交互式会话
在交互式 Python 会话中，你在提示符 `>>>` 之后输入代码。Python 解释器会读取并执行你输入的内容，依次完成你的各种命令。
要在 VS Code 内启动交互式会话，先从 Terminal 菜单中选择 New Terminal，然后输入 `py`（Windows）或 `python3`（Mac/Linux）来启动 Python 解释器。
如果看到 Python 提示符 `>>>`，说明你已经成功进入交互式会话。试着输入 `2 + 2` 并按回车（Windows）或 return（Mac/Linux），你应该会看到答案 `4`。
```python
>>> 2 + 2
4
```
在 VS Code 里，运行 Python 解释器的终端看起来大致如下：
**小技巧**：上下方向键可以翻阅你此前写过的 Python 代码历史。
### 错误
Python 正等着你的命令。鼓励你大胆尝试这门语言。在本章余下的部分，请把你读到的表达式敲进去、来回改改，看看会发生什么。不过，也要做好出错的准备。编程语言固然强大，却也极其死板：哪怕拼写或格式上最微小的改动，也会带来意想不到的输出和报错。
学会解读错误、定位意外错误的成因，这门功夫叫**调试（debugging）**。调试有几条指导原则：
* **增量测试**：每个写得好的程序，都由小而模块化的部件组成，每个部件都能单独试验。不要一上来就写又长又复杂的表达式，先对它的各个部分求值，确认结果符合预期。这样做能及早发现问题，也让你对自己的部件更有把握。
* **隔离错误**：某条语句输出上的错误，通常可以归因到代码中的某个具体位置。诊断时，先把错误追踪到尽可能小的代码片段，再动手修改。
* **检验假设**：解释器会一字不差地执行你的指令——不多也不少。当我们观察到的行为与程序员所相信（或假设）的不一致时，输出就显得「意外」。弄清你的假设，再把调试精力集中在验证这些假设是否真的成立上。
* **请教他人**：你并不孤单。读不懂错误信息时，去问朋友、老师、搜索引擎或 AI 工具。讨论程序的过程中，能共享大量有价值的编程知识。
增量测试、模块化设计、精确假设与讨论交流——这些主题将贯穿本书，也希望它们伴随你的整个计算机科学生涯。
---
---
## 1.2 编程的基本要素
一门编程语言，绝不只是指挥计算机干活的手段。它还为我们提供了组织「计算过程之描述」的方式。程序的作用，在于在编程共同体成员之间交流这些思想。SICP 初版序言特别强调了这一点：「**程序首先是写给人读的，顺带才让机器执行。**」
在描述一门语言时，我们应特别留意它用何种手段，把简单的描述组合成更复杂的描述。每一门强大的语言都有三种这样的机制：
* **基本表达式与语句**：语言所提供的最简单的构件；
* **组合手段**：由较简单的元素构造出复合元素；
* **抽象手段**：为复合元素命名，并将其作为单元来操作。
编程主要处理两类对象：函数与数据。（很快我们就会发现，二者其实并没有那么泾渭分明。）通俗地说，**数据**是我们想要操作的信息，而**函数**描述操作数据的具体步骤。因此，任何强大的编程语言都应既能描述数据与函数，又能提供用于组合、抽象二者的方法。
### 表达式
> 🎬 视频：Expressions
我们从简单之处入手，很快就会推向更有趣的例子。
**基本表达式**内部不含任何其他表达式。数字就是一种基本表达式——更确切地说，你输入的表达式由若干代表该数字的数字符号组成。
```python
>>> 42
42
```
表示数字的表达式可以用数学运算符组合起来，构成**复合表达式**，解释器会对其求值：
```python
>>> -1 - -10
9
>>> 1/2 + 1/4 + 1/8 + 1/16 + 1/32 + 1/64 + 1/128
0.9921875
```
Python 提供了许多构造复合表达式的方式。与其一上来就罗列殆尽，不如沿途逐一介绍新的表达式形式，以及支撑它们的语言特性。
### 调用表达式
> 🎬 视频：Functions, Objects, and Interpreters
最重要的一类复合表达式是**调用表达式（call expression）**：它把某个函数作用于若干参数之上。在数学中，函数是从输入值到输出值的映射。类似地，在 Python 中，函数被施加于称为其**实参（arguments，也译作参数）**的输入值，执行若干计算，最后返回一个输出值，通常称为**返回值（return value）**。例如，`max` 函数把它的各个输入映射为单个输出——诸输入中的最大值。调用表达式的写法，与数学中的函数调用如出一辙。
```python
>>> max(7.5, 9.5)
9.5
```
这个调用表达式含有子表达式：**运算符（operator）**是位于圆括号之前的一个表达式，圆括号内则是以逗号分隔的**操作数（operand）**表达式列表。[1]
运算符求值为即将被调用的函数，每个操作数求值为一个实参。随后，函数被作用于这些实参。
调用表达式中实参的顺序至关重要。例如，`pow` 函数将第一个实参提升到第二个实参所给的幂次。
```python
>>> pow(100, 2)
10000
>>> pow(2, 100)
1267650600228229401496703205376
```
相较于把 `+` 之类的运算符夹在两个表达式中间的数学惯例（即**中缀记法**），函数记法有三大优点。
其一，函数可以接受任意多个实参，而非只限于两个：
```python
>>> max(1, -2, 3, -4)
3
```
其二，函数记法支持**嵌套**——其中的元素本身也是复合表达式。像 `+`、`*` 这样的运算符有一套必须先记住的运算优先级规则；而嵌套调用表达式的求值顺序，在层层括号之中已写得明明白白。
```python
>>> max(min(1, -2), min(pow(3, 5), -4))
-2
```
在原则上，这种嵌套的深度，以及 Python 解释器所能求值的表达式整体复杂度，都没有上限。然而，再深的嵌套也转瞬就会把人绕晕。作为程序员，你的一个重要职责，就是组织好表达式，使它们始终能被你自己、你的编程伙伴，以及将来阅读这些表达式的其他人所理解。
其三，数学记法形态繁多：乘法藏在两项之间，指数化作上标，除法画成横线，平方根则像一顶斜檐的屋顶——其中不少字形极难输入！而把这些运算统统改写成调用表达式，既统一又便于键入，可谓一举两得。
### 导入库函数
Python 定义了大量函数，却并不默认把所有名字都摆在你面前。它把内置函数分门别类地收进**模块（module）**，这些模块共同构成 **Python 标准库**。要使用其中的元素，先得**导入**它们。例如，`math` 模块提供了一系列我们耳熟能详的数学函数：
```python
>>> from math import sqrt
>>> sqrt(256)
16.0
```
`operator` 模块则给出了与中缀运算符相对应的函数：
```python
>>> from operator import add, sub, mul
>>> add(14, 28)
42
>>> sub(100, mul(7, add(8, 4)))
16
```
import 语句先指明模块名（如 `operator` 或 `math`），再列出要从该模块导入的具名属性（如 `sqrt`）。函数一旦导入，便可反复调用。
使用这些运算符函数（如 `add`）与直接使用运算符符号本身（如 `+`），二者并无区别。
Python 3 标准库文档逐一列出了各模块定义的函数，`math` 模块亦在其列。不过，这份文档是为通晓整门语言的开发者而写的。就眼下而言，你或许会发现：动手试一个函数，比读文档更能弄清它的脾气。等你渐渐熟悉了 Python 的语法与词汇，这份文档自会成为一座宝贵的参考资料库。
### 名称与环境
> 🎬 视频：Names, Assignment, and User-Defined Functions
编程语言的一项核心能力，是为值赋予名字。若某个值有了名字，我们就说该名字**绑定（binds）**到了这个值上。
在 Python 中，我们可以用**赋值语句（assignment statement）**建立新的绑定：等号 `=` 的左边是一个名字，右边是一个值：
```python
>>> radius = 10
>>> radius
10
>>> 2 * radius
20
>>> radius
10
>>> diameter = 2 * radius
>>> diameter
20
```
名字也可以经由 import 语句而获得绑定。
```python
>>> from math import pi
>>> pi * 71 / 223
1.0002380197528042
```
在 Python（以及许多其他语言）中，`=` 符号称为**赋值运算符**。赋值是我们最朴素的抽象手段：它让简单的名字可以指向复合表达式的计算结果，比如上面算出的 `diameter`。正是这样，复杂程序由一层层构造、复杂度层层递进的数据搭建起来。
名字既能绑定值、日后又能凭名字取回这些值，这就意味着解释器必须维护某种「记忆」，以追踪名字、值、绑定三者的关系。这份记忆称为**环境（environment）**。
名字也可以绑定到函数上。例如，`max` 这个名字就绑定在我们一直使用的 `max` 函数上。与数字不同，函数很难原样呈现为文本，因此当要求 Python 描述一个函数时，它会打印一段标识性的说明：
```python
>>> max
```
我们可以用赋值语句为已有的函数另取新名：
```python
>>> f = max
>>> f
>>> f(2, 3, 4)
4
```
而接连的赋值语句，可以将一个名字重新绑定到新的值上：
```python
>>> f = 2
>>> f
2
```
在 Python 中，名字常被称作**变量名**或**变量**，因为在程序执行的过程中，它们可以绑定到不同的值。当某个名字通过赋值绑定到新值时，它便不再绑定于此前的任何值。你甚至可以把内置的名字重新绑定到新值上：
```python
>>> max = 5
>>> max
5
```
把 `max` 赋值为 5 之后，名字 `max` 就不再绑定到函数了，此时若尝试调用 `max(2, 3, 4)`，便会出错。
执行赋值语句时，Python 会先对 `=` 右边的表达式求值，再改变 `=` 左边名字的绑定。因此，你完全可以在右侧表达式中引用正要被这条赋值语句绑定的那个名字：
```python
>>> x = 2
>>> x = x + 1
>>> x
3
```
我们还可以在一条语句中为多个名字赋予多个值：`=` 左侧的名字与右侧的表达式，均以逗号分隔。
```python
>>> area, circumference = pi * radius * radius, 2 * pi * radius
>>> area
314.1592653589793
>>> circumference
62.83185307179586
```
改变一个名字的值，并不会影响其他名字。下面，尽管 `area` 当初是依据 `radius` 定义出来的，`area` 的值却并未随之改变。想更新 `area` 的值，得再写一条赋值语句。
```python
>>> radius = 11
>>> area
314.1592653589793
>>> area = pi * radius * radius
>>> area
380.1327110843649
```
使用多重赋值时，`=` 右侧的所有表达式会先全部求值，然后才把左侧的名字依次绑定上去。有了这条规则，交换两个名字所绑定的值，一条语句即可完成：
```python
>>> x, y = 3, 4.5
>>> y, x = x, y
>>> x
4.5
>>> y
3
```
### 求值嵌套表达式
表达式求值本身就是一个计算过程，可以描述为一串步骤。例如，在求值嵌套调用表达式时，解释器遵循如下流程：
* 先对运算符与操作数这些子表达式求值，然后
* 把运算符子表达式的值——即那个函数——作用于各操作数子表达式的值——即那些实参。
即便这样一条简单的流程，也揭示了关于「过程」的一般性要点。第一步规定：要完成一个调用表达式的求值过程，我们必须先求值其他表达式。可见，求值流程在本质上是**递归**的——它把「援引本规则自身」列为自己的一个步骤。
例如，求值
```python
>>> mul(add(2, mul(4, 6)), add(3, 5))
208
```
需要把这一求值流程应用四次。倘若把每一个被求值的表达式都画出来，这一过程的层次结构便一目了然。
这张图称为**表达式树（expression tree）**。树中的每个位置，都是一个表达式连同它的值。
要求值位于最顶端的整个表达式，必须先求值它下方的子表达式。底部的表达式是基本表达式，求值结果要么是函数，要么是数字。以树的眼光看待求值，可以想象操作数的值自底向上「渗透」：从最底层的原始表达式出发，在越来越高的层级上逐级汇合。
接着请注意，第一步的反复施用，最终把我们带到这样一个境地：需要求值的不再是调用表达式，而是数字（如 `2`）和名字（如 `add`）这样的基本表达式。对于这些基本情形，我们这样规定：
* 数字求值为它所指称的那个数；[2]
* 一个（变量）名字，求值为当前环境中绑定到该名字的值。
请注意环境在确定表达式中符号取值时所扮演的重要角色。在 Python 中，脱离环境去谈论下面这个表达式的值，是没有意义的：
```python
>>> add(x, 1)
```
因为没有任何信息指明环境会为名字 `x`（乃至名字 `add`）提供什么值。环境提供了求值赖以发生的语境，这对我们理解程序的执行至关重要。
这套求值流程并不足以求值所有 Python 代码——它只涵盖调用表达式、数字与名字。例如，它处理不了赋值语句。执行
```python
>>> x = 3
```
既不返回值，也不把函数作用于任何实参，因为赋值的用意本就在于把名字绑定到值上。语句不求值，而是**执行**；它们不产生值，而是做出某种改变。每一类表达式或语句，都有各自的求值或执行流程。
### 纯函数与非纯函数
> 🎬 视频：Print and None
本书通篇都将区分两类函数。
#### 纯函数
**纯函数（pure function）**接收输入（其实参），给出输出（施加于输入的结果），仅此而已。纯函数可以执行计算，而之所以称其为「纯」，是因为除了提供返回值之外，它对程序或计算机别无其他影响；并且，只要以相同的实参调用，它返回的值永远相同。
内置函数 `abs` 就是一例——它算得并返回其参数的绝对值。
```python
>>> abs(-2)
2
```
可以把它描画成一台小机器：送入输入，送出输出。
#### 非纯函数
**非纯函数（non-pure function）**除了返回值之外，还能产生**副作用（side effects）**，对解释器或计算机的状态做出某种改变。一种常见的副作用，是在屏幕上产生输出，`print` 函数正是如此。
```python
>>> print(1, 2, 3)
1 2 3
```
尽管在这些例子中 `print` 与 `abs` 看起来颇为相似，二者行事的方式却有着根本的不同。`print` 返回的值永远是 `None`——一个代表「空无一物」的 Python 特殊值。交互式 Python 解释器不会主动打印 `None` 这个值。对 `print` 而言，输出是它被调用时产生的副作用，是函数自己把东西打在了屏幕上。
把返回值赋给一个名字，差别就显出来了：
```python
>>> x = abs(-3)
>>> print(x)
3
>>> y = print(-3)
-3
>>> print(y)
None
```
由于 `print` 并不返回它的实参，调用 `print` 的结果也就无法参与到更复杂的表达式之中。例如，`abs(-3) * 2` 等于 6，因为 `abs(-3)` 返回 3；而 `print(-3) * 2` 会报错，因为 `print(-3)` 返回的是 `None`，而 `None` 无法与 2 相乘。
把对 `print` 的调用嵌套起来，是个颇堪玩味的例子。每次调用 `print` 都会显示一行；而对着 `print` 调用的返回值再调用 `print`，显示的便是 `None`。
```python
>>> print(print(1), print(2))
1
2
None None
```
若你觉得这个输出出乎意料，不妨画一棵表达式树，弄清这个表达式为何会生出这般古怪的结果。
纯函数受到的限制在于：它不能有副作用，行为也不能随时间而改变。施加这些限制，收获颇为丰厚。其一，纯函数可以可靠地复合成复合调用表达式——我们已经看到，`max`、`pow`、`sqrt` 这类函数都能在嵌套表达式中用得得心应手。
纯函数还有其他好处：让复杂程序更易理解、更可预测，也让多个函数得以并发执行。
正因如此，本章余下部分，我们将着力于创建与使用纯函数。非纯函数留待第 2 章详加讨论。
---
**注释**
1. 官方 Python 语言参考用另一套术语来描述调用表达式的各个部分：圆括号之前的表达式不叫运算符，而叫 primary（有时干脆就叫函数）；圆括号内的表达式不叫操作数，而叫 argument expressions（实参表达式）。本书沿用更为经典的 operator / operand 之说，因为它们有助于区分表达式（属于代码）与值（属于数据）。↩
2. 咬文嚼字地说，当我们断言某表达式求值为某值，实际意思是 Python 解释器把该表达式求值为该值。是解释器通过运行程序，赋予了这门编程语言以意义。既然解释器是一个行为始终如一的固定程序，那么在 Python 程序的语境下谈论表达式求值的结果，自然是顺理成章的事。↩
---
## 1.3 定义新函数
> 🎬 视频：Defining Functions
在 Python 中，我们已经识别出任何一门强大的编程语言都必须具备的若干要素：
* 数字与算术，是内置的基本数据值，以及函数或运算符；
* 嵌套的函数应用，提供了组合各种操作的手段；
* 把名字绑定到值，提供了一种有限的抽象手段。
现在，我们要学习**函数定义**——一种强大得多的抽象技术。凭借它，一个名字可以绑定到一项复合操作上，此后便可把这操作作为一个单元来引用。
我们先来考察如何表达「平方」这一观念。我们不妨说：「要平方某物，就把它自己乘自己。」在 Python 中，这就写成
```python
>>> def square(x):
return mul(x, x)
```
这定义了一个新函数，并给了它名字 `square`。这个**用户自定义函数**并非解释器内置的；它代表着「把某物乘以它自身」这一复合操作。定义中的 `x` 称为**形式参数（formal parameter）**，它为「被乘的那个东西」提供了一个名字。这条定义创建了这个用户自定义函数，并将它绑定到名字 `square` 上。
### def 语句
函数定义由一条 **def 语句**构成：它指明一个 ``（名字）和一份以逗号分隔的具名 ``（形式参数）列表；随后是一条 **return 语句**，称为**函数体（function body）**，它指明函数的 ``（返回表达式）——所谓返回表达式，就是函数每次被施加时要求值的那个表达式：
```python
def ():
return
```
第二行必须缩进——多数程序员用四个空格缩进。返回表达式并不会立刻求值；它作为新定义函数的一部分被保存起来，只在函数最终被施加时才求值。
定义了 `square` 之后，便可用调用表达式来施加它：
```python
>>> square(21)
441
>>> square(add(2, 5))
49
>>> square(square(3))
81
```
我们还可以把 `square` 当作积木，用来定义其他函数。例如，我们很容易定义 `sum_squares`：给定任意两个数作为实参，返回它们平方之和：
```python
>>> def sum_squares(x, y):
return add(square(x), square(y))
>>> sum_squares(3, 4)
25
```
用户自定义函数的使用方式，与内置函数完全一样。事实上，单从 `sum_squares` 的定义，根本看不出 `square` 究竟是解释器内置的、从模块导入的，还是用户自己定义的。
def 语句与赋值语句都把名字绑定到值上，任何已有的绑定都会因此失去。例如下面的 `g`，先指向一个无参函数，继而是一个数字，最后又变成另一个接受两个实参的函数。
```python
>>> def g():
return 1
>>> g()
1
>>> g = 2
>>> g
2
>>> def g(h, i):
return h + i
>>> g(1, 2)
3
```
### 环境
> 🎬 视频：Environment Diagrams
我们眼下这个 Python 子集已经复杂到「程序的含义不再显而易见」的地步。倘若某个形式参数与某个内置函数同名，会怎样？两个函数可以共用一个名字而互不混淆吗？要解答这类问题，就必须更细致地描述**环境**。
表达式求值所在的环境，是一串**帧（frames）**，通常画成一个个方框。每个帧包含若干**绑定（bindings）**，每个绑定把一个名字与其对应的值关联起来。在一个帧内，同一个名字只能出现一次。全局有且仅有一个**全局帧**。赋值语句与 import 语句把条目加入当前环境的第一个帧。到目前为止，我们的环境只由全局帧构成。
> 📊 *原文此处嵌入一个交互式环境图：`from math import pi; tau = 2 * pi`。环境图展示了当前环境的绑定，以及各名字所绑定的值。本书原版的环境图可以按行单步执行，观察右侧环境状态的演变，也可点击链接载入 Online Python Tutor——那是 Philip Guo 为生成这类环境图而做的工具。建议你自拟例子，研读生成的环境图。*
函数也会出现在环境图里。import 语句把名字绑定到内置函数；def 语句把名字绑定到由该定义所创建的用户自定义函数。导入 `mul` 并定义 `square` 之后的环境如下：
```python
from operator import mul
def square(x):
return mul(x, x)
```
> 📊 *环境图中，每个函数画成一行，以 `func` 打头，后面跟着函数名与形式参数。诸如 `mul` 这样的内置函数没有形式参数名，因此此处一律用 `...` 代替。*
函数的名字出现了两次：一次在帧里，一次作为函数自身的一部分。函数自身携带的那个名字，称为**内在名字（intrinsic name）**；帧中的那个名字，则是**绑定名（bound name）**。两个乃至更多不同的绑定名可以指向同一个函数，但函数自身只有一个内在名字，且永不改变。
求值时使用的，是帧中绑定到函数的那些名字；函数的内在名字在求值中不起作用。请用「前进」按钮单步走一遍下例，你会看到：一旦名字 `max` 绑定到值 3，它便再也不能充当函数了。
```python
f = max
max = 3
result = f(2, 3, 4)
max(1, 2) # 会引发错误
```
错误信息 `TypeError: 'int' object is not callable` 报告的是：名字 `max`（此时绑定到数字 3）是一个整数而非函数，因此不能充当调用表达式中的运算符。
**函数签名（function signatures）**。不同的函数，允许接受的实参个数也不同。为了记录这些要求，我们画每个函数时，都标出函数名及其形式参数。用户自定义函数 `square` 只接受 `x`；多给或少给实参都会出错。对函数形式参数的这种描述，称为该函数的**签名**。
函数 `max` 可以接受任意多个实参，因而不加区分地画作 `max(...)`。无论能接受几个实参，所有内置函数都画成 `(...)`，因为这些基本函数从未被显式定义过。
### 调用用户自定义函数
要求值一个运算符指向用户自定义函数的调用表达式，Python 解释器要遵循一套计算流程。与对待任何调用表达式一样，解释器先求值运算符与操作数表达式，再把具名函数作用于所得的各实参。
施加一个用户自定义函数，会引入第二个**局部帧（local frame）**，它仅对该函数可见。把用户自定义函数施加于若干实参，其过程是：
* 在一个新的局部帧中，把各实参绑定到该函数的形式参数名上；
* 以这个帧为起点的环境中，执行该函数的函数体。
求值函数体所在的环境由两个帧构成：先是含有形式参数绑定的局部帧，然后是含有其他一切的全局帧。函数应用的每一个实例，都有其自己独立的局部帧。
为了讲清楚，下面把同一个例子的环境图分作几步来描绘。执行完第一条 import 语句后，全局帧中只绑定了名字 `mul`。
```python
from operator import mul
def square(x):
return mul(x, x)
square(-2)
```
> 📊 *第 1 步：全局帧中 `mul` 指向内置函数。*
接着执行 `square` 函数的定义语句。请注意，整条 def 语句在一步之内处理完毕。函数的函数体并不执行——要等到函数被调用时才执行（定义时一概不动）。
> 📊 *第 2 步：全局帧中新增 `square`，指向用户自定义函数 `func square(x) ...`。*
接下来，`square` 函数以实参 `-2` 被调用，于是新建一个帧，形式参数 `x` 在其中绑定到值 `-2`。
> 📊 *第 3 步：新增局部帧 `square(x)`，其中 `x` 绑定为 -2。*
随后，在当前环境中查找名字 `x`——当前环境由图中所示的两个帧构成。两处 `x` 都求值为 `-2`，于是 `square` 函数返回 4。
> 📊 *第 4 步：`square()` 帧中显示「Return value: 4」。*
`square()` 帧里的「Return value」（返回值）并不是一条名字绑定，它表示的是：创建这个帧的那次函数调用所返回的值。
哪怕在这样简单的例子里，也用到了两个不同的环境。顶层表达式 `square(-2)` 在全局环境中求值；返回表达式 `mul(x, x)` 则在调用 `square` 所创建的环境中求值。`x` 与 `mul` 都在这个环境中有着落，只不过分属不同的帧。
环境中各帧的次序，会影响在表达式中查找名字所得的取值。我们先前说过，名字求值为当前环境中与该名字关联的值。现在可以讲得更精确些：
> **名字求值规则。** 一个名字求值为：在当前环境中找到该名字的**最早**那个帧里，绑定在该名字上的值。（这里的「最早」，指检查帧的先后顺序，从正被调用的函数的局部帧开始。）
之所以要设多个帧，是为了让同一个名字在不同语境下可以有不同的含义。英语这样的自然语言也有此性质：在覆盖千万观众的美国新闻报道中，「president」指的是美国总统——那是一个宽泛的全球语境；而在某个学生社团的成员会议上，「president」指的则是该社团的社长——那是一个本土得多的语境。在社团会议里，取用的是「president」更贴近局部的含义，而非更全球化的那层意思。
这种名字求值方式意味着：函数体内（def 语句被缩进的代码段）使用的名字，会优先取用该函数内的形式参数与赋值语句，其次才轮到全局名字。若同一名字在局部帧与全局帧中都出现，我们就说局部名字**遮蔽（shadows）**了全局名字。
我们这套关于环境、名字与函数的概念框架，构成一个**求值模型（model of evaluation）**——它精确而正确地描述了解释器如何求值调用表达式。称之为「模型」，是因为它略去了一些细节，比如计算机内存是如何组织的。那些细节对速度优化至关重要，但对理解程序的行为却无关宏旨。
### 示例：调用一个用户自定义函数
让我们再次审视那两个简单的函数定义，并描绘求值一个用户自定义函数调用表达式的过程。
```python
from operator import add, mul
def square(x):
return mul(x, x)
def sum_squares(x, y):
return add(square(x), square(y))
result = sum_squares(5, 12)
```
Python 首先求值名字 `sum_squares`，它在全局帧中绑定到一个用户自定义函数。基本数值表达式 `5` 与 `12` 求值为它们所代表的数。
接下来，Python 施加 `sum_squares`，引入一个局部帧，把 `x` 绑定为 5、`y` 绑定为 12。
`sum_squares` 的函数体包含如下调用表达式：
```text
add ( square(x) , square(y) )
________ _________ _________
运算符 操作数 0 操作数 1
```
三个子表达式都在当前环境中求值，而当前环境以标着 `sum_squares()` 的帧为起点。运算符子表达式 `add` 是从全局帧中找到的名字，绑定着做加法的内置函数。两个操作数子表达式必须依次求值，然后才能施加加法。两个操作数都在以 `sum_squares` 帧为起点的当前环境中求值。
在操作数 0 中，`square` 指的是全局帧里的一个用户自定义函数，而 `x` 指的是局部帧里的数字 5。Python 把 `square` 施加于 5，为此又引入一个局部帧，把 `x` 绑定为 5。
借助这个环境，表达式 `mul(x, x)` 求值为 25。
求值流程随即转向操作数 1，这里的 `y` 指的是数字 12。Python 再次求值 `square` 的函数体，这次又引入一个局部帧，把 `x` 绑定为 12。于是操作数 1 求值为 144。
最后，把加法施加于实参 25 与 144，得到 `sum_squares` 的最终返回值：169。
这个例子体现了我们至今建立的许多基本观念。名字绑定到值，这些值散布在许多相互独立的局部帧中，再加上一个含有共享名字的全局帧。每当函数被调用，就引入一个新的局部帧——哪怕调用的是同一个函数两次，也不例外。
所有这些机制，都是为了保证在程序执行的过程中，名字能在恰当的时刻解析到恰当的值上。这个例子也说明，我们的模型为何必须具备这些复杂性：三个局部帧里都含有名字 `x` 的绑定，但在不同的帧中，该名字绑定着不同的值。正是局部帧把同名者隔离开来。
### 局部名字
函数实现中有一个细节，不应当影响函数的行为，那就是实现者为形式参数所选的名字。因此，下面两个函数应当表现出相同的行为：
```python
>>> def square(x):
return mul(x, x)
>>> def square(y):
return mul(y, y)
```
这条原则——函数的含义应当独立于其作者所选的参数名——有几项重要推论。例如，函数的参数名只在函数体内部指称其实参；它们是函数**局部（local）**的。
倘若参数不是各自函数体的局部名字，那么 `square` 里的参数 `x` 就可能与 `sum_squares` 里的参数 `x` 混淆。关键在于：这种混淆并不会发生——不同局部帧中 `x` 的绑定互不相干。语言的种种设计，正是为了保证这种独立性。
我们说，一个局部名字的**作用域（scope）**限于定义它的那个用户自定义函数的函数体。当一个名字不再可被访问时，它就**超出作用域（out of scope）**了。这种作用域行为并非我们模型之外的新事实，它正是环境运作方式的必然结果。
作用域与环境是什么关系？作用域关乎**代码**：它描述名字在代码的何处可用——例如，函数的参数名可用在函数体内，出了函数体便不可用。环境关乎**代码的求值**：它在程序运行时追踪名字与值之间的绑定。二者之所以相关，是因为「如何创建与使用不同环境」的规则，保证了作用域内的名字总在当前环境中，而作用域外的名字则不在。
### 选择名字
名字可以互换，并不意味着形式参数名就无足轻重。恰恰相反，精心挑选的函数名与参数名，对于函数定义能否被人读懂至关重要！
以下准则改编自 Python 代码风格指南（PEP 8），这份指南是全体（不那么叛逆的）Python 程序员的共同守则。一套共享的约定，能让开发者共同体内部的交流更为顺畅。遵循这些约定，还有一个附带的好处：你会发现自己的代码在内部愈发自洽。
* 函数名用小写，单词之间用下划线分隔；提倡使用描述性的名字。
* 函数名通常应当唤起「解释器对实参所做的操作」（如 `print`、`add`、`square`），或者「结果所得的那个量」（如 `max`、`abs`、`sum`）。
* 参数名用小写，单词之间用下划线分隔；优先使用单个单词。
* 参数名应当唤起该参数在函数中的角色，而不只是所允许的实参类型。
* 当角色一目了然时，单字母参数名可以接受；但要避开 `l`（小写 L）、`O`（大写 O）、`I`（大写 I），以免与数字混淆。
这些准则有许多例外，即便在 Python 标准库里也不例外。如同英语的词汇，Python 也从形形色色的贡献者那里继承了词语，结果未必总是整齐划一。
### 函数即抽象
尽管十分简单，`sum_squares` 却体现了用户自定义函数最强大的性质。`sum_squares` 是依据函数 `square` 定义的，但它只倚赖 `square` 所定义的「输入实参与输出值之间的关系」，而不问其内部如何运作。
我们写 `sum_squares` 时，根本不必操心「如何平方一个数」。阅读 `sum_squares` 的函数体时，可以完全忽略平方是如何算出来的。事实上，对 `sum_squares` 而言，`square` 并不是某个特定的函数体，而是对函数的**抽象**——一种所谓的**函数抽象（functional abstraction）**。它可以靠乘法来平方，也可以靠反复相加来平方，或者先乘再加。任何能算出平方的函数，都同样合格。
因此，只看返回值的话，下面两个平方函数应当无从分辨。二者各接受一个数值实参，并以该数的平方作为返回值。
```python
>>> def square(x):
return mul(x, x)
>>> def square(x):
return mul(x, x-1) + x
```
换言之，函数定义为「输入与输出之间的某种关系」赋予了一个名字，而把细节抽象掉了。函数的使用者未必亲手写过这个函数，甚至可能根本不知道它是怎么实现的。程序员使用一个函数时，本不该需要了解它的实现方式。Python 库正具备这一性质：无数开发者使用其中定义的函数，却很少有人去翻看实现。这就是抽象的威力。
**函数抽象的诸方面。** 要掌握一种函数抽象，常常需要考察它的三大核心属性。函数的**定义域（domain）**是它能接受的实参集合；**值域（range）**是它能返回的值集合；**意图（intent）或行为**则是它所计算的输入与输出之间的关系（以及可能产生的任何副作用）。通过定义域、值域与意图来理解函数抽象，是在复杂程序中正确使用它们的关键。
例如，用来实现 `sum_squares` 的任何平方函数，都应具备如下属性：
* 定义域：任意单个实数；
* 值域：任意非负实数；
* 意图：输出为输入的平方。
这些属性并未规定意图如何实现；实现细节已被抽象掉了。
### 运算符
> 🎬 视频：Operators and Division
数学运算符（如 `+`、`-`）提供了我们关于「组合手段」的第一个例子，但我们尚未为含有这些运算符的表达式定义求值流程。
含中缀运算符的 Python 表达式各有自己的求值流程，不过你大可以把它们视为调用表达式的简写。当你看到
```python
>>> 2 + 3
5
```
不妨就把它当成下面这行的简写：
```python
>>> add(2, 3)
5
```
中缀记法可以嵌套，一如调用表达式。Python 遵循通常的数学运算优先级规则，这些规则决定了含有多个运算符的复合表达式该如何解读。
```python
>>> 2 + 3 * 4 + 5
19
```
求值结果与下面这行相同：
```python
>>> add(add(2, mul(3, 4)), 5)
19
```
调用表达式中的嵌套比运算符版本更为显式，但也更难读。Python 允许用圆括号对子表达式分组，以覆盖常规的优先级规则，或让表达式的嵌套结构更清晰。
```python
>>> (2 + 3) * (4 + 5)
45
```
求值结果与下面这行相同：
```python
>>> mul(add(2, 3), add(4, 5))
45
```
说到除法，Python 提供了两个中缀运算符：`/` 与 `//`。前者是普通除法，结果总是浮点数（小数），即便除尽也是如此：
```python
>>> 5 / 4
1.25
>>> 8 / 4
2.0
```
后者 `//` 则把结果向下取整为整数：
```python
>>> 5 // 4
1
>>> -5 // 4
-2
```
这两个运算符分别是 `truediv` 与 `floordiv` 函数的简写。
```python
>>> from operator import truediv, floordiv
>>> truediv(5, 4)
1.25
>>> floordiv(5, 4)
1
```
在你的程序中，尽可放心大胆地使用中缀运算符与圆括号。对于简单的数学运算，地道的 Python 偏爱运算符，而非调用表达式。
---
> **译者注**：原文中的若干「环境图」是可交互的 Web 组件（点击即可逐步演示），静态文档无法承载，已改写为对应的程序片段与分步说明。
---
## 1.4 设计函数
> 🎬 视频：Designing Functions
函数是一切程序的必要成分，无论程序大小；它也是我们在编程语言中表达计算过程的主要媒介。至此，我们讨论的都是函数的形式性质以及如何施加它们。现在，我们转而讨论：什么样的函数才算好的函数。从根本上说，好函数的各项品质，都在强化「函数即抽象」这一理念。
* **每个函数只应承担一件事。** 这件事应当能用简短的名字指认，并用一行文字概述。凡按序承担多件事的函数，都应当拆成多个函数。
* **不要重复自己（Don't repeat yourself）**，这是软件工程的一条核心信条。所谓的 DRY 原则指出：多段代码不应当重复描述同一逻辑；那逻辑应当只实现一次，给它一个名字，然后反复施加。当你发现自己在一段段地复制粘贴代码时，多半是遇到了做函数抽象的好机会。
* **函数应当定义得尽量一般（general）。** Python 库中之所以没有「平方」函数，恰恰因为它只是 `pow` 函数的一个特例——而 `pow` 能把数提升到任意幂次。
这些准则能提高代码的可读性、减少错误，而且往往能减少总的代码量。把复杂任务分解为简洁的函数，是一门需要经验才能掌握的技艺。所幸，Python 提供了若干特性来助你一臂之力。
### 文档
函数定义中往往包含描述该函数的**文档（documentation）**，称为**文档字符串（docstring）**，它必须与函数体一同缩进。按照惯例，文档字符串使用三引号。第一行用一句话描述该函数的职责；随后的行可以说明各个参数，并澄清函数的行为：
```python
>>> def pressure(v, t, n):
"""Compute the pressure in pascals of an ideal gas.
Applies the ideal gas law: https://en.wikipedia.org/wiki/Ideal_gas_law
v -- volume of gas, in cubic meters
t -- absolute temperature in degrees kelvin
n -- particles of gas
"""
k = 1.38e-23 # Boltzmann's constant
return n * k * t / v
```
当你以函数名作为实参调用 `help` 时，便会看到它的文档字符串（输入 `q` 可退出 Python 帮助）：
```python
>>> help(pressure)
```
编写 Python 程序时，除最简单的函数外，都应写上文档字符串。请记住：代码只写一次，却常常被读很多次。Python 官方文档中载有文档字符串的撰写指南，它能让不同的 Python 项目保持一致。
**注释。** Python 中的注释可以附在一行末尾，以 `#` 号引出。例如，上面那条 `# Boltzmann's constant` 注释就在说明 `k`。这类注释不会出现在 Python 的帮助信息中，解释器也对它视而不见——它们只为人类而存在。
### 默认参数值
把函数定义得一般化，随之而来的副产品是参数数量的增加。参数一多，函数调用起来别扭，读起来也费劲。
在 Python 中，我们可以为函数的参数提供**默认值（default values）**。调用该函数时，带默认值的参数就是可选的；若未提供，则把默认值绑定到对应的形式参数名上。例如，若某个应用常常要算一摩尔粒子的压强，就可以把这个值设为默认值：
```python
>>> def pressure(v, t, n=6.022e23):
"""Compute the pressure in pascals of an ideal gas.
v -- volume of gas, in cubic meters
t -- absolute temperature in degrees kelvin
n -- particles of gas (default: one mole)
"""
k = 1.38e-23 # Boltzmann's constant
return n * k * t / v
```
在这个例子里，`=` 符号依用法的不同而有两种含义。在 def 语句的头部，`=` 并不执行赋值，而是指明调用 `pressure` 函数时若无对应实参则采用的默认值。相比之下，函数体中给 `k` 的那条赋值语句，把名字 `k` 绑定到玻尔兹曼常数的一个近似值上。
```python
>>> pressure(1, 273.15)
2269.974834
>>> pressure(1, 273.15, 3 * 6.022e23)
6809.924502
```
`pressure` 函数定义为接受三个参数，但上面第一个调用表达式只提供了两个。此时，`n` 的取值来自 def 语句中的默认值。若提供了第三个实参，默认值便被忽略。
作为一条准则：函数体中使用的多数数据值，都应当写成具名参数的默认值，以便检查，也便于调用者修改。有些永不改变的值，比如基本常数 `k`，则可以在函数体中或全局帧中绑定。
---
## 1.5 控制
> 🎬 视频：Conditional Statements、Iteration（详见下文）
我们已经能定义的那些函数，表达能力还十分有限——因为尚未引入比较的手段，也无法根据比较的结果执行不同的操作。**控制语句（control statements）**赋予我们这种能力。它们依据逻辑比较的结果，来控制程序执行的流向。
控制语句与我们此前研究的表达式有所不同。它们不像表达式那样有一个值；相反，执行一条控制语句，决定的是解释器接下来该做什么。
### 语句
我们已经见过三类语句：赋值语句、def 语句和 return 语句。这几行 Python 代码本身并不是表达式——尽管它们都以表达式作为组成部分。
语句不求值，而是**执行**。每条语句都描述了某种对解释器状态的改变，执行一条语句就是施行这种改变。正如在 return 与赋值语句中所见，执行语句往往涉及求值其中所含的子表达式。
函数的函数体是一串语句。在 Python 中，一个表达式可以单独占一行，此时它被当作语句处理，称为**表达式语句（expression statement）**，其值则被丢弃。
例如，下面把 `return` 关键字漏掉之后，`mul(x, x)` 就成了一条表达式语句：`x` 确实乘了自己，但结果被丢弃，而没有返回。
```python
>>> def square(x):
mul(x, x) # 当心！这个调用不返回值。
>>> print(square(3))
None
>>> y = square(4)
>>> print(y)
None
```
要想利用某个表达式的值做点什么，它必须成为某条更大语句的一部分，比如赋值语句或 return 语句。
```python
>>> def square(x):
return mul(x, x)
>>> print(square(3))
9
>>> y = square(4)
>>> print(y)
16
```
有时，当函数体调用的是 `print` 这样的非纯函数时，让函数体只含一个表达式也确实说得过去。然而，用 `print` 显示一个值，并不等于返回它；那个值也就无法再被赋值，或进一步参与组合。
```python
>>> def print_square(x):
print(mul(x, x))
>>> print_square(3)
9
>>> y = print_square(4)
16
>>> print(y)
None
```
Python 解释器的职责是执行程序，而程序是语句的序列。不过，计算中许多有趣的工作，恰恰来自表达式的求值。语句控制着：程序中有哪些表达式被求值、它们在什么环境中求值，以及它们的结果何去何从。
### 复合语句
**简单语句（simple statement）**是不以冒号结尾的单独一行。**复合语句（compound statement）**之所以这么叫，是因为它由其他语句（简单语句与复合语句皆可）复合而成。复合语句通常跨越多行，以一个以冒号结尾的单行**头部（header）**开始，由此标明语句的类型。头部连同其后缩进的一组语句，合称一个**子句（clause）**。一条复合语句由一个或多个子句构成：
```text
:
...
:
...
```
用这套术语来理解，我们已经介绍的语句便可归位：
* 表达式语句、return 语句和赋值语句，都是简单语句；
* def 语句是复合语句，def 头部之后的那组语句定义了函数体。
每一类头部都有各自专门的求值规则，规定其子句组中的语句何时执行、是否执行。我们说，头部**控制（controls）**着它的子句组。例如在 def 语句中，我们看到返回表达式并不立即求值，而是被保存起来，留待所定义的函数最终被调用时使用。
现在我们也能理解多行程序了：
* 要执行一串语句，先执行第一条。若该语句没有重定向控制，就继续执行这串语句的其余部分（若还有剩余）。
这个定义揭示了递归定义的序列之本质结构：一个序列可以分解为它的第一项与其余各项。而一串语句的「其余部分」，本身又是一串语句！于是，我们可以递归地施用这条执行规则。
这条规则的重要推论是：语句按序执行，但若控制被重定向，后面的语句可能永远也执行不到。
**实用建议。** 为子句组缩进时，所有行必须缩进相同的量、相同的方式（用空格，不要用制表符）。缩进上任何不一致都会导致错误。
### 局部赋值
起初，我们说用户自定义函数的函数体只包含一条 return 语句、一个返回表达式。事实上，函数可以定义一序列操作，远远超出单个表达式的范围。
每当用户自定义函数被施加，其定义的子句组序列就会在这样一个环境中执行：该环境以一个局部帧为起点，而此帧正是由调用该函数所创建的。return 语句会**重定向控制**：函数应用的过程一旦执行到第一条 return 语句便告结束，该返回表达式的值，就是被施加函数的返回值。
赋值语句可以出现在函数体内部。例如，下面这个函数用两步计算，返回两个量之差相对于第一个量的百分比：
```python
def percent_difference(x, y):
difference = abs(x-y)
return 100 * difference / x
result = percent_difference(40, 50)
```
赋值语句的作用，是在当前环境的第一个帧中把名字绑定到值上。因此，函数体内的赋值语句无法影响全局帧。函数只能操作自己的局部帧，这一点极大地简化了编程——纯函数只通过所取的值和所返回的值发生交互，而不去影响其他函数的行为。
当然，`percent_difference` 也可以写成一个表达式，如下所示——只不过返回表达式要复杂些：
```python
>>> def percent_difference(x, y):
return 100 * abs(x-y) / x
>>> percent_difference(40, 50)
25.0
```
至此，局部赋值尚未增强我们函数定义的表达能力。它与别的控制语句结合时才会大显身手；但即便单用，它也颇有用处——通过为中间量赋予名字，能让复杂表达式的含义更清晰。
### 条件语句
> 🎬 视频：Conditional Statements
Python 有一个计算绝对值的内置函数。
```python
>>> abs(-2)
2
```
我们想自己实现这样一个函数，但这样做需要比较与选择。我们想表达的是：若 `x` 为负，`abs(x)` 返回 `-x`；若 `x` 为 0，`abs(x)` 返回 0；否则 `x` 为正，`abs(x)` 返回 `x`。在 Python 中，这种选择可以用**条件语句（conditional statement）**来表达。
```python
def absolute_value(x):
"""Compute abs(x)."""
if x < 0:
return -x
elif x == 0:
return 0
else:
return x
result = absolute_value(-2)
```
Python 的条件语句由一系列头部与子句组构成：一个必需的 if 子句、若干可选的 elif 子句，最后是一个可选的 else 子句：
```text
if :
elif :
else:
```
执行条件语句时，各子句按序逐一考察。执行一个条件子句的计算流程如下：
* 求值头部的表达式；
* 若为真值，执行该子句组，然后跳过条件语句中其后所有的子句。
若执行到了 else 子句（只有当前面所有 if 与 elif 的表达式都求值为假值时才可能），则执行它的子句组。
#### 布尔值与布尔运算符
**布尔语境（boolean contexts）。** 上面的执行流程提到了「假值」与「真值」。条件块头部语句中的表达式，据说处于**布尔语境**之中：它们的真值关乎控制流，除此之外，它们的值既不被赋值，也不被返回。Python 中有若干假值，包括 `0`、`None`，以及布尔值 `False`。其他所有数字都是真值。在第 2 章中我们会看到，Python 中每一种内置数据类型都兼有真值与假值。
**布尔值。** Python 有两个布尔值，`True` 与 `False`。布尔值表示逻辑表达式里的真值。内置的比较运算 `>`、`<`、`>=`、`<=`、`==`、`!=` 就返回这两个值。
```python
>>> 4 < 2
False
>>> 5 >= 5
True
```
第二个例子读作「5 大于或等于 5」，对应于 `operator` 模块中的函数 `ge`。
```python
>>> 0 == -0
True
```
最后一个例子读作「0 等于 -0」，对应于 `operator` 模块中的 `eq`。请注意，Python 把赋值（`=`）与相等比较（`==`）区分开来——这是许多编程语言共有的约定。
**布尔运算符。** Python 还内置了三个基本的逻辑运算符：
```python
>>> True and False
False
>>> True or False
True
>>> not False
True
```
逻辑表达式各有相应的求值流程。这些流程利用了一个事实：逻辑表达式的真值，有时无需求值全部子表达式便可确定——这一特性称为**短路求值（short-circuiting）**。
要求值表达式 ` and `：
* 求值子表达式 ``；
* 若结果为假值 v，则该表达式求值为 v；
* 否则，该表达式求值为子表达式 `` 的值。
要求值表达式 ` or `：
* 求值子表达式 ``；
* 若结果为真值 v，则该表达式求值为 v；
* 否则，该表达式求值为子表达式 `` 的值。
要求值表达式 `not `：
* 求值 ``；若结果为假值则得 `True`，否则得 `False`。
这些值、规则与运算符，赋予我们组合比较结果的手段。执行比较、返回布尔值的函数，其名字通常以 `is` 开头，且后面不接下划线（如 `isfinite`、`isdigit`、`isinstance` 等）。
### 迭代
> 🎬 视频：Iteration
控制语句除了用来选择执行哪些语句，还用来表达重复。如果我们写的每一行代码都只执行一次，那么编程将是一门极低效的营生。唯有反复执行语句，才能充分释放计算机的潜力。我们已经见过一种重复的形式：一个函数只定义一次，却能被调用许多次。而**迭代控制结构**，则是反复执行同样语句的另一种机制。
考察斐波那契数列，其中每个数都是前两个数之和：
```text
0, 1, 1, 2, 3, 5, 8, 13, 21, ...
```
其中的每个值，都是反复施用「前两数相加」的规则构造出来的。第 0 个与第 1 个固定为 0 和 1，因此 1 是第二项。例如，第八个斐波那契数是 21。
我们可以用 **while 语句**计算第 n 个斐波那契数。需要追踪：算到了哪个位置（`k`）、第 k 个值（`curr`）以及它的前一个值（`pred`）。请单步执行下面的函数，观察斐波那契数是如何一个个演进、并绑定到 `curr` 上的。
```python
def fib(n):
"""Compute the nth Fibonacci number, for n >= 1."""
pred, curr = 0, 1 # 第 0 个与第 1 个斐波那契数
k = 1 # curr 是第几个斐波那契数？
while k < n:
pred, curr = curr, pred + curr
k = k + 1
return curr
result = fib(8)
```
请记住，赋值语句中用逗号分隔多个名字与多个值。这一行：
```python
pred, curr = curr, pred + curr
```
的效果是：把名字 `pred` 重新绑定到 `curr` 的值，同时把 `curr` 重新绑定到 `pred + curr` 的值。`=` 右侧的所有表达式，都在任何重新绑定发生之前求值完毕。
这种顺序——先求值 `=` 右边的一切，再更新左边的任何绑定——对保证这个函数的正确性至关重要。
一个 while 子句包含一个头部表达式，随后是一个子句组：
```text
while :
```
要执行一个 while 子句：
* 求值头部的表达式；
* 若为真值，执行子句组，然后回到第 1 步。
在第 2 步中，while 子句的整个子句组执行完毕，头部表达式才会被再次求值。
为了防止 while 子句的子句组无休无止地执行下去，子句组在每一轮中都应改变某个绑定。
不终止的 while 语句称为**无限循环（infinite loop）**。按 `-C` 可迫使 Python 停止循环。
### 测试
**测试（testing）**一个函数，就是验证该函数的行为是否与预期相符。我们这门函数语言如今已足够复杂，是时候开始测试自己的实现了。
**测试（test）**是系统化地执行这种验证的机制。测试通常采取另一个函数的形式，其中包含一处或多处对待测函数的示例调用，再把返回值与预期结果加以核对。与大多数力求通用的函数不同，测试要选取具体的实参值来调用并验证。测试同时也是一份文档：它演示了如何调用一个函数，以及什么样的实参值才算恰当。
#### 断言
程序员用 **assert 语句**来验证预期，比如被测试函数的输出。assert 语句含有一个处于布尔语境中的表达式，随后是一行带引号的文本（单引号双引号皆可，但要前后一致）；若该表达式求值为假值，这行文本就会显示出来。
```python
>>> assert fib(8) == 21, 'The 8th Fibonacci number should be 21'
```
当被断言的表达式求值为真值时，执行 assert 语句毫无效果；而若为假值，assert 会引发错误，中止执行。
`fib` 的测试函数应当测试若干实参，包括 n 的极端取值。
```python
>>> def fib_test():
assert fib(1) == 1, 'The 1st Fibonacci number should be 1'
assert fib(3) == 2, 'The 3rd Fibonacci number should be 2'
assert fib(50) == 12586269025, 'Error at the 50th Fibonacci number'
```
在文件中写 Python 时（而非直接敲进解释器），测试通常写在同一个文件中，或写在后缀为 `_test.py` 的相邻文件里。
#### 文档测试
Python 提供了一种便利的做法：把简单的测试直接放进函数的文档字符串。文档字符串的第一行应是一句话的函数描述，随后空一行，再往后可以详细描述参数与行为。此外，文档字符串还可以包含一段调用该函数的示例交互会话：
```python
>>> def sum_naturals(n):
"""Return the sum of the first n natural numbers.
>>> sum_naturals(10)
55
>>> sum_naturals(100)
5050
"""
total, k = 0, 1
while k <= n:
total = total + k
k = k + 1
return total
```
随后，可以借助 `doctest` 模块来验证这段交互：
```python
>>> from doctest import testmod
>>> testmod()
TestResults(failed=0, attempted=2)
```
若只想验证单个函数的文档测试交互，我们使用 `doctest` 中一个名为 `run_docstring_examples` 的函数。遗憾的是，这个函数的调用方式略嫌繁琐：第一个实参是要测试的函数；第二个永远应当是表达式 `globals()` 的结果——这是个内置函数，返回全局环境；第三个实参为 `True`，表示希望得到「啰嗦」的输出，即列出所有运行过的测试。
```python
>>> from doctest import run_docstring_examples
>>> run_docstring_examples(sum_naturals, globals(), True)
Finding tests in NoName
Trying:
sum_naturals(10)
Expecting:
55
ok
Trying:
sum_naturals(100)
Expecting:
5050
ok
```
当函数的返回值与预期结果不符时，`run_docstring_examples` 会把这一问题报告为测试失败。
在文件中写 Python 时，可以用 doctest 命令行选项启动 Python，一次性运行文件中的所有文档测试：
```bash
python3 -m doctest
```
有效测试的关键，是在实现新函数之后立即编写（并运行）测试。更好的习惯是：在动手实现之前就先写一些测试，好让心中先有几个示例输入与输出。只施加单个函数的测试称为**单元测试（unit test）**。彻底的单元测试，是优秀程序设计的一块试金石。
---
> **译者注**：1.4 与 1.5 原文中的交互式环境图，同样改写为程序片段与文字说明。
---
## 1.6 高阶函数
> 🎬 视频：Higher-Order Functions
我们已经看到，函数描述的是复合操作，而不依赖其实参的具体取值。也就是说，在 `square` 中
```python
>>> def square(x):
return x * x
```
我们谈论的并不是某个特定数的平方，而是求得任意数平方的方法。当然，即使从不定义这个函数，只消一直写下
```python
>>> 3 * 3
9
>>> 5 * 5
25
```
而从不明确提起 `square`，日子照样能过。这种做法应付得了 `square` 这样简单的计算，但遇上 `abs`、`fib` 之类更复杂的例子，就变得苦不堪言了。总的来说，缺少函数定义，我们就始终被迫停留在「语言恰好内置了哪些具体操作」的层面（此处是乘法），而无法凭借函数抽象来思考。程序固然能算出平方，语言却无从表达「平方」这个概念。
我们对一门强大的编程语言的要求之一，是能够通过「为常见模式赋予名字，再直接按名字操作」来建立抽象。函数正提供了这种能力。从下面的例子中我们会看到，有些常见的编程模式反复出现于代码之中，只是所配的函数各不相同。这些模式同样可以被抽象出来，办法同样是给它们起名字。
要把某些一般模式表达为具名的概念，我们需要构造这样的函数：它能接受其他函数作为实参，或者把函数作为返回值。操作函数的函数，称为**高阶函数（higher-order functions）**。本节将展示，高阶函数如何充当强大的抽象机制，从而极大增强我们语言的表达能力。
### 函数作为实参
考察下面三个函数，它们都在计算求和。第一个 `sum_naturals` 求自然数之和，直加到 n：
```python
>>> def sum_naturals(n):
total, k = 0, 1
while k <= n:
total = total + k
k = k + 1
return total
>>> sum_naturals(100)
5050
```
第二个 `sum_cubes` 求自然数立方之和，直加到 n：
```python
>>> def sum_cubes(n):
total, k = 0, 1
while k <= n:
total = total + k * k * k
k = k + 1
return total
>>> sum_cubes(100)
25502500
```
第三个 `pi_sum` 求下列级数之和：
```text
8/(1·3) + 8/(5·7) + 8/(9·11) + …
```
该级数收敛于 π（收敛得非常慢）。
```python
>>> def pi_sum(n):
total, k = 0, 1
while k <= n:
total = total + 8 / ((4*k-3) * (4*k-1))
k = k + 1
return total
>>> pi_sum(100)
3.1365926848388144
```
这三个函数显然共享着一个底层的共同模式。它们大体上一模一样，只在名字，以及「用 k 计算待加项的那个表达式」上有所不同。把同一个模板里留空的地方填上，就能生成这三个函数：
```python
def (n):
total, k = 0, 1
while k <= n:
total = total + (k)
k = k + 1
return total
```
这样一个共同模式的存在，强有力地表明：有一种有用的抽象正等着被请到台面上来。这三个函数，无非都是「若干项之和」。作为程序设计者，我们希望语言足够强大，能写出表达「求和」这个概念本身的函数，而不只是算出某个具体和的函数。在 Python 中，把上面那个公共模板里的「空位」变成形式参数，便可轻而易举地做到这一点。
在下面的例子中，`summation` 接受两个实参：上界 `n`，以及计算第 k 项的函数 `term`。我们可以像使用任何函数那样使用 `summation`，它能简洁地表达求和。请花些时间单步走一遍这个例子，注意：把 `cube` 绑定到局部名字 `term` 之后，结果 1×1×1 + 2×2×2 + 3×3×3 = 36 是如何被正确算出的。在这个例子里，不再需要的帧已被移除，以节省空间。
```python
def summation(n, term):
total, k = 0, 1
while k <= n:
total = total + term(k)
k = k + 1
return total
def cube(x):
return x*x*x
def sum_cubes(n):
return summation(n, cube)
result = sum_cubes(3)
```
借助一个返回其自身实参的**恒等函数（identity function）**，我们还能用同一个 `summation` 函数来做自然数求和：
```python
>>> def summation(n, term):
total, k = 0, 1
while k <= n:
total = total + term(k)
k = k + 1
return total
>>> def identity(x):
return x
>>> def sum_naturals(n):
return summation(n, identity)
>>> sum_naturals(10)
55
```
`summation` 函数也可以直接调用，不必为某个特定数列另写一个函数。
```python
>>> summation(10, square)
385
```
借助我们这套求和抽象，再定义一个计算各项的函数 `pi_term`，便能写出 `pi_sum`。我们传入实参 `1e6`——那是 1 × 10⁶ = 1000000 的简写——以得到一个足够逼近 π 的近似值。
```python
>>> 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
```
### 函数作为一般方法
我们引入用户自定义函数，是为了把数值运算的模式抽象出来，使之脱离具体数字而独立。有了高阶函数，我们开始看到一种更强大的抽象：某些函数表达的是一般的**计算方法**，独立于它们所调用的具体函数。
尽管「函数」这一概念在观念上被如此拓展，我们那套用来求值调用表达式的环境模型，却能优雅地延展到高阶函数的情形，无需任何改动。当用户自定义函数被施加于若干实参时，形式参数就在一个新的局部帧中绑定到那些实参的值上（这些值可以是函数）。
考察下面这个例子：它实现了一种通用的**迭代改进（iterative improvement）**方法，并用它来计算黄金比例。黄金比例常被称为「phi」或 φ，是一个接近 1.6 的数，频频现身于自然、艺术与建筑之中。它恰是一个比自己的倒数多 1 的数：φ = 1 + 1/φ。
迭代改进算法先给出方程解的一个猜测值，然后反复施加一个**更新函数（update function）**来改进这个猜测，再施加一次「接近比较」，检查当前的猜测是否「足够接近」而可视为正确。
```python
>>> def improve(update, close, guess=1):
while not close(guess):
guess = update(guess)
return guess
```
这个 `improve` 函数是对「反复精炼」的一般表达。它并未规定求解的是什么问题——那些细节，都留给作为实参传入的 `update` 与 `close` 函数了。
黄金比例有几条著名性质：它可以由「反复把任意正数的倒数与 1 相加」算出；它比自己的平方小 1。我们可以把这些性质表达成函数，供 `improve` 使用。
```python
>>> def golden_update(guess):
return 1/guess + 1
>>> def square_close_to_successor(guess):
return approx_eq(guess * guess, guess + 1)
```
上面我们引入了一处对 `approx_eq` 的调用，其用意是：若两个实参彼此近似相等，就返回 `True`。要实现 `approx_eq`，可以把两数之差取绝对值，再与一个很小的容差值比较。
```python
>>> def approx_eq(x, y, tolerance=1e-15):
return abs(x - y) < tolerance
```
以 `golden_update` 与 `square_close_to_successor` 为实参调用 `improve`，便会算出黄金比例的一个有限近似：
```python
>>> improve(golden_update, square_close_to_successor)
1.6180339887498951
```
沿着求值的各个步骤追溯一遍，就能看清这个结果是如何算出来的。首先，为 `improve` 构造一个局部帧，其中绑定 `update`、`close` 与 `guess`。在 `improve` 的函数体里，名字 `close` 绑定到 `square_close_to_successor`，它被施加于 `guess` 的初始值。请继续追随后续步骤，观察计算过程如何演进，最终算出黄金比例。
```python
def improve(update, close, guess=1):
while not close(guess):
guess = update(guess)
return guess
def golden_update(guess):
return 1/guess + 1
def square_close_to_successor(guess):
return approx_eq(guess * guess, guess + 1)
def approx_eq(x, y, tolerance=1e-3):
return abs(x - y) < tolerance
phi = improve(golden_update, square_close_to_successor)
```
这个例子体现了计算机科学中两个互为表里的大观念。其一，命名与函数让我们得以把大量复杂性抽象掉：每个函数定义都平淡无奇，可我们的求值流程所启动的计算过程却相当错综复杂。其二，正是因为 Python 语言有着一套极其通用的求值流程，微小的组件才得以组合成复杂的过程。理解「解释程序的流程」，使我们能够验证并审视自己创造出来的过程。
一如既往，我们这项新的一般方法 `improve` 也需要一个测试来检验其正确性。黄金比例恰好能提供这样一个测试——它还有一个精确的闭式解，可以拿来与这个迭代结果作比较。
```python
>>> 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()
```
对这个测试而言，没有消息就是好消息：`improve_test` 在 assert 语句顺利执行之后返回 `None`。
### 定义函数之三：嵌套定义
上面的例子证明：把函数作为实参传递的能力，显著增强了我们编程语言的表达力。每个一般概念或方程，都对应着一段自己的短小函数。这种做法有一个负面后果：全局帧里塞满了小函数的名字，而这些名字必须个个独一无二。另一个问题是，我们受制于特定的函数签名：`improve` 的 `update` 参数必须恰好接受一个实参。**嵌套函数定义（Nested function definitions）**同时解决了这两个问题，但需要我们把环境模型加以充实。
让我们考虑一个新问题：计算一个数的平方根。在编程语言中，「平方根」常缩写为 `sqrt`。反复施加下面这个更新，就会收敛到 a 的平方根：
```python
>>> def average(x, y):
return (x + y)/2
>>> def sqrt_update(x, a):
return average(x, a/x)
```
这个双参数的更新函数与 `improve` 格格不入（它要两个实参，不是一个）；而且它只给出一次更新，而我们真正在乎的恰恰是通过反复更新来求平方根。两个问题的共同解法，是把函数定义放进其他定义的函数体内。
```python
>>> 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`，而 `a` 是其外围函数 `sqrt` 的形式参数。这种在嵌套定义之间共享名字的规程，称为**词法作用域（lexical scoping）**。关键在于：内层函数访问的是**定义它们时**所在环境的那些名字（而不是调用它们时所在的环境）。
要让词法作用域生效，我们需要对环境模型作两项扩展：
* 每个用户自定义函数都有一个**父环境（parent environment）**：即定义它时所处的环境；
* 当用户自定义函数被调用时，其局部帧的父环境，就是那个父环境。
在 `sqrt` 之前，所有函数都定义在全局环境中，因此它们的父环境都相同：`global`。相比之下，当 Python 求值 `sqrt` 的头两个子句时，它创建的函数便与一个局部环境相关联。在调用
```python
>>> sqrt(256)
16.0
```
中，环境首先为 `sqrt` 添加一个局部帧，并求值 `sqrt_update` 与 `sqrt_close` 的 def 语句。
```python
def average(x, y):
return (x + y)/2
def improve(update, close, guess=1):
while not close(guess):
guess = update(guess)
return guess
def approx_eq(x, y, tolerance=1e-3):
return abs(x - y) < tolerance
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)
result = sqrt(256)
```
今后，环境图中的函数值都会多出一项新标注：**父环境（parent）**。函数值的父环境，就是定义该函数时所处环境的第一个帧。没有父环境标注的函数，都是在全局环境中定义的。当用户自定义函数被调用时，所创建的帧与那个函数有着相同的父环境。
接着，名字 `sqrt_update` 解析到这个新定义的函数，它被作为实参传给 `improve`。在 `improve` 的函数体内，我们必须把这个更新函数（此时绑定于 `sqrt_update`）施加于初始猜测值 1。这最后一次施加为 `sqrt_update` 创建了一个环境：它以只含 `x` 的局部帧为起点，而父帧 `sqrt` 中仍然含有 `a` 的绑定。
在这个求值过程中，最关键的一环，是 `sqrt_update` 的父环境被传递给了「调用 `sqrt_update` 所创建的帧」。这个帧同样标注着 `[parent=f1]`。
**延展的环境（Extended environments）。** 一个环境可以由任意长的帧链构成，链的尽头总是全局帧。在 `sqrt` 这个例子之前，环境至多只有两个帧：一个局部帧和一个全局帧。通过调用那些定义在其他函数内部的函数（借助嵌套 def 语句），我们可以造出更长的链。这次调用 `sqrt_update` 的环境由三个帧构成：`sqrt_update` 的局部帧；定义 `sqrt_update` 的那个 `sqrt` 帧（记作 f1）；以及全局帧。
`sqrt_update` 函数体中的返回表达式，可以顺着这条帧链为 `a` 解析出值来。名字查找，是在当前环境中找出第一个绑定着该名字的值。Python 先查 `sqrt_update` 帧——没有 `a`。接着查父帧 f1，发现 `a` 绑定为 256。
由此，我们领会到 Python 词法作用域的两个关键优势：
* 局部函数的名字不会干扰其定义所在函数之外的任何名字，因为这个局部函数名会绑定在其**定义时**所在的当前局部环境中，而非全局环境；
* 局部函数可以访问外围函数的环境，因为局部函数的函数体，是在「扩展了其定义环境」的环境中求值的。
`sqrt_update` 函数随身携带着一些数据：它定义环境中被引用的 `a` 的值。因为局部函数以这种方式把信息「围拢」（enclose）起来，它们常被称为**闭包（closures）**。
### 函数作为返回值
> 🎬 视频：Functions as Return Values
创建以函数为返回值的函数，能让我们的程序获得更强的表达力。词法作用域编程语言的一个重要特性是：局部定义的函数在被返回时，仍保留其父环境。下面这个例子说明了这一特性的用处。
一旦定义了许多简单函数，**函数复合（function composition）**便成了值得纳入编程语言的一种自然的组合手段。也就是说，给定两个函数 f(x) 与 g(x)，我们也许想定义 h(x) = f(g(x))。用现有的工具，就能定义函数复合：
```python
>>> def compose1(f, g):
def h(x):
return f(g(x))
return h
```
这个例子的环境图表明：即便存在名字冲突，`f` 与 `g` 也能被正确解析。
```python
def square(x):
return x * x
def successor(x):
return x + 1
def compose1(f, g):
def h(x):
return f(g(x))
return h
def f(x):
"""Never called."""
return -x
square_successor = compose1(square, successor)
result = square_successor(12)
```
`compose1` 中的那个 1，意在表示所复合的函数都接受单个实参。这一命名约定并不由解释器强制实施；那个 1 只不过是函数名的一部分。
至此，我们开始看到「精确定义计算的环境模型」这番工夫的回报：要解释我们何以能够以这种方式返回函数，环境模型无需任何修改。
### 示例：牛顿法
> 🎬 视频：Newton's Method
这个篇幅较长的例子展示：函数的返回值与局部定义可以携手并进，简洁地表达一般观念。我们将实现一种广泛用于机器学习、科学计算、硬件设计与优化之中的算法。
**牛顿法（Newton's method）**是一种经典的迭代方法，用来寻找使某个数学函数返回值为 0 的实参。这样的值称为函数的**零点（zeros）**。求函数的零点，常常等价于求解某个我们真正关心的问题，比如计算平方根。
动手之前，先说一句有启发性的话：我们太容易把「会算平方根」这件事视为理所当然。不只是 Python，你的手机、浏览器、口袋里的计算器都能替你算。然而，学习计算机科学的一部分，恰恰是理解这类量究竟是如何算出来的；而这里所展示的一般方法，适用于求解 Python 内置能力之外的一大类方程。
牛顿法是一种迭代改进算法：对任何**可微（differentiable）**的函数，它都能改进对零点的猜测。「可微」意味着该函数在任意一点都能用一条直线近似。牛顿法顺着这些线性近似，去逼近函数的零点。
想象一条穿过点 (x, f(x)) 的直线，其斜率与函数 f(x) 曲线在该点的斜率相同。这样的直线称为**切线（tangent）**，其斜率称为 f 在 x 处的**导数（derivative）**。
这条直线的斜率，是函数值的变化量与函数自变量的变化量之比。因此，把 x 平移 f(x) 除以斜率那么多，得到的便是这条切线与 0 相触处的自变量值。
`newton_update` 表达的正是「顺着这条切线走向 0」的计算过程——给定函数 `f` 及其导数 `df`：
```python
>>> def newton_update(f, df):
def update(x):
return x - f(x) / df(x)
return update
```
最后，我们可以用 `newton_update`、`improve` 算法，再加上一个「看看 f(x) 是否已接近 0」的比较，来定义 `find_zero` 函数：
```python
>>> 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 = a（x 重复 n 次）的那个 x。例如：
* 64 的平方（二次）根是 8，因为 8×8 = 64；
* 64 的立方（三次）根是 4，因为 4×4×4 = 64；
* 64 的六次方根是 2，因为 2×2×2×2×2×2 = 64。
基于如下观察，我们便能以牛顿法求根：
* 64 的平方根（记作 √64）是满足 x² − 64 = 0 的那个值 x；
* 更一般地，a 的 n 次方根（记作 ⁿ√a）是满足 xⁿ − a = 0 的那个值 x。
只要能求出后一个方程的零点，也就求得了 n 次方根。画出 n 分别取 2、3、6 而 a 取 64 时的曲线，这种关系便一目了然。
> 🎬 视频：Iterative Improvement
> 🎬 视频：Implementing Newton's Method
我们先来实现 `square_root_newton`，定义 `f` 及其导数 `df`。这里用上微积分中的一个事实：f(x) = x² − a 的导数是线性函数 df(x) = 2x。
```python
>>> 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 次方根，我们计算 f(x) = xⁿ − a 及其导数 df(x) = n·xⁿ⁻¹。
```python
>>> 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` 的容差改得更小来削减。
在你玩味牛顿法时，请注意它并不总能收敛。`improve` 的初始猜测必须足够接近零点，而且函数还得满足种种条件。尽管有这些短板，牛顿法仍是一种强大的通用计算方法，可用来求解可微方程。现代计算机中那些极快的对数算法与大整数除法算法，都采用了这项技术的各种变体。
### 柯里化
> 🎬 视频：Currying
我们可以用高阶函数，把接受多个实参的函数，转换成一条「每个函数只接受一个实参」的函数链。更具体地说，给定函数 f(x, y)，我们可以定义一个函数 g，使得 g(x)(y) 等价于 f(x, y)。这里的 g 是一个高阶函数：它接受单个实参 x，返回另一个接受单个实参 y 的函数。这种变换称为**柯里化（currying）**。
举个例子，我们可以定义一个柯里化版本的 `pow` 函数：
```python
>>> def curried_pow(x):
def h(y):
return pow(x, y)
return h
>>> curried_pow(2)(3)
8
```
有些编程语言（如 Haskell）只允许函数接受单个实参，因而程序员必须把所有多参数的过程都柯里化。而在 Python 这类更一般的语言中，当我们需要一个只接受单个实参的函数时，柯里化便派上了用场。例如，`map` 模式会把一个单参数函数施加于一串值。后面的章节我们会看到更一般的 `map` 模式示例；眼下，我们可以在一个函数里实现这个模式：
```python
>>> def map_to_range(start, end, f):
while start < end:
print(f(start))
start = start + 1
```
用 `map_to_range` 与 `curried_pow`，可以算出 2 的前十次幂，而不必专为这件事写一个函数：
```python
>>> map_to_range(0, 10, curried_pow(2))
1
2
4
8
16
32
64
128
256
512
```
同样地，用这两个函数可以算出其他数的幂。柯里化让我们不必为每一个想求幂的数专门写函数。
在上面的例子里，我们是手工对 `pow` 施展柯里化变换，得到 `curried_pow` 的。其实，我们可以定义函数来自动完成柯里化，以及它的逆变换——**去柯里化（uncurrying）**：
```python
>>> 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` 函数则逆转柯里化变换，使得 `uncurry2(curry2(f))` 等价于 f。
```python
>>> uncurry2(pow_curried)(2, 5)
32
```
### Lambda 表达式
> 🎬 视频：Lambda Expressions
到目前为止，每当想定义一个新函数，我们都得给它起个名字。但对其他类型的表达式，我们并不需要把中间值跟名字关联起来。也就是说，我们可以在不给子表达式 a*b、c*d 或整个表达式命名的前提下，算出 a*b + c*d。在 Python 中，我们可以用 **lambda 表达式**随手创建函数值——其求值结果是一个未命名的函数。lambda 表达式求值所得的函数，以单个返回表达式为函数体；赋值语句与控制语句都不允许出现。
```python
>>> def compose1(f, g):
return lambda x: f(g(x))
```
构造一个对应的英文句子，就能理解 lambda 表达式的结构：
```text
lambda x : f(g(x))
“一个函数， 接受 x， 并返回 f(g(x)）”
```
lambda 表达式的结果称为 **lambda 函数**。它没有内在名字（因此 Python 打印名字时显示 ``），除此之外，举止与任何其他函数无异。
```python
>>> s = lambda x: x * x
>>> s
at 0xf3f490>
>>> s(12)
144
```
在环境图中，lambda 表达式的结果同样是一个函数，名字用希腊字母 λ 表示。我们的 `compose` 例子，可以用 lambda 表达式写得相当紧凑。
```python
def compose1(f, g):
return lambda x: f(g(x))
f = compose1(lambda x: x * x,
lambda y: y + 1)
result = f(12)
```
有些程序员觉得，使用 lambda 表达式得来的无名函数，写起来更短、更直接。然而，复合的 lambda 表达式虽然简短，却出了名地难读。下面这个定义是正确的，但许多程序员都难以一眼看懂：
```python
>>> compose1 = lambda f,g: lambda x: f(g(x))
```
总的来说，Python 的风格偏好显式的 def 语句，而非 lambda 表达式；但当需要一个简单函数作为实参或返回值时，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 演算（lambda calculus）**——都是计算机科学的基本概念，其影响远远超出 Python 编程共同体。待第 3 章研究解释器的设计时，我们会重温这个话题。
### 抽象与一等函数
> 🎬 视频：Abstraction
本节开头我们指出：用户自定义函数是一种关键的抽象机制，因为它们让我们能把一般的计算方法写成编程语言中的显式元素。现在我们已经看到，高阶函数如何让我们操作这些一般方法，从而创造出进一步的抽象。
作为程序员，我们应当敏锐地留意那些可以识别出程序中底层抽象的机会，在此基础上构建、推广，从而创造出更强大的抽象。这并不是说，写程序就该永远以尽可能最抽象的方式去写；老练的程序员懂得如何选择与任务相称的抽象层次。但重要的是，要能以这些抽象来思考，从而随时准备把它们应用于新的语境。高阶函数的意义在于：它们使我们能够把这些抽象显式地表示为编程语言中的元素，从而像对待其他计算元素一样对待它们。
总的来说，编程语言会对「计算元素可被操作的方式」施加限制。所受限制最少的元素，据说具有**一等地位（first-class status）**。一等元素的一些「权利与特权」是：
* 可以绑定到名字；
* 可以作为实参传递给函数；
* 可以作为函数的返回值；
* 可以放进数据结构。
Python 赋予函数完全的一等地位，由此带来的表达力提升是巨大的。
### 函数装饰器
> 🎬 视频：Decorators
Python 提供了特殊的语法，用来在 def 语句执行过程中施加高阶函数，这种语法称为**装饰器（decorator）**。最常见的例子或许是 `trace`（跟踪）：
```python
>>> def trace(fn):
def wrapped(x):
print('-> ', fn, '(', x, ')')
return fn(x)
return wrapped
>>> @trace
def triple(x):
return 3 * x
>>> triple(12)
-> ( 12 )
36
```
这个例子里定义了一个高阶函数 `trace`，它返回的函数会在调用其参数之前，先执行一条打印语句，输出那个实参。`triple` 的 def 语句带着一个标注 `@trace`，它影响了 def 的执行规则。照常，函数 `triple` 被创建出来。然而，名字 `triple` 并不绑定到这个函数上；相反，它绑定到「对新定义的 triple 函数调用 trace」所返回的那个函数值上。在代码中，这个装饰器等价于：
```python
>>> def triple(x):
return 3 * x
>>> triple = trace(triple)
```
在与本书配套的项目中，装饰器被用于跟踪，也用于在从命令行运行程序时挑选要调用哪些函数。
**给专家的额外内容。** 装饰器符号 `@` 之后也可以跟一个调用表达式。`@` 后面的表达式先求值（就像上面的名字 `trace` 那样），def 语句其次，最后，把装饰器表达式的求值结果施加于新定义的函数，所得结果绑定到 def 语句中的那个名字上。
---
> **译者注**：1.6 原文中的交互式环境图，同样改写为程序片段与文字说明。
---
## 1.7 递归函数
> 🎬 视频：Recursive Functions
若一个函数的函数体调用了该函数自身——无论是直接还是间接，这个函数就称为**递归函数（recursive function）**。也就是说，执行递归函数的函数体的过程，可能反过来又需要施加这个函数。递归函数在 Python 中并不使用什么特殊语法，但要理解和编写它们，确实得费些功夫。
我们从一个示例问题入手：写一个函数，求一个自然数的各位数字之和。设计递归函数时，我们要寻找把问题拆解成更简单问题的途径。在本例中，运算符 `%` 与 `//` 可以把一个数拆成两部分：最后一位，以及除最后一位以外的所有位。
```python
>>> 18117 % 10
7
>>> 18117 // 10
1811
```
18117 的各位数字之和是 1+8+1+1+7 = 18。正如我们可以拆分这个数，我们也可以把这个和拆成最后一位数字 7，以及除最后一位之外各位之和 1+8+1+1 = 11。这一拆分给出一个算法：要求 n 的各位数字之和，就把它的最后一位 n % 10，加到 n // 10 的各位数字之和上。有一个特殊情形：若一个数只有一位，那么它的各位数字之和就是它自己。这个算法可以写成一个递归函数：
```python
>>> def sum_digits(n):
"""Return the sum of the digits of positive integer n."""
if n < 10:
return n
else:
all_but_last, last = n // 10, n % 10
return sum_digits(all_but_last) + last
```
`sum_digits` 的这个定义既完整又正确，尽管 `sum_digits` 函数在自己的函数体中被调用了。求各位数字之和的问题被拆成两步：先求除最后一位之外的各位之和，再加上最后一位。这两步都比原问题更简单。之所以说这个函数是递归的，是因为第一步与原来的问题是同一类问题。也就是说，`sum_digits` 正是我们实现 `sum_digits` 所需要的那个函数。
```python
>>> sum_digits(9)
9
>>> sum_digits(18117)
18
>>> sum_digits(9437184)
36
>>> sum_digits(11408855402054064613470328848384)
126
```
借助我们的环境计算模型，我们可以精确地理解这个递归函数为何能成功施用。无需任何新规则。
```python
def sum_digits(n):
if n < 10:
return n
else:
all_but_last, last = n // 10, n % 10
return sum_digits(all_but_last) + last
sum_digits(738)
```
执行 def 语句时，名字 `sum_digits` 绑定到一个新函数上，但该函数的函数体尚未执行。因此，`sum_digits` 的循环性质此时还不成问题。接着，`sum_digits` 被施加于 738：
* 为 `sum_digits` 创建一个局部帧，`n` 绑定为 738，`sum_digits` 的函数体就在以这个帧为起点的环境中执行；
* 因为 738 不小于 10，执行第 5 行的赋值语句，把 738 拆成 73 与 8；
* 在接下来的 return 语句中，`sum_digits` 被施加于 73，即当前环境中 `all_but_last` 的值；
* 又为 `sum_digits` 创建一个局部帧，这次 `n` 绑定为 73；`sum_digits` 的函数体再次在以此帧为起点的新环境中执行；
* 因为 73 也不小于 10，73 被拆成 7 与 3，`sum_digits` 被施加于 7，即在该帧中求得的 `all_but_last` 的值；
* 为 `sum_digits` 创建第三个局部帧，`n` 绑定为 7；
* 在以此帧为起点的环境中，`n < 10` 为真，于是返回 7；
* 在第二个局部帧中，返回值 7 与 `last` 的值 3 相加，返回 10；
* 在第一个局部帧中，返回值 10 与 `last` 的值 8 相加，返回 18。
这个递归函数尽管有循环的性质，却能正确施用，因为它虽然被施用了两次，但每次的实参都不相同；而且第二次施用是「各位数字求和」问题的一个更简单的实例。请为调用 `sum_digits(18117)` 画出环境图，你会看到每一次相继的 `sum_digits` 调用所取的实参都比上一次更小，直到最终到达一个只有一位的输入。
这个例子也表明：函数体简单的函数，借助递归也能演化出复杂的计算过程。
### 递归函数的解剖
> 🎬 视频：Recursion in Environment Diagrams
在许多递归函数的函数体中，都能找到一个共同的模式。函数体以**基准情形（base case）**开头——那是一条条件语句，规定了函数在处理最简单的输入时的行为。就 `sum_digits` 而言，基准情形是任何只有一位的实参，我们直接返回该实参。有些递归函数会有多个基准情形。
基准情形之后，则是一个或多个**递归调用（recursive calls）**。递归调用总有一种特定的性格：它们**简化**了原问题。递归函数通过逐步简化问题来表达计算。例如，求 7 的各位数字之和，比求 73 的各位数字之和更简单；而后者又比求 738 的各位数字之和更简单。每一次后续调用，待办的工作都更少。
递归函数解决问题的方式，往往与我们此前用过的迭代方法不同。考虑一个计算 n 的阶乘的函数 `fact`，例如 `fact(4)` 计算 4! = 4·3·2·1 = 24。
用 while 语句的一种自然实现，是把 1 到 n 的每个正整数依次乘进来，累积出总数。
```python
>>> def fact_iter(n):
total, k = 1, 1
while k <= n:
total, k = total * k, k + 1
return total
>>> fact_iter(4)
24
```
另一方面，阶乘的递归实现，可以用 `fact(n-1)`——一个更简单的问题——来表达 `fact(n)`。递归的基准情形是问题的最简形式：`fact(1)` 就是 1。
```python
def fact(n):
if n == 1:
return 1
else:
return n * fact(n-1)
fact(4)
```
这两个阶乘函数在观念上有所不同。迭代函数从基准情形 1 出发，通过逐项相乘构造出最终结果；而递归函数则直接从最后一项 n，以及更简单问题的结果 `fact(n-1)` 出发，构造出结果。
随着递归通过一次次施加 `fact` 于越来越简单的问题实例而「展开」（unwind），结果最终自基准情形起被构造出来。递归在把实参 1 传给 `fact` 时结束；每次调用的结果都依赖下一次调用，直至抵达基准情形。
这个递归函数的正确性，从阶乘的数学定义即可轻易验证：
```text
(n-1)! = (n-1)·(n-2)·…·1
n! = n·(n-1)·(n-2)·…·1
n! = n·(n-1)!
```
我们固然可以用计算模型把递归「摊开」来看，但把递归调用视为函数抽象，往往更为清晰。也就是说，我们不该操心 `fact(n-1)` 在 `fact` 的函数体中是如何实现的；我们只管相信它算出了 n-1 的阶乘。把递归调用当作函数抽象，这种做法被称为**递归的信仰之跃（recursive leap of faith）**。我们用一个函数自身来定义它，但在验证其正确性时，只管相信更简单的情形会正确工作。在这个例子里，我们相信 `fact(n-1)` 会正确算出 (n-1)!；我们只需检查：在此假设之下，n! 是否被正确算出。如此一来，验证递归函数的正确性，便成了**数学归纳法**的一种形式。
`fact_iter` 与 `fact` 还有一处不同：前者必须引入两个额外的名字 `total` 与 `k`，而递归实现并不需要。总的来说，迭代函数必须维护某种局部状态，这种状态在计算过程中不断变化。在迭代的任何一个时刻，这种状态刻画着「已完成工作」的结果与「剩余工作量」。例如，当 `k` 为 3、`total` 为 2 时，还有两项待处理，即 3 与 4。相比之下，`fact` 只由它唯一的实参 n 来刻画。计算的状态完全蕴含在环境的结构之中：环境的返回值扮演着 `total` 的角色，并在不同的帧中把 `n` 绑定到不同的值，而非显式地追踪 `k`。
递归函数利用了「求值调用表达式以把名字绑定到值」的规则，往往省去了迭代过程中正确指派局部名字的麻烦。正因如此，递归函数可能更容易被正确地定义出来。然而，要学会辨识递归函数所演化出的计算过程，那必然需要一番练习。
### 相互递归
> 🎬 视频：Mutual Recursion
当一个递归过程被分置于两个互相调用的函数之中时，这两个函数就称为**相互递归（mutually recursive）**的。举个例子，考察下面关于非负整数「偶」与「奇」的定义：
* 一个数是偶数，当且仅当它比某个奇数多 1；
* 一个数是奇数，当且仅当它比某个偶数多 1；
* 0 是偶数。
依据这一定义，我们可以实现两个相互递归的函数，来判断一个数是偶数还是奇数：
```python
def is_even(n):
if n == 0:
return True
else:
return is_odd(n-1)
def is_odd(n):
if n == 0:
return False
else:
return is_even(n-1)
result = is_even(4)
```
打破两个函数之间的抽象边界，相互递归的函数便可化归为单个递归函数。在这个例子里，可以把 `is_odd` 的函数体并入 `is_even` 的函数体——只需把 `is_odd` 函数体中的 `n` 换成 `n-1`，以反映传给它的实参：
```python
>>> def is_even(n):
if n == 0:
return True
else:
if (n-1) == 0:
return False
else:
return is_even((n-1)-1)
```
由此可见，相互递归并不比简单的递归更神秘、更强大；不过，它为在复杂的递归程序中维持抽象提供了一种机制。
### 递归函数中的打印
> 🎬 视频：Order of Recursive Calls
递归函数所演化出的计算过程，常常可以通过调用 `print` 来可视化。举个例子，我们来实现一个函数 `cascade`：它把一个数的所有前缀，按从大到小再到大（先降后升）的顺序打印出来。
```python
>>> def cascade(n):
"""Print a cascade of prefixes of n."""
if n < 10:
print(n)
else:
print(n)
cascade(n//10)
print(n)
>>> cascade(2013)
2013
201
20
2
20
201
2013
```
在这个递归函数中，基准情形是个一位数，直接打印。否则，递归调用就夹在两处 `print` 调用之间。
> 🎬 视频：Example: Inverse Cascade
把基准情形写在递归调用之前，并非硬性要求。事实上，观察到 `print(n)` 在条件语句的两个子句中重复出现，因而可以提到条件语句之前，这个函数就能表达得更紧凑：
```python
>>> def cascade(n):
"""Print a cascade of prefixes of n."""
print(n)
if n >= 10:
cascade(n//10)
print(n)
```
再看一个相互递归的例子。考虑一个双人游戏：桌上初始有 n 颗石子。双方轮流从桌上取走一颗或两颗石子，取走最后一颗石子者获胜。假设 Alice 与 Bob 玩这个游戏，各自采用一套简单的策略：
* Alice 总是取走一颗石子；
* Bob 若见桌上石子数为偶数便取走两颗，否则取走一颗。
给定初始石子数 n，且 Alice 先手，谁获胜？
这个问题的一种自然分解，是把每套策略封装进各自的函数。这样一来，改动其中一套策略便不会影响另一套，两人之间的抽象屏障得以维持。为了体现游戏一回合接一回合的性质，这两个函数在每回合结束时互相调用：
```python
>>> def play_alice(n):
if n == 0:
print("Bob wins!")
else:
play_bob(n-1)
>>> def play_bob(n):
if n == 0:
print("Alice wins!")
elif is_even(n):
play_alice(n-2)
else:
play_alice(n-1)
>>> play_alice(20)
Bob wins!
```
在 `play_bob` 中我们看到，一个函数的函数体里可以出现多处递归调用。不过在这个例子里，每次调用 `play_bob` 最多只调用一次 `play_alice`。下一节我们要考察的，是当一次函数调用直接发起多处递归调用时，会发生什么。
### 树递归
> 🎬 视频：Tree Recursion
另一种常见的计算模式称为**树递归（tree recursion）**：函数不止一次地调用自身。举个例子，考察斐波那契数列的计算，其中每个数都是前两个数之和。
```python
def fib(n):
if n == 0:
return 0
if n == 1:
return 1
else:
return fib(n-2) + fib(n-1)
result = fib(6)
```
与我们此前的种种尝试相比，这个递归定义格外动人：它与我们熟悉的斐波那契数定义分毫不差。带有多个递归调用的函数，据说就是树递归的——因为每一次调用都会分岔出多个更小的调用，每一个又分岔出更小的调用，正如树木的枝条自树干延伸出去，越分越细，也越来越多。
我们早先就已经能够不用树递归来定义计算斐波那契数的函数了。事实上，我们此前的尝试效率更高——这个话题将在 2.9 节讨论。接下来，我们考察一个问题：树递归的解法要比任何迭代方案都简单得多。
### 示例：整数划分
> 🎬 视频：Tree Recursion (Part 2)
正整数 n 使用不超过 m 的部分的**划分数（number of partitions）**，是指把 n 表示成若干个不大于 m 的正整数之和（按递增顺序排列）的方法数。例如，用不超过 4 的部分来划分 6，共有 9 种方法：
* 6 = 2 + 4
* 6 = 1 + 1 + 4
* 6 = 3 + 3
* 6 = 1 + 2 + 3
* 6 = 1 + 1 + 1 + 3
* 6 = 2 + 2 + 2
* 6 = 1 + 1 + 2 + 2
* 6 = 1 + 1 + 1 + 1 + 2
* 6 = 1 + 1 + 1 + 1 + 1 + 1
我们来定义一个函数 `count_partitions(n, m)`，返回用不超过 m 的部分划分 n 的不同方法数。这个函数有一个简单的树递归解法，依据如下观察：
用不超过 m 的整数划分 n 的方法数，等于
* 用不超过 m 的整数划分 n−m 的方法数，加上
* 用不超过 m−1 的整数划分 n 的方法数。
要弄清这条为何成立，请注意：所有划分 n 的方法可以分为两组——包含了至少一个 m 的，以及不包含 m 的。而且，第一组中的每一种划分，都是先划分 n−m，再在末尾加一个 m。在上面的例子里，前两种划分含有 4，其余的不含。
因此，我们可以把「用不超过 m 的整数划分 n」这一难题，递归地化归为两个更简单的问题：(1) 划分一个更小的数 n−m；(2) 用更小的部分（不超过 m−1）来划分。
为了完成实现，还需规定如下基准情形：
* 划分 0 有 1 种方法：不取任何部分；
* 划分负数有 0 种方法；
* 用大小为 0 或更小的部分来划分任何大于 0 的 n，有 0 种方法。
```python
>>> def count_partitions(n, m):
"""Count the ways to partition n using parts up to m."""
if n == 0:
return 1
elif n < 0:
return 0
elif m == 0:
return 0
else:
return count_partitions(n-m, m) + count_partitions(n, m-1)
>>> count_partitions(6, 4)
9
>>> count_partitions(5, 5)
7
>>> count_partitions(10, 10)
42
>>> count_partitions(15, 15)
176
>>> count_partitions(20, 20)
627
```
我们可以把树递归函数看作在探索各种可能性。在本例中，我们探索「用一个大小为 m 的部分」与「不用」这两种可能。第一次与第二次递归调用，正对应着这两种可能。
不用递归来实现这个函数，会麻烦得多。有兴趣的读者不妨一试。
---
## 函数参考
第 1 章讨论了表达式、名字、赋值、控制与函数。本节收录本章最重要的定义，以及一份内置函数清单，还有一些示例中出现的数学背景材料。
### 表达式
**表达式（expression）**是可以被求值、因而具有值的代码。
学习 Python，就包括学习它各种形式的表达式以及求值方式。重要的表达式类型包括：
* **数字**：求值为自身——`3.14` 求值为数字 3.14；
* **名字**：求值为其在当前环境中的值；
* **调用表达式**：把某个函数作用于若干实参。
#### 名字
程序可以有各种行为（例如显示消息、发送电子邮件等等），但它们大多是为操作**值**而存在的。**值（value）**是对某份数据的统称，它可以是单个数字，也可以是整份文档。本课程开始时只关注少数几种值：数字、布尔值（`True` 与 `False`）、`None` 值、字符串以及函数。
代码中包含**名字（names）**，它们指称值。一切表达式都在某种**环境**中求值——环境是 Python 解释器中追踪「哪个名字指称哪个值」的那一部分。当一个名字与一个值在环境中绑定在一起时，该名字在该环境中就求值为那个值。
说「名字绑定到一个值」，与说「一个值被赋给了一个名字」，意思相同。
#### 调用表达式
下面是两个调用表达式及其值的例子：
```python
pow(2, 10)
pow(1 + 1, min(3, abs(-4)))
```
调用表达式在圆括号之前有一个表达式，本课程称之为**运算符表达式**。[1] 运算符几乎总是名字，它求值为被调用的函数。
调用表达式的圆括号内还有一些以逗号分隔的表达式，本课程称之为**操作数表达式**，它们求值为函数的实参。
Python 求值调用表达式的过程是：先求值运算符，再求值各操作数，然后把函数（即运算符的值）施加于其各实参（即各操作数的值）。把函数施加于若干实参，会返回一个值；调用表达式的值，就是被调用函数所返回的那个值。
例如，在 `pow(1 + 1, min(3, abs(-4)))` 中：
* 运算符是名字 `pow`，其值是内置的 `pow` 函数；
* 操作数是 `1 + 1` 与 `min(3, abs(-4))`，它们的值分别是 2 与 3；
* 把 `pow` 函数施加于 2 与 3，返回 8——这就是整个表达式的值。
#### 内置函数
Python 运行所有程序时都从全局环境起步。起初，许多名字都绑定着内置函数。例如，名字 `max` 起初绑定着内置的 `max` 函数。本课程第一单元用到的内置函数有：
* `pow` 总是接受两个数字。`pow(x, y)` 返回 x 的 y 次幂。`pow(2, 3)` 返回 8。
* `abs` 接受单个数字，返回其绝对值。`abs(-5)` 返回 5。
* `bool` 接受单个实参，若该实参为真值（有时称作 truthy 值）则返回 `True`，否则返回 `False`。一些假值：`0`、`False`、`''`、`None`。其他所有数字与字符串都是真值，所有函数亦然。
* `str` 为任意值返回一个字符串。`str(123)` 返回 `'123'`。
* `round` 接受一个数字，并可选地接受要保留的小数位数，返回四舍五入后的数。`round(3.14159, 2)` 返回 3.14，`round(3.5)` 返回 4。
* `max` 接受两个或更多实参，返回其中最大的一个。`max(1, 5, 3)` 返回 5。
* `min` 接受两个或更多实参，返回其中最小的一个。`min(1, 5, 3)` 返回 1。
* `len` 接受一个有长度的实参（如字符串），返回该字符串的长度。它不能施加于数字。
第 2 章我们还会学到调用 `max` 与 `min` 的其他方式，也会学到许多别的内置函数，比如 `sum`。一个常见的陷阱：在 Python 中，`sum(2, 3)` **并不**返回 5。请改用 `add(2, 3)` 或 `2 + 3`。
有些函数需要导入。第一单元用到的有：
* `add` 总是接受两个实参，二者可以都是数字，或都是字符串。`add(2, 3)` 返回 5，`add('two', 'three')` 返回 `twothree`。对任意两个表达式 x 与 y，`add(x, y)` 的值与行为都与 `x + y` 相同。
* `sub(x, y)` 等同于 `x - y`。
* `mul(x, y)` 等同于 `x * y`。
* `floordiv(x, y)` 等同于 `x // y`。
* `truediv(x, y)` 等同于 `x / y`。
### 数字
本课程的许多例子涉及与数字相关的概念，比如倍数与因数。
作业与试卷上出现的定义，力求简短、一般、精确，而不追求直观与口语化。例如，定义「倍数」一词时，你不会看到：「10 的倍数是 20、30、40、50，等等。它们就是把同一个数反复相加所得的结果。」这个定义有问题：一来「等等」并不精确，二来它留下了许多悬而未决的问题，比如 0、10、−20 是不是 10 的倍数。你看到的会是：「若存在整数 b 使得 n 等于 m * b，则称 n 是整数 m 的倍数。」这个定义更短，并且说明了 0、10、−20 和 20、30、40、50 一样，都是 10 的倍数。
以下是一些与数字有关的有用概念：
若只要 y > x 就有 f(y) > f(x)，则称函数 f 是**递增的（increasing）**。递增函数 f 的一些性质包括：
* 对任意 x 与任意正数 a，f(x + a) > f(x)；
* f(max(x, y)) = max(f(x), f(y))。
一个密切相关的概念是**非递减（non-decreasing）**：若只要 y > x 就有 f(y) ≥ f(x)，则称函数 f 是非递减的。非递减函数 f 的性质与之相仿：
* 对任意 x 与任意正数 a，f(x + a) ≥ f(x)；
* f(max(x, y)) = max(f(x), f(y))。
若 n/k 是整数，则称正整数 k 是正整数 n 的**因数（factor）**。当 n/k 为整数时，我们说 k **整除（evenly divides）**n。一些性质：
* k 是 n 的因数，当且仅当 n 是 k 的倍数；
* 对任意 n，至少有 1 与 n 两个因数。若只有这两个因数，则 n 是**素数（prime）**。
用整数 k 除整数 n 所得的**余数（remainder）**，是满足「存在整数 d 使 k*d + r 等于 n」的最小的 r。把 n 除以……
* 10，所得余数是 n 的最后一位；
* 100，所得余数是 n 的最后两位；
* pow(10, p)（p 为正整数），所得余数是 n 的最后 p 位。
---
**注释**
1. 运算符表达式在不同的文档中有不同的叫法。例如，Python 文档中称之为 primary。↩
---
# 第 2 章 数据
## 2.1 引言
第 1 章我们专注于计算过程，以及函数在程序设计中的角色。我们看到了如何使用基本数据（数字）与基本操作（算术），如何通过复合与控制来构成复合函数，以及如何通过为过程命名来创造函数抽象。我们还看到，高阶函数让我们能以一般的计算方法来操作、进而推理，从而增强了语言的表达力。这已触及编程的许多精髓。
本章聚焦于**数据**。这里研究的各项技术，将让我们能够表示并操作来自众多不同领域的信息。由于互联网的爆炸式增长，海量结构化信息在网上免费向所有人敞开，计算得以施用于极其广泛的各种问题。有效使用内置数据类型与用户自定义数据类型，是数据处理应用的根本。
### 原生数据类型
Python 中的每个值都有一个**类（class）**，决定着它是什么类型的值。同属一类的值，行为也相同。例如，整数 1 与 2 都是 `int` 类的实例，这两个值可以被同样对待——比如都能取负，或与另一个整数相加。内置的 `type` 函数让我们得以查看任意值的类。
```python
>>> type(2)
```
我们至今用到的值，都是 Python 语言内置的少数几种**原生数据类型（native data types）**的实例。原生数据类型具有如下性质：
* 有若干表达式求值为原生类型的值，这些表达式称为**字面量（literals）**；
* 有内置的函数与运算符来操作原生类型的值。
`int` 类是用来表示整数的原生数据类型。整数字面量（相邻数字符号组成的序列）求值为 `int` 值，而数学运算符则操作这些值。
```python
>>> 12 + 3000000000000000000000000
3000000000000000000000012
```
Python 包含三种原生数值类型：整数（`int`）、实数（`float`）与复数（`complex`）。
```python
>>> type(1.5)
>>> type(1+1j)
```
#### 浮点数
`float` 这个名字，源自实数在 Python 及许多其他编程语言中的表示方式：**浮点（floating point）**表示法。数字在计算机内部究竟如何表示，并不是本书的话题；但 `int` 与 `float` 对象之间的一些高层差别，却值得了解。尤其是：`int` 对象精确地表示整数，没有任何近似，大小也不设上限。相形之下，`float` 对象能表示范围广泛的小数，但并非所有数都能被精确表示，而且有最小值和最大值。因此，`float` 值应当被当作实数的**近似值**来对待。这些近似只具有有限的精度。把 `float` 值组合起来，会带来近似误差；若不是因为近似，下面两个表达式的结果都该是 7：
```python
>>> 7 / 3 * 3
7.0
>>> 1 / 3 * 7 * 3
6.999999999999999
```
上面虽然组合的都是 `int` 值，但一个 `int` 除以另一个 `int`，得到的却是 `float` 值：一个对两整数之商所作的截断式有限近似。
```python
>>> type(1/3)
>>> 1/3
0.3333333333333333
```
当我们做相等性检验时，这种近似带来的问题便会浮现：
```python
>>> 1/3 == 0.3333333333333333 # 当心浮点近似
True
```
`int` 类与 `float` 类之间这些微妙的差别，对写程序有着广泛的影响，因此是程序员必须背下来的细节。所幸，原生数据类型屈指可数，要精通一门编程语言，需要记的东西也就有限。而且，同样的细节在许多编程语言之间都是一致的——由 IEEE 754 浮点标准之类的共同体规范所保障。
#### 非数值类型
值可以表示许多其他类型的数据，如声音、图像、位置、网址、网络连接等等。其中一些由原生数据类型表示，比如表示 `True` 与 `False` 的 `bool` 类，以及表示 `'Hello, World!'` 这类文本值的 `str` 类。而许多其他值的类型，必须由程序员用本章将要展开的组合手段与抽象手段来定义。
本章将介绍 Python 的许多原生数据类型，以及我们即将创造的新类型。想了解更多的读者，可以参阅在线书籍 *Dive Into Python 3* 中讲述原生数据类型的章节——它对 Python 全部原生数据类型及其操作做了实用的概览，包含大量用法示例与实践窍门。
### 与类型打交道
各编程语言对待数据类型的方式不尽相同。Python 围绕类型来组织，却不要求在代码中显式地写出类型。相同类型的值，在许多场合可以被同一个函数互换使用（比如 `int` 值与 `float` 值）。不过，有时检查、标注或依据值的类型作条件判断，是有用的。
#### 类型检查
内置函数 `isinstance` 接受一个值与一个类，若该值是该类的实例便返回真。例如，`show` 会把 `float` 值四舍五入后再打印，而其他值照原样打印。
```python
>>> def show(n):
if isinstance(n, float):
print(round(n, 2))
else:
print(n)
>>> show(100 / 3)
33.33
>>> show(100 > 5)
True
```
#### 类型强制转换
把一种类型的值转换为另一种类型中相等价的值，这一过程称为**类型强制转换（type coercion）**。一种原生类型的值，在某些情况下可以转换为另一种。所有值都能转换为 `str`；仅含数字的字符串可以转换为 `int`（若没有小数部分）或 `float`。把一个类型施加于一个值，即执行转换。
```python
>>> str(12)
'12'
>>> float('34.56')
34.56
>>> int(78.0)
78
>>> int('9')
9
```
#### 类型提示
大多数函数是为施加于特定类型的值而设计的。函数可以为它的形式参数（即其各实参的名字）以及返回值（跟在 `->` 符号之后）标注预期类型。这些标注在 Python 中称为**类型提示（type hints）**。在下面的例子里，形式参数 `x` 与返回值都标注为 `int` 值。
```python
>>> def square(x: int) -> int:
return x * x
>>> square(5)
25
```
类型提示并不是对函数能接受和返回什么的限制，而是对该函数预期用途的**文档**。尽管有类型提示，这个 `square` 函数照样可以接受并返回 `float` 值，而且能顺利返回。
```python
>>> square(1.4142)
1.9999616399999998
```
`square` 函数也可以施加于 `str` 实参，例如 `square('three')`——这会引发 `TypeError`，但原因并不在类型提示。`square` 的调用本身是被允许的，错误发生在 Python 解释器试图求值 `x * x`、而 `x` 绑定着一个 `str` 值之时。
**联合类型（Union types）。** 一个既能接受 `str` 又能接受 `float` 的函数，可以标注联合类型 `str | float`。下面这个 `double` 函数把一个数翻倍，遇到 `str` 实参时先转成 `float`、再转回来。
```python
>>> def double(x: str | float) -> str | float:
if isinstance(x, str):
return str(2 * float(x))
else:
return 2 * x
>>> double('3')
'6.0'
>>> double(3.5)
7.0
```
**类型别名（Type aliases）。** 为类型起个名字的办法之一，是使用 type 语句。用户自定义的类型名按惯例首字母大写。新类型名一经引入，便可用于类型提示。
```python
type Quantity = str | float
def double(x: Quantity) -> Quantity:
if isinstance(x, str):
return str(2 * float(x))
else:
return 2 * x
```
**类型变量（Type variables）。** 类型变量用来描述「接受并返回相关类型」的函数。通常用一个名字（往往取作 `T`）来表示：同样的类型出现在两个或更多形式参数或返回值之中。例如，恒等函数接受任意类型的实参并把它返回。
```python
def identity[T](x: T) -> T:
return x
```
此外，类型变量还可以被约束为一组其他类型之一。下面针对 `square` 函数的这条提示表明：它既能接受 `int` 值也能接受 `float` 值，而返回值与其实参同属一种类型。
```python
def square[T: (int, float)](x: T) -> T:
return x * x
```
类型变量与类型别名的这套语法，是最近才引入的——2023 年发布的 Python 3.12。若你尝试这些例子时见到 `SyntaxError`，请升级到较新的 Python 版本。
**类型检查器（Type checkers）。** 类型提示可以被**类型检查**——这一过程不执行 Python 文件，而是审查其中的代码，判断标注了类型的名字是否会被绑定到相容的值上；同样，它也检查函数的所有返回值是否与其标注的返回类型相容。安装了 Microsoft Python 扩展的 Visual Studio Code 编辑器，能在你编辑 Python 源文件时检测出类型不相容，但这一类型检查默认关闭。要开启它，请在 Mac 上从 Code 菜单选择 Settings，或在 Windows 上从 File 菜单选择 Preferences，然后把名为 `Python › Analysis: Type Checking Mode` 的设置从 off 改为 standard；搜索「type checking mode」即可找到该设置。此后，类型不相容之处便会被红线标为错误。Python 的类型检查并不仅限于 VS Code，许多编辑器都可以配置。
类型提示是可选的，有时反而会让程序更难读。即便不加类型提示，类型检查器往往也能推断出形式参数与返回值的类型。在大型 Python 程序中，类型提示正变得越来越普遍，但请记住：为函数标注类型，并不会改变它的行为。
---
## 2.2 序列
**序列（sequence）**是值的有序集合。序列在 Python 中并不是某个特定内置类型的实例，而是一种**抽象**：一组行为的集合。
**长度（Length）。** 序列具有有限的长度；空序列的长度为 0。
**取项（Item selection）。** 对于任何小于其长度的非负整数**下标（index）**，序列都有一个与之对应的项；第一项的下标从 0 开始。
序列虽是项的集合（项本身也是值），但每个序列自身同样是一个值。也就是说，序列可以被赋予名字、作为实参传递，或从函数返回。
这些行为为若干不同的数据类型所共享，其中最重要的便是**列表（list）**。
### 列表
把若干表达式放进方括号、以逗号分隔，即可构造一个列表。这样的表达式称为**列表字面量（list literal）**。
```python
>>> [10, 20]
[10, 20]
```
访问列表中的项有两种方式。第一种是我们熟悉的多重赋值——它把列表拆解为各项，并将每一项绑定到不同的名字。
```python
>>> pair = [10, 20]
>>> pair
[10, 20]
>>> x, y = pair
>>> x
10
>>> y
20
```
第二种访问列表各项的方式，是**取项运算符（item selection operator）**，同样用方括号表示。与列表字面量不同，紧跟在另一个表达式之后的方括号表达式，求值的不是列表值，而是从前面那个表达式的值中选出一项。
```python
>>> pair[0]
10
>>> pair[1]
20
```
Python 中的列表（以及大多数其他编程语言中的序列）采用 **0 起下标（0-indexed）**：下标 0 选出第一项，下标 1 选出第二项，依此类推。支持这一下标约定的一个直觉是：下标表示该项距离列表开头有多远。
与取项运算符等价的函数称为 `getitem`，它同样用 0 起的下标从列表中选出一项。
```python
>>> from operator import getitem
>>> getitem(pair, 0)
10
>>> getitem(pair, 1)
20
```
列表可以有任意有限的长度，现代计算机能处理包含数百万项的列表。
内置函数 `len` 返回序列的长度。下面 `digits` 是一个含四项的列表，下标 3 处的项是 8。
```python
>>> digits = [1, 8, 2, 8]
>>> len(digits)
4
>>> digits[len(digits) - 1]
8
```
列表可以相加，也可以乘以整数。对序列来说，加法与乘法并非把各项相加或相乘，而是把序列本身拼接、复写。也就是说，`+` 运算符（以及 `operator` 模块中的 `add` 函数）返回一个列表，它是各相加列表实参的连接；`*` 运算符（以及 `operator` 中的 `mul` 函数）接受一个列表与一个整数 k，返回由原列表重复 k 次构成的列表。
```python
>>> [2, 7] + digits * 2
[2, 7, 1, 8, 2, 8, 1, 8, 2, 8]
```
任何值都可以放进列表，包括另一个列表。取项可以反复施加，从而在「列表套列表」的结构中选出深层嵌套的项。
```python
>>> pairs = [[10, 20], [30, 40]]
>>> pairs[1]
[30, 40]
>>> pairs[1][0]
30
```
允许列表包含其他列表，使我们得以构造**层次结构（hierarchical structures）**——由部件构成的结构，而部件自身又由部件构成，如此层层递进。
```python
>>> dog = [['head', ['face', ['nose', 'eyes']], ['ears']],
['body', ['legs', ['paws']]],
'tail']
>>> dog[0]
['head', ['face', ['nose', 'eyes']], ['ears']]
```
在环境图中，我们可以用**盒指针记法（box-and-pointer notation）**来直观表示列表。列表被画成一排相邻的方格，里面盛着列表的各项。数字、字符串、布尔值与 `None` 这类基本值就写在方格内；而函数值、其他列表这类复合值，则用箭头表示。
```python
one_two = [1, 2]
nested = [[1, 2], [],
[[3, False, None],
[4, lambda: 5]]]
```
### 序列迭代
许多时候，我们想要遍历序列的各项，依次对每一项做某种计算。这一模式如此常见，以至于 Python 专为处理序列数据增设了一条控制语句：**for 语句**。
考虑这样一个问题：数一数某个值在序列中出现了多少次。我们可以用 while 循环实现一个函数来计算这个计数：
```python
>>> def count(s, value):
"""Count the number of occurrences of value in sequence s."""
total, index = 0, 0
while index < len(s):
if s[index] == value:
total = total + 1
index = index + 1
return total
>>> count(digits, 8)
2
```
Python 的 for 语句能简化这个函数体：直接遍历各项的值，全然不必引入名字 `index`。
```python
>>> def count(s, value):
"""Count the number of occurrences of value in sequence s."""
total = 0
for item in s:
if item == value:
total = total + 1
return total
>>> count(digits, 8)
2
```
for 语句由单个子句构成，形如：
```text
for in :
```
for 语句按如下流程执行：
* 求值头部 ``，它必须得出一个**可迭代值（iterable value）**；
* 对那个可迭代值中的每个项值，依次：A. 在当前帧中把 `` 绑定到该项值；B. 执行 ``。
这套执行流程提到了可迭代值。列表是一种序列，而序列都是可迭代值——它们的各项按顺序被逐一考察。Python 还包含其他可迭代类型，但眼下我们只关注序列；「可迭代」一词的一般定义，见 2.8 节。
这条求值流程的一个重要推论是：for 语句执行完毕后，`` 会绑定到序列的最后一个项（除非序列为空）。for 循环为「语句可以更新环境」提供了又一种方式。
#### 序列解包
程序中有一种常见的模式：一个序列的各项本身也是序列，而且长度固定。for 语句的头部可以包含多个名字，从而把每个项序列「解包」到各自的各项中。例如，我们可能有一个由二元列表组成的列表
```python
>>> pairs = [[1, 2], [2, 2], [2, 3], [4, 4]]
```
并且想找出其中首项与次项相同的数对有多少个。
```python
>>> same_count = 0
```
下面这条头部带两个名字的 for 语句，会把 `x` 与 `y` 分别绑定到每一对中的第一项与第二项。
```python
>>> for x, y in pairs:
if x == y:
same_count = same_count + 1
>>> same_count
2
```
这种把多个名字绑定到定长序列中多个值的模式，称为**序列解包（sequence unpacking）**；这与我们在赋值语句中把多个名字绑定到多个值所见的是同一种模式。
#### range
Range 是 Python 中另一种内置的序列类型，表示一段整数区间。Range 用 `range` 创建，它接受两个整数实参：期望区间的第一个数，以及最后一个数**再往后一个**。
```python
>>> range(1, 10) # 包含 1，但不包含 10
range(1, 10)
```
对 range 施加 `list` 构造器，会求值为一个各项与 range 相同的列表，便于查看各项。
```python
>>> list(range(5, 8))
[5, 6, 7]
```
若只给一个实参，它被理解为「从 0 开始、到该值再往后一个为止」的区间终点。
```python
>>> list(range(4))
[0, 1, 2, 3]
```
Range 常出现在 for 头部，用来指定子句组应执行的次数。一个常见的惯例是：若名字在子句组中并不使用，就用单个下划线字符作 for 头部的名字。
```python
>>> for _ in range(3):
print('Go Bears!')
Go Bears!
Go Bears!
Go Bears!
```
在解释器看来，这个下划线不过是环境中的又一个名字；但在程序员之间，它是一种约定俗成的记号，表示这个名字不会出现在今后的任何表达式中。
### 序列处理
序列是如此常见的一种复合数据形式，以至于整个程序常常围绕这单一的抽象来组织。以序列为输入、又以序列为输出的模块化组件，可以自由搭配，完成数据处理。把一串简单的序列处理操作——每一项都单纯而专注——连成流水线，便能定义出复杂的组件。
#### 列表推导式
许多序列处理操作，都可以这样表达：对序列中的每一项求值某个固定的表达式，再把所得的各值收集成一个结果序列。在 Python 中，**列表推导式（list comprehension）**正是执行这类计算的表达式。
```python
>>> odds = [1, 3, 5, 7, 9]
>>> [x+1 for x in odds]
[2, 4, 6, 8, 10]
```
上面这个 `for` 关键字并不是 for 语句的一部分，而是列表推导式的一部分，因为它处于方括号之内。子表达式 `x+1` 依次在 `x` 绑定到 `odds` 的每一项时求值，所得各值被收集成一个列表。
另一种常见的序列处理操作，是选出满足某个条件的值的子集。列表推导式也能表达这个模式，例如选出 `odds` 中能整除 25 的所有项。
```python
>>> [x for x in odds if 25 % x == 0]
[1, 5]
```
列表推导式的一般形式是：
```text
[