CS 与 LLM 学习知识库

数据抽象与对象

23分钟阅读

假设你要写一个处理分数的程序：1/2 + 1/3 = 5/6。分数用什么存？一个二元列表 [1, 2]，一个元组，一个字典，还是一个类？更要紧的问题是：如果写到一半想换一种存法，要改多少处代码？这一篇的主线是把”数据怎么用”和”数据怎么存”隔开。先用纯函数做到这一点，然后发现需要会变的数据，最后自然走到对象和类。

前置：函数与环境模型、高阶函数与递归

抽象屏障：只通过构造器和选择器碰数据

先约定分数这个抽象需要哪些操作：一个构造器 rational(n, d) 造出分数，两个选择器 numer(x)、denom(x) 取出分子和分母。有了这三个函数，加法和乘法就能写出来，完全不用知道分数内部长什么样：

from math import gcd
def rational(n, d):
    g = gcd(n, d)
    return [n // g, d // g]
def numer(x): return x[0]
def denom(x): return x[1]
def add_rational(x, y):
    return rational(numer(x)*denom(y) + numer(y)*denom(x), denom(x)*denom(y))
def mul_rational(x, y):
    return rational(numer(x)*numer(y), denom(x)*denom(y))
def show(x): return f'{numer(x)}/{denom(x)}'
half, third = rational(1, 2), rational(1, 3)
print(show(add_rational(half, third)), show(mul_rational(half, rational(2, 3))))
5/6 1/3

这里的代码分成了几层：

层用什么看待分数只能使用
使用分数的程序一个数add_rational、mul_rational、show
分数运算分子和分母rational、numer、denom
分数的表示一个二元列表列表下标 x[0]、x[1]

每一层只调用紧邻下一层提供的函数，层与层之间的分界线叫抽象屏障（abstraction barrier）。如果 add_rational 里直接写 x[0]，就越过了屏障：代码现在还能跑，但它和”分数是列表”这个实现细节绑死了。

屏障的价值在换表示的时候才显现。下面把分数换成一个函数，连列表都不用：

def rational(n, d):
    g = gcd(n, d)
    def select(name):
        return n // g if name == 'n' else d // g
    return select
def numer(x): return x('n')
def denom(x): return x('d')
half, third = rational(1, 2), rational(1, 3)
print(show(add_rational(half, third)))
5/6

只改了构造器和两个选择器，add_rational、mul_rational、show 一行没动，结果照旧。这个例子还说明了一件更深的事：数据可以完全由函数来表示。分数”是什么”并不重要，重要的是它满足一组行为约定：numer(rational(n, d)) / denom(rational(n, d)) 等于 n / d。只要满足这个约定，用列表、用闭包、用类实现都行。闭包 select 记住了帧里的 n、d、g，正是上一篇讲的机制。

停一下，检查理解单选

分数从列表表示换成闭包表示后，下面哪段代码会坏掉？

序列：一种通用的数据抽象

分数是我们自己定义的抽象。Python 内置了一种用途最广的抽象：序列（sequence），包括列表、元组、字符串、range。它们的共同行为是：有长度，能按下标取元素，能切片，能用 in 判断成员，能被 for 遍历：

words = ['apple', 'kiwi', 'fig']
print(len(words), words[-1], words[1:], 'fig' in words, sorted(words, key=len))
print({w: len(w) for w in words})
3 fig ['kiwi', 'fig'] True ['fig', 'kiwi', 'apple']
{'apple': 5, 'kiwi': 4, 'fig': 3}

处理序列最常用的三种操作是 map（对每个元素做变换）、filter（按条件保留）、reduce（把所有元素合成一个值）。Python 用列表推导式把前两者写成一行：

print([x * x for x in range(10) if x % 3 == 0])
print(sum([[1], [2, 3]], []))
pairs = [[1, 2], [3, 4]]
print([x + y for x, y in pairs], [p[0] for p in pairs])
[0, 9, 36, 81]
[1, 2, 3]
[3, 7] [1, 3]

[表达式 for 名字 in 序列 if 条件] 的求值过程是：对序列里每个元素，在一个新的局部帧里绑定名字，条件为真就求值表达式，收集结果。sum(..., []) 是一个 reduce：从 [] 开始依次用 + 拼接。for x, y in pairs 在每一步都做了一次多重赋值，把内层的二元列表拆开。

序列可以嵌套，嵌套的序列就能表示层级结构。序列这个抽象在 Python 里由一组特殊方法（__len__、__getitem__）定义，最后一节会看到怎样让自己的类也”成为”序列；数组、链表、哈希表在性能上的取舍属于 数据结构。

可变状态：同一个对象，随时间改变

到目前为止所有的值都不会变：rational(1, 2) 创建之后永远是 1/2。但很多东西天然有状态，比如一个银行账户的余额。列表是可变的：

nums = [1, 2, 3]
alias = nums
alias.append(4)
print(nums, nums is alias, nums == [1, 2, 3, 4], nums is [1,2,3,4])
[1, 2, 3, 4] True True False

alias = nums 没有复制列表，只是让第二个名字指向同一个对象，所以通过 alias 修改，nums 也看得到。这引出两种”相等”：== 比较值是否相同，is 比较是否是同一个对象。一旦有了可变数据，**身份（identity）**就变得重要，因为改变一个对象会影响所有指向它的名字。引用、浅拷贝深拷贝、参数传递的完整故事属于 Python 对象模型，这里只需要知道：可变性让”同一个”和”一样的”成了两回事。

函数也能有状态。用闭包实现一个取款函数：

def make_withdraw(balance):
    def withdraw(amount):
        nonlocal balance
        if amount > balance:
            return 'Insufficient funds'
        balance -= amount
        return balance
    return withdraw
w = make_withdraw(100)
print(w(25), w(25), w(60))
75 50 Insufficient funds

同样的调用 w(25) 两次返回不同的值，所以 w 是非纯函数。状态存在哪里？在 make_withdraw 的调用帧里，balance 绑定在那里，withdraw 作为闭包一直引用这个帧。

nonlocal balance 是关键。第一篇讲过：函数体里对名字赋值，会让这个名字变成局部的。没有 nonlocal，balance -= amount 会被当成对局部 balance 的赋值：

def make_withdraw_bad(balance):
    def withdraw(amount):
        balance -= amount
        return balance
    return withdraw
try: make_withdraw_bad(100)(10)
except Exception as e: print(type(e).__name__)
UnboundLocalError

nonlocal 声明”这个名字在外层函数的帧里，赋值请改那里的绑定”。它和 global 是同一种东西，只是指向的帧不同。注意，如果只是修改外层的可变对象（比如 cache[n] = ... 往字典里放东西），不需要 nonlocal，因为没有重新绑定名字，上一篇的 memo 就是这样。只有重新绑定外层名字时才需要。

停一下，检查理解多选

在内层函数里，以下哪些操作需要对外层函数的名字 x 声明 nonlocal x？

用对象表示递归结构：链表和树

可变数据和数据抽象结合起来，可以表示更复杂的结构。CS61A 用两个类贯穿后半学期：链表和树。

**链表（linked list）**的定义是递归的：一个链表要么是空的，要么是”第一个元素 + 剩下的链表”。

class Link:
    empty = ()
    def __init__(self, first, rest=empty):
        assert rest is Link.empty or isinstance(rest, Link)
        self.first, self.rest = first, rest
    def __repr__(self):
        rest = '' if self.rest is Link.empty else ', ' + repr(self.rest)
        return f'Link({self.first}{rest})'
    def __str__(self):
        s, p = '<', self
        while p is not Link.empty:
            s += str(p.first) + ' '; p = p.rest
        return s[:-1] + '>'
def link_map(f, s):
    if s is Link.empty: return s
    return Link(f(s.first), link_map(f, s.rest))
s = Link(1, Link(2, Link(3)))
print(repr(s)); print(s); print(link_map(lambda x: x * 10, s))
Link(1, Link(2, Link(3)))
<1 2 3>
<10 20 30>

注意 link_map 的结构和链表的定义一模一样：空链表是基本情况，非空链表处理 first，对 rest 递归。数据是递归定义的，处理它的函数也就自然是递归的。

**树（tree）**是一个标签（label）加上若干分支（branches），每个分支又是一棵树；没有分支的树叫叶子。用树记录上一篇 Fibonacci 的调用过程：

class Tree:
    def __init__(self, label, branches=[]):
        self.label, self.branches = label, list(branches)
    def is_leaf(self):
        return not self.branches
def fib_tree(n):
    if n <= 1:
        return Tree(n)
    left, right = fib_tree(n - 2), fib_tree(n - 1)
    return Tree(left.label + right.label, [left, right])
def count_leaves(t):
    if t.is_leaf():
        return 1
    return sum(count_leaves(b) for b in t.branches)
def height(t):
    return 0 if t.is_leaf() else 1 + max(height(b) for b in t.branches)
t = fib_tree(5)
print(t.label, count_leaves(t), height(t))
5 8 4

fib_tree(5) 的根标签是 5，它有 8 片叶子，高度 4。处理树的函数几乎都是同一个模板：叶子是基本情况，否则对每个分支递归，再把结果合起来（sum、max）。这就是上一篇树递归在数据上的镜像：树递归的调用过程是一棵树，而处理树的函数是树递归。

list(branches) 那一步是故意的：默认参数 [] 只在定义时创建一次，复制一份能避免所有叶子共享同一个列表对象。

停一下，检查理解单选

count_leaves 对一棵树求叶子数，它的基本情况和递归情况分别是什么？

类：把数据和操作捆在一起

Link 和 Tree 已经在用类了，现在正式看一下类在做什么。前面闭包版的取款函数，状态藏在帧里，操作只有一个。如果一个账户既要存款又要取款、还要查余额，就需要把一组状态和一组操作放在一起，这就是对象；描述一类对象的模板是类（class）。

class Account:
    interest = 0.02
    def __init__(self, holder):
        self.holder, self.balance = holder, 0
    def deposit(self, amount):
        self.balance += amount
        return self.balance
    def __repr__(self): return f'{type(self).__name__}({self.holder!r}, {self.balance})'

Account('Ada') 创建一个新实例，然后自动调用 __init__，把这个实例作为 self 传进去。self.balance = 0 在实例上建立一个实例属性。interest 写在类体里，是类属性，所有实例共享。

方法调用 a.deposit(100) 背后发生的事是：在 a 上找 deposit，实例上没有，去类里找到函数，把它和 a 绑在一起成为一个绑定方法（bound method），调用时 a 自动作为第一个参数。属性查找的规则很像环境模型的父帧链：先查实例，再查类，再查父类；赋值则总是写在点号左边那个对象上：

a = Account('Ada')
print(a.deposit(100))
print(type(a.deposit).__name__, Account.deposit(a, 1))
print(a.interest)
a.interest = 0.05
print(a.interest, Account.interest, Account('Cy').interest)
100
method 101
0.02
0.05 0.02 0.02

Account.deposit(a, 1) 和 a.deposit(1) 完全等价，self 不是关键字，只是第一个参数的约定名字。a.interest = 0.05 只在 a 上新建了一个实例属性，遮蔽了类属性；Account.interest 还是 0.02，新实例 Account('Cy') 自己没有 interest，去类里找到的也是 0.02。

停一下，检查理解单选

Account.interest 是 0.02。执行 a.interest = 0.05 后，Account('Cy').interest 是多少？

继承与多态

支票账户是一种特殊的账户：利率更低，每次取款收 1 元手续费。不必从头写一个类，用**继承（inheritance）**只描述它和 Account 的不同之处：

class CheckingAccount(Account):
    interest = 0.01
    fee = 1
    def withdraw(self, amount):
        self.balance -= amount + self.fee
        return self.balance
c = CheckingAccount('Bob')
print(c.deposit(100), c.withdraw(10))
Account.interest = 0.04
print(Account('Cy').interest, c.interest)
print(CheckingAccount.__mro__)
print(a, [c])
for obj in [a, c]:
    print(type(obj).__name__, obj.interest)
100 89
0.04 0.01
(<class '__main__.CheckingAccount'>, <class '__main__.Account'>, <class 'object'>)
Account('Ada', 101) [CheckingAccount('Bob', 89)]
Account 0.05
CheckingAccount 0.01

c.deposit(100) 在 c 上找不到 deposit，去 CheckingAccount 找不到，再去 Account 找到。c.interest 在 CheckingAccount 里就找到了 0.01，所以改 Account.interest 不影响它。查找顺序由 __mro__（method resolution order）给出，多重继承时它决定先查哪个父类。改 Account.interest 影响了新实例 Account('Cy')，却影响不到 a（它有自己的实例属性 0.05），也影响不到 c（CheckingAccount 自己定义了 0.01）。这段代码接着上一节运行，所以 a 的余额是 101。

self.fee 写的是 self.fee 而不是 CheckingAccount.fee，这让将来的子类可以只覆盖 fee 就改变手续费，不用重写 withdraw。__repr__ 里用 type(self).__name__ 也是同样的道理，所以 c 显示为 CheckingAccount(...)。

最后那个循环体现了多态（polymorphism）：同一行 obj.interest、同一个 repr(obj)，对不同类的对象做出各自的行为，调用者不需要知道具体类型。这和第一节的抽象屏障是同一种思想：调用者只依赖接口（有 interest、有 deposit），不依赖实现。

继承表达的是”是一种（is-a）“关系：支票账户是一种账户。如果关系是”有一个（has-a）“，比如银行有很多账户，应该用组合：让 Bank 对象持有一个账户列表，而不是让 Bank 继承 Account。

停一下，检查理解单选

CheckingAccount.withdraw 里写 self.fee 而不是 CheckingAccount.fee，好处是什么？

特殊方法：让自己的类融入语言

print(a) 为什么会显示 Account('Ada', 101)？因为 Python 在需要对象的字符串表示时会调用 __repr__（交互式解释器显示值）或 __str__（print、str()）。Link 定义了两者，所以 repr(s) 和 print(s) 显示不同，前者像构造它的代码，后者给人读。

这类前后带双下划线的方法叫特殊方法。Python 的运算符和内置函数在底层都是调用特殊方法：a + b 调用 a.__add__(b)，len(x) 调用 x.__len__()，if x: 调用 x.__bool__()。定义它们，自己的类就能像内置类型一样使用：

class Vec:
    def __init__(self, x, y): self.x, self.y = x, y
    def __add__(self, o): return Vec(self.x + o.x, self.y + o.y)
    def __mul__(self, k): return Vec(self.x * k, self.y * k)
    def __rmul__(self, k): return self * k
    def __len__(self): return 2
    def __bool__(self): return bool(self.x or self.y)
    def __repr__(self): return f'Vec({self.x}, {self.y})'
v = Vec(1, 2)
print(v + Vec(3, 4), v * 3, 3 * v, len(v), bool(Vec(0, 0)))
Vec(4, 6) Vec(3, 6) Vec(3, 6) 2 False

3 * v 先试 int.__mul__(3, v)，int 不认识 Vec，返回 NotImplemented；Python 再试右操作数的 v.__rmul__(3)。这个”先左后右”的协议让新类型可以和已有类型互相运算，而不用修改 int。

特殊方法是 Python 里接口的具体形式：一个对象”是不是序列”，不看它继承自谁，只看它有没有 __len__ 和 __getitem__。这种”有这些方法就能当这种东西用”的风格叫鸭子类型（duck typing）。下一篇的主角，for 循环所依赖的 __iter__ 和 __next__，就是同一套机制。

停一下，检查理解单选

Vec 只定义了 __mul__ 而没有定义 __rmul__ 时，3 * v 会怎样？

记住这三件事

  1. 用构造器和选择器隔出抽象屏障，使用数据的代码就不依赖数据的表示；数据甚至可以完全用函数表示。
  2. 可变状态让”同一个对象”有了意义：闭包配合 nonlocal 能保存状态，对象和类把一组状态和一组操作捆在一起。
  3. 属性查找是”实例、类、父类”一条链，继承只描述差异，特殊方法让自定义类型融入运算符和内置函数。

延伸阅读

反向链接