SICP笔记(六)

符号数据

编程中,我们使用言简意赅的变量名为变量命名以提高代码的可读性,此时我们处理的是变量名构成的表达式,但有时需要直接处理字符本身,将其视为数据对象,为了不引起歧义,我们便需要一种新的表示方法。在scheme中,在对象前放一个引号便表示这个对象是被引用对象,形如'a,存在等价用法quote(quote a)'a等价,后者是解释器的实际工作方式。 解释器看到的所有表达式都可以作为数据对象去操作,当解释器看到'(a b c),将会代换成(quote (a b c))

书中后面介绍了几个构造复合数据的实例,包括符号求导,集合的表示,霍夫曼编码树。这几个实例中,通过数据抽象将数据的表示与使用分开,通过愿望思维,在抽象屏障之上先实现功能,然后再考虑复合数据的具体表示,以及完成构造函数与选择函数。
在符号求导的实例中,开始我们对程序计算的结果没有化简表示不满意,我们希望程序能给我们化简的结果,得益于数据抽象,不需要对整个程序大面积修改,只需要在构造函数上修改下便达到了优化的目的。开始看书时,觉得构造函数,选择函数实在多此一举,但这就是数据抽象的魅力所在。

带标志数据

选择复数的表示方法时,我们有两个选择,实部虚部表示法和模长幅角表示法,计算加减法时前者合适,计算乘除法时后者有绝对优势,二者各有长短,能否两种表示方法同时存在,取长补短?
为了二者共存,两种表示方法不会相互混淆,我们便需要带标志的数据(Tagged data),对每种表示方法打上标签,在两种表示方法中间竖立了一个垂直屏障。在水平的抽象屏障之上,我们可以实现通用型过程(generic operation),通用过程根据打上的标签,将撕去标签的对象分派到合适的包中。数据对象,从最顶层一层层传递到底层,标签一层层撕去,相反方向,便一层层打上相应的标签。

数据导向的程序设计

上面提到的带有显式分派的通用型操作有个巨大的缺陷,每当有新的包安装时,便需要对大量修改程序,没有可加性。每次分派时,需要依次检查标签,选择合适的包,不够智能,并且当系统复杂时,复杂度不好控制。
我们可以想象有一张抽象的operation-type表,可以对这张表进行增加,检索等操作,这种策略称为数据导向的程序设计(Data-directed Programming)。使用时,根据操作,类型的键值在表中查找合适的过程,实现操作的“智能化”。当有新的包需要添加时,只需往表中写入内容,维持了系统的灵活性。
数据导向是一行行地处理表格,同理我们也可以对operation-type表一列一列处理,实现一个“智能操作对象”,以消息的方式接收到所需操作的名字,这种策略称为消息传递(Message passing),适合需要大量添加新类型的系统。

通用型算术运算

使用数据导向的思想,我们将前面实现的有理数,复数都整合进一个算术运算包,此前我们实现的都是相同类型对象之间的操作,该如何实现跨类型的操作呢?
一种的可行的策略便是在每个包中实现跨类型的操作,无疑这是个好方法,但是绝对也是一项很繁重的任务!
另一种巧的策略是利用这些类型的潜在联系,将不同类型转化至同一类型。按照这种策略,我们只需要实现类型之间转化的操作,然后将这些操作安装至一张抽象的coercion表,与上面的operation-type表类似。
在各种类型的层次结构有一种最简单的情况,一个类型只有至多一个超类型和至多一个子类型,称为类型塔(tower)。 每个类型能够“继承”其超类型中定义的所有操作。如果类型的层次结构是塔的话,可以很好地实现这个概念,并且类型转换时,只要顺着塔,一层层往上升,将不同类型的对象转换成同一层就可以实现计算。但大型系统的类型层次不会这么简单,处理好一大批相互有关的类型有保持系统的模块性,这是一个值得深思的问题…


习题解答:传送门