[Back]

Chapter 2

2.1 数据抽象导引

DEF.26 数据抽象 数据抽象是一种方法学,它能够将我们对复合数据的使用与基本抽象隔离开。

DEF.27 选择函数和构造函数 使用数据抽象构造复合数据的过程,被称为构造函数和选择函数。

DEF.28 序对 一个序对取两个参数,返回一个复合的数据对象,cons = construct car = Contents of Address part of Register cdr = Contents of Decrement part of Register

DEF.29 表结构 使用序对构造的数据对象叫做表结构数据。

一般而言,数据抽象的基本思想是构造出一组基本的过程,使得对该数据类型的任何操作都基于这一组过程,并且也只能用这一组过程描述。

DEF.30 抽象屏障 通过在系统的各层之间树立起抽象屏障,我们就有了对大型系统的维护性。

一般而言,我们总能把数据作为一组构造函数和选择函数,使其被合法表示,既满足一组特定的条件。

 

2.2 层次数据和闭包性质

DEF.31 闭包 一般而言,当某种组合数据对象组合的对象本身还可以进行再次组合,我们把这样的性质称为闭包。 闭包在Lisp中还可以指柯里化 实际上,所有Lisp的闭包性质都来自于列表本身的闭包性质。

DEF.32 序列 使用序对进行组合的一类数据结构是序列: (cons <a1> (cons <a2> (cons <a3> (…… 等价于(list <a1> <a2> ……)

和对过程进行高层抽象一样,我们可以建立起很多处理表的高层抽象,这样的抽象能从序列应用到序列而不用考虑低层实现,因此,这也就成了一层抽象屏障。

DEF.33 树 在Lisp中,序列组合而成的序列被称为树。

由于树是一种以序列组合而成的序列,那么,递归地进行序列操作往往就能扩展为对树的操作。

DEF.34 约定界面 一种数据结构处理过程中的方法,是使用类似信号流处理的约定的界面。 在工程化的问题上采用映射、过滤器和累积器的思想能够是整个问题变得优美而简单。

通过对映射进行累积和继续映射,我们也可以得到一个嵌套映射的过程。

在这一节中,我们对程序设计语言的一个分层设计有了强有力的理解。

 

2.3 符号数据

我们目前使用过的所有复合数据都是从数值构造的,我们现在要更进一步,引入任意符号构造的数据。

DEF.35 语义实体和语法实体 我们一般所指称的语言中的简单词语,是有具体的语义的,只有用形如引号一类的标识符包括起来,才能使它仅具有语法意义。这种引入引号的行为其实是十分危险的,因为它会损害一门语言的数理逻辑性,比如自然语言。

严格来说,引号的引入破坏了Lisp中的表结构和表规则,因此,我们可以定义引号的实质是(quote <expr>)的语法糖。这样对待就不会破坏Lisp的求值规律。

eq?过程可以使我们检查两个符号是否相同

符号求导是推动人们去设计符号计算语言的动力之一,是这个需求间接导致了Lisp的诞生

现在我们考虑一个实例:集合的表示 首先是集合作为未排序的表

然后是集合作为排序的表

如果将集合作为二叉搜索树看待,那么它往往会比单纯的线性表拥有更快的效率。 比如,我们可以这么设计一棵树,该节点保存一个数据,而节点的左子树中所有数据都小于该节点的数据,右子树的所有数据都大于这个节点的数据,很显然,我们的搜索操作会快到对数级。 对于一颗非平衡的二叉搜索树,它的操作也会退化到线性。

DEF.36 定长码和变长码 在信息论中,如果我们采用定长的编码方式,那么信息所需编码长度就是 ,其中T代表出现的信息种数。 而如果我们根据使用频率来划分信息的长度,显然会让信息的编码长度大大缩小。

DEF.37 前缀码 有效区分变长码有两种方法,一种是引入独一无二的分隔符,另一种则是将每个编码的完整长度不作为任何一个其他编码的前缀,这种编码方式被称为前缀码。有效的构建变长前缀码的方式便是采用一种叫做Huffman树的数据结构。

 

2.4 抽象数据的多重表示

除了隔离抽象数据之间的屏障,也需要抽象数据的不同中表示,并使得它们在同一个系统中能够自洽的工作

DEF.38 通用性过程 建造一个能够在带有类型标志的数据对象上操作的过程被称为通用性过程,同时,我们还需要使用一种被叫做数据导向的程序设计。

实际上,这是缺乏可加性的体现。

DEF.39 消息传递 我们可以将数据对象看作一个过程,由输入的参数来执行相应的过程,这种工程思想被称为消息传递。

 

2.5 带有通用型操作的系统

DEF.40 强制 将一种数据类型以某种规则解析为另一种数据类型的过程,被称为强制。

DEF.41 类型塔 描述类型之间的层次关系的图表结构被称为类型塔。

计算机层面的不同类型之间的复杂关系和如何处理他们的方法艺术,以及技巧,实际上也可以上升为哲学层面的“本体论”。例如,面向对象中最大的复杂性,就是对这种类型之间通用操作的处理。 也许……如果没有知识表示和计算机推理的进一步完善,这些工作是无法通过语言设计层面很好的完成的。