月度归档:2015年06月

SICP 读书笔记 - 构造抽象数据

SICP中的基础抽象数据与本科看过的一本算法书中提到的ADT有异曲同工之妙,即对数据用过程进行封装,数据的具体表现形式隐藏在过程接口下,用SICP的原话,这叫“抽象屏障”。如此,可以在保持操作接口不变的情况下,调整内部的数据实现形式。

相对于基础抽象数据与后面的带标志数据,让人震撼的是后面的数据导向的程序设计,这完全就是“代码确定规则,数据实现策略”的真实写照。即将由于程序属于一种逻辑范畴,一旦固定便难以只执行一种特定逻辑的局限性,通过数据(易调整,易加,易减)对程序进行边界扩展。用SICP中的原话:“可加性”,即可扩展性。目前,这种设计范式还不是特别熟悉,只是偶尔用一下,但其精髓还需要学习。

采用数据导向设计风格将通用型操作的系统实现了一把,在实现复数时看到TCP/IP协议栈分层的影子,由于SICP在80年代初即已在MIT作为教案被使用,因此可见分层思想影响之深远。其分层思路为:由于复数有两种形式(例如协调栈中某层有多种协议),因此,在打上复数标记“complex”前,需要将其具体复数类型(rectangular还是polar)打上。这样在查找操作表时,可由复数找到相关的复数计算,然后由具体复数类型找到其具体的计算方式。

在通用型操作的系统实现中,还发现了一个特殊的设计,但书中并没有着重强调,觉得这个设计也是数据导向设计的精髓之处:即操作所需要的参数类型作为查表中的维度。即二维表中:第一维是操作类型名,第二维是操作参数类型列表;两维确定唯一的操作过程。

后续添加扩展操作时,由数据导向设计带来的“可加性”之震撼,对得起近三个月晚上都献给SICP。读到后续的扩展跨类型操作时,看到“强制”策略,不免想到流式计算系统TM中使用ChunkFile向RefFile强制转换的策略。即进行跨类型操作时,可将“低“层次类型转换为”高“层次类型,这样就可以采取统一的操作进行处理(前提是类型间存在继承关系)。

后面提到的猜想:对类型的通用型操作处理,在没有知识表示与自动推理的帮助下,仅仅通过程序设计语言很难办到。首先,不清楚这里的知识表示与自动推理的准确定义是什么,不过看到这里,想到了公司最近在做的项目:类SQL-【ANTLR】->C++完成复杂统计报表的表达与计算是否在理论上就有障碍。