SICP读书笔记--第2章《构造数据抽象》

一、说明

在第1章中我们关注了计算过程,讨论了程序设计语言的一个关键思想—-过程抽象。它的重要意义可能在于:

  • 屏蔽计算的细节,将过程作为黑箱抽象,使用者只需要知道它的功能。

  • 允许我们抽象出过程中的公共模式,允许我们对过程进行操作,形成高阶过程,达到更高一级的抽象。

本章将讨论的是程序设计语言的另一个方面:数据抽象。

  • 本章小节分布
    • 2.1数据抽象导引
    • 2.2层次性数据和闭包性质
    • 2.3符号数据
    • 2.4抽象数据的多重表示
    • 2.5带有通用型操作的系统

二、总结

  • 与第1章对应本章将讨论程序设计语言的另一个关键方面

讨论如何将数据对象组合起来,形成复合数据的方式。这样做是为了提升我们在程序设计时所位于的概念层次,提高设计的模块性,增强语言的表达能力。

1.数据抽象导引

  • 数据抽象的基本思想

设法构造出一些使用复合数据对象的程序,使它们就像在“抽象数据”上操作一样。

  • 我们使用构造函数选择函数在具体的表示之上实现抽象的数据。

1.1序对

我们使用cons将两个对象结合成一个对偶,形成一个复合数据对象,为了可以提取出cons里的两个对象,我们分别使用carcdr去完成。后面我们会用序对构造更复杂的、被称为的数据结构。

1.2抽象屏障

复合数据的使用帮助我们提高了程序的模块性,因为它将程序中处理数据对象的表示的部分与处理数据对象的使用的部分相互隔离,数据抽象使我们在程序的不同部分之间建立起适当的抽象屏障

值得注意的是,任一数据结构可以有多种方式将其表示为简单对象的组合,所以抽象屏障有下面的优点:

  • 使程序很容易进行维护和修改,数据具体表示的改动对整体程序不会产生很大的影响。
  • 只有少数界面对数据的具体表示存在依赖,允许我们推迟确定具体表示方法的时间,而不会阻碍系统其他部分的工作进展。

1.3数据意味什么?

数据就是一些简单的数字、字符?或者它们组合起来的稍微复杂的一些东西吗?这样的想法可能有点简单!

来看一个有点颠覆但又非常合理的定义:

我们总可以将数据定义为一组适当的选择函数构造函数,以及使这些过程变成合法表示而需要的一组特定条件

现在我们就可以使用过程来定义序对了:

1
2
3
4
5
6
7
8
9
(define (cons x y)
(define (dispatch m)
(cond ((= m 0) x)
((= m 1) y)
(else (error "Argument not 0 or 1 -- CONS" m))))
dispatch) ;返回的是一个接收单参数的判断选择过程

(define (car z) (z 0)) ;向过程z传递参数0
(define (cdr z) (z 1)) ;向过程z传递参数1

上面的程序还是出现了xy这样的具体数据,干脆把数字这种基本的东西也用过程定义吧!

Church就用了λ表达式定义了的自然数,并且满足自然数的形式化定义(皮亚诺公理

其中,$f^n$表示$f$函数连续迭代$n$次,即$f^n x= f (f ( \cdots (f x) \cdots ))$ 。代码实现可参考练习2.6

2.层次性数据和闭包性质

  • 某种组合数据对象的操作满足闭包性质

    通过它组合起来的数据对象本身还可以通过同样的操作再进行组合。

  • 闭包性质使我们可以建立起层次性的结构。

2.1序列表示和表操作

  • 我们使用(list <a1> <a2> ... <an>)来定义表,它等价于一个序对的序列:

    (cons <a1> (cons <a2> (cons ... (cons <an> '()) ... )))

  • 表操作:

    • (list-ref items n)取表的第n个元素
    • (length items)取表的长度
    • (append list1 list2)list2接在list1后面
  • 表的映射

    (map proc items)对表里的每个元素执行proc操作

2.2层次性结构

  • 一个序列的元素本身也是序列,应用这种递归的表示,我们可以表示出—-一种层次性结构的数据。

2.3序列作为一种约定的界面

  • 对于一些序列的操作我们总可以抽象为下面的一种模块化的约定界面(顺序可调整):

    • enumerate:枚举每一个元素
    • filter:过滤出满足条件的元素
    • map:对满足条件的元素进行操作
    • accumulate:累积上面的结果

3.数据导向的程序设计

为了维护程序的模块性,将介绍数据导向的程序设计技术,它允许我们孤立地设计每一种数据表示,而后用添加的方式将它们组合。

下面我们辨析一下数据导向里的两种程序分派方式:

3.1基于类型的分派(也称数据导向)

  • 是一种基于类型进行分派的组织方式,其中让每个操作管理自己的分派。

  • 从效果上来看,这种方式是将操作-类型表格按行分解,每个通用型过程表示表格中的一行。采用一批“智能操作”去基于数据类型进行分派。

  • 如果新增类型,只需再增加一个程序包即可,不需要修改源代码。

  • 如果新增操作,同样也不需要修改之前的代码,只需要增加相应的分发函数即可。

数据导向可以很方便地通过包机制增加新类型和新的通用操作,因此无论是增加新类型还是增加新操作,这种策略都很适合。

3.2基于操作名的分派(消息传递)

  • 这种方式是将操作-类型表格按列分解,采用一批“智能数据对象”去基于操作名进行分派。

  • 如果这样做就需要做出一种安排,将每一个数据对象表示为一个过程。它以操作的名字作为输入,能够去执行指定的操作。

  • 如果新增类型,只需再增加一个分发过程,原有代码不需要修改。

  • 如果新增操作,则需要修改每个分发过程,把新增的操作添加上。

消息传递将数据对象和数据对象所需的操作整合在一起,因此它可以很方便地增加新类型,但是这种策略不适合增加新操作,因为每次为某个数据对象增加新操作之后,这个数据对象已有的实例全部都要重新实例化才能使用新操作。

三、本章习题解答

------------- 本文结束 感谢您的阅读 -------------

本文标题:SICP读书笔记--第2章《构造数据抽象》

文章作者:Perry

发布时间:2019年03月19日 - 05:00

最后更新:2019年09月19日 - 13:48

原始链接:https://perry96.com/archives/5335d2dd.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%