CS61A Summary

Summary

没有太多充足的时间看Textbook，先暂时用GPT进行一些总结。

第一章：用函数构建抽象

1.1 入门

计算机科学是一个广泛的学科领域，涉及分布式系统、人工智能、机器人技术、图形学、安全性、科学计算等多个领域。计算机科学的迅速进步对人类生活的许多方面都产生了深远的影响，如商业、通信、科学、艺术、娱乐和政治。

计算机科学的高效生产力得益于一组优雅且强大的基本思想。所有计算都始于信息表示、处理逻辑的定义，以及用于管理这些逻辑复杂性的抽象设计。掌握这些基础知识要求我们精确理解计算机如何解释程序并执行计算过程。

1.1.1 使用 Python 编程

编程语言不仅是学习工具，更是让人融入开发者社区的桥梁。Python 是一种广泛使用的编程语言，拥有庞大的用户群。它的代码强调可读性、美观性和简洁性，因此非常适合作为教学语言。本书将通过 Python 来引入抽象和计算模型。

1.1.2 安装 Python 3

建议安装 Python 3 的最新稳定版本。本书不会使用 Python 2.7，因此确保下载 Python 3。

1.1.3 交互式会话

通过 Python 交互式会话，用户可以在提示符 >>> 后输入 Python 代码，并立即得到结果。这是一种与 Python 解释器互动的方式，可以帮助用户迅速了解代码的执行结果。

1.1.4 第一个示例

Python 具备广泛的功能支持，比如处理文本、显示图形以及网络通信。通过一个简单的例子展示了 Python 的多种功能，如使用 urlopen 函数从互联网获取数据，处理莎士比亚全集，并找出反转后依然是单词的六个字母的词。

1.1.5 错误处理

计算机强大但“愚蠢”，它们严格执行指令，但也容易因为细小错误而产生意外结果。程序员需要通过调试（debugging）来解决这些问题。调试的几个原则包括：增量测试、隔离错误、检查假设、以及寻求他人帮助。

本书将通过这些调试技巧帮助读者克服编程中的挑战，并培养在整个计算机科学生涯中的调试能力。

---

1.2 编程的元素

编程语言不仅是指令计算机执行任务的工具，还用于表达和交流关于计算过程的想法。编程不仅为了机器执行，也为了让人理解，因此编写的程序需要清晰易读。每种强大的编程语言都提供了三种机制来构建复杂的计算：

1. 原始表达式和语句：最基本的构建模块。
2. 组合方法：通过简单元素组合成更复杂的元素。
3. 抽象方法：将复合元素命名并作为一个单元进行操作。

编程中的两大核心要素是函数和数据。数据是我们想要操作的内容，而函数是操作数据的规则。强大的编程语言应该能够描述原始数据、原始函数，并提供组合和抽象的方法。

1.2.1 表达式

表达式是程序的基本构件。最简单的表达式是数字，比如 42。通过数学运算符（如 +、-、*、/），可以将简单表达式组合成复杂表达式。

1.2.2 调用表达式

调用表达式是最重要的复合表达式，用于调用函数并传入参数。比如 max(7.5, 9.5) 调用了 max 函数，传入了两个参数。函数调用的优点包括能够接收任意数量的参数、支持嵌套表达式，以及统一表示不同的操作符（如 pow、add）。

1.2.3 导入库函数

Python 提供了大量的内置函数和模块，但并非所有函数都默认可用。通过 import 语句可以引入模块中的函数。例如，math 模块提供数学函数，operator 模块提供对应运算符的函数。

1.2.4 名称与环境

Python 中的名称通过赋值语句绑定到值。比如，radius = 10 将名称 radius 绑定到值 10。赋值是最简单的抽象形式，允许通过名称引用复杂计算的结果。环境是解释器跟踪名称和值的绑定关系的内存。

1.2.5 嵌套表达式的求值

Python 对调用表达式的求值过程是递归的。Python 先求值操作符和操作数，再应用函数。该过程可以用表达式树表示，树的叶子节点表示原始表达式（如数字或函数），内部节点表示调用表达式及其结果。

1.2.6 非纯粹的 print 函数

Python 中有两类函数：纯函数和非纯函数。纯函数只返回值，不会产生副作用；而非纯函数（如 print）则会产生副作用，如输出结果。纯函数的优势包括更易于组合、测试和并发执行。

---

在 Python 中，函数定义是一个非常重要的抽象技术，它使我们可以把一组操作封装在一个函数中，然后通过函数名来引用和使用这些操作。以下是 Python 中定义和使用函数的核心概念和步骤：

1.3 定义新的功能

1.3.1 定义一个新函数

定义一个函数的语法格式如下：

def 函数名(参数):
    return 返回值

示例：定义一个平方函数

def square(x):
    return x * x

在这个示例中，square 是函数名，x 是参数，return x * x 是函数的返回值，它会返回参数 x 的平方。

1.3.2 函数调用

定义函数后，我们可以通过函数名来调用它，并传递适当的参数。例如：

>>> square(4)
16

这个调用返回 16，因为 4 * 4 等于 16。

1.3.3 函数的参数

函数可以接收一个或多个参数。比如，我们可以定义一个函数来计算两个数的平方和：

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

在这个函数中，x 和 y 是两个参数，返回的结果是 x 的平方加上 y 的平方。

>>> sum_squares(3, 4)
25

这个调用返回 25，因为 3 * 3 + 4 * 4 = 9 + 16 = 25。

1.3.4 局部变量与全局变量

在函数内部定义的参数和变量只在该函数的作用域内有效，我们称之为局部变量。外部的全局变量和函数内的局部变量是相互独立的，即使它们的名字相同也不会混淆。例如：

x = 10  # 全局变量

def foo(x):
    return x + 5  # 这里的 x 是局部变量，与全局变量 x 无关

>>> foo(3)
8

调用 foo(3) 返回 8，因为函数内的 x 是局部变量，取值为 3，而不是全局的 x = 10。

1.3.5 函数的作用域与环境

在 Python 中，每当调用函数时，都会创建一个新的局部作用域，即一个独立的环境，用来存储函数参数和函数内定义的变量。Python 解释器通过这种方式确保变量不会相互混淆。

例如，调用 sum_squares(5, 12) 时，Python 会创建一个局部环境，其中 x = 5 和 y = 12，然后依次计算它们的平方并返回结果。

1.3.6 抽象的作用

函数是非常有用的抽象工具，因为它们可以隐藏复杂的实现细节。你可以使用函数，而不需要知道它内部是如何实现的。对于使用者来说，函数更像是一个“黑箱”，他们只需要知道如何调用函数，以及函数的输入和输出是什么即可。

这种抽象特性使得编写和维护代码更加简单和高效。

---

1.4 设计函数

函数是所有程序的重要组成部分，无论大小，它们是我们在编程语言中表达计算过程的主要媒介。本文将讨论什么是良好函数的特征，这些特征本质上都强化了函数的抽象性。

1.4.1 函数的特点

1. 单一职责：每个函数应该只有一个明确的任务，并且可以用简短的名称和一行文字描述。执行多个任务的函数应拆分为多个函数。

2. 遵循DRY原则：不要重复自己（DRY原则）是软件工程的核心原则，意味着多个代码片段不应描述冗余的逻辑，而应将逻辑实现一次、命名并多次应用。如果发现自己在复制粘贴代码块，可能是抽象化的机会。

3. 通用性：函数应通用。例如，平方操作不在Python库中，因为它是pow函数（可以将数字提升到任意幂）的特殊情况。

这些指导方针提高了代码的可读性，减少了错误数量，并通常最小化了书写的总代码量。将复杂任务分解为简洁函数的技能需要经验来掌握。幸运的是，Python提供了多种功能来支持这一努力。

1.4.2 文档说明

函数定义通常包括文档说明，称为文档字符串（docstring），它必须与函数体缩进对齐。文档字符串通常用三重引号括起来。第一行描述函数的任务，后续行可以描述参数并阐明函数的行为。例如：

def pressure(v, t, n):
    """计算理想气体的压力（单位：帕斯卡）。

    应用理想气体法则：http://en.wikipedia.org/wiki/Ideal_gas_law

    v -- 气体体积（单位：立方米）
    t -- 绝对温度（单位：开尔文）
    n -- 气体颗粒数
    """
    k = 1.38e-23  # 玻尔兹曼常数
    return n * k * t / v

调用help函数并传入函数名作为参数，可以查看其文档字符串。

help(pressure)

在编写Python程序时，建议为所有但最简单的函数包含文档字符串。记住，代码只写一次，但常常被阅读多次。Python文档包括文档字符串的指导方针，以保持不同Python项目之间的一致性。

1.4.3 注释

在Python中，可以在行尾使用#符号附加注释。例如，上述关于玻尔兹曼常数的注释描述了k。这些注释不会出现在Python的帮助信息中，解释器也会忽略它们。它们仅供人类参考。

1.4.4 默认参数值

定义通用函数的一个结果是引入额外的参数。具有多个参数的函数可能调用起来显得笨拙且难以阅读。

在Python中，可以为函数的参数提供默认值。调用函数时，带有默认值的参数是可选的。如果不提供，则将默认值绑定到形式参数名。例如，如果应用程序通常计算一摩尔颗粒的压力，则可以将该值作为默认值提供：

def pressure(v, t, n=6.022e23):
    """计算理想气体的压力（单位：帕斯卡）。

    v -- 气体体积（单位：立方米）
    t -- 绝对温度（单位：开尔文）
    n -- 气体颗粒数（默认：一摩尔）
    """
    k = 1.38e-23  # 玻尔兹曼常数
    return n * k * t / v

在这个例子中，=符号在不同的上下文中有不同的含义。在def语句头中，=并不是赋值，而是指示调用函数时使用的默认值。相比之下，在函数体中对k的赋值语句将名称k绑定到玻尔兹曼常数的近似值。

pressure(1, 273.15)  # 输出：2269.974834
pressure(1, 273.15, 3 * 6.022e23)  # 输出：6809.924502

pressure函数被定义为接受三个参数，但在第一个调用表达式中只提供了两个。在这种情况下，n的值取自def语句中的默认值。如果提供了第三个参数，则忽略默认值。

作为指导原则，大多数在函数体中使用的数据值应表示为命名参数的默认值，以便于检查并可以由函数调用者更改。某些不会改变的值（例如基本常量k）可以在函数体内或全局框架中绑定。

当然可以，下面是更详细的学习笔记，包括一些适当的示例。

---

1.5 控制语句

控制语句赋予程序根据逻辑比较的结果执行不同操作的能力，从而控制程序的执行流。

1.5.1 语句

• 定义：语句是解释器执行的命令，而不是计算值。执行语句会改变解释器的状态。

• 类型：

  • 赋值语句：将值绑定到变量。例如：

    x = 10

  • 函数定义（def）：定义函数的过程。例如：

    def square(x):
        return x * x

  • 返回语句（return）：在函数中返回值。例如：

    def add(a, b):
        return a + b

• 执行与表达式：

  • 表达式可以被执行为语句，但它们的值会被丢弃。例如：

    print(square(4))  # 输出：16，但没有存储返回值

1.5.2 复合语句

• 定义：复合语句由多个简单语句组成，通常包括以冒号结尾的头部和缩进的代码块。

• 示例：

  def greet(name):
      """打印问候信息"""
      print("Hello, " + name + "!")

• 执行顺序：在复合语句中，执行是有序的，直到遇到控制语句（如返回或条件语句）为止。

1.5.3 定义函数 II：局部赋值

• 功能：局部赋值允许在函数内部定义变量，这些变量只在该函数的局部环境中有效。

• 示例：

  def percent_difference(x, y):
      difference = abs(x - y)
      return 100 * difference / x
  
  result = percent_difference(40, 50)
  print(result)  # 输出：25.0

  • 这里，difference是局部变量，不会影响全局命名空间。

• 复杂表达式：使用局部赋值可以使复杂的计算更易于理解。

  def calculate_area(length, width):
      area = length * width
      return area

1.5.4 条件语句

• 定义：条件语句使用if、elif和else结构来选择执行不同的代码块。

• 示例：

  def absolute_value(x):
      """计算绝对值"""
      if x > 0:
          return x
      elif x == 0:
          return 0
      else:
          return -x
  
  print(absolute_value(-2))  # 输出：2

• 布尔上下文：条件表达式在布尔上下文中计算，返回True或False。

• 布尔值和操作符：

  • 布尔值：True和False是Python中的布尔值。

  • 示例：

    print(4 < 2)  # 输出：False
    print(5 >= 5)  # 输出：True

  • 布尔操作符：

    print(True and False)  # 输出：False
    print(True or False)   # 输出：True
    print(not False)       # 输出：True

1.5.5 迭代

• 定义：控制语句也用于表示重复操作，允许在满足条件时重复执行相同的语句。

• 示例：

  def fib(n):
      """计算第n个斐波那契数"""
      pred, curr = 0, 1  # 第1和第2个斐波那契数
      for k in range(2, n):  # 从第3个开始
          pred, curr = curr, pred + curr
      return curr
  
  print(fib(8))  # 输出：21

• while循环：

  def count_down(n):
      while n > 0:
          print(n)
          n -= 1  # 减少n的值
      print("Blast off!")
  
  count_down(5)  # 输出：5 4 3 2 1 Blast off!

• 注意：确保每次迭代都能改变某些绑定，避免出现无限循环。

1.5.6 测试

• 定义：测试是验证函数行为是否符合预期的过程，通常通过断言语句进行验证。

• 示例：

  def test_fib():
      assert fib(2) == 1, 'The 2nd Fibonacci number should be 1'
      assert fib(3) == 2, 'The 3rd Fibonacci number should be 2'
      assert fib(8) == 21, 'The 8th Fibonacci number should be 21'
  
  test_fib()  # 如果所有断言通过，什么也不输出

• 文档测试（doctest）：

  def sum_naturals(n):
      """返回前n个自然数的和。
  
      >>> sum_naturals(10)
      55
      >>> sum_naturals(100)
      5050
      """
      total, k = 0, 1
      while k <= n:
          total, k = total + k, k + 1
      return total
  
  if __name__ == "__main__":
      import doctest
      doctest.testmod()

  • 这段代码可以直接在文档字符串中进行测试，提供了简洁的测试方式。

实用建议

• 缩进规范：确保所有代码块的缩进一致，以避免IndentationError。
• 测试习惯：在实现新功能后立即编写和运行测试，以确保其行为符合预期。良好的测试习惯有助于快速发现和修复错误。

通过以上内容，我们可以更清晰地理解控制语句如何在程序中起到核心作用，从而使编程更具表达力和可维护性。

---

这里补充介绍一下文档测试：

文档测试（doctest）是一种在 Python 中用于测试代码的技术。它的主要思想是将代码的使用示例写入文档字符串（docstring）中，然后 doctest 模块会自动执行这些示例并检查它们的输出是否与期望的结果一致。这样，你不仅可以提供代码的使用说明，还可以确保代码的行为符合预期。

代码解释

def sum_naturals(n):
 """返回前n个自然数的和。

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

函数 sum_naturals(n)

这个函数用于计算前 n 个自然数的和。

1. 参数：

   • n：要计算的前 n 个自然数。

2. 实现逻辑：

   • total, k = 0, 1：初始化两个变量，total 用于存储总和，k 用于从 1 开始计数。
   • while k <= n:：循环从 k = 1 开始，逐步将 k 累加到 total，并每次将 k 增加 1，直到 k > n 为止。
   • return total：返回最终累加得到的总和。

3. 文档字符串（docstring）：

   • 文档字符串中包含了两个使用示例：

     >>> sum_naturals(10)
     55
     >>> sum_naturals(100)
     5050

   • >>> 表示 Python 交互式解释器中的命令，doctest 将执行这些命令并验证它们的输出是否与文档中给出的结果一致。

if __name__ == "__main__":
    import doctest
    doctest.testmod()

主程序部分

这部分代码会在脚本作为主程序运行时执行：

• import doctest：导入 doctest 模块。
• doctest.testmod()：运行当前模块中的文档测试。它会检查所有函数的 docstring 中的测试用例，自动执行它们，并验证输出是否与预期结果匹配。

总结

• 文档测试的优势：它将代码示例嵌入文档中，可以直接运行这些示例进行测试，非常适合用于快速验证代码的正确性，尤其在编写教程或提供使用说明时。
• 这段代码的作用：计算前 n 个自然数的和，并使用 doctest 来验证 sum_naturals 函数是否正确通过了文档中提供的测试用例。

---

下面是关于高阶函数的学习笔记，包含示例和要点，以帮助理解这一概念。

---

1.6 高阶函数

在计算机科学中，高阶函数是指接受其他函数作为参数或者返回一个函数的函数。高阶函数可以帮助我们抽象出常见的编程模式，从而提高代码的可读性和可复用性。

1.6.1 函数作为参数

高阶函数允许我们将一个函数作为参数传递给另一个函数，从而抽象出通用的计算模式。

示例：

1. 求自然数的和：

   def sum_naturals(n):
       total, k = 0, 1
       while k <= n:
           total, k = total + k, k + 1
       return total
   
   print(sum_naturals(100))  # 输出：5050

2. 求立方数的和：

   def sum_cubes(n):
       total, k = 0, 1
       while k <= n:
           total, k = total + k*k*k, k + 1
       return total
   
   print(sum_cubes(100))  # 输出：25502500

3. 使用通用的求和函数： 我们可以定义一个通用的summation函数，并将计算每个项的函数作为参数传递：

   def summation(n, term):
       total, k = 0, 1
       while k <= n:
           total, k = total + term(k), k + 1
       return total
   
   def cube(x):
       return x*x*x
   
   def sum_cubes(n):
       return summation(n, cube)
   
   print(sum_cubes(3))  # 输出：36

4. 求自然数的和： 我们可以使用identity函数来求自然数的和：

   def identity(x):
       return x
   
   def sum_naturals(n):
       return summation(n, identity)
   
   print(sum_naturals(10))  # 输出：55

5. 直接调用sumation函数：

   def square(x):
       return x * x
   
   print(summation(10, square))  # 输出：385

6. 使用summation计算π：

   def pi_term(x):
       return 8 / ((4*x-3) * (4*x-1))
   
   def pi_sum(n):
       return summation(n, pi_term)
   
   print(pi_sum(1e6))  # 输出：接近 π 的值

1.6.2 函数作为通用方法

高阶函数不仅可以简化特定计算，还可以创建通用的计算方法。

示例：

1. 改进算法：

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

   这个improve函数是一个通用的重复改进方法。

2. 计算黄金比例：

   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-15):
       return abs(x - y) < tolerance
   
   phi = improve(golden_update, square_close_to_successor)
   print(phi)  # 输出接近黄金比例

3. 测试improve函数的正确性：

   from math import sqrt
   
   phi_exact = 1/2 + sqrt(5)/2
   
   def improve_test():
       approx_phi = improve(golden_update, square_close_to_successor)
       assert approx_eq(phi_exact, approx_phi), 'phi differs from its approximation'
   
   improve_test()  # 如果通过测试，则没有输出

总结

• 抽象能力：高阶函数提供了一种强大的抽象机制，使得我们可以通过函数来表达通用的计算模式，而不仅仅是特定的计算。
• 代码复用：通过将函数作为参数传递，我们可以编写更加通用和可复用的代码。
• 简化复杂性：高阶函数可以帮助我们简化复杂的逻辑，使代码更易于理解和维护。

高阶函数在实际编程中具有重要意义，能显著提高程序的表达能力和灵活性。

1.6.3 嵌套函数定义

嵌套函数定义使得在函数内部定义其他函数成为可能，这有助于简化全局命名空间并避免函数签名的限制。

示例：计算平方根

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

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)

• sqrt_update和sqrt_close函数仅在sqrt函数内部可用，利用了词法作用域（lexical scoping）。

词法作用域

• 嵌套函数能够访问其定义环境中的变量，而不是调用环境中的变量。
• 这意味着在调用内嵌函数时，可以访问包含它的函数的参数。

1.6.4 函数作为返回值

通过创建返回函数的函数，可以实现更强大的功能，例如函数组合。

示例：函数组合

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

def square(x):
    return x * x

def successor(x):
    return x + 1

square_successor = compose1(square, successor)
result = square_successor(12)  # 返回169

• compose1返回一个新的函数h，该函数执行f(g(x))。

1.6.5 牛顿法（Newton's Method）

牛顿法是一种用于寻找函数零点的迭代改进算法，适用于可微分函数。

示例：实现牛顿法

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

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

• 通过使用牛顿更新方法，可以计算平方根和任意次数的根。

示例：平方根

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

result = square_root_newton(64)  # 返回8.0

一般化至任意次数的根

通过定义相应的函数和导数，可以计算任意次数的根。

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

总结

• 嵌套函数和函数作为返回值极大增强了编程语言的表达能力。
• 词法作用域允许内嵌函数访问其定义环境中的变量。
• 牛顿法提供了一种通用的迭代方法，用于求解可微分函数的零点。尽管牛顿法并不总是收敛，但它在计算机科学中的应用非常广泛。

1.6.6 柯里化 (Currying)

柯里化是将一个多参数的函数转换为一系列单参数函数的过程。给定一个函数 f(x, y)，我们可以定义一个高阶函数 g，使得 g(x)(y) 等价于 f(x, y)。

示例：定义幂函数的柯里化版本

def curried_pow(x):
    def h(y):
        return pow(x, y)
    return h

curried_pow(2)(3)  # 输出 8

在 Python 中，柯里化可以用于需要单参数函数的场景，如 map 模式。可以通过 map_to_range 函数结合 curried_pow 来计算二的前十个幂：

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

map_to_range(0, 10, curried_pow(2))
# 输出：1, 2, 4, 8, 16, 32, 64, 128, 256, 512

自动化柯里化与反柯里化

def curry2(f):
    def g(x):
        def h(y):
            return f(x, y)
        return h
    return g

def uncurry2(g):
    def f(x, y):
        return g(x)(y)
    return f

pow_curried = curry2(pow)
pow_curried(2)(5)  # 输出 32
uncurry2(pow_curried)(2, 5)  # 输出 32

1.6.7 Lambda 表达式

Lambda 表达式用于创建匿名函数，具有单一返回表达式。其语法如下：

lambda 参数: 表达式

示例：使用 lambda 表达式定义复合函数

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

f = compose1(lambda x: x * x, lambda y: y + 1)
result = f(12)  # 输出 169

尽管 lambda 表达式简洁，但复合表达式可能难以阅读，因此在复杂情况下推荐使用 def 语句。

1.6.8 抽象与一等函数

用户定义函数是重要的抽象机制，使我们能够以明确的方式表达通用计算方法。一等函数具有以下特性：

• 可以绑定到名字
• 可以作为参数传递给函数
• 可以作为函数的返回值
• 可以包含在数据结构中

Python 中的函数具备完全的一等地位，显著提升了表达能力。

1.6.9 函数装饰器 (Function Decorators)

装饰器是 Python 中用于高阶函数的一种特殊语法，可以在定义函数时应用。常见的例子是跟踪函数调用的装饰器：

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 ...> ( 12 ), 36

使用装饰器的语法相当于：

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

总结

通过柯里化、lambda 表达式、函数的一等地位以及装饰器，Python 允许更灵活和强大的函数式编程。这些概念使得程序员能够构建更高效和抽象的代码结构。

---

1. 7 递归函数的定义

递归函数是指函数的主体调用自身，无论是直接还是间接。递归函数在 Python 中没有特殊的语法，但理解和创建递归函数需要一定的努力。

1.7.0 示例：求自然数的数字和

• 通过 % 和 // 操作符将一个数字分解为其最后一位和其余部分。算法步骤为：求数字 n 的最后一位 n % 10，加上去掉最后一位后的数字的数字和 sum_digits(n // 10)。
• 特殊情况：如果 n 只有一位数，则返回 n 本身。

def sum_digits(n):
    """返回正整数 n 的数字和。"""
    if n < 10:
        return n
    else:
        all_but_last, last = n // 10, n % 10
        return sum_digits(all_but_last) + last

1.7.1 递归函数的结构

• 基本情况：函数体开始部分的条件语句，定义了函数对最简单输入的行为。
• 递归调用：后续的递归调用逐步简化原问题。

例子：计算阶乘

• 迭代实现：

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

• 递归实现：

def fact(n):
    if n == 1:
        return 1
    else:
        return n * fact(n - 1)

1.7.2 互递归

• 两个相互调用的函数称为互递归。例如，定义偶数和奇数的函数。

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)

1.7.3 打印递归函数中的信息

• 可以使用打印语句可视化递归函数的计算过程。

def cascade(n):
    """打印 n 的所有前缀，从大到小再从小到大。"""
    print(n)
    if n >= 10:
        cascade(n // 10)
        print(n)

1.7.4 树形递归

• 树形递归指一个函数多次调用自身的情况，例如计算斐波那契数列。

def fib(n):
    if n == 1:
        return 0
    if n == 2:
        return 1
    else:
        return fib(n - 2) + fib(n - 1)

1.7.5 示例：整数的划分

• 使用部分的划分问题的树形递归函数示例。

def count_partitions(n, m):
    """计算使用部分不超过 m 的 n 的不同划分方式的数量。"""
    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)

结论

• 递归函数提供了一种通过简化问题逐步构造解决方案的方法。通过对简单情况的处理和递归调用的组合，能够以较少的代码实现复杂的计算任务。然而，理解递归函数的调用过程和返回值的构建需要一定的实践和思考。

---

第二章：通过数据构建抽象

2.1 引言

在第一章中，我们重点讨论了计算过程以及函数在程序设计中的作用。我们学习了如何使用原始数据（如数字）和原始操作（如算术运算），如何通过组合和控制构建复合函数，以及如何通过为过程命名来创建函数抽象。我们还了解到，高阶函数增强了语言的能力，使我们能够操作并推理一般的计算方法。这些是编程的本质。

本章将重点关注数据。我们将在这里探讨的技术将使我们能够表示和操作来自不同领域的信息。由于互联网的快速发展，海量的结构化信息可供我们在线获取，计算可以应用于各种不同的问题。有效使用内置和用户定义的数据类型是数据处理应用程序的基础。

2.1.1 原生数据类型

在 Python 中，每个值都有一个类来决定其数据类型。具有相同类的值共享相同行为。例如，整数 1 和 2 都是 int 类的实例，它们可以执行相同的操作，如取反或加另一个整数。Python 中的 type 函数可以用于查看任意值的类型。

Python 中常用的一些原生数据类型包括整数（int）、浮点数（float）和复数（complex）。

• 整数（int） 可以精确表示，不存在大小限制。
  
• 浮点数（float） 则是近似值，表示范围广，但会有精度损失，尤其是在执行多次浮点数运算时，可能会产生舍入误差。
  
• 复数（complex） 用于表示具有实部和虚部的复数。

浮点数的近似特性在进行等值比较时可能会引发问题，比如：

>>> 1 / 3 == 0.333333333333333312345  # 注意浮点数近似
True

除此之外，Python 还包含其他非数值类型，如布尔值（bool），用来表示 True 和 False。然而，大多数值的类型需要程序员自行定义，后续章节将介绍如何通过组合和抽象来创建有用的数据抽象。

总之，原生数据类型的数量有限，记住这些差异可以帮助编程。许多编程语言都遵循类似的标准，例如 IEEE 754 浮点数标准，使这些细节在不同语言中一致。

---

2.2 数据抽象

当我们考虑想在程序中表示的广泛事物时，发现大多数事物具有复合结构。例如，地理位置由纬度和经度组成。我们希望编程语言能够将纬度和经度结合起来，形成一个复合数据值。使用复合数据可以提高程序的模块化，使计算过程中不必关心数据的具体表示方式。这种隔离数据表示与操作的设计方法称为数据抽象，它能使程序更容易设计、维护和修改。

数据抽象类似于函数抽象。函数抽象隐藏了函数的实现细节，而数据抽象则隔离了数据的使用与其表示细节。

基本思路：

• 程序操作抽象数据，尽量少假设数据的具体细节。
  
• 数据的具体表示作为程序独立部分进行定义。
  
• 抽象数据和具体表示通过少量函数连接。

2.2.1 例子：有理数

有理数是整数比值，如 1/3 或 17/29。直接计算这些数的比值会产生浮点数近似，导致精度丢失。例如：

>>> 1 / 3
0.3333333333333333
>>> 1 / 3 == 0.333333333333333300000  # 近似值比较
True

我们可以通过将分子和分母组合，创建精确的有理数表示。

通过构造函数和选择器函数实现有理数的抽象：

• rational(n, d) 构造有理数。
• numer(x) 获取有理数的分子。
• denom(x) 获取有理数的分母。

使用这些函数，可以定义加法、乘法、打印和相等性测试操作，而无需关心有理数的具体表示：

def add_rationals(x, y):
    nx, dx = numer(x), denom(x)
    ny, dy = numer(y), denom(y)
    return rational(nx * dy + ny * dx, dx * dy)

def print_rational(x):
    print(numer(x), '/', denom(x))

half = rational(1, 2)
print_rational(half)  # 输出：1 / 2

2.2.2 复合数据：对

Python 提供了列表作为一种复合结构，可以用于实现对（pair）。通过列表，我们可以将分子和分母组合为有理数。列表可以通过索引访问元素，或通过多重赋值解构：

pair = [10, 20]
x, y = pair
print(x)  # 输出：10
print(y)  # 输出：20

为了使有理数保持最简形式，可以在构造函数中使用最大公约数（GCD）简化分子和分母：

from fractions import gcd

def rational(n, d):
    g = gcd(n, d)
    return (n // g, d // g)

print_rational(add_rationals(rational(1, 3), rational(1, 3)))  # 输出：2 / 3

2.2.3 抽象屏障

抽象屏障的概念：

• 数据抽象通过一组基本操作来屏蔽底层数据的具体表示。
  
• 在操作数据时，只能使用这些基本操作，不能直接访问数据的具体表示。
  
• 如果打破抽象屏障，程序的可维护性和灵活性会下降。

例如，实现有理数平方时，应该使用 mul_rational 函数，而不是直接操作分子和分母：

def square_rational(x):
    return mul_rational(x, x)  # 正确实现

def square_rational_violating_once(x):
    return rational(numer(x) * numer(x), denom(x) * denom(x))  # 违反一次抽象屏障

2.2.4 数据的性质

抽象屏障不仅适用于有理数，也适用于我们之前使用的对。实际上，列表并不是创建对的唯一方法。我们可以通过高阶函数创建一个同样能够表示对的实现，满足数据抽象的要求即可：

def pair(x, y):
    """返回表示对的函数。"""
    def get(index):
        if index == 0:
            return x
        elif index == 1:
            return y
    return get

p = pair(20, 14)
print(select(p, 0))  # 输出：20
print(select(p, 1))  # 输出：14

通过数据抽象，可以轻松切换数据的表示方式，确保程序的灵活性和正确性。

---

2.3 序列

序列是有序的值集合，是计算机科学中的一种重要抽象。序列不是特定的内置类型或抽象数据表示，而是一组共享特定行为的不同数据类型。所有序列都有以下共同特性：

• 长度：序列具有有限长度。空序列的长度为 0。
• 元素选择：序列中每个元素都有对应的非负整数索引，索引从 0 开始。

在 Python 中，多个内置数据类型都是序列，最重要的是列表。

2.3.1 列表

列表是可以具有任意长度的序列。列表有丰富的内置行为以及特定的语法来表达这些行为。我们已经见过列表字面量（literal），它评估为列表实例，还有元素选择表达式，用于获取列表中的值。内置的 len 函数返回序列的长度。以下是一个示例，digits 是一个包含四个元素的列表，索引 3 的元素是 8。

digits = [1, 8, 2, 8]
len(digits)  # 输出：4
digits[3]    # 输出：8

此外，列表可以相加和乘以整数。对于序列来说，加法和乘法并不是对元素的加法或乘法，而是组合和重复序列本身。+ 运算符（和 add 函数）返回两个序列的连接，* 运算符（和 mul 函数）将返回一个包含原列表 k 次重复的列表。

[2, 7] + digits * 2  # 输出：[2, 7, 1, 8, 2, 8, 1, 8, 2, 8]

任何值都可以包含在列表中，包括另一个列表。可以多次应用元素选择以选择嵌套在列表中的深层元素。

pairs = [[10, 20], [30, 40]]
pairs[1]     # 输出：[30, 40]
pairs[1][0]  # 输出：30

2.3.2 序列迭代

在许多情况下，我们希望遍历序列中的元素，并对每个元素执行某些计算。这种模式如此常见，以至于 Python 提供了额外的控制语句来处理顺序数据：for 语句。

考虑计算一个值在序列中出现多少次的问题。我们可以使用 while 循环实现此计数的函数。

def count(s, value):
    """计算值在序列 s 中出现的次数。"""
    total, index = 0, 0
    while index < len(s):
        if s[index] == value:
            total += 1
        index += 1
    return total

count(digits, 8)  # 输出：2

使用 for 语句可以简化这个函数体，直接遍历元素值，而不需要引入索引名称。

def count(s, value):
    """计算值在序列 s 中出现的次数。"""
    total = 0
    for elem in s:
        if elem == value:
            total += 1
    return total

count(digits, 8)  # 输出：2

for 语句的结构为：

for <name> in <expression>:
    <suite>

for 语句的执行过程如下：

1. 评估头部 <expression>，该表达式必须返回一个可迭代值。
2. 对于该可迭代值中的每个元素值，按顺序：
   • 将 <name> 绑定到当前值。
   • 执行 <suite>。

这个执行过程提到了可迭代值。列表是一种序列类型，而序列是可迭代值。它们的元素按顺序处理。Python 还包括其他可迭代类型，但我们暂时将重点放在序列上；关于“可迭代”的一般定义将在第四章的迭代器部分中讨论。

重要的是，执行完 for 语句后，<name> 将绑定到序列的最后一个元素，这意味着 for 循环又为更新环境引入了一种新方式。

序列解包

程序中常见的一种模式是拥有元素序列，而这些元素自身也是固定长度的序列。for 语句的头部可以包含多个名称，以“解包”每个元素序列。例如，我们可能有一个包含二元列表的列表。

pairs = [[1, 2], [2, 2], [2, 3], [4, 4]]

我们希望找出这些对中有多少对具有相同的第一个和第二个元素。

same_count = 0
for x, y in pairs:
    if x == y:
        same_count += 1

此时，same_count 的值为 2。

这种将多个名称绑定到多个值的模式称为序列解包；它与赋值语句中将多个名称绑定到多个值的模式相同。

范围

范围是 Python 中的另一种内置序列类型，表示一系列整数。范围是通过 range 创建的，它接受两个整数参数：第一个数字和想要的范围的最后一个数字的下一个数字。

range(1, 10)  # 包含 1，但不包含 10

调用 list 构造函数来评估范围将返回一个与范围相同元素的列表，以便可以轻松检查这些元素。

list(range(5, 8))  # 输出：[5, 6, 7]

如果只给出一个参数，它被解释为从 0 开始到最后值的下一个值。

list(range(4))  # 输出：[0, 1, 2, 3]

范围通常作为 for 头部中的表达式出现，以指定套件应执行的次数：通常约定如果名称在套件中未使用，则在 for 头部使用单个下划线字符：

for _ in range(3):
    print('Go Bears!')

# 输出：
# Go Bears!
# Go Bears!
# Go Bears!

这个下划线在解释器看来只是环境中的另一个名称，但在程序员中有一个约定的含义，表示该名称在未来的表达式中不会出现。

2.3.3 序列处理

序列是复合数据的一种常见形式，整个程序通常围绕这一抽象进行组织。可以通过模块化组件混合处理具有序列作为输入和输出的功能。常见的序列处理操作包括：

列表推导式（List Comprehensions）是用于执行序列处理操作的一种简洁表达方式。例如，增加每个奇数的 1：

odds = [1, 3, 5, 7, 9]
print([x + 1 for x in odds])  # 输出: [2, 4, 6, 8, 10]

可以选择满足某些条件的值的子集，例如：

print([x for x in odds if 25 % x == 0])  # 输出: [1, 5]

聚合（Aggregation）是将序列中的所有值合并为单个值的操作。例如，计算一个数的所有因子的和：

def divisors(n):
    return [1] + [x for x in range(2, n) if n % x == 0]

print(divisors(12))  # 输出: [1, 2, 3, 4, 6]

使用列表推导式可以计算 1 到 1000 的所有完美数：

print([n for n in range(1, 1000) if sum(divisors(n)) == n])  # 输出: [6, 28, 496]

还可以使用更复杂的函数处理，例如计算给定面积的矩形的最小周长：

def width(area, height):
    assert area % height == 0
    return area // height

def perimeter(width, height):
    return 2 * width + 2 * height

def minimum_perimeter(area):
    heights = divisors(area)
    perimeters = [perimeter(width(area, h), h) for h in heights]
    return min(perimeters)

area = 80
print(minimum_perimeter(area))  # 输出: 36

高阶函数。序列处理的常见模式可以通过高阶函数来表达，例如 map 和 filter。以下是一些示例：

def apply_to_all(map_fn, s):
    return [map_fn(x) for x in s]

def keep_if(filter_fn, s):
    return [x for x in s if filter_fn(x)]

使用 reduce 函数可以聚合序列中的元素：

from functools import reduce
from operator import mul

def product(s):
    return reduce(mul, s)

print(product([1, 2, 3, 4, 5]))  # 输出: 120

在 Python 程序中，通常直接使用列表推导式而不是高阶函数。

2.3.4 序列抽象

我们已经介绍了两种符合序列抽象的原生数据类型：列表和范围。Python 还包括满足序列抽象的两个其他行为：

1. 成员资格：可以使用 in 和 not in 操作符来测试一个值是否在序列中。

digits = [1, 8, 2, 8]
print(2 in digits)          # 输出: True
print(1828 not in digits)   # 输出: True

2. 切片（Slicing）：序列可以包含更小的子序列。切片是原始序列的任何连续范围，使用两个整数表示。

print(digits[0:2])  # 输出: [1, 8]
print(digits[1:])   # 输出: [8, 2, 8]

序列的丰富抽象在计算中是非常普遍的，因此学习一些复杂的行为是合理的。在定义用户自定义抽象时，通常应该尽量保持简单。

2.3.5 字符串

字符串是计算机科学中非常基础的文本值类型，Python 程序本身就是以文本形式编写和存储的。Python 中的字符串数据类型由构造函数 str 表示。

这一部分将介绍字符串的基本行为，包括如何表示、表达和操作字符串。

字符串字面量

字符串字面量可以用单引号或双引号包围，表示任意文本：

print('I am string!')           # 输出: I am string!
print("I've got an apostrophe")  # 输出: I've got an apostrophe
print('您好')                     # 输出: 您好

字符串的特性

字符串满足序列的两个基本条件：具有长度和支持元素选择。

city = 'Berkeley'
print(len(city))  # 输出: 8
print(city[3])    # 输出: k

字符串的元素本身是长度为 1 的字符串，表示单个字符。字符可以是字母、标点符号或其他符号。与许多其他编程语言不同，Python 没有单独的字符类型，任何文本都是字符串。

字符串的组合

字符串可以通过加法和乘法进行组合：

print('Berkeley' + ', CA')  # 输出: Berkeley, CA
print('Shabu ' * 2)         # 输出: Shabu Shabu 

成员资格

字符串的行为与其他序列类型有所不同。字符串的成员资格操作符 in 适用于字符串，但它的行为与在序列上使用时完全不同。它匹配的是子字符串，而不是单个元素。

print('here' in "Where's Waldo?")  # 输出: True

多行字面量

字符串不仅限于单行。三重引号可以定义跨越多行的字符串字面量。我们已经在文档字符串中广泛使用了三重引号。

print("""The Zen of Python
claims, Readability counts.
Read more: import this.""")
# 输出: The Zen of Python
# claims, "Readability counts."
# Read more: import this.

在上述输出中，\n 被视为一个单一元素，表示新行。

字符串强制转换

可以通过调用 str 构造函数将任何对象转换为字符串，这对于构建描述性字符串非常有用：

digits = [1, 8, 2, 8]
print(str(2) + ' is an element of ' + str(digits))  # 输出: 2 is an element of [1, 8, 2, 8]

深入阅读

文本编码在计算机中是一个复杂的话题。本节中我们抽象掉了字符串的具体表示细节，但了解字符串在计算机中的编码方式对许多应用来说是至关重要的。关于字符编码和 Unicode 的描述可以参考《Dive Into Python 3》的字符串章节。

2.3.6 树

我们可以将列表作为其他列表的元素，这种组合能力是数据类型的闭包属性。闭包属性意味着，数据组合的结果仍然可以使用相同的方法继续组合。这一属性是组合方法强大之处的关键，因为它允许我们创建层次结构——由部分组成的结构，这些部分本身又由更小的部分组成，依此类推。

树是一个基本的数据抽象，能使我们以规则的方式构建和操作层次结构的值。树有一个根标签和一系列分支。每个分支也是一棵树。没有分支的树称为叶子。树中的每一棵子树称为这棵树的子树，而子树的根称为该树的一个节点。

树的基本实现

树的构造函数是 tree，选择器是 label 和 branches：

def tree(root_label, branches=[]):
    for branch in branches:
        assert is_tree(branch), 'branches must be trees'
    return [root_label] + list(branches)

def label(tree):
    return tree[0]

def branches(tree):
    return tree[1:]

树的验证和叶子的判断

is_tree 函数用于验证树的结构是否正确：

def is_tree(tree):
    if type(tree) != list or len(tree) < 1:
        return False
    for branch in branches(tree):
        if not is_tree(branch):
            return False
    return True

is_leaf 函数用于判断一棵树是否为叶子：

def is_leaf(tree):
    return not branches(tree)

构建和操作树

我们可以通过嵌套表达式构建树：

t = tree(3, [tree(1), tree(2, [tree(1), tree(1)])])
print(t)  # 输出: [3, [1], [2, [1], [1]]]

树递归函数可以用来构造树，例如，Fibonacci 树：

def fib_tree(n):
    if n == 0 or n == 1:
        return tree(n)
    else:
        left, right = fib_tree(n-2), fib_tree(n-1)
        fib_n = label(left) + label(right)
        return tree(fib_n, [left, right])

print(fib_tree(5))
# 输出: [5, [2, [1], [1, [0], [1]]], [3, [1, [0], [1]], [2, [1], [1, [0], [1]]]]]

计算叶子的数量

树递归函数还可以用来处理树，例如 count_leaves 函数用于计算树的叶子数量：

def count_leaves(tree):
    if is_leaf(tree):
        return 1
    else:
        branch_counts = [count_leaves(b) for b in branches(tree)]
        return sum(branch_counts)

print(count_leaves(fib_tree(5)))  # 输出: 8

分割树

树还可以用来表示整数的分割。例如，partition_tree 函数构建分割树：

def partition_tree(n, m):
    if n == 0:
        return tree(True)
    elif n < 0 or m == 0:
        return tree(False)
    else:
        left = partition_tree(n-m, m)
        right = partition_tree(n, m-1)
        return tree(m, [left, right])

print(partition_tree(2, 2))
# 输出: [2, [True], [1, [1, [True], [False]], [False]]]

我们还可以通过递归遍历分割树打印分割结果：

def print_parts(tree, partition=[]):
    if is_leaf(tree):
        if label(tree):
            print(' + '.join(partition))
    else:
        left, right = branches(tree)
        m = str(label(tree))
        print_parts(left, partition + [m])
        print_parts(right, partition)

print_parts(partition_tree(6, 4))
# 输出:
# 4 + 2
# 4 + 1 + 1
# 3 + 3
# ...

二叉化树

right_binarize 函数将树二叉化，转换成右分支结构：

def right_binarize(tree):
    if is_leaf(tree):
        return tree
    if len(tree) > 2:
        tree = [tree[0], tree[1:]]
    return [right_binarize(b) for b in tree]

print(right_binarize([1, 2, 3, 4, 5, 6, 7]))
# 输出: [1, [2, [3, [4, [5, [6, 7]]]]]]

2.3.7 链表

链表简介

链表（Linked List）是一种序列结构，它由嵌套的成对元素表示。链表的每一个节点包含两个部分：一个是序列的第一个元素，另一个是指向剩余部分的链接。

例如，四个元素 1, 2, 3, 4 的链表表示为：

four = [1, [2, [3, [4, 'empty']]]]

这里，'empty' 表示链表的结束，[1, [2, [3, [4, 'empty']]]] 是一个递归结构。

链表的构造与选择器

我们可以定义一些函数来构造和操作链表：

• 构造器：

  def link(first, rest):
      """从第一个元素和剩余部分构造一个链表"""
      assert is_link(rest), "rest 必须是一个链表"
      return [first, rest]

• 选择器：

  def first(s):
      """返回链表的第一个元素"""
      return s[0]
  
  def rest(s):
      """返回链表的其余部分"""
      return s[1]

链表的验证与基本操作

• 验证链表：

  def is_link(s):
      """验证是否为链表"""
      return s == 'empty' or (len(s) == 2 and is_link(s[1]))

• 长度计算： 计算链表的长度可以使用迭代或递归：

  def len_link(s):
      """返回链表的长度（迭代版）"""
      length = 0
      while s != 'empty':
          s, length = rest(s), length + 1
      return length

  递归版：

  def len_link_recursive(s):
      """返回链表的长度（递归版）"""
      if s == 'empty':
          return 0
      return 1 + len_link_recursive(rest(s))

• 元素访问： 可以根据索引访问链表中的元素：

  def getitem_link(s, i):
      """返回链表中索引为 i 的元素"""
      while i > 0:
          s, i = rest(s), i - 1
      return first(s)

  递归版：

  def getitem_link_recursive(s, i):
      """返回索引为 i 的元素（递归版）"""
      if i == 0:
          return first(s)
      return getitem_link_recursive(rest(s), i - 1)

递归操作

链表的递归结构使得递归操作十分方便。

• 扩展链表： 我们可以将两个链表连接起来：

  def extend_link(s, t):
      """将链表 s 和链表 t 连接"""
      if s == 'empty':
          return t
      return link(first(s), extend_link(rest(s), t))

• 对链表中每个元素应用函数：

  def apply_to_all_link(f, s):
      """对链表 s 中的每个元素应用函数 f"""
      if s == 'empty':
          return s
      return link(f(first(s)), apply_to_all_link(f, rest(s)))

  例如，对链表中每个元素求平方：

  apply_to_all_link(lambda x: x*x, four)

• 筛选链表中的元素： 我们可以保留链表中满足特定条件的元素：

  def keep_if_link(f, s):
      """返回一个只包含满足条件 f 的元素的链表"""
      if s == 'empty':
          return s
      kept = keep_if_link(f, rest(s))
      if f(first(s)):
          return link(first(s), kept)
      else:
          return kept

• 拼接链表中的元素： 使用指定的分隔符，将链表的元素转换为字符串并拼接：

  def join_link(s, separator):
      """返回由 s 中的所有元素组成的字符串，元素间由 separator 分隔"""
      if s == 'empty':
          return ""
      elif rest(s) == 'empty':
          return str(first(s))
      return str(first(s)) + separator + join_link(rest(s), separator)

递归构造与组合

链表特别适用于递归构造序列的场景。例如，可以用递归的方式构造所有整数划分的链表：

def partitions(n, m):
    """返回一个包含所有划分的链表，每个划分由链表表示"""
    if n == 0:
        return link('empty', 'empty')
    elif n < 0 or m == 0:
        return 'empty'
    else:
        using_m = partitions(n - m, m)
        with_m = apply_to_all_link(lambda s: link(m, s), using_m)
        without_m = partitions(n, m - 1)
        return extend_link(with_m, without_m)

输出划分

可以将划分的结果转换为可读格式：

def print_partitions(n, m):
    lists = partitions(n, m)
    strings = apply_to_all_link(lambda s: join_link(s, " + "), lists)
    print(join_link(strings, "\n"))

例如：

print_partitions(6, 4)

输出：

4 + 2
4 + 1 + 1
3 + 3
3 + 2 + 1
3 + 1 + 1 + 1
2 + 2 + 2
2 + 2 + 1 + 1
2 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1

总结

链表是一种具有递归结构的序列类型，可以通过迭代或递归进行操作。它提供了构建复杂数据结构的基础，并且适合于增量地构造和处理序列。

---

2.4 可变数据

在大型系统中，抽象对帮助我们应对复杂性至关重要。为了有效编写程序，我们还需要组织原则，帮助我们设计模块化的程序。模块化程序分成独立开发和维护的部分，其中一种强有力的技术是使用可以随时间变化状态的数据。

添加状态到数据中是面向对象编程（OOP）中的核心思想。通过这种方式，数据对象可以独立于程序的其他部分，表现出随历史变化的行为。

2.4.1 对象的隐喻

最开始，我们区分了函数和数据：函数执行操作，而数据是被操作的对象。当函数值也被视为数据后，数据就开始拥有了行为。对象结合了数据和行为，既代表信息，又像它们所代表的事物一样有行为。

例如，日期对象结合了日期信息和相关的行为。在Python中，datetime模块的date类就是一个例子：

from datetime import date
tues = date(2014, 5, 13)
print(date(2014, 5, 19) - tues)  # 输出：6天
tues.year  # 输出：2014
tues.strftime('%A, %B %d')  # 输出：Tuesday, May 13

对象不仅有属性，还拥有方法（行为）。方法是函数，它们通过使用对象自身和传入的参数来进行计算。例如，strftime方法格式化日期输出。

2.4.2 序列对象

Python中，所有的值都是对象。某些对象是不可变的（例如数字和字符串），而列表是可变的。这意味着它们可以随时间改变。可变对象的行为类似于现实世界中的事物，例如一个人虽然每天都在改变，但仍然是同一个人。

列表的可变性

列表是可变的，我们可以对其进行增删操作。例如：

chinese = ['coin', 'string', 'myriad']
suits = chinese  # 两个变量指向同一个列表
suits.pop()  # 删除最后一个元素
suits.append('cup')  # 添加元素到列表末尾
suits[2] = 'spade'  # 替换指定位置的元素

修改列表的操作会影响引用同一列表的所有变量。例如，修改suits列表时，chinese列表也会随之改变，因为它们引用的是同一个列表对象。

我们可以通过list()函数复制列表，从而避免这种情况：

nest = list(suits)  # 创建一个新列表，内容相同
nest[0] = suits  # 创建嵌套列表

列表的身份与相等性

Python中使用is和is not判断两个对象是否是同一个，而使用==判断两个对象的内容是否相等：

suits is nest[0]  # 输出：True
suits == ['heart', 'diamond', 'spade', 'club']  # 输出：True

列表推导式

列表推导式创建新列表，并不会修改原有列表。例如，使用unicodedata模块来查找扑克牌花色符号：

from unicodedata import lookup
[lookup('WHITE ' + s.upper() + ' SUIT') for s in suits]  # 输出：['♡', '♢', '♤', '♧']

元组

元组（tuple）是不可变的序列对象。它们的创建方式与列表类似，但不能修改其内容：

code = ("up", "down", "left", "right")
code[0]  # 输出："up"

元组常用于多值赋值：

a, b = 1, 2  # 相当于 a = (1, 2)

虽然元组不可变，但其内部包含的可变元素（如列表）仍可以改变：

nest = (10, 20, [30, 40])
nest[2].pop()  # 修改了元组中的列表元素

总结：Python中的所有值都是对象，有些对象是不可变的（如元组），而有些是可变的（如列表）。对于可变对象，修改它们会影响所有引用该对象的变量。

2.4.3 字典

字典是 Python 中内置的数据类型，用于存储和操作键值对。字典中的键和值都是对象，通常用于存储非连续整数索引的对应关系。

• 键-值对：字典由键值对组成，例如：

  numerals = {'I': 1.0, 'V': 5, 'X': 10}

  通过键来查找对应的值：

  numerals['X']  # 输出: 10

• 字典无序性：字典是无序集合，键值对的顺序无法预知，不同运行结果可能不一样。

• 修改和添加键值对：可以通过赋值来添加或修改键值对。

  numerals['I'] = 1
  numerals['L'] = 50

• 键的要求：字典的键必须是不可变类型，例如字符串、元组，不能是列表等可变类型。

• get 方法：get 方法可用于返回键对应的值，若键不存在则返回默认值：

  numerals.get('A', 0)  # 输出: 0

• 字典推导式：可以使用字典推导式快速创建字典：

  {x: x*x for x in range(3,6)}  # 输出: {3: 9, 4: 16, 5: 25}

2.4.4 局部状态

字典和列表有局部状态，即它们的值会随着程序的执行而变化。函数也可以具有局部状态，例如模拟银行账户的取款操作。

• 函数的局部状态：定义一个 withdraw 函数，模拟取款操作。取款会减少账户余额，每次调用的结果依赖于之前的操作：

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

  通过 nonlocal 关键字，可以在函数中修改父作用域中的变量 balance。当调用 withdraw 函数时，balance 会被更新，影响下一次调用的结果。

• nonlocal 声明：nonlocal 允许在局部作用域中修改外部变量，而不再局限于仅查找变量。它的作用是使得变量的赋值影响整个闭包作用域，而非仅限于局部作用域。

• 错误示例：如果没有 nonlocal 声明，Python 会认为 balance 是局部变量，并抛出 UnboundLocalError：

  UnboundLocalError: local variable 'balance' referenced before assignment

通过使用 nonlocal 语句，允许函数在多个调用间共享状态，管理复杂的数据流和逻辑。

2.4.5 非本地赋值的好处

非本地赋值为我们提供了一种管理局部状态的方法，这个状态随着函数的多次调用而变化。每个 withdraw 函数的 balance 是独立的，并且不可被程序中的其他部分直接访问。通过调用 make_withdraw 创建了不同的 withdraw 实例，每个实例都管理自己的余额，并且它们不会互相影响。

示例：

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

wd = make_withdraw(20)
wd2 = make_withdraw(7)
print(wd2(6))  # 输出: 1
print(wd(8))   # 输出: 12

2.4.6 非本地赋值的代价

非本地赋值引入了复杂性。特别是当两个变量指向同一个函数实例时，它们的状态会互相影响。例如，wd 和 wd2 指向同一个函数时，改变 wd2 的状态会影响 wd 的状态。

示例：

wd = make_withdraw(12)
wd2 = wd
print(wd2(1))  # 输出: 11
print(wd(1))   # 输出: 10

2.4.7 实现可变链表和字典

可以通过函数实现可变链表。链表使用一个函数来表示，它接受不同的消息进行操作。如下的链表支持 len、getitem、push_first、pop_first 和 str 操作。

def mutable_link():
    contents = empty
    def dispatch(message, value=None):
        nonlocal contents
        if message == 'len':
            return len_link(contents)
        elif message == 'getitem':
            return getitem_link(contents, value)
        elif message == 'push_first':
            contents = link(value, contents)
        elif message == 'pop_first':
            first_item = first(contents)
            contents = rest(contents)
            return first_item
        elif message == 'str':
            return join_link(contents, ", ")
    return dispatch

通过消息传递的方式，也可以实现一个简单的字典。字典存储键值对，并通过 setitem 和 getitem 消息进行插入和查询操作。

def dictionary():
    records = []
    def getitem(key):
        matches = [r for r in records if r[0] == key]
        if matches:
            return matches[0][1]
    def setitem(key, value):
        nonlocal records
        non_matches = [r for r in records if r[0] != key]
        records = non_matches + [[key, value]]
    def dispatch(message, key=None, value=None):
        if message == 'getitem':
            return getitem(key)
        elif message == 'setitem':
            setitem(key, value)
    return dispatch

非本地赋值虽然增加了程序的复杂性，但它为实现模块化程序提供了重要的工具。通过函数和局部状态的组合，我们能够模拟许多内置的可变数据类型，如列表和字典。

2.4.8 消息传递系统和字典

我们可以使用字典来实现消息传递接口，避免使用条件语句来处理不同消息。字典的键可以是字符串，用于查找对应的值或函数。

示例：银行账户的消息传递系统 在下面的银行账户实现中，我们通过字典存储账户状态（余额）和操作（存款、取款函数）。通过消息传递的方式，使用字典中的函数实现操作。

def account(initial_balance):
    def deposit(amount):
        dispatch['balance'] += amount
        return dispatch['balance']
    def withdraw(amount):
        if amount > dispatch['balance']:
            return 'Insufficient funds'
        dispatch['balance'] -= amount
        return dispatch['balance']
    
    dispatch = {
        'deposit': deposit,
        'withdraw': withdraw,
        'balance': initial_balance
    }
    return dispatch

def withdraw(account, amount):
    return account['withdraw'](amount)

def deposit(account, amount):
    return account['deposit'](amount)

def check_balance(account):
    return account['balance']

# 示例使用
a = account(20)
deposit(a, 5)
withdraw(a, 17)
check_balance(a)

2.4.9 约束传播系统

约束传播系统模拟了变量之间的关系和约束，允许双向计算。它是一种声明式编程，其中程序员声明变量的关系，而不指定具体的计算过程。

理想气体定律：
\(p * v = n * k * t\)
传统程序语言中，通常我们只能将一个变量表示为其他变量的函数。例如，计算压力 p 需要给定 v、n、k、t。但在约束传播系统中，我们可以实现双向计算，任意一个未知量都可以通过其他已知量来计算。

摄氏温度与华氏温度的转换网络

通过定义基本约束（例如加法器、乘法器）和连接器，我们可以构建一个转换摄氏温度和华氏温度的网络。

摄氏温度与华氏温度的关系式：

9 * c = 5 * (f - 32)

该系统会在任何连接器的值发生变化时，自动更新其他受影响的连接器。以下是如何使用约束系统计算温度转换：

# 创建连接器
celsius = connector('Celsius')
fahrenheit = connector('Fahrenheit')

# 定义转换网络
def converter(c, f):
    u, v, w, x, y = [connector() for _ in range(5)]
    multiplier(c, w, u)
    multiplier(v, x, u)
    adder(v, y, f)
    constant(w, 9)
    constant(x, 5)
    constant(y, 32)

converter(celsius, fahrenheit)

# 设置摄氏温度，自动更新华氏温度
celsius['set_val']('user', 25)  # 输出: Celsius = 25, Fahrenheit = 77.0

实现约束和连接器

在约束传播系统中，约束和连接器都是字典，它们通过消息进行通信。

• 约束（Constraints）：接收连接器的消息，更新其他连接器的值。
• 连接器（Connectors）：保存当前的值，并在值更新时通知约束。

加法器的实现：

from operator import add, sub

def adder(a, b, c):
    """约束：a + b = c"""
    return make_ternary_constraint(a, b, c, add, sub, sub)

def make_ternary_constraint(a, b, c, ab, ca, cb):
    def new_value():
        av, bv, cv = [connector['has_val']() for connector in (a, b, c)]
        if av and bv:
            c['set_val'](constraint, ab(a['val'], b['val']))
        elif av and cv:
            b['set_val'](constraint, ca(c['val'], a['val']))
        elif bv and cv:
            a['set_val'](constraint, cb(c['val'], b['val']))

    def forget_value():
        for connector in (a, b, c):
            connector['forget'](constraint)

    constraint = {'new_val': new_value, 'forget': forget_value}
    for connector in (a, b, c):
        connector['connect'](constraint)
    return constraint

连接器的实现：

def connector(name=None):
    """连接器的构造函数"""
    informant = None
    constraints = []
    
    def set_value(source, value):
        nonlocal informant
        if connector['val'] is None:
            informant, connector['val'] = source, value
            if name is not None:
                print(name, '=', value)
            inform_all_except(source, 'new_val', constraints)
        else:
            if connector['val'] != value:
                print('Contradiction detected:', connector['val'], 'vs', value)

    def forget_value(source):
        nonlocal informant
        if informant == source:
            informant, connector['val'] = None, None
            if name is not None:
                print(name, 'is forgotten')
            inform_all_except(source, 'forget', constraints)
    
    connector = {
        'val': None,
        'set_val': set_value,
        'forget': forget_value,
        'has_val': lambda: connector['val'] is not None,
        'connect': lambda source: constraints.append(source)
    }
    return connector

def inform_all_except(source, message, constraints):
    """通知所有连接的约束，除了指定的 source"""
    for c in constraints:
        if c != source:
            c[message]()

• 字典是实现消息传递和存储状态的有效方式。
• 约束系统可以建立变量间复杂的关系，并实现多方向的计算。
• 使用字典和消息传递的方式可以模拟对象的行为，这为后续的面向对象编程奠定了基础。

---

2.5 面向对象编程学习笔记

2.5.1 面向对象编程（OOP）概述

• OOP简介：面向对象编程是一种通过对象与方法来组织程序的编程范式。对象结合了数据（状态）和行为（方法），能够抽象复杂性，并且通过交互产生有用的结果。
• 核心概念：
  • 对象：拥有属性和方法的数据类型。
  • 类：定义对象的模板。
  • 继承：对象可以从其他对象继承特性和行为。

2.5.2 定义类和对象

• 类定义：使用 class 关键字定义类。类通常包含属性（实例属性）和方法。

• 实例化对象：类通过调用生成具体的对象实例。实例化是通过调用类名，并传入参数来完成的。

  class Account:
      def __init__(self, account_holder):
          self.balance = 0  # 实例属性
          self.holder = account_holder  # 实例属性
  
  a = Account('Kirk')

• 实例属性：对象的属性，例如账户的余额和持有人。它们是通过 self 来绑定到对象实例的。

  a.holder  # 'Kirk'
  a.balance  # 0

方法定义与调用

• 方法：类内定义的函数，用于操作对象的属性。例如，deposit 方法用于给账户存钱，withdraw 方法用于取钱。

  class Account:
      def deposit(self, amount):
          self.balance += amount
          return self.balance

• 方法调用：对象方法的调用通过点号表示法，例如 spock_account.deposit(100)。

2.5.3 消息传递与点号表示法

• 消息传递：对象通过点号表示法接收消息，访问其方法和属性。例如，spock_account.deposit 是一个点表达式，它返回 spock_account 对象上的 deposit 方法。

  spock_account.deposit(100)  # 存款100

• getattr 和 hasattr：可以使用 getattr 来动态访问对象的属性或方法，使用 hasattr 检查对象是否具有某个属性或方法。

  getattr(spock_account, 'balance')  # 返回余额
  hasattr(spock_account, 'deposit')  # True

2.5.4 类属性

• 类属性：类属性是与类关联的值，而非对象实例。例如，银行的利率是所有账户共享的，可以通过类属性定义。

  class Account:
      interest = 0.02  # 类属性

• 类属性访问与修改：类属性可以通过类或实例访问，但修改时需要特别注意。如果修改类属性，将影响所有实例；而如果修改实例的同名属性，实例将拥有独立的属性值。

  Account.interest = 0.04  # 修改类属性
  spock_account.interest  # 0.04
  kirk_account.interest = 0.08  # kirk的独立实例属性

方法与函数的区别

• 方法绑定：在类中定义的方法在实例化时会自动绑定到对象，传入的第一个参数默认为对象本身 (self)。

  Account.deposit(spock_account, 1000)  # 直接调用函数
  spock_account.deposit(1000)  # 调用绑定的方法

总结

• 面向对象编程通过对象、方法和类将数据与行为整合在一起。类定义了对象的属性和行为，实例化后可以对每个对象进行操作。点号表示法用于访问对象的属性和方法，类属性为所有实例共享的值，方法通过自动绑定 self 来实现对象的操作。

2.5.5 继承

在面向对象编程中，类之间常常有某种关联性。某些类可能代表另一个类的特例。比如，CheckingAccount（支票账户）是 Account（账户）的一个特例。支票账户每次取款时收取额外费用，利率也更低。

例子：

>>> ch = CheckingAccount('Spock')
>>> ch.interest     # 支票账户的较低利率
0.01
>>> ch.deposit(20)  # 存款操作与普通账户相同
20
>>> ch.withdraw(5)  # 取款时收取额外费用
14

CheckingAccount 继承了 Account 类的所有属性和方法，但可以覆盖某些方法，比如 withdraw 方法。这样可以只编写不同的部分，其余行为由基类 Account 继承。

2.5.6 使用继承

下面是完整的 Account 类实现，包含了存款和取款操作的定义：

class Account:
    """一个具有非负余额的银行账户。"""
    interest = 0.02
    def __init__(self, account_holder):
        self.balance = 0
        self.holder = account_holder
    def deposit(self, amount):
        """存款并返回新余额。"""
        self.balance += amount
        return self.balance
    def withdraw(self, amount):
        """取款并返回新余额，如果余额不足返回‘Insufficient funds’。"""
        if amount > self.balance:
            return 'Insufficient funds'
        self.balance -= amount
        return self.balance

支票账户是对普通账户的特例，继承了 Account 的基本功能，但修改了 withdraw 方法，增加了取款费用：

class CheckingAccount(Account):
    """一个对取款收取费用的银行账户。"""
    withdraw_charge = 1
    interest = 0.01
    def withdraw(self, amount):
        return Account.withdraw(self, amount + self.withdraw_charge)

例子：

>>> checking = CheckingAccount('Sam')
>>> checking.deposit(10)
10
>>> checking.withdraw(5)
4

2.5.7 多重继承

Python 支持多重继承，即子类可以继承多个父类。假设有一个 SavingsAccount 类（储蓄账户），对每次存款收取费用：

class SavingsAccount(Account):
    deposit_charge = 2
    def deposit(self, amount):
        return Account.deposit(self, amount - self.deposit_charge)

我们还可以创建一个既有 CheckingAccount 又有 SavingsAccount 特性的账户：

class AsSeenOnTVAccount(CheckingAccount, SavingsAccount):
    def __init__(self, account_holder):
        self.holder = account_holder
        self.balance = 1  # 赠送1美元

在 AsSeenOnTVAccount 中，取款和存款操作都会收取费用：

例子：

>>> such_a_deal = AsSeenOnTVAccount("John")
>>> such_a_deal.balance
1
>>> such_a_deal.deposit(20)  # 储蓄账户的存款费用
19
>>> such_a_deal.withdraw(5)  # 支票账户的取款费用
13

在多重继承中，Python 采用 C3 方法解析顺序来处理属性或方法的查找。

2.5.8 对象的角色

Python 的对象系统提供了方便且灵活的数据抽象和消息传递机制。类、方法、继承、点表达式等语法特性帮助我们在程序中实现对象模型，使得编写和管理大型程序变得更加有条理。

---

2.6 实现类和对象

在面向对象编程范式中，我们使用对象隐喻来指导程序的组织。大多数关于如何表示和操作数据的逻辑都在类声明中表达。在这一节中，我们看到类和对象本身可以仅用函数和字典来表示。通过这种方式实现对象系统的目的是为了说明，使用对象隐喻并不需要特定的编程语言。即使在没有内置对象系统的编程语言中，程序也可以是面向对象的。

为了实现对象，我们将放弃点符号（这需要内置语言支持），而创建调度字典，行为与内置对象系统的元素非常相似。我们已经看到如何通过调度字典实现消息传递行为。为了完整实现对象系统，我们将在实例、类和基类之间发送消息，所有这些都作为包含属性的字典。

我们不会实现整个Python对象系统，因为它包括一些在本书中未覆盖的特性（例如，元类和静态方法）。相反，我们将专注于用户定义的类，不使用多重继承，也不使用反射行为（例如返回实例的类）。我们的实现并不打算遵循Python类型系统的精确规范，而是旨在实现支持对象隐喻的核心功能。

2.6.1 实例

实例具有命名属性，例如账户的余额，可以设置和获取。我们使用调度字典来实现实例，该字典响应“获取”和“设置”属性值的消息。属性本身存储在名为 attributes 的局部字典中。

示例：创建实例

def make_instance(cls):
    """返回一个新的对象实例，即一个调度字典。"""
    def get_value(name):
        if name in attributes:
            return attributes[name]
        else:
            value = cls['get'](name)
            return bind_method(value, instance)
    
    def set_value(name, value):
        attributes[name] = value
    
    attributes = {}
    instance = {'get': get_value, 'set': set_value}
    return instance

在这个实现中，make_instance 函数返回一个调度字典 instance，它响应 get 和 set 消息。

绑定方法

def bind_method(value, instance):
    """如果值是可调用的，返回一个绑定的方法，否则返回值本身。"""
    if callable(value):
        def method(*args):
            return value(instance, *args)
        return method
    else:
        return value

当调用方法时，第一个参数 self 将绑定到 instance 的值。

2.6.2 类

类也是对象，既在Python的对象系统中，也在我们实现的系统中。为了简化起见，我们假设类本身没有类（在Python中，类确实有类；几乎所有类都共享同一个类，称为 type）。类可以响应 get 和 set 消息，以及 new 消息。

示例：创建类

def make_class(attributes, base_class=None):
    """返回一个新的类，即一个调度字典。"""
    def get_value(name):
        if name in attributes:
            return attributes[name]
        elif base_class is not None:
            return base_class['get'](name)
    
    def set_value(name, value):
        attributes[name] = value
    
    def new(*args):
        return init_instance(cls, *args)
    
    cls = {'get': get_value, 'set': set_value, 'new': new}
    return cls

初始化

def init_instance(cls, *args):
    """返回一个类型为cls的新对象，用args初始化。"""
    instance = make_instance(cls)
    init = cls['get']('__init__')
    if init:
        init(instance, *args)
    return instance

2.6.3 使用实现的对象

现在我们使用之前的银行账户示例，创建 Account 类、CheckingAccount 子类，以及每个类的实例。

示例：创建账户类

def make_account_class():
    """返回Account类，具有存款和取款方法。"""
    interest = 0.02

    def __init__(self, account_holder):
        self['set']('holder', account_holder)
        self['set']('balance', 0)

    def deposit(self, amount):
        """增加账户余额并返回新余额。"""
        new_balance = self['get']('balance') + amount
        self['set']('balance', new_balance)
        return self['get']('balance')

    def withdraw(self, amount):
        """减少账户余额并返回新余额。"""
        balance = self['get']('balance')
        if amount > balance:
            return '资金不足'
        self['set']('balance', balance - amount)
        return self['get']('balance')

    return make_class(locals())

创建账户实例

Account = make_account_class()  # 创建Account类
kirk_account = Account['new']('Kirk')  # 创建账户实例

使用 get 消息传递给 kirk_account，可以检索属性和方法。可以调用方法来更新账户余额。

获取账户持有者

kirk_account['get']('holder')  # 获取账户持有者

小结

本节展示了如何在不依赖内置对象系统的情况下实现面向对象编程，通过调度字典模拟实例和类的行为。通过这种方法，我们能够创建和管理对象，同时理解类的继承和属性的设置与获取机制。

---

2.7 对象抽象

对象系统允许程序员高效地构建和使用抽象数据表示。它的设计允许多种抽象数据表示在同一程序中共存。

对象抽象的一个核心概念是泛型函数，即可以接受多种不同类型值的函数。我们将考虑三种实现泛型函数的不同技术：共享接口、类型调度和类型强制。在构建这些概念的过程中，我们还将发现支持创建泛型函数的Python对象系统特性。

2.7.1 字符串转换

为了有效地表示数据，对象值应表现出它所代表的数据类型，包括生成自身的字符串表示。数据值的字符串表示在交互式语言（如Python）中尤为重要，因为在交互式会话中，Python会自动显示表达式值的字符串表示。

示例：基本字符串表示

>>> 12e12
12000000000000.0
>>> print(repr(12e12))  # repr返回可被eval评估为相同对象的字符串
12000000000000.0

在没有有效的字符串表示可以评估为原始值的情况下，Python通常会生成一个用尖括号括起来的描述。

>>> repr(min)
'<built-in function min>'

人类可读和Python可读的字符串表示

字符串的构造函数str通常与repr相吻合，但在某些情况下提供更易理解的文本表示。例如，对于日期，我们看到 str 和 repr 的区别：

from datetime import date
tues = date(2011, 9, 12)
>>> repr(tues)
'datetime.date(2011, 9, 12)'  # Python可读表示
>>> str(tues)
'2011-09-12'  # 更易理解的人类可读表示

实现__repr__和__str__方法

我们希望repr函数能适用于所有数据类型，包括那些在实现时不存在的数据类型。我们希望它是一个泛型或多态函数，能应用于多种（poly）不同形式（morph）的数据。对象系统在这种情况下提供了优雅的解决方案：repr函数总是调用其参数的__repr__方法。

>>> tues.__repr__()
'datetime.date(2011, 9, 12)'  # 调用__repr__方法

同样，str构造函数通过调用其参数的__str__方法实现：

>>> tues.__str__()
'2011-09-12'  # 调用__str__方法

这些多态函数是一个更一般原则的例子：某些函数应该适用于多种数据类型。创建这样的函数的一种方法是使用共享属性名，并在每个类中定义不同的实现。

2.7.2 特殊方法

在Python中，某些特殊名称在特定情况下由Python解释器自动调用。例如，类的__init__方法在构造对象时自动调用；__str__方法在打印时自动调用，__repr__方法在交互式会话中显示值时调用。

布尔值

所有Python对象都有一个布尔值。默认情况下，用户定义类的对象被认为是True，但可以使用特殊的__bool__方法覆盖此行为。例如，我们可以让余额为0的银行账户被视为False：

Account.__bool__ = lambda self: self['get']('balance') != 0  # 定义__bool__方法

可以通过调用bool构造函数来查看对象的布尔值，并在布尔上下文中使用任何对象。

>>> bool(Account('Jack'))  # 查看账户的布尔值
False
>>> if not Account('Jack'):
        print('Jack has nothing')  # 输出: Jack has nothing

序列操作

我们可以使用len函数确定序列的长度，该函数调用其参数的__len__方法。

>>> len('Go Bears!')
9
>>> 'Go Bears!'.__len__()  # 直接调用__len__方法
9

如果序列未提供__bool__方法，Python会使用序列的长度来确定其布尔值。空序列为False，而非空序列为True。

>>> bool('')  # 空字符串
False
>>> bool('Go Bears!')  # 非空字符串
True

可调用对象

在Python中，函数是第一类对象，可以像数据一样传递，并具有与其他对象相同的属性。Python还允许我们通过包含__call__方法来定义可以像函数一样“调用”的对象。

class Adder(object):
    def __init__(self, n):
        self.n = n
    def __call__(self, k):
        return self.n + k

add_three_obj = Adder(3)  # 创建一个Adder对象
>>> add_three_obj(4)  # 调用对象
7

算术运算

特殊方法还可以定义应用于用户定义对象的内置运算符的行为。为了提供这种通用性，Python遵循特定协议来应用每个运算符。例如，为了评估包含+运算符的表达式，Python首先检查左操作数的__add__方法，然后检查右操作数的__radd__方法。

2.7.3 多重表示法

抽象屏障 允许我们分离数据的使用与表示。然而，在大型程序中，可能并不总是能谈论“数据类型的底层表示”。可能会有多个有用的表示方式，我们希望设计能处理多重表示的系统。

示例：复数的表示

复数可以用两种方式表示：矩形形式（实部和虚部）和极坐标形式（幅度和角度）。在不同情况下，两种形式可能都更合适。例如，矩形形式便于加法，而极坐标形式更适合于乘法。

以下是复数类的定义：

class Number:
    def __add__(self, other):
        return self.add(other)

    def __mul__(self, other):
        return self.mul(other)

这里的 Number 类需要实现 add 和 mul 方法，但没有定义它们。这意味着 Number 不是直接实例化的，而是作为具体数字类的超类。

复数类的实现

复数类 Complex 继承自 Number，并定义了复数的加法和乘法：

class Complex(Number):
    def add(self, other):
        return ComplexRI(self.real + other.real, self.imag + other.imag)
    
    def mul(self, other):
        magnitude = self.magnitude * other.magnitude
        return ComplexMA(magnitude, self.angle + other.angle)

复数的矩形表示

ComplexRI 类使用实部和虚部表示复数，并通过 @property 装饰器计算幅度和角度：

from math import atan2

class ComplexRI(Complex):
    def __init__(self, real, imag):
        self.real = real
        self.imag = imag

    @property
    def magnitude(self):
        return (self.real ** 2 + self.imag ** 2) ** 0.5

    @property
    def angle(self):
        return atan2(self.imag, self.real)

    def __repr__(self):
        return 'ComplexRI({0:g}, {1:g})'.format(self.real, self.imag)

使用示例：

ri = ComplexRI(5, 12)
print(ri.real)        # 输出：5
print(ri.magnitude)   # 输出：13.0
ri.real = 9
print(ri.magnitude)   # 输出：15.0

复数的极坐标表示

ComplexMA 类使用幅度和角度表示复数：

from math import sin, cos, pi

class ComplexMA(Complex):
    def __init__(self, magnitude, angle):
        self.magnitude = magnitude
        self.angle = angle

    @property
    def real(self):
        return self.magnitude * cos(self.angle)

    @property
    def imag(self):
        return self.magnitude * sin(self.angle)

    def __repr__(self):
        return 'ComplexMA({0:g}, {1:g} * pi)'.format(self.magnitude, self.angle/pi)

使用示例：

ma = ComplexMA(2, pi/2)
print(ma.imag)       # 输出：2.0
ma.angle = pi
print(ma.real)       # 输出：-2.0

2.7.4 泛型函数

泛型函数 是适用于不同类型参数的方法或函数。例如，Complex.add 方法可以接受 ComplexRI 或 ComplexMA 作为参数。

示例：有理数类

为了实现复数与有理数的混合操作，我们可以定义 Rational 类：

from fractions import gcd

class Rational(Number):
    def __init__(self, numer, denom):
        g = gcd(numer, denom)
        self.numer = numer // g
        self.denom = denom // g

    def add(self, other):
        nx, dx = self.numer, self.denom
        ny, dy = other.numer, other.denom
        return Rational(nx * dy + ny * dx, dx * dy)

    def mul(self, other):
        numer = self.numer * other.numer
        denom = self.denom * other.denom
        return Rational(numer, denom)

类型调度

通过类型调度，我们可以基于参数的类型选择行为：

def is_real(c):
    """判断复数c是否为实数（没有虚部）"""
    if isinstance(c, ComplexRI):
        return c.imag == 0
    elif isinstance(c, ComplexMA):
        return c.angle % pi == 0

结论

通过抽象屏障和接口，我们可以在同一个程序中实现多种不同的数据表示。泛型函数允许我们在不改变程序意义的情况下，灵活处理不同类型的数据。

注意事项

• 多重表示法 有助于应对复杂系统中不同的设计选择。
• 泛型函数 提供了对不同类型的操作能力，增强了代码的灵活性与可维护性。
• 类型调度 和 类型强制 是实现泛型函数的两种重要方法。

---

2.8 效率

2.8.1 测量效率

效率通常是由表示和处理数据的方式决定的。效率指的是某个表示或过程所需的计算资源，比如计算某个函数的结果所需的时间和内存。这些资源的使用情况可能因实现的细节而有所不同。

斐波那契函数

我们用计算斐波那契数列的树递归函数 fib 作为例子：

def fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib(n-2) + fib(n-1)

例如，调用 fib(5) 时，计算过程呈现树状结构。每个蓝点表示完成的斐波那契数计算。该函数效率低下，因为存在大量重复计算，特别是计算 fib(3) 的过程会被重复多次。

计算调用次数

为了测量这个效率，可以使用高阶函数 count 来记录调用次数：

def count(f):
    def counted(*args):
        counted.call_count += 1
        return f(*args)
    counted.call_count = 0
    return counted

fib = count(fib)
fib(19)
print(fib.call_count)  # 输出：13529

空间复杂度

在评估函数的空间需求时，我们需要了解在计算环境中如何使用、保留和回收内存。评估表达式时，解释器会保留所有活动环境及其引用的值。树递归函数的空间需求通常与树的最大深度成正比。

例如，调用 fib(3) 的环境结构显示如下：

fib(3)
 ├─ fib(1)  # 完成后可回收
 └─ fib(2)
     ├─ fib(0)  # 完成后可回收
     └─ fib(1)  # 活跃状态

使用帧计数器

使用 count_frames 函数来跟踪活动帧的数量：

def count_frames(f):
    def counted(*args):
        counted.open_count += 1
        counted.max_count = max(counted.max_count, counted.open_count)
        result = f(*args)
        counted.open_count -= 1
        return result
    counted.open_count = 0
    counted.max_count = 0
    return counted

fib = count_frames(fib)
fib(19)
print(fib.open_count)  # 输出：0
print(fib.max_count)   # 输出：19

总结一下，fib 函数的空间需求与输入大小 n 的关系是 \(\Theta(n)\)，而时间需求则是 \(\Theta(\phi^n)\)，其中 \(\phi\) 是黄金比例。

2.8.2 备忘录化

树递归计算过程可以通过备忘录化技术提高效率。备忘录化会存储任何先前接收参数的返回值，以避免重复计算。

备忘录化的实现

以下定义创建了一个缓存来存储之前计算的结果：

def memo(f):
    cache = {}
    def memoized(n):
        if n not in cache:
            cache[n] = f(n)
        return cache[n]
    return memoized

将备忘录化应用于斐波那契函数，计算过程的模式如下：

counted_fib = count(fib)
fib = memo(counted_fib)
fib(19)
print(counted_fib.call_count)  # 输出：20

2.8.3 增长阶数

计算过程中消耗空间和时间的速度可能相差很大。通过增长阶数来分析过程，可以有效地描述资源需求如何随输入增长。

示例：因数计数

以下函数计算输入 n 的因数数量：

from math import sqrt

def count_factors(n):
    sqrt_n = sqrt(n)
    k, factors = 1, 0
    while k < sqrt_n:
        if n % k == 0:
            factors += 2
        k += 1
    if k * k == n:
        factors += 1
    return factors

result = count_factors(576)  # 输出：21

复杂度分析

count_factors(n) 的执行时间为 \(\Theta(\sqrt{n})\)。这意味着总的计算步骤与输入的平方根成正比。

2.8.4 示例：指数计算

计算给定数字的指数可以通过以下递归实现：

def exp(b, n):
    if n == 0:
        return 1
    return b * exp(b, n-1)

这种线性递归过程的时间复杂度为 \(\Theta(n)\)，空间复杂度也为 \(\Theta(n)\)。

使用快速幂法

通过快速幂法，我们可以减少所需的步骤，例如：

def fast_exp(b, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        return square(fast_exp(b, n//2))
    else:
        return b * fast_exp(b, n-1)

在此实现中，所需的步骤和空间复杂度均为 \(\Theta(\log n)\)。

2.8.5 增长类别

增长阶数帮助简化分析和比较计算过程，许多不同的过程可能具有相同的增长阶数。

常见类别

类别	Theta 表示	增长描述	示例
常数	\(\Theta(1)\)	增长与输入无关	abs
对数	\(\Theta(\log n)\)	输入增加资源增加	fast_exp
线性	\(\Theta(n)\)	输入增加资源线性增加	exp
二次	\(\Theta(n^2)\)	输入增加资源以平方速度增加	one_more
指数	\(\Theta(b^n)\)	输入增加资源以指数速度增加	fib

对于快速增长的过程，变化的基数会影响增长阶数。

通过以上内容，可以更好地理解时间和空间复杂度，以及如何通过不同的技术提高效率。

---

2.9 递归对象

对象可以具有其他对象作为属性值。当一个类的对象具有该类的属性值时，它就是一个递归对象。这种结构在编程中非常有用，特别是在处理复杂数据结构时，如链表、树等。

2.9.1 链表类

链表是一种递归定义的数据结构，由一个首元素和其余部分组成。链表的其余部分本身也是一个链表。这种定义是递归的，因而形成了链表的特性。空链表是一个特殊的链表，它没有首元素或其余部分。

链表的特点包括：

• 有限长度：链表的长度是有限的，可以通过递归方法计算。
• 元素选择：支持通过索引选择元素。

实现链表类

下面我们实现一个链表类 Link，以便能够使用内置的 len 函数和元素选择操作符（如方括号或 operator.getitem）进行操作。这些内置函数会调用类的特殊方法名：

• __len__：计算链表的长度。
• __getitem__：获取链表中的元素。

在实现中，空链表用一个空元组表示，它的长度为 0，并且没有元素。

class Link:
    """一个具有首元素和其余部分的链表。"""
    empty = ()  # 定义空链表
    
    def __init__(self, first, rest=empty):
        # 确保 rest 是空元组或 Link 的实例
        assert rest is Link.empty or isinstance(rest, Link)
        self.first = first  # 首元素
        self.rest = rest  # 其余部分
        
    def __getitem__(self, i):
        # 通过索引获取元素
        if i == 0:
            return self.first
        else:
            return self.rest[i - 1]
        
    def __len__(self):
        # 计算链表的长度
        return 1 + len(self.rest)

# 创建一个链表实例
s = Link(3, Link(4, Link(5)))
print(len(s))  # 输出：3，表示链表的长度
print(s[1])    # 输出：4，获取索引为 1 的元素

在上述代码中，__len__ 和 __getitem__ 的定义实际上是递归的。当调用 len(s) 时，Python 内置函数 len 会调用 s 的 __len__ 方法。在这个方法中，我们递归地调用 len(self.rest)，直到 self.rest 为 Link.empty，这时返回 0。类似地，__getitem__ 方法也会递归地调用自身，以获取所需的元素。

调试和字符串表示

为了方便调试，我们可以定义一个函数将链表转换为字符串表达式，以便查看链表的内容。

def link_expression(s):
    """返回一个字符串，该字符串可以求值为 s。"""
    if s.rest is Link.empty:
        rest = ''
    else:
        rest = ', ' + link_expression(s.rest)  # 递归获取剩余部分的表达式
    return 'Link({0}{1})'.format(s.first, rest)

# 显示链表的字符串表示
print(link_expression(s))  # 输出：'Link(3, Link(4, Link(5)))'

我们希望在每次显示 Link 实例时都使用这个字符串表示。为此，可以将 link_expression 函数设置为特殊类属性 __repr__ 的值，Python 将通过调用该方法来显示 Link 实例。

Link.__repr__ = link_expression
print(s)  # 输出：Link(3, Link(4, Link(5)))

链表的嵌套

Link 类具有闭包属性。就像一个列表的元素本身可以是一个列表一样，一个 Link 可以将另一个 Link 作为其首元素。

# 创建一个嵌套的链表
s_first = Link(s, Link(6))
print(s_first)  # 输出：Link(Link(3, Link(4, Link(5))), Link(6))

在这个例子中，s_first 链表有两个元素，其中第一个元素是一个链表，包含三个元素，第二个元素是数字 6。

递归处理链表

递归函数特别适合处理链表。例如，递归 extend_link 函数构建一个包含 Link 实例 s 的元素后跟 Link 实例 t 的链表。将此函数安装为 Link 类的 __add__ 方法可以模拟内置列表的加法行为。

def extend_link(s, t):
    """将两个链表 s 和 t 连接起来。"""
    if s is Link.empty:
        return t  # 如果 s 为空，返回 t
    else:
        return Link(s.first, extend_link(s.rest, t))  # 递归连接

# 执行链表加法
print(extend_link(s, s))  # 输出：Link(3, Link(4, Link(5, Link(3, Link(4, Link(5))))))
Link.__add__ = extend_link
print(s + s)  # 输出：Link(3, Link(4, Link(5, Link(3, Link(4, Link(5))))))

使用高阶函数处理链表

而不是使用列表推导式，可以使用两个高阶函数：map_link 和 filter_link 从一个链表生成另一个链表。以下定义的 map_link 函数将函数 f 应用到链表 s 的每个元素，并构建一个包含结果的链表。

def map_link(f, s):
    """将函数 f 应用到链表 s 的每个元素。"""
    if s is Link.empty:
        return s  # 如果链表为空，返回空链表
    else:
        # 递归构建新的链表
        return Link(f(s.first), map_link(f, s.rest))

# 定义一个平方函数
def square(x):
    return x * x

# 应用 map_link 函数
print(map_link(square, s))  # 输出：Link(9, Link(16, Link(25)))，每个元素平方

filter_link 函数返回一个链表，包含链表 s 中所有 f 返回真值的元素。可以使用 map_link 和 filter_link 的组合来表达与列表推导式相同的逻辑。

def filter_link(f, s):
    """返回链表 s 中所有满足条件 f 的元素。"""
    if s is Link.empty:
        return s  # 如果链表为空，返回空链表
    else:
        filtered = filter_link(f, s.rest)  # 递归过滤
        if f(s.first):
            return Link(s.first, filtered)  # 如果满足条件，加入链表
        else:
            return filtered  # 否则直接返回过滤后的链表

# 定义一个判断奇数的函数
odd = lambda x: x % 2 == 1

# 使用 map 和 filter 组合
print(map_link(square, filter_link(odd, s)))  # 输出：Link(9, Link(25))
print([square(x) for x in [3, 4, 5] if odd(x)])  # 输出：[9, 25]

连接链表的元素

join_link 函数递归构建一个包含链表元素的字符串，并以某个分隔符字符串分隔。结果比 link_expression 的输出更紧凑。

def join_link(s, separator):
    """返回一个由链表元素构成的字符串，元素之间用 separator 分隔。"""
    if s is Link.empty:
        return ""  # 如果链表为空，返回空字符串
    elif s.rest is Link.empty:
        return str(s.first)  # 如果只有一个元素，返回该元素
    else:
        return str(s.first) + separator + join_link(s.rest, separator)  # 递归连接

# 连接链表元素
print(join_link(s, ", "))  # 输出：'3, 4, 5'

递归构造示例

链表在递归计算时非常有用，尤其是在逐步构建序列时，这种情况经常发生。例如，我们可以使用递归方法来列举划分。

在第 1 章中，count_partitions 函数计算了使用不大于 m 的部分来划分整数 n 的方式。我们还可以使用类似的过程明确列举这些划分。

划分 n 使用不大于 m 的整数主要有两种方式：

1. 使用 m 的划分：划分 n-m 使用不大于 m 的整数。
2. 不使用 m 的划分：划分 n 使用不大于 m-1 的整数。

以下是关于树类和集合的学习笔记，包含适当的例子及时间复杂度的分析，使用了LaTeX格式。

2.9.2 树类

树可以通过用户定义的类表示，而不是嵌套的内置序列类型。树是任何数据结构，其属性是一个分支序列，这些分支也是树。

内部值

我们之前定义的树使所有值出现在树的叶子上。现在，我们定义树，使每个子树的根也有内部值。内部值在树中被称为标签。下面的 Tree 类表示这样的树，每棵树有一系列分支，分支也是树。

class Tree:
    def __init__(self, label, branches=()):
        self.label = label
        for branch in branches:
            assert isinstance(branch, Tree)
        self.branches = branches
        
    def __repr__(self):
        if self.branches:
            return 'Tree({0}, {1})'.format(self.label, repr(self.branches))
        else:
            return 'Tree({0})'.format(repr(self.label))
        
    def is_leaf(self):
        return not self.branches

例子：斐波那契树

fib_tree(n) 函数返回一个 Tree，其中包含第 n 个斐波那契数作为标签，并在其分支中追踪之前计算的所有斐波那契数。

def fib_tree(n):
    if n == 1:
        return Tree(0)
    elif n == 2:
        return Tree(1)
    else:
        left = fib_tree(n-2)
        right = fib_tree(n-1)
        return Tree(left.label + right.label, (left, right))

# 示例
fib_tree(5)

输出：

Tree(3, (Tree(1, (Tree(0), Tree(1))), Tree(2, (Tree(1), Tree(1, (Tree(0), Tree(1)))))))

递归处理

我们可以使用递归函数来计算树的标签之和。作为基例，返回空分支的标签和为0。

def sum_labels(t):
    """计算树实例的标签之和，可以是None。"""
    return t.label + sum([sum_labels(b) for b in t.branches])

# 示例
sum_labels(fib_tree(5))

输出：

10

2.9.3 集合

Python 还有一种内置的容器类型叫做集合（set）。集合文字遵循数学符号的表示方式，元素用大括号括起来。重复元素在构造时被移除。集合是无序的，因此打印顺序可能与集合文字中的元素顺序不同。

s = {3, 2, 1, 4, 4}
print(s)  # 输出 {1, 2, 3, 4}

集合操作

集合支持多种操作，包括成员测试、长度计算以及并集和交集等标准集合操作。

# 成员测试
3 in s  # 输出 True

# 计算长度
len(s)  # 输出 4

# 并集
s.union({1, 5})  # 输出 {1, 2, 3, 4, 5}

# 交集
s.intersection({6, 5, 4, 3})  # 输出 {3, 4}

集合的实现

作为无序序列的集合

一种表示集合的方法是将其视为一个不包含重复元素的序列。空集合由空序列表示。成员测试通过递归遍历列表。

def empty(s):
    return s is Link.empty

def set_contains(s, v):
    """如果集合 s 包含 v，则返回 True。"""
    if empty(s):
        return False
    elif s.first == v:
        return True
    else:
        return set_contains(s.rest, v)

s = Link(4, Link(1, Link(5)))
set_contains(s, 2)  # 输出 False
set_contains(s, 5)  # 输出 True

此实现的 set_contains 在平均情况下需要 \(\Theta(n)\) 时间，\(n\) 是集合 s 的大小。

作为有序序列的集合

通过将集合元素按升序列出，可以加速集合操作。

def set_contains(s, v):
    if empty(s) or s.first > v:
        return False
    elif s.first == v:
        return True
    else:
        return set_contains(s.rest, v)

u = Link(1, Link(4, Link(5)))
set_contains(u, 0)  # 输出 False
set_contains(u, 4)  # 输出 True

在最坏情况下，查找的步骤与无序表示相同，但在平均情况下，预计需要检查约一半的元素，因此平均所需的步骤为 \(\Theta(n)\)。

作为二叉搜索树的集合

我们可以使用二叉树来表示集合，树的根节点包含一个元素，左分支包含所有小于根的元素，右分支包含所有大于根的元素。

def set_contains(s, v):
    if s is None:
        return False
    elif s.entry == v:
        return True
    elif s.entry < v:
        return set_contains(s.right, v)
    elif s.entry > v:
        return set_contains(s.left, v)

# 结合前面的 adjoin_set 函数
def adjoin_set(s, v):
    if s is None:
        return Tree(v)
    elif s.entry == v:
        return s
    elif s.entry < v:
        return Tree(s.entry, s.left, adjoin_set(s.right, v))
    elif s.entry > v:
        return Tree(s.entry, adjoin_set(s.left, v), s.right)

# 示例
adjoin_set(adjoin_set(adjoin_set(None, 2), 3), 1)

输出：

Tree(2, Tree(1), Tree(3))

时间复杂度

• 在无序集合中，集合操作的时间复杂度为 \(\Theta(n^2)\)。
• 在有序集合中，查找的时间复杂度为 \(\Theta(n)\)，而交集操作可以优化为 \(\Theta(n)\)。
• 在平衡的二叉搜索树中，查找和添加元素的时间复杂度为 \(\Theta(\log n)\)，这对大集合的性能有显著提升。

Python 集合实现

Python 内置的集合类型使用了一种基于哈希的技术实现，提供常数时间的成员测试和添加操作。由于哈希的性质，内置的 Python 集合不能包含可变数据类型，例如列表和字典。为允许嵌套集合，Python 还包括一个内置的不可变类 frozenset。

---

第三章：解释计算机程序

3.1 介绍

第一、二章探讨了编程中两个基本要素——函数与数据之间的紧密联系。我们看到如何使用高阶函数将函数视为数据来操作，也了解了通过消息传递和面向对象系统赋予数据行为。此外，还学习了组织大型程序的技术，如函数抽象、数据抽象、类继承和泛型函数。这些核心概念为构建模块化、可维护、可扩展的程序奠定了坚实的基础。

本章重点介绍编程的第三个基本要素：程序本身。Python程序仅仅是一段文本，只有通过解释过程，才能基于该文本进行有意义的计算。像Python这样的编程语言之所以有用，是因为我们可以定义一个解释器——这个程序执行Python的求值和执行过程。可以说，解释器是编程中最基本的思想，它决定了编程语言中的表达式意义，而解释器本身也只是一个程序。

理解这一点会改变我们作为程序员的自我认知：我们不仅仅是使用他人设计语言的用户，而是语言的设计者。

3.1.1 编程语言

编程语言在其语法结构、功能和应用领域方面有很大差异。在通用编程语言中，函数定义和函数应用是普遍存在的构造。然而，有些强大的语言不包含面向对象系统、高阶函数、赋值操作，甚至不包含控制结构（如while和for循环）。作为一个具有最小特性集合的强大语言的例子，文中引入了Scheme编程语言。本书介绍的Scheme子集完全不允许可变值。

本章我们研究解释器的设计以及其在执行程序时创建的计算过程。设计一个通用编程语言的解释器似乎是一项艰巨的任务，毕竟解释器是根据输入执行任何可能计算的程序。然而，许多解释器具有一种优雅的共同结构：两个相互递归的函数。第一个在环境中求值表达式，第二个将函数应用于参数。

这些函数是递归的，因为它们是基于彼此定义的：应用一个函数需要对其主体中的表达式进行求值，而求值表达式可能涉及应用一个或多个函数。

通过这一学习笔记，我们可以更好地理解程序设计中的解释器设计思想，并将程序员的角色从语言的使用者转变为语言的设计者。

---

3.2 函数式编程

现代计算机上的软件使用多种编程语言编写。有物理语言，如特定计算机的机器语言。这些语言关注数据的表示和控制，涉及存储的位数和原始的机器指令。机器语言程序员专注于使用现有硬件构建系统和工具，以高效实现资源受限的计算。高层语言建立在机器语言的基础上，隐藏了关于数据作为位集合表示以及程序作为原始指令序列表示的关切。这些语言具有组合和抽象手段，如函数定义，适用于软件系统的大规模组织。

本节我们将介绍一种鼓励使用函数式编程风格的高级编程语言——Scheme语言的一个子集。它与Python有类似的计算模型，但只使用表达式（没有语句）、专注于符号计算，并只使用不可变的值。

3.2.1 表达式

Scheme程序由表达式组成，这些表达式要么是调用表达式，要么是特殊形式。调用表达式由操作符表达式和零个或多个操作数子表达式组成，类似于Python。操作符和操作数都包含在括号内：

(quotient 10 2)

结果是 5。Scheme完全使用前缀表示法，运算符通常是符号，如+ 和 *。调用表达式可以嵌套，并且可以跨越多行：

(+ (* 3 5) (- 10 6))

结果是 19。

再来看一个复杂的嵌套表达式：

(+ (* 3
      (+ (* 2 4)
         (+ 3 5)))
   (+ (- 10 7)
      6))

结果是 57。

在Scheme中，表达式可以是原始的或组合的。数字字面量是原始的，而调用表达式是组合形式，包含任意的子表达式。Scheme的调用表达式的求值过程与Python类似：首先求值操作符和操作数表达式，然后将操作符的值（函数）应用于操作数的值（参数）。

3.2.2 定义

值可以使用define特殊形式命名，例如：

(define pi 3.14)
(* pi 2)

结果是 6.28。

可以使用define定义新的函数（Scheme中称为过程）：

(define (square x) (* x x))

然后我们可以通过以下方式调用它：

(square 21)  ; 441
(square (+ 2 5))  ; 49
(square (square 3))  ; 81

匿名函数可以使用lambda表达式创建：

(lambda (x) (* x x))

这一表达式与定义了函数的define相同，唯一的区别是它没有与任何名称关联。

3.2.3 复合值

Scheme中内置了对“对”（pair）的支持，使用cons函数创建，使用car和cdr函数访问对的元素：

(define x (cons 1 2))
(car x)  ; 1
(cdr x)  ; 2

可以使用递归定义列表，例如：

(cons 1 (cons 2 (cons 3 (cons 4 nil))))
; (1 2 3 4)

3.2.4 符号数据

Scheme中的一个优势是可以操作任意符号。使用单引号'可以构造符号列表，例如：

(list 'a 'b)  ; (a b)

这个单引号类似于引用操作，用来表示不进行求值，而是直接使用符号本身。

3.2.5 乌龟图形绘制（Turtle Graphics）

本节所介绍的Scheme实现中包含了Turtle图形绘制，这是一个源自Logo语言（另一种Lisp方言）的图形环境。乌龟图形绘制是通过让“乌龟”在画布上移动并绘制线条来实现的，最初旨在引导儿童学习编程，但它同样也是一个非常适合高级程序员的可视化工具。

在Scheme程序执行过程中，乌龟始终有一个位置和朝向。通过调用单参数过程，如forward和right，可以改变乌龟的当前位置和朝向。常用的指令有缩写，例如forward可以简写为fd。

多重命令

Scheme中的begin特殊形式允许在一个表达式中包含多个子表达式，适合用于发出多个命令，例如：

(define (repeat k fn) 
  (if (> k 0)
      (begin (fn) (repeat (- k 1) fn))
      nil))

这个定义了一个repeat函数，可以多次重复执行某个函数。

绘制五角星示例

可以使用repeat函数绘制复杂的图形，例如五角星：

(repeat 5
        (lambda () (fd 100)
                   (repeat 5
                           (lambda () (fd 20) (rt 144)))
                   (rt 144)))

递归绘制Sierpinski三角形

乌龟图形绘制还可以用于递归图形，例如Sierpinski三角形。以下是递归定义的Sierpinski三角形绘制过程：

• triangle：重复绘制三次，并在每次绘制后左转。
• sier：接受一个边长d和递归深度k的参数。如果深度为1，则绘制普通三角形；否则通过调用leg来递归绘制。
• leg：绘制Sierpinski三角形的一条边，包含对sier的递归调用，先绘制一半边长，然后乌龟移动到下一个顶点。

为了防止在乌龟移动时绘制多余的线条，可以使用penup和pendown过程抬起和放下乌龟的画笔。通过sier和leg的互相递归调用，可以绘制出完整的Sierpinski三角形。

(sier 400 6)

3.3 异常处理（Exceptions）

程序员在编写程序时，必须时刻注意可能出现的错误。常见的错误场景包括：函数接收到不符合要求的参数、所需资源缺失、或网络连接丢失。在设计程序时，应考虑可能出现的异常情况，并采取适当的措施进行处理。

没有统一的错误处理方法。对于提供持续服务的程序（如Web服务器），应在记录错误日志的同时尽可能继续提供服务。而对于解释型语言（如Python），解释器会立即终止程序并打印错误信息，方便程序员及时解决问题。无论如何，程序员都需要做出明确选择，决定程序在遇到异常时的反应。

异常的引发（Raising Exceptions）

异常（Exception）是一个从BaseException类继承的对象。当Python解释器检测到表达式或语句中的错误时，会自动引发异常。用户也可以使用raise或assert语句手动引发异常。

• 示例1：引发异常

  在下面的例子中，我们引发了一个基本的异常Exception，并输出了自定义的错误信息 "An error occurred"。

  >>> raise Exception('An error occurred')
  Traceback (most recent call last):
    File "<stdin>", line 1, in <module>
  Exception: an error occurred

  当引发异常后，当前代码块中的其他语句将不再执行。如果异常未被捕获和处理，解释器会直接返回到交互式会话或终止整个程序，并输出一个堆栈跟踪（stack backtrace），即展示异常发生时调用的嵌套函数。

异常的处理（Handling Exceptions）

可以通过try语句处理异常。try语句由多个子句组成，首先是try子句，后面是一个或多个except子句，用于捕获和处理不同类型的异常。

• 示例2：处理ZeroDivisionError异常

  在下面的例子中，尝试执行除法 1/0 时会引发 ZeroDivisionError。except 子句捕获到该异常，并输出处理信息，同时将 x 设置为 0。

  >>> try:
          x = 1 / 0
      except ZeroDivisionError as e:
          print('handling a', type(e))  # 输出异常类型
          x = 0  # 设置 x 为 0
  handling a <class 'ZeroDivisionError'>
  >>> x
  0

  当1 / 0导致ZeroDivisionError时，程序不会崩溃，而是跳转到except子句进行处理。在这个例子中，异常对象e被捕获并绑定到异常类ZeroDivisionError。

• 示例3：处理函数中的异常

  下面的示例演示了如何在函数中处理异常。我们定义了两个函数：invert 和 invert_safe。在 invert 函数中，除数为 0 时会引发 ZeroDivisionError；而在 invert_safe 中，我们通过 try-except 结构捕获该异常，并返回错误信息。

  >>> def invert(x):
          result = 1 / x  # 如果 x 为 0，会引发 ZeroDivisionError
          print('This will not print if x is 0')
          return result
  >>> def invert_safe(x):
          try:
              return invert(x)
          except ZeroDivisionError as e:
              return str(e)  # 返回异常描述信息
  >>> invert_safe(2)
  0.5
  >>> invert_safe(0)
  'division by zero'

  在这个例子中，当 invert(0) 引发ZeroDivisionError时，invert_safe(0)捕获到异常并返回错误信息'division by zero'，而不是让程序崩溃。

3.3.1 异常对象（Exception Objects）

异常对象可以拥有属性，如错误信息或异常发生的位置。用户还可以定义自己的异常类，并添加自定义属性。

• 示例4：定义自定义异常类

  在此例中，我们创建了一个名为IterImproveError的自定义异常类，继承自Exception，并增加了一个last_guess属性，用于存储迭代过程中的最后一个猜测值。

  >>> class IterImproveError(Exception):
          def __init__(self, last_guess):
              self.last_guess = last_guess

  该异常类可在迭代改进算法中使用，当迭代过程中发生异常时，我们可以将最新的猜测值保存下来。

• 示例5：在改进的牛顿法中使用自定义异常

  在这个示例中，改进的牛顿法使用了自定义的异常处理。improve 函数在发生 ValueError 时，会引发一个 IterImproveError 并存储当前猜测的值。find_zero 函数会捕获该异常并返回最后的猜测值。

  >>> def improve(update, done, guess=1, max_updates=1000):
          k = 0
          try:
              while not done(guess) and k < max_updates:
                  guess = update(guess)
                  k += 1
              return guess
          except ValueError:
              raise IterImproveError(guess)  # 引发自定义异常并保存最后的猜测值
  >>> def find_zero(f, guess=1):
          def done(x):
              return f(x) == 0
          try:
              return improve(newton_update(f), done, guess)
          except IterImproveError as e:
              return e.last_guess  # 返回最后的猜测值
  >>> from math import sqrt
  >>> find_zero(lambda x: 2 * x * x + sqrt(x))
  -0.030211203830201594

  尽管这个结果距离正确答案 \(0\) 仍有较大误差，但在某些应用中，能够返回一个粗略的近似值比抛出异常更有用。

时空复杂度分析（Time and Space Complexity Analysis）

1. 引发异常的时空复杂度：

   当程序执行raise语句引发异常时，程序的控制流会立刻跳转到最近的异常处理器。因此，raise语句的时间复杂度为 $ O(1) $，因为它的执行时间与异常处理逻辑的复杂度无关。空间复杂度也为 $ O(1) $，因为引发异常本身只涉及常量空间。

2. 异常处理的时空复杂度：

   对于try-except结构，try块中的代码的时间复杂度取决于其包含的代码逻辑。如果发生异常，程序会跳转到最近的except子句。这个跳转过程是常数时间的，因此异常处理的时间复杂度也是 $ O(1) $。在处理异常时，通常只绑定异常对象并执行一些处理逻辑，因此空间复杂度为 $ O(1) $。

3. 自定义异常类的时空复杂度：

   创建自定义异常类的时间复杂度主要体现在实例化操作上，这通常是常数时间 $ O(1) $。自定义异常对象的空间复杂度取决于其存储的属性，在示例4中，IterImproveError类只存储了一个last_guess属性，因此其空间复杂度也是 $ O(1) $。

4. 改进的牛顿法中的时空复杂度：

   在使用自定义异常的改进牛顿法中，假设最大迭代次数为 $ k $，则improve函数的时间复杂度为 $ O(k) $，因为它最多进行 $ k $ 次迭代。当发生异常时，异常处理器会保存最后的猜测值并返回，因此处理过程的时间复杂度为 $ O(1) $。同样，保存最后的猜测值只需常量空间，因此空间复杂度也是 $ O(1) $。

---

3.4 解释器与组合语言

概述

本节介绍了如何通过编写解释器（Interpreter）来定义新语言。解释器是一种函数，负责接受并执行一种编程语言的表达式。我们通过一个名为Calculator的Scheme子集语言来学习构建解释器的基本原理，最终将其扩展为Scheme的一个完整实现。

3.4.1 Scheme语法的计算器（Calculator）

Calculator是一种基于Scheme的简单语言，支持基本的四则运算（加、减、乘、除）。它的语法和运算符行为与Scheme类似。每个表达式都是一个列表，运算符是第一个元素，后面跟随参数。

示例

(+ 1 2 3 4) ; 结果为 10
(*)         ; 结果为 1
(- 10 1 2 3) ; 结果为 4
(/ 30 5 2)  ; 结果为 3

解释：

• (+ 1 2 3 4) 代表求和运算，输出 10。
• (*) 表示乘法的空操作，返回 1。
• (- 10 1 2 3) 计算结果为 10 - 1 - 2 - 3，输出 4。
• (/ 30 5 2) 表示 30 除以 5 再除以 2，输出 3。

3.4.2 表达式树（Expression Trees）

要编写解释器，我们需要将输入的表达式作为数据进行操作。一个基本表达式可以是数字或符号，而组合表达式通常是一个嵌套的Scheme列表。我们通过Python的Pair类模拟Scheme中的列表结构。

示例

# Pair类用于构建表达式树
class Pair:
    def __init__(self, first, second):
        self.first = first  # 表示列表中的第一个元素
        self.second = second  # 表示剩余的部分（即列表的尾部）

# 构建列表 (1 2) 对应于 Scheme 中的 (1 2)
s = Pair(1, Pair(2, nil))

# 构建表达式 (+ (* 3 4) 5)
expr = Pair('+', Pair(Pair('*', Pair(3, Pair(4, nil))), Pair(5, nil)))

# 输出嵌套表达式树：(+ (* 3 4) 5)
print(expr)

• 在这个例子中，Pair 类的实例用于构建表达式树，表达式树的结构体现了嵌套的操作，例如 ( + (* 3 4) 5)。最终的计算结果是 17。

3.4.3 解析表达式（Parsing Expressions）

表达式解析的第一步是将输入的字符串解析成语法单元（Token）。然后，语法单元再进一步解析为嵌套的表达式树。

词法分析：将输入字符串切割成符号（Token），如数字和运算符。

语法分析：将Token序列转换为嵌套的表达式树。

示例

# Scheme读取函数：将输入的字符串解析为表达式树
lines = ['(+ 1', '   (* 2.3 45))']
expression = scheme_read(Buffer(tokenize_lines(lines)))

# 解析结果：表达式树 (+ 1 (* 2.3 45))
print(expression)

• scheme_read 函数使用递归的方法将语法单元（Token）序列解析为嵌套的表达式树，类似于解析嵌套的Scheme列表。

3.4.4 计算器的求值（Evaluation of Expressions）

计算器解释器的核心是一个递归的求值函数 calc_eval。这个函数的基本思路是：

• 如果表达式是数字，直接返回该数字。
• 如果表达式是组合表达式（列表），则递归地对每个操作数求值，然后将结果传递给相应的运算符进行计算。

代码与注释

def calc_eval(exp):
    """
    对表达式进行求值。
    - 如果exp是数字，直接返回其值。
    - 如果exp是一个组合表达式（列表），对每个操作数递归求值，然后调用calc_apply处理操作符。
    """
    if type(exp) in (int, float):  # 如果表达式是数字类型
        return simplify(exp)  # 直接返回
    elif isinstance(exp, Pair):  # 如果表达式是一个Pair，即组合表达式
        # 递归地求解参数部分，并将结果存入arguments列表
        arguments = exp.second.map(calc_eval)
        # 调用calc_apply函数根据操作符执行运算
        return simplify(calc_apply(exp.first, arguments))
    else:
        raise TypeError(f'{exp} is not a number or call expression')  # 如果表达式既不是数字也不是组合表达式，则报错

calc_apply函数负责应用操作符，它根据传入的操作符和参数执行相应的运算。

示例

def calc_apply(operator, args):
    """
    根据operator对args进行相应的计算。
    支持的操作符包括 +, -, *, /。
    """
    if operator == '+':  # 加法
        return reduce(add, args, 0)  # 使用add函数将所有参数相加
    elif operator == '-':  # 减法
        if len(args) == 1:
            return -args.first  # 单一参数时返回其相反数
        else:
            return reduce(sub, args.second, args.first)  # 多个参数时依次相减
    elif operator == '*':  # 乘法
        return reduce(mul, args, 1)  # 使用mul函数将所有参数相乘
    elif operator == '/':  # 除法
        if len(args) == 1:
            return 1 / args.first  # 单一参数时返回其倒数
        else:
            return reduce(truediv, args.second, args.first)  # 多个参数时依次相除
    else:
        raise TypeError(f'Unknown operator: {operator}')  # 如果操作符未知，抛出异常

示例

(+ (* 3 4) 5)  ; 输出为17

• (+ (* 3 4) 5) 的求值过程首先计算内层表达式 (* 3 4)，其结果为 12。然后计算外层表达式 ( + 12 5)，结果为 17。

3.4.5 交互式求值循环（REPL）

交互式解释器的经典实现是REPL（Read-Eval-Print Loop），它不断地读取用户输入、对表达式进行求值并打印结果。以下是一个简单的REPL实现，它能够处理用户的输入并返回相应的计算结果。

示例

def read_eval_print_loop():
    """
    REPL 循环：
    1. 读取用户输入的表达式。
    2. 解析并求值。
    3. 打印结果。
    """
    while True:
        try:
            # 读取输入行，并解析为表达式
            src = buffer_input()
            while src.more_on_line:
                expression = scheme_read(src)
                print(calc_eval(expression))  # 对表达式求值并打印结果
        except (SyntaxError, TypeError, ValueError, ZeroDivisionError) as err:
            # 处理各种错误并打印错误信息
            print(type(err).__name__ + ':', err)
        except (KeyboardInterrupt, EOFError):
            # 捕获退出命令（Ctrl+C 或 Ctrl+D）
            print('Calculation completed.')
            return

这个函数实现了REPL的基本功能：

• 读取用户输入，并通过scheme_read解析为表达式树。
• 求值表达式，并通过calc_eval函数计算其结果。
• 打印求值结果，并在发生错误时捕捉并处理异常。

总结

通过编写一个简单的解释器，我们学习了如何解析表达式树、递归求值以及处理错误。这些是解释器和编译器设计中的基本概念。

---

3.5 支持抽象的语言解释器

概述

在这一节中，我们从简单的计算器语言（Calculator）转向更为通用的Scheme语言，该语言支持抽象，通过绑定名称到值，并定义新的操作来实现更复杂的计算。我们将描述如何构建一个支持抽象的解释器，并探讨环境模型及其在计算中的作用。

3.5.1 解释器的结构

Scheme解释器的结构与之前的计算器解释器类似。它的基本流程包括解析表达式并通过求值器（Evaluator）执行表达式。不同之处在于Scheme语言支持用户定义的函数、特殊形式（Special Forms），并且依赖环境模型进行计算。

解析（Parsing）：
解析过程由scheme_reader模块实现，该模块可以将Scheme表达式解析为嵌套的数据结构。然而，目前它还不支持点对列表（dotted lists）和引用（quotation）。要实现一个完整的Scheme解释器，我们需要扩展该模块。

示例

(car '(1 . 2))  ; 解析为 (car (quote (1 . 2)))

解释：
(car '(1 . 2)) 是一个调用表达式，quote 引用了一个点对列表 (1 . 2)。我们需要能够正确地解析这些语法结构。

求值（Evaluation）：
求值是逐个表达式进行的。scheme_eval函数负责在当前环境下求值每个表达式。求值的主要内容包括三种形式：

1. 原子表达式（Primitive）
   
2. 特殊形式（Special Forms）
   
3. 调用表达式（Call Expressions）

scheme_eval函数会根据表达式的第一部分来决定如何处理。每种特殊形式都有其独特的求值规则。以下是一个简化的scheme_eval实现：

示例

def scheme_eval(expr, env):
    """
    在环境env中求值Scheme表达式expr。
    - 如果expr是符号，返回其在环境中的值。
    - 如果expr是原子，直接返回。
    - 如果是组合表达式，根据其第一部分判断操作类型。
    """
    if scheme_symbolp(expr):
        return env[expr]  # 查找符号在环境中的值
    elif scheme_atomp(expr):
        return expr  # 返回原子值
    first, rest = expr.first, expr.second
    if first == "lambda":
        return do_lambda_form(rest, env)  # 处理lambda表达式
    elif first == "define":
        do_define_form(rest, env)  # 处理define表达式
        return None
    else:
        # 求值函数调用表达式
        procedure = scheme_eval(first, env)
        args = rest.map(lambda operand: scheme_eval(operand, env))
        return scheme_apply(procedure, args, env)  # 应用函数

解释：
这个函数首先检查表达式类型，如果是符号则在当前环境中查找其绑定的值。如果是组合表达式（列表），则根据其第一部分来决定是特殊形式还是普通的函数调用。

函数调用（Procedure Application）：
scheme_apply函数负责函数调用的实际执行。Scheme支持两种函数类型：

1. 原生函数（PrimitiveProcedure）：用Python实现的函数。
2. Lambda函数（LambdaProcedure）：用Scheme实现的函数。

每个LambdaProcedure都包含一个body，该body是在一个新的环境中求值的。新的环境通过扩展当前环境来构造，参数列表中的符号与实际传入的参数值绑定。

示例：

(lambda (x) (+ x 1))  ; 一个简单的Lambda表达式

解释：
在调用LambdaProcedure时，会为参数x创建一个新的环境，将传入的实际值绑定到x，然后对(+ x 1)进行求值。

求值/应用的递归关系：
scheme_eval和scheme_apply是相互递归的。求值函数在遇到调用表达式时调用scheme_apply，而函数应用则依赖求值来解析操作数。这种互相递归的结构在解释器中非常常见，它是解释器求值过程的核心。

3.5.2 环境（Environments）

环境的作用：
解释器中的环境模型由Frame类实现。每个Frame实例代表一个符号绑定到值的环境，并且有一个指向父环境的引用。通过这种方式，可以支持嵌套作用域。

环境的主要操作有两个：

1. lookup（查找）： 查找符号在环境中的值。如果当前环境没有找到，会递归查找父环境。
2. define（定义）： 在当前环境中绑定符号到值。

示例

(define (factorial n)
  (if (= n 0) 1 (* n (factorial (- n 1)))))
(factorial 5)  ; 计算结果为120

解释：
define创建了一个LambdaProcedure，其参数为n，在调用factorial时，会为n创建一个新的环境并绑定其值为5。接下来，解释器在这个新的环境中对factorial的主体进行求值，最终计算得到120。

环境模型的实现：
Frame类的lookup和define方法是实现环境模型的关键。定义函数时，解释器需要创建一个新的LambdaProcedure并绑定到当前环境中。当调用该函数时，需要在一个新的环境中对其主体进行求值。

示例

class Frame:
    def __init__(self, parent):
        self.bindings = {}  # 当前环境的符号绑定
        self.parent = parent  # 父环境

    def lookup(self, symbol):
        """
        查找符号symbol在当前或父环境中的值。
        """
        if symbol in self.bindings:
            return self.bindings[symbol]
        elif self.parent is not None:
            return self.parent.lookup(symbol)
        else:
            raise NameError(f"undefined symbol: {symbol}")

    def define(self, symbol, value):
        """
        在当前环境中定义symbol，并绑定其值为value。
        """
        self.bindings[symbol] = value

总结

通过引入抽象机制，我们的Scheme解释器支持用户定义函数、局部变量和递归等复杂操作。环境模型通过作用域链实现了符号的绑定与查找。