文档：2.2 Data Abstraction

参考：cs61a.org/spring2018

2.2 数据抽象

我们总希望在程序中表达世界上许多的事物，而他们中的大多数都具有复合结构。例如，地理位置具有纬度和经度坐标。为了表示位置，我们希望编程语言能够将纬度和经度结合在一起，形成一个复合数据值，这样使程序可以作为单一的概念单元来操作。

复合数据的使用能够增加程序的模块性。如果我们可以将地理位置作为整体值来操作，那么我们可以将程序中各部分分离，从这些位置的本质上来处理。分离和处理数据是一种强大的设计方法，称为数据抽象。数据抽象使程序更容易设计，维护和修改。

数据抽象与函数抽象类似。当我们创建函数抽象时，函数实现的细节被淡化了，特定的函数本身可以被任何具有相同行为函数所替代。换句话说，我们构建抽象将函数的使用方式与函数实现的细节分离。类似地，数据抽象将如何使用复合数据值和构建方式隔离。

数据抽象的基本思想是结构化程序，以便它们操作抽象数据。也就是说，我们的程序应该使用数据，而不是做出关于数据的假设。同时，数据的具体表示方式是程序的独立部分。

这两部分程序：抽象数据运行的部分和定义具体表示的部分，它们通过一组小型函数相连，实现了抽象数据。为了展示这种技术，我们将介绍一组用于操纵有理数的函数。

2.2.1 示例:有理数运算

有理数是整数的比值，它是实数的重要子类。 如1/3或17/29的有理数通常被表示为：

<numerator>/<denominator>

其中<分子>和<分母>都是值为整数的占位符。有理数的值 需要两个部分来精确地表征。 实际上将分子和分母相除会产生一个小数近似值，从而失去精确度。

>>> 1/3
0.3333333333333333
>>> 1/3 == 0.333333333333333300000  # Dividing integers yields an approximation
True

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

我们从函数抽象中了解，在我们实现程序的某些部分之前，我们已经可以高效地开始编程。 我们首先假设我们已经有了一种由分子和分母构建有理数的方法。 我们还假定，给定一个有理数，我们有办法来提取它的分子和分母。 我们进一步假设构造函数和选择器可用到如下三个函数：

1. rational(n，d)返回分子为n,分母为d的有理数。
2. numer(x)返回有理数x的分子。
3. denom(x)返回有理数x的分母。
   在这里我们使用强大的合成策略：心想事成。 我们还没有说出有理数是如何表示的，或者numer、denom、rational如何实现。 即使如此，如果我们确定了这三个函数，我们可以执行加法，乘法，以及测试有理数的平等：

>>> 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 mul_rationals(x, y):
        return rational(numer(x) * numer(y), denom(x) * denom(y))
>>> def print_rational(x):
        print(numer(x), '/', denom(x))
>>> def rationals_are_equal(x, y):
        return numer(x) * denom(y) == numer(y) * denom(x)

现在我们拥有了选择器函数numer和denom，以及构造器函数rational定义的有理数操作，但是我们还没有定义这些函数。 我们需要的是将分子和分母粘合成一个复合的整体。

2.2.2 pairs

为了实现数据抽象的具体层面，Python提供了一个列表list的复合结构，它将表达式放在方括号内，用逗号分隔。 这样的表达式称为列表文字。

>>> [10, 20]
[10, 20]

列表的元素可以通过两种方式访问。 第一种方式是通过我们熟悉的多重赋值法，它将一个列表分解成元素，并将每个元素绑定到一个不同的名称。

>>> pair = [10, 20]
>>> pair
[10, 20]
>>> x, y = pair
>>> x
10
>>> y
20

访问列表元素的第二种方法是通过下标运算符，也用方括号表示。

>>> pair[0]
10
>>> pair[1]
20

Python中的列表（和大多数其他编程语言中的序列）下标都是从0开始索引的，这意味着下标0表示第一个元素，下标1表示第二个元素，以此类推。 我们对这个下标惯例的直觉是,下标表 示一个元素距离元组开头有多远。

与元素选择操作的等效函数称为getitem，它也使用下标以0开始的位置来在列表中选择元素。

>>> from operator import getitem
>>> getitem(pair, 0)
10
>>> getitem(pair, 1)
20

双元素列表不是在Python中表示pairs的唯一方法。 将两个值组合成一个的任何方式都可以被认为是一对pair。 列表是一种常用的方法。 列表还可以包含两个以上的元素，我们将在本章后面探讨。

表示有理数。现在我们可以将一个有理数表示为一对两个整数：分子和分母。

>>> def rational(n, d):
        return [n, d]
>>> def numer(x):
        return x[0]
>>> def denom(x):
        return x[1]

与我们之前定义的算术运算一样，我们可以用我们定义的函数来操纵有理数。

>>> half = rational(1, 2)
>>> print_rational(half)
1 / 2
>>> third = rational(1, 3)
>>> print_rational(mul_rationals(half, third))
1 / 6
>>> print_rational(add_rationals(third, third))
6 / 9

正如上面的例子所示，有理数的实现并不能将有理数化为最简。 我们可以通过修改rational来弥补这个缺陷。 如果我们有一个用于计算两个整数的最大公约数的函数，我们可以在构造pair之前将分子和分母化为最简。 这种函数已经存在于Python库中。

>>> from fractions import gcd
>>> def rational(n, d):
        g = gcd(n, d)
        return (n//g, d//g)

双斜杠运算符//表示整数除法，它会向下取整除法结果的小数部分。 由于我们知道g能整除n和d，整数除法正好适用于这里。 这个修改确保了有理数表达的最低限度。

2.2.3 抽象界限

在列举更多复合数据和数据抽象的示例之前，让我们思考一下有理数的示例产生的一些问题。 我们根据构造器rational和选择器numer和denom来定义操作。 一般来说，数据抽象的底层概念是，基于某个值的类型操作表达，为这个值的类型确定一组基本的操作。之后使用这些操作来操作数据。
对于有理数来说，程序的不同部分使用不同的方式来操纵有理数，如下表所述。

在上面的每层中，最后一列中的函数强制划分了抽象边界。 这些功能被更高级别调用，并使用较低级别的抽象来实现。

只要能够使用较高级别函数的程序使用较低级别的函数，就会发生抽象边界冲突。 例如，一个计算有理数平方的函数最好用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))

假设用包含两个元素的list来表示有理数也会发生抽象边界冲突。

>>> def square_rational_violating_twice(x):
        return [x[0] * x[0], x[1] * x[1]]

抽象边界冲突使程序更容易维护及修改。 依赖于特定表示的函数越少，需要改进时的发生的变更越少。即使我们改变了有理数的表示方法，square_rational平方函数也不需要更新。 相比之下，当选择器或构造函数签名更改时，square_rational_violating_once将需要更改，而只要有理数的实现方法更改，square_rational_violating_twice将需要更新。

2.2.4 数据属性

抽象障碍塑造了我们对数据的思考。有理数字的有效表示不限于任何特定的实现（例如双元素列表）;它是由理性返回的可以传递给数字和值的值。另外，构造函数和选择符之间必须保持适当的关系。也就是说，如果我们从整数n和d构造有理数x，那么应该是numer（x）/ denom（x）等于n / d的情况。

一般来说，我们可以将抽象数据类型当做一些选择器和构造器的集合。只要满足行为条件（如上述的除法属性），选择器和构造函数就构成一种数据的有效表示。抽象屏障下面的实现细节可能会改变，但是如果行为没有，则数据抽象仍然有效，并且使用此数据抽象编写的任何程序将保持正确。

这个观点可以广泛应用，包括我们用来实现有理数字的pair的值。我们没有真正说过pair到底是什么，只是提及这种语言提供了用两个元素创建和操纵列表的手段。我们需要实现pair的方法是将两个值粘在一起。作为行为条件，如果一个pair ‘p’由x和y构成，那么select(p, 0)返回x, 并且select(p, 1)返回y。
我们并不需要用list类型来创造pairs。相反，我们可以用pair和select两个函数来表达这个概念。

>>> def pair(x, y):
        """Return a function that represents a pair."""
        def get(index):
            if index == 0:
                return x
            elif index == 1:
                return y
        return get
>>> def select(p, i):
        """Return the element at index i of pair p."""
        return p(i)

使用以上的表达，我们可以创造和操纵pairs.

>>> p = pair(20, 14)
>>> select(p, 0)
20
>>> select(p, 1)
14

这种高阶函数的使用与我们直觉的数据概念完全不同。尽管如此，这些函数足够表示pairs。函数足够表示符合数据。
函数式表示一对pair的要点并不是Python实际使用这种方法（处于效率的原因，列表的实现更加直接），而是它可以这样的工作。函数的表示虽然晦涩难懂，但它却是表述pairs的完全合适的方法，因为它满足了pairs需要完成的唯一条件。数据抽象的实现使我们能够轻松地在各种表示中切换。

上一节：SICP 第一章 使用数据构建抽象 2.1 引言
下一节：SICP 第二章 使用数据构建抽象 2.3 序列