論壇

在整本书中, 基本上我们都将消息表示为符号. 另外, 现在我们新的句法结构case.

它就等价于

else不是必须的, 但若出现只能出现在最后一行.

在某些实现中, 相等也可能使用equal?进行判断.

基本上我们使用case时<datum>只可能是符号.

让我们通过几个例子来熟悉case和消息传递.

第一个例子是counter的变种.

新的counter具有几种不同的机能, 当收到消息add1!时, 它计上一; 当收到消息init!时, 它重置计数; 当收到消息x时, 它反馈当前统计.

第二个例子是栈, 栈是一种「先进后出」的数据结构. 从现在开始, 我们将引入数据抽象和数据结构的概念.

提到数据抽象, 就不得不提到抽象数据类型. 抽象数据类型是由一系列创建, 解构, 操作数据的过程和它们所满足的约束定义的. 这就在数据及其具体实现之间建立了抽象边界. 如果一个程序使用抽象数据类型, 但不依赖于任何的实现细节, 我们就称这个程序尊重抽象边界. 尊重抽象边界的程序可以换用不同的实现而不会影响其机能, 这也是经常的事情, 尤其是在原型设计时. Scheme本身没有提供什么强制执行抽象边界的机制, 但是的确也有一些常见的方法. 不过, 在本书中, 我们完全不关心这点, 我们只希望读者理解抽象数据类型是什么而已.

数据结构则是一个多义词, 它可以指

1.  一个抽象数据类型;

2.  一个抽象的一个具体实现;

3.  一个实现的一个实例;

4.  一种特定的数据的物理表示.

对于作为抽象数据类型的栈而言, 最重要的操作是push!和pop!, push!压入一个元素进栈, pop!从栈中弹出一个元素. 另外重要的可能是判断栈是否为空的谓词empty-stack?.

现在我们给出一个简单的实现.

以下是例子.

注记1. 我们可以编写几个额外的过程.

这只是风格上的不同, 消息传递风格vs传统过程调用风格.

注记2. 当然, 我们还可以更简单一点.

不过, 如果需要栈的多个实例, 这么做就不方便了.

注记3. 消息传递风格当然也可能有不同的变种, 比如以下的版本.

这样的话, 每个栈对象接受消息之后, 得到的是「方法」 (面向对象的术语). 这么做的好处, 虽然这个例子里面完全没有用, 其中一个是可以引用对象自身. 当然, 我们需要一个辅助过程来调用方法.

我必须要说, 这些东西完全不是我的创制, 而是长久流传于Scheme程序员间的一些习语. 它们可以ad hoc地运用一些面向对象的机制, 但是我要说在Scheme中嵌入一个CLOS (Common Lisp Object System) 式的面向对象系统要比人们想象中的可能要容易得多, 不过这也不在本书中交代.

练习. 给我们的实现添加一些机能, 比如对于最大栈深度和当前栈深度的统计.

练习. 我们的实现基于列表, 另一种典型的实现基于向量, 请读者完成这个实现.

现在让我们引入向量, 在某种意义上它类似于列表, 可以用来表示有限序列.

过程vector, 类似于list, 可以创建向量.

过程vector-ref, 类似于list-ref, 可以取得向量的分量.

过程vector-length, 类似于length, 可以取得向量的长度.

vector-set!, 类似于list-set!, 可以修改向量的分量. (好吧, 我还没提过list-set!. 不过, 一般没有人使用这个过程.)

练习. 编制过程list-set!.

过程vector?判断一个值是否是向量.

向量和列表的不同在于向量是随机可达的, 但列表不是. 回想一下list-ref的定义, 它需要经过许多序对才能到达目标, 而且这个序对的数目是由分量的位置决定的, 当然list-set!也是如此. 但是vector-ref和vector-set!不同, 它们可以在很短的常量时间内完成, 因为从计算机器的实现来说, 当你知道向量对象在什么位置的时候, 就可以直接计算出它每个分量的位置, 但是列表不行, 因为列表是由序对串在一起的.

练习. 实现队列, 一种「先进先出」的数据结构.