2.1 Specifying Data via Interfaces
一般来说,数据类型可以对应多个满足这种类型的实现。比如整数,可以使用阿拉伯数字,也可以通过数点的个数来实现。如果在需要表示一种数据类型时,我们直接定义一种数据类型的实现以及相关操作。但在需要更改实现时,会很麻烦,因为使用者也需要更改所有依赖这种实现的代码。
通过数据抽象,一种数据类型可以分成两个部分:interface(接口,是数据类型的本质特征所在)和implementation(具体实现)。接口表明数据类型(概念上的类型)的特征,具体实现是该数据类型的一种实现。通过这种方式定义的类型也叫abstract data type(抽象数据类型)。使用这种方法,可以只给使用者提供接口,把实现细节隐藏。这样当我们更改数据类型的实现时,使用者不需要更改任何东代码。
如果用户程序只通过抽象数据类型的接口来操作数据,那么用户程序就是representation-independent(具体实现无关)的。
举个例子,自然数这种数据类型,其向外提供以下接口:zero、is-zero?、successor、predecessor。其中zero、successor、predecessor称为constructor(构造器),is-zero?称为observer(观察者)。
实现方法有:Unary representation(一元表示法),Scheme number representation(Scheme语言表示法),Bignum representation(大数表示法)。
如果能知道抽象数据类型的具体实现,这该类型是transparent(透明),如果无法知道,则是opaque(不透明)。如果是透明型的数据类型,则需要约束使用者,让其只使用接口,不依赖具体实现,才能体现抽象数据类型的价值。
2.2 Representation Strategies for Data Types
本节通过使用environments(环境)数据类型来介绍一些实现数据类型的策略。环境数据类型用于关联变量名称和变量值的结构,可以理解成这样一个函数,如果给其一个变量名称,会返回一个值。
2.2.1 The Environment Interface
环境类型包括的接口:empty-env,apply-env,extend-env。
2.2.2 Data Structure Representation
The Interpreter Recipe
- Look at a piece of data.
- Decide what kind of data it represents.
- Extract the components of the datum and do the right thing with them.
2.2.3 Procedural Representation
2.3 Interfaces for Recursive Data Types
Designing an Interface for a recursive data type
- Include one constructor for each kind of data in the data type.
- Include one predicate for each kind of data in the data type.
- Include one extractor for each piece of data passed to a constructor of the data type.
2.4 A Tool for Defining Recursive Data Types
名称:define-datatype
2.5 Abstract Syntax and Its Representation
语法,可以用来表示某种意思。语法分为concrete syntax(具体语法)和abstract syntax(抽象语法),类似数据类型的接口和具体实现。抽象语法通常使用abstract syntax tree(AST,抽象语法树)来表示。
同一个抽象语法,可以对应多个具体语法。例如,概念中的鸟,中文叫“鸟”,英文则叫“bird”,还有其它语言的叫法。不同的文字,可以表示同一个概念。