转载

(cons '(肆 . 数据类型) 《为自己写本-Guile-书》)

(car 《为自己写本-Guile-书》)

所谓数据类型,是数据集合以及定义在这个数据集合上的一组运算。从大部分计算机的 CPU 的角度来看,存储器中的数据,只是以字节为单位的二值信号,并且 CPU 拥有一组可以操控它们的指令。因此,字节是一种数据类型,而且对于大部分计算机而言是最为基本的数据类型。用汇编语言写程序,就是以字节类型为基础,构造更为复杂的数据类型,然后基于它们用程序模拟真实世界里的一些不太复杂的现象——没人愿意用汇编语言编写大规模并且局限于特定机器的程序。不妨将 Guile 解释器视为 CPU,而 Guile 语言内建的数据类型——原子与序对是对存储器字节类型的抽象。在原子与序对的基础上,可以构造一些基本但是常用的复合数据类型,譬如列表、关联列表、树以及 Hash 表等。以这些数据类型为原料,便可以对现实世界的一些复杂的现象进行程序模拟了。

原子

人要用计算机存储器中的二值信号对真实世界的事物或信息进行模拟,必须对二值信号赋予约定的意义。Guile 认为,布尔值(真与假)、数字、字符、字符串、数组以及符号等是最为基本的信息,需要将它们的意义赋予二值信号,并建立一组能够处理这些信息的运算,这样便建立了一组基本的数据类型,它们被统称为 原子

这些基本的数据类型,一个一个的讲出来,其实是很无趣的。已经有人很耐心的将这些无趣的东西都写了出来。如果想具体的了解一下它们,可阅读 《Teach Yourself Scheme in Fixnum Days》 第 2 章。如果英文不好,或不想花太多时间去看英文,可以阅读这本书的 中文译本 。

要想真正弄清楚原子是什么,只需看懂下面这个谓词的定义:

(define (atom? x)   (and (not (pair? x)) (not (null? x))))

也就是说,只要 x 不是序对,也不为 '() ,那么 x 就是原子类型。Guile 为 '() 定义了一个等价的值 #nil ,但是从本章开始,我不再使用 #nil 。因为 Scheme 标准中没有 #nil ,只有 '()

Guile 对原子类型的变量或值进行求值的过程,相当于直接从存储器中取出数据,然后按照人赋予这些数据的具体意义来解读它们。Guile 解释器能够根据值的形式推断值的类型,进而能推断出绑定到这些值的变量的类型。这样,在使用 Guile 语言编写程序时,不需要像 C 语言那样在代码中显式的声明变量的类型。

更有趣的是,像函数的参数也不需要指定类型,Guile 会认为参数的类型是未知的。例如 atom? 的参数 x 的类型就是未知的。只有在使用函数时,向它传递了具体的参数值,例如:

(atom? #t)

这时 Guile 可以推断出所传入的参数值 #t 的类型是布尔类型,这样便可以确定参数 x 的类型为布尔类型。由于这个过程发生于程序的运行时,因此像 Guile 这样的语言,例如 Python, Lua, Ruby, JavaScript 等,它们被称为动态类型语言。与 C++ 或 Java 的泛型相比,动态类型语言天生就是泛型的。

事实上,Guile 中并未定义 atom? 这个函数,这意味着怎么理解原子,这取决于个人偏好。思考一下,函数应用的表达式是原子么?

(atom? (atom? '()))

序对

序对,就是包含两个元素的数据类型。 cons 运算符可以将两个元素粘连为序对,例如:

> (define foo (cons 1 2)) > (car foo) 1 > (cdr foo) 2 > (pair? foo) #t

carcdr 操作符分别用于取出序对的第一个元素与第二个元素。 pair? 是判断一个表达式是否为序对的谓词。

如果用 C 语言来表示这种序对,数据结构只能设计为:

typedef struct {         void *head;         void *tail; } Pair;

当然,这个 Pair 类型用起来不像 Guile 的序对那样随意。要实现上述 Guile 的效果,还需要定义 conscar 以及 cdr 等运算符:

Pair * cons(void *x, void *y) {         Pair *pair = malloc(sizeof(Pair));         pair->head = x;         pair->tail = y;         return pair; }  #define car(pair, type) ((type *)((pair)->head)) #define cdr(pair, type) ((type *)((pair)->tail))

为了向序对中存入整型数据,需要专门定义一个生成整型数据对象的运算符:

int * mk_int_obj(int data) {         int *obj = malloc(sizeof(int));         *obj = data;         return obj; }

经过上述精心的准备,终于可以写出与 Guile 序对等效的 C 代码了,如下:

Pair *foo = cons(mk_int_obj(1), mk_int_obj(2)); printf("%d/n", *car(foo, int)); printf("%d/n", *cdr(foo, int));

正如上述 C 代码所模拟的序对那样,Guile 的序对所包含的两个元素本质上是两个指针,它们可以指向任意类型的数据对象。不过,我们并不关心序对所包含的元素是不是指针,只关心 carcdr 从序对中所取出的东西,并认为 carcdr 所取出的东西就是序对所包含的东西。

Guile 序对能够存储任意类型的数据,包括序对类型的数据:

> (define bar (cons 1 (cons 2 3))) > (car bar) 1 > (car (cdr bar)) 2 > (cdr (cdr bar)) 3

要写出与上述 Guile 代码等效的 C 代码也不难:

Pair *bar = cons(mk_int_obj(1), cons(mk_int_obj(2), mk_int_obj(3))); printf("%d/n", *car(bar, int)); printf("%d/n", *car(cdr(bar, Pair), int)); printf("%d/n", *cdr(cdr(bar, Pair), int));

虽然 Guile 序对所包含的元素是指针类型,但是 carcdr 取出来的东西是指针指向的值。等效的 C 代码做不到这一点,所以在上述代码中,需要使用 * 对序对中的指针进行解引用来获取指针所指的数据。

列表:序对的级联

基于序对可以构造出列表这种结构:

> (define foo (cons 1 (cons 2 (cons 3 (cons 4 (cons 5 '())))))) > foo (1 2 3 4 5) > (pair? foo) #t > (list? foo) #t

列表是一组级联的序对,并且最后一个序对的第 2 个元素是 '()

'() 表示一个空的列表:

> (list? '()) #t > (pair? '()) #f

因为用一连串的 cons 来构造列表太麻烦了,所以 Guile 提供了一个 list 运算符来简化列表的构造过程,其用法如下:

> (define foo (list 1 2 3 4 5)) > foo (1 2 3 4 5)

也可以直接以值的形式构造列表:

> (define foo '(1 2 3 4 5)) > foo (1 2 3 4 5)

'(1 2 3 4 5)(quote 1 2 3 4 5) 的『简写』,表示引用一个已经存在的列表。虽然在上面的示例中,列表的引用形式与 list 运算符得到的结果相同,但是二者有着本质的区别。以引用的形式构造一个列表,前提是列表的所有元素是已知的,即所有的元素不需要再求值。如果被引用的列表中含有待求值对象,那么这个对象会被视为符号。看下面的例子:

> (define x 5) > (define foo '(1 2 3 4 x)) > foo (1 2 3 4 x)

list 运算符本质上是一个函数,它会迫使 Guile 对它的参数进行求值。例如:

> (define x 5) > (define foo (list 1 2 3 4 x)) > foo (1 2 3 4 5)

不过,在列表的引用形式中,有迫使 Guile 对待求值对象进行求值的办法,请参考本书第二章『输入/输出』中的『反引号与逗号』一节。

如果一个列表 x 中某些元素本身也是列表,那么 x 是树。除此以外,就没什么好说的了。

关联列表

如果列表 x 中的每个元素都是一个序对,那么 x 便是关联列表。除此以外,就没什么好说的了。

Hash 表

Scheme 标准中没有 Hash 表类型,但是 Guile 内建了这种类型,同时,Guile 也提供了复合Sheme 的准标准 SRFI 第 69 条 的 Hash 表类型的实现,还提供了 R6RS 标准中的 Hash 表,三者的用法相差无几。由于使用 SRFI 或 R6RS 的 Hash 表,还需要额外导入相应的模块,所以我选择使用 Guile 的内建版本。

定义一个 Hash 表:

> (define foo (make-hash-table)) > foo #<hash-table 0/31>

make-hash-table 默认会分配 31 个 Hash 表单元。如果知道要向 Hash 表中存储的元素的个数,可以在调用 make-hash-table 函数时设定 Hash 表最少要分配相应数量的单元。例如:

> (define foo (make-hash-table 32)) > foo #<hash-table 0/61>

make-hash-table 分配的单元个数可能不会等于指定的数量,但是它能保证不会比指定的数量少。

hash-set! 可以向 Hash 表中写入键-值对:

> (hash-set! foo 'name "garfileo") "garfileo"

使用 hash-ref 从 Hash 表中以键取值:

> (hash-ref foo 'name) "garfileo" > (hash-ref foo 'not-there) #f

使用 hash-count 函数可以获取 Hash 表中满足指定谓词(检索条件)的键-值对的个数。如果只想查询 Hash 表中存入了多少个键-值对,可将谓词设为 (const #t) 。例如:

> (hash-count (const #t) foo) 1

const 函数是一个二阶函数。也就是说, const 返回一个函数,这个函数可以接受无数个参数,但是它的返回值是 const 所接受的的参数值。

hash-remove! 函数可从 Hash 表中移除一个键值对。被移除的键值是这个函数的返回值。例如:

> (hash-remove! foo 'name) (name . "garfileo") > (hash-ref foo 'name) #f

Guile 的 Hash 表还有许多细节知识,详见《 The Guile Reference Manual 》的『 6.7.14 Hash Tables 』节。不过,对于本书的主题——编写一个文式编程工具而言,上述这几个函数就足够用了。

记录

上面所提到的数据类型要么是 Guile 内建的基本类型与序对,要么是基于序对的各种衍生类型。虽然它们已经足以用于模拟真实世界中的各种现象了,但是并不直观。例如,可以用列表可以模拟人这种事物,只需要将人的属性抽象为可表示为 Guile 原子的信息,然后将这些信息存入表中即可:

(define (创造一个角色 年龄 性别 民族 籍贯) (list 姓名 年龄 性别 民族 籍贯))

下面来模拟一个具体的角色:

> (define 黄蓉 (创建一个角色 16 "女" "汉" "桃花岛")) > 黄蓉 (16 "女" "汉" "桃花岛")

虽然我们自以为是的认为已经模拟出来黄蓉这个角色了,但实际上这个黄蓉只不过是一个列表而已:

> (list? 小女生) #t

既然要模拟,那就应该模拟的更真实一些,像下面这样:

> (角色? 黄蓉) #t

除此之外,还应当能够根据属性的名称来获取列表中的信息,而不是基于 carcdr 的一堆机械操作。例如:

> (角色的年龄 黄蓉) 16 > (角色的性别 黄蓉) 女 > (角色的民族 黄蓉) 汉 > (角色的籍贯 黄蓉) "桃花岛"

也就是说,我们希望能自行定义一种自己喜欢的数据类型,这种数据类型的每个元素是一个访问函数。Scheme 的 SRFI-9 提案为我们提供的记录(Record)类型可帮助我们达到这一目的:

> (use-modules (srfi srfi-9)) ;;; 加载 srfi-9 模块 > (define-record-type     <角色>     (创建一个角色 年龄 性别 民族 籍贯)     角色?     (年龄 角色的年龄)     (性别 角色的性别)     (民族 角色的民族)     (籍贯 角色的籍贯)) > (define 黄蓉 (创建一个角色 16 '女 '汉 "桃花岛")) > 黄蓉 #<<角色> 年龄: 16 性别: 女 民族: 汉 籍贯: "桃花岛"> > (record? 黄蓉) #t > (角色? 黄蓉) #t > (角色的年龄 黄蓉) 16 > (角色的性别 黄蓉) 女 > (角色的民族 黄蓉) 汉 > (角色的籍贯 黄蓉) "桃花岛"

<角色> 便是使用 define-record-type 定义的一种记录类型,它包含 年龄性别民族 以及 籍贯 等属性或域。 define-record-type 不是函数,而是一个宏。我打算在下一章讲 Guile 的宏。

记录类型能存储任意类型的数据,包括函数。例如:

> (define-record-type     <角色>     (创建一个角色 年龄 性别 民族 籍贯 武功)     角色?     (年龄 角色的年龄)     (性别 角色的性别)     (民族 角色的民族)     (籍贯 角色的籍贯)     (武功 角色所习的武功)) > (define 黄蓉 (创建一个角色                 16                 '女                 '汉                 "桃花岛"                 (lambda ()                   (display "落英神剑掌")                   (newline)))) > (define 黄蓉施展武功 (角色所习的武功 黄蓉)) > (黄蓉施展武功) 落英神剑掌

就此止步。再往下走,可能就会跌入面向对象编程的坑。因为所谓的面向对象,讲究的是封装、继承与多态。记录显然是支持用户自定义的一种数据封装形式。如果想让 Guile 面向对象,可以考虑使用 Guile 的 Goops 扩展 。

总结

充满层层括号的 Guile 代码像是『指令流』,Guile 解释器能够根据括号所表达的层次关系有序的解释这些指令。从这个角度来看,Guile 语言像是人类概念上的计算机中的汇编语言。想想看,前缀表达式不正是汇编语言的一大特点么?将一个变量绑定到一个值或表达式上,这个变量像不像寄存器?从这一点来看,Guile 的数据类型本质上是人类概念上的计算机存储空间及基本操作指令集。

也许不会再有比 Scheme 更高层次的编程语言了——抽象之抽象对于真实世界不会再有意义。会存在与它同一级别但是不需要那么多括号的编程语言,而且它们已经存在了。但是,要消除将 Scheme 语言中的括号,需要在编写解释器方面付出很大的代价,结果会导致解释器的内部机制也变得非常复杂。复杂的解释器为了能够正确的运行,必然要对变量或函数的命名以及代码的编排格式提出非常严格的要求。

原文  https://segmentfault.com/a/1190000005591675
正文到此结束
Loading...