第二章 构造数据抽象

序言

简单数据并不能解决所有问题。有时候为了模拟复杂的现象，就需要去构造一些计算对象，集中的部分会反映真实世界中的一些若干角度的现象。本章讨论将数据对象组合起来，形成复合数据的方式。

与需要复合过程的原因一样，使用复合数据能够提升我们设计程序时所位于的层次，提高设计的模块性，增强语言的表达方式。

如何提高程序的模块性与层次性？总的来说，就是把处理数据对象的表示部分（具体实现）与处理数据部分的使用部分相互隔离。这在书中就被称作数据抽象。关键在于，数据抽象在不同部分之间构建起了一道屏障（数据屏障），把两者隔离开来。同时借助隔离开来的操作，我们又可以表示出新的对象，导出新的对象的操作，继续构造出抽象屏障。从某种程度上看，这很像是一层又一层的黑箱，黑箱之中也被隔离出了具体实现与具体操作。

形成复合对象的关键在于，要有某种“粘合剂”把不同的基本对象贴合在一起。虽然非必要，但这其中有一个关键性的思想，就是闭包的概念。与数学的封闭的概念类似，粘合剂不但能组合基本对象，同时还可以作用与本身，即用于复合的数据对象。

同时为了进一步提高表达能力，引入了符号表达式的概念（类似于现代语言的字符串？maybe）从模式匹配的犯法更好地完成“选择”“搜索”等功能。

最后引出通用型操作，数据导向的程序设计。

2.1导引

数据抽象的基本思想，就是使程序能够就像是在操作这些抽象的数据一样（即效果相同）。除了完成本职工作，不对其作出更多的限制。而且，一种具体数据表示的定义，应该与程序使用这种数据的方式无关。为此，我们往往需要一组过程：构造函数和选择函数。以便在具体表示之上实现抽象的数据。

仅仅表示出抽象数据还是不够，我们还得让数据能够被我们所操作。我们需要为数据对象标识出一组操作，使得对数据对象的所有操作都可以基于这些基本操作进行表示。这时就应该构建出一个抽象屏障，使我们在之后进行更复杂的操作时不再需要考虑其底层实现。这样可以隔离系统中的不同层次。

这么操作的一个优点就在于程序能够更好地实现与修改。如果在某一层出问题，我们只需要从上到下一层层地进行测试与查找，而不是检查整个程序。这一做法在效率上更有优势，同时结构也会更加清晰。

说了这么多，数据到底意味这什么（我们为什么能这么做？）一般而言，我们可以把数据定义为一组适当的构造函数和选择函数，以及这些数据能够执行的所有操作（或者说条件）。同时我们会发现反过来看也是没问题的。只要我们定义的对象及操作能够满足我们研究的对象的性质，我们就可以认为这个程序实现了这个对象（如果把我们定义的对象和操作封装起来，给用户使用，在用户看来就与实际在操作对象一样）

2.2层次性数据与闭包性质

闭包即指通过某种东西组合起来的数据对象的结果能够被这种东西以同样方式再次进行组合。这一点与“组合式的成员本身也可以是组合式”很像。书中介绍了一种lisp的实现：表。我不会记录其具体使用，只会记录其中包含到的思想或方法。

一个有用的操作：对将一个过程应用与表中的每个元素，把得到的结果记录为一个表并返回。（map）

显然，这个操作就构建了一层抽象屏障，是我们不需要关心应用，变化，结果的收集的过程。

对众多程序进行考察，我们往往可以把一个程序（或者说很多程序）抽象为使用了一套大致相同的流程或方法（在书中被称作使用约定的界面（把序列作为一种约定的界面），我并不理解这种表述）：

过滤器（filter）：根据条件，从表中筛选出符合条件的元素，组成一个新的表。

累积器（accumulate）：根据特定的累积方式，初始值和表，返回一个值。

枚举器（enumerate）根据特定的条件，生成出符合条件的表。

当然，还有之前提到的map（映射器）

需要注意的是，在编写这些工具时，其所谓的条件等都是参数（过程）需要实际使用中才会输入的。即它们都应该是高度抽象的

将程序表示为上述工具的排列组合，能让我们得到模块化的程序，对控制程序的复杂度极为有效。

书上还提到了一个嵌套映射。简单讲一下原理，我们可以把一个表中的每个元素都映射成一个表，把新的表中的每个元素再取出来应用于某个过程。

这种设计方法能让我们的程序更加健壮：设法构建出当前层次的基本元素，用基本元素组合出来的部件又可以用于构建上一层的基本元素

2.3：符号数据

在我看来，把符号数据理解为字符（串）毫无问题。书中引入这个概念，主要是为了将符号与他的值（过程）区别开来。我认为就是字符“1”与数字1的区别。引入这个概念，能够让我们更好地进行模式匹配（这是视频讲座中的标题，让我联想到正则表达式）。进行查找等功能。这应该不是什么重要的内容。

2.4：抽象数据的多重表示

在之前我们接触的系统往往是层层叠加的，从另一种方面看，这也是很简单的结构。对每一层，其上只有一层（或0层），其下也只有一层（或0层）。这显然不可能满足实际生产中的需要。比如对于一个数据，我们可以采用不同的表示方法。又或者，随着状态的发展，我们需要往某一层添加一些内容（这些内容与原内容互相独立，但又确实处于同一层次上）。在同一层次上会有不同的“包”。形象得看，在每一层我们还需要构建一道垂直的“抽象屏障”。

为此这需要我们构造通用型过程。一个解决办法是让数据对象带上类型标志。我们可以构造一个通用型选择函数，检查数据的类型（标志），把数据传入对应的过程。在传入的过程中，还需要“刨去”数据的最外层的类型标志。（与之对应的，构造的时候就要添加）。这种方法被称作基于类型的分派。但是这一方法是有缺点的。首先，为了避免命名冲突，处于同一层次的包需要进行检查以防重命名。这是很低效的工作。而且，如果需要对这个系统加入新的内容，我们就需要修改一次通用型选择函数。这种修改是病态且无意义的。换句话说，这种系统不具有可加性。

书上介绍了另外一种方法：数据导向的程序设计。假设我们有一个表格。首先编写好一个程序，然后设计好这个程序的标识。然后把这个程序“推入”到由标识指定的表格的位置上。需要时，我们再把标识作为索引，把这个程序（过程）“取出来”。这种方法可以很好的避免上面的缺点。首先表格里保存的实际的程序而非其标识，不需要重命名。另外只要表格够大或者可扩充，就直接在系统中添加新内容，所要做的修改量也变得极小。

上述问题看似已经很好地解决，但还是有缺陷的。在实际操作时，有时候我们需要打破向上向下或者左右的抽象屏障（类型的强制转换）。对数据对象进行转换。这其中涉及到了很多问题，如可行性与信息的丢失，（层次结构不是塔型而是图，无法找到转换的方向）等。但我们仍然需要这种操作。我们同样可以把这些操作都导入到表格中。“上升”往往不会丢失数据，但‘下降’是有这种可能的。书中提供了一种方法。先将数据‘投影’到下一层再“上升”，检查两个数据是否相同，即可判断可行性。

以上就是我总结的第二章的核心内容。这些内容让我联想到了泛式编程。以下是从gpt抄下来的内容：

泛式编程（Generic Programming）是一种编程范式，它致力于写出可重用、高效且能够适用于多种数据类型的代码。这种范式与面向对象编程（Object-Oriented Programming, OOP）和过程式编程（Procedural Programming）有所不同，它侧重于算法的结构和行为，而不是数据的具体类型。以下是泛式编程的详细解释：

泛式编程的核心概念

1. 抽象：泛式编程通过抽象来定义算法和数据结构，这样它们就可以在不依赖于特定数据类型的情况下工作。例如，排序算法可以设计成不关心它正在排序的数据的具体类型。
2. 通用性：泛式编程的目标是创建可以适用于多种情况的代码。这意味着编写的函数或类可以与不同的数据类型一起工作，而不仅仅是单一类型。
3. 参数化类型：在泛式编程中，类型本身可以成为参数。这允许程序员创建可以处理不同类型数据的模板或泛型类。

泛式编程的关键技术

1. 模板：在C++等语言中，模板是一种实现泛式编程的技术。模板允许程序员编写代码模板，这些模板在编译时根据实际使用的数据类型生成具体的代码。
   例如，C++中的模板函数：

   template <typename T>
   T max(T a, T b) {
       return (a > b) ? a : b;
   }

   这个max函数可以接受任何支持比较操作的数据类型。

2. 泛型：在Java、C#等语言中，泛型是一种实现泛式编程的技术。泛型允许在类或方法定义中使用类型参数，这些参数在实际使用时会被具体类型替换。
   例如，Java中的泛型类：

   public class Pair<T, U> {
       private T first;
       private U second;
       public Pair(T first, U second) {
           this.first = first;
           this.second = second;
       }
       // getters and setters
   }

   Pair类可以用来存储任意类型的两个值。

泛式编程的优势

• 代码复用：通过编写可以应用于多种数据类型的代码，减少了代码的重复编写。
• 类型安全：泛型代码在编译时进行类型检查，减少了运行时类型错误的风险。
• 性能：由于泛型代码通常在编译时生成具体类型的代码，因此可以避免运行时的类型转换，提高性能。

泛式编程的局限性

• 复杂性：编写泛型代码有时会比编写特定类型的代码更加复杂。
• 类型限制：某些语言对泛型类型的使用有特定限制，例如，某些操作可能不适用于所有类型。
  泛式编程在标准库中有广泛的应用，例如C++的STL（Standard Template Library）和Java的Collections Framework都大量使用了泛式编程的概念。通过这些库，程序员可以高效地处理数据，而不必为每种数据类型编写特定的代码。

​

我认为这两者是存在关系的。它们都把‘过程’当做了一种普通的元素，‘过程’与数据之间的极限是模糊的。如果以后我会再来查看这方面的内容，或许对这些内容会有更深的理解吧。