Scheme程序语言介绍

简介

Scheme 是差不多三十年前诞生在 MIT 人工智能实验室的一门程序语言。它是 Lisp 语言的发展。今天的 Scheme 在程序语言的理论研究和工程应用两方面都发挥着持久和越来越重要的影响。本文作者在 IBM developerWorks 中国网站 Linux 技术专区上的另一个系列，专门介绍 Scheme 在 UNIX 上的应用。本文介绍 Scheme 的语言特性，不涉及具体的应用。在本文最后，我们开发了一个在 Scheme 环境里面模拟中华学习机上 BASIC 语言的简单的程序解释器。

Scheme 的历史和沿革

在网上有这样一句有趣的评论：计算机科学的大部分，就是在重复发现很久以前别人就早已发现过的东西。当然，这是一句玩笑。不过我们可以给这句玩笑接个下巴：对于程序语言中的每一个重要概念，你都可以先在 Lisp 当中发明一次，再在 C++ 里面发明一次，再在 Java 里面发明一次，再在 Python 里面发明一次，再在 Perl 里面发明一次，再在 Ruby 里面发明一次，当然，最后还要在 C# 里面再发明一次。我们以此开始我们对 Scheme 的介绍。^_^

Scheme 的前身是 Lisp。和 Scheme 一样，这也是一门诞生在 MIT 人工智能实验室的语言。据说 Lisp 在程序语言的族谱上，班辈仅次于 Fortran，是第二古老的语言。但和 Fortran 不同，Fortran 经常被大名鼎鼎的计算机科学家批评，作为反面教材，这些计算机科学家当中有著名的图灵奖获得者 Edsger Dijkstra。而 Lisp 和 Scheme 恰恰相反，它们常被计算机科学家作为正面例子，一个优秀作品的例子。赞扬 Lisp 的人当中有 Smalltalk 和图形用户界面的发明人之一 Alan Kay。

Lisp 由图灵奖获得者 John McCarthy 发明。据说一开始 McCarthy 只想把这门他正在设计的语言的语法的设计，往后拖一拖，等到后面有趣的工作做完了，再回头来给这门基于 Lambda 演算的程序语言加上为数学家们所熟悉的语法。可是 McCarthy 的一个学生很快发现，直接在还没有正式语法的抽象语法里面写程序，感觉非常好。就用不着一个正式的语法了。于是 Lisp 诞生了。Lisp 重要的特征就是：第一，基于 Lambda 演算的计算模型；第二，加上 List processing，这也是 Lisp 名称的由来；第三，直接在抽象语法里面工作，这是非常特别的。前两个重要特征，是 McCarthy 天才的设计，第三个特征则是有趣的巧合。

又过了十多年，还在 MIT 人工智能实验室，不过这次不是 McCarthy，而是两个更年轻的计算机科学家。Guy Steele, Jr. 和他的老师 Gerald Sussman 合作对古典 Lisp 做了两个重要改进。一是把 Lisp 从 Dynamic scope 变成了 Lexical scope。现在大家熟悉的几乎所有的语言都是 Lexical scope，所以大家见怪不怪了。后来 Steele 成为 Common Lisp 设计的主力，Common Lisp 把 Scheme 的 Lexical scope、还有其它一些由 Scheme 所创造的特征，都加入到主流 Lisp 语言当中，Dynamic scope 终于成为了历史。Steele 和 Sussman 做的另一个主要改进是把 Continuation 这个概念引入到程序语言里面。这样一门新的程序语言就此诞生。他们按照人工智能实验室的传统，把它命名为 Scheme。

这个 Continuation 据说是计算机科学里面，在程序语言设计这个领域，最让人感到激动，并且在开始学习的时候，也是最让人感到困惑的概念。或许有些读者朋友听说过 Continuation，这些读者朋友可以尝试分析一下下面由 David Madore 提出的著名的"阴阳迷题"。David Madore 是有名的 Unlambda 语言的发明人。

(let* ((yin ((lambda (foo) (newline) foo)
             (call/cc (lambda (bar) bar))))
       (yang ((lambda (foo) (write-char #\*) foo)
              (call/cc (lambda (bar) bar)))))
  (yin yang))

初学 Scheme 的读者朋友可以不管这个迷题。这是个专门写出来让人伤脑筋的东西。不过，如果能自己弄懂这个迷题，那说明你的确弄懂了 Continuation 是怎么回事了。对于一般使用 Continuation 来说，并没有这么样的古怪和晦涩。读者朋友大可放心。至于那个 Unlambda 语言也是如此。Unlambda 据说是函数式程序设计语言家族里面的 Intercal。和 Intercal 一样，也是一个专门折磨人的语言。

Steele 和 Sussman 发明了 Scheme 以后，写了份 Report on Scheme。后来经过修改，又发布了 Revised Report on Scheme，这样不停的 Revise 下去。根据大师们历史悠久的找乐子的光荣传统，这一系列的 Report 被依次命名为 R2RS、R3RS、R4RS 和目前最新的 R5RS。现在还没有听说 R6RS 的消息。R4RS 是 IEEE 制定的 Scheme 语言标准的基础。 R5RS 比起这个 IEEE 标准，主要增添了"卫生（Hygenic）"的 Macro 支持。

R5RS 之前，Lisp 的 Macro 就早已是程序员非常喜欢的、非常强大的语言特征。前面说过， Lisp 没有正式的语法，程序员直接在抽象语法树里面写程序。他们为什么喜欢这样呢？原因主要是他们发现，直接在抽象语法树上工作，其实是个非常大的便利，这使得 Lisp 可以拥有强大的 Macro。据后来 Steele 和 Richard Gabriel 所回忆，在 Lisp 历史上，不断有人想给 Lisp 加上正式的语法，这些努力和尝试包括 Apple 公司支持的 Dylan 语言，可是这些努力每一次都失败了。主要原因，就是 Lisp 的 Macro 浑身上下都散发出让人头晕目眩的迷人魅力。它拥有无比的能量，又让初学者感到无比的困惑。

传统 Lisp 的 Macro，在 R5RS 的作者们看来，有严重的缺陷，这促使他们在 R5RS 中发明了"卫生"的 Macro。可是这个卫生的 Macro，反过来又遭到了传统 Lisp 支持者的严厉批评。

对于不太熟悉程序语言理论的读者朋友来说，上面讲到的内容，Lexical scope 和 Dynamic scope，还有基于 Lambda 演算的 List processing，以及 Continuation 和卫生的 Macro，这些概念可能一时让人摸不着头脑，不过不要紧，这些内容我们以后都会讲到。读者朋友弄明白了这些概念以后，可以回过头来看看这里的历史介绍。

Lambda

首先介绍 Lambda。许多非常精彩、非常重要、也非常困难的概念，随着时间发展，慢慢变成了日常生活中丝毫不引起人注意的事情。比如火和轮子这样关系到人类文明进程的重大发明，数字"零"的发现，等等。计算机科学里面也是如此。计算机科学发展的幼儿时期，数理逻辑中的 s-m-n 定理和通用图灵机等的发现，都被认为是重要成果，可是今天，许多熟悉电脑的中学生都知道，用软件模拟通用计算机是可能的。关于 Lambda 演算的理论也差不多是这样。

如果不是专门研究 Lambda 演算的理论，Lambda 对于今天的程序员来说，几乎是个透明而不可见的概念。实在是太普通，都很难把它说的有趣一点，或者看上去深奥一点。因为所谓Lambda，其实就是表达了区区一个"函数"的概念而已。不过，在 Scheme 里面，Lambda 还是表达了两个值得注意的重要特征。第一个，就是广泛的允许匿名对象的存在。这很难说和正宗的 Lambda 演算的理论有特别的联系，它更像是由 Lambda 演算的理论所衍生出来的编程风格。第二个特征，就是所谓的高阶函数。这个特征和 Lambda 演算理论息息相关。高阶函数是 Lambda 演算理论的精髓，是由 Lisp 首先介绍到程序语言这个世界的。也是大量的现代语言，比如流行的 Python 当中一个似乎是不那么引人注目的特征。

下面我们分头介绍这两个和 Lambda 演算理论紧密相关的 Scheme 特征。

高阶函数

Python 发明人 Guido van Rossum 和 Fred Drake 编写的 Python Tutorial 第 4.6 节列举了下面的例子。

>>> fib

>>> f = fib
>>> f(100)
1 1 2 3 5 8 13 21 34 55 89

对于事先不了解 Lambda 演算理论的读者朋友来说，第一次看到上面例子的时候，哪会想到背后深刻的理论基础和悠久的历史发展呢？这似乎就是公路上数不清的普通的轮子当中的普通的又一个而已，谁会想起生活在石器时代的我们的先祖们第一次看到这个滚动的玩意儿的时候是怎样的兴奋呢？不过，计算机科学就是不一样，如果你当真想亲眼看到有人对"轮子"发出由衷的赞叹的话，可以找一个 C 或者 Pascal 语言的程序员来碰碰运气。不过，如果你的运气实在不好，也许会听到类似下面的话的哦。"轮子？没有我家的小叫驴好呀！"

玩笑说了这么多，我们下面讲点干巴巴的"理论"。^_^

高阶函数有两点内容。第一是让函数对象成为程序语言当中所谓"第一等公民"。我们所说程序语言当中的"第一等公民"，指的是可以对这样的数据对象进行赋值、传递等操作。就像我们可以对整数型变量所做的那样。如果函数对象也是程序语言当中的第一等公民，我们就可以像上面列举的 Python 的例子那样，把函数对象在变量之间进行赋值和传递等操作。

高阶函数的第二点内容是像下面这样。既然函数本身，就像整数或者浮点数那样，成了我们所谓"第一等公民"，我们当然就希望可以像以前能够做的那样，在我们需要的时候，把所有这些"第一等公民"，拿在手上揉来揉去、捏来捏去，无论它们是整数型数据、或者是浮点型数据、还是函数型数据。我们要把它们这样变换过来，再那样变换过去。把这些"第一等公民"放到我们的变换函数里面，对它们进行任意的、我们所需要的各种各样的操作。换句话说，我们可以像对待整数和浮点型数据那样，把函数本身也作为某个函数的输入数据和输出数据。也就是说，我们的函数可以对函数本身进行操作。这些可以操作别的函数的函数的地位不就是更高级了吗？这就是所谓"高阶"这个词的由来。

匿名函数

除了高阶函数这个本质性的东西以外，Lambda 在 Scheme 里面还代表了一种原则。这个原则就是把程序语言中的对象和对象的名字分离开，并且允许存在匿名对象。对于和 Lambda 直接相关的"函数"这个概念来说，就是允许存在匿名函数。函数可以没有名字，在我们需要的时候，又可以给它加上名字。这更多的是一种需要程序语言提供支持的编程风格。这个所需要的支持，就是对上面所说"高阶函数"的支持。确实有一些程序语言在实现高阶函数的时候，却没能够提供对匿名函数的支持。这的确是一个有趣的现象。当然，在这样的语言中加上对匿名函数的支持是轻而易举的。

把数据对象和变量名称剥离开来的原则，对于程序员来说，是非常大的解脱。就像 Lisp 和 Scheme 程序员视为当然的自动内存管理一样，这也是一个 Lisp 和 Scheme 程序员享受了很久的东西，可是 Lisp 这个圈子外的程序员直到最近，才开始接触到这些概念。要知道， Lisp 据说是自 Fortran 以来，第二个最古老的语言哦。像自动内存管理这样的技术，直到上世纪九十年代中后期，才开始被 Lisp 圈子外的程序员所了解。而这其实是 Lisp 程序员自上世纪六十年代以来，就一直在享受的东西。

在以后的例子里面将会具体的看到用 Lambda 定义匿名函数的例子。到时候，我们将有机会看到这样的匿名函数对于编程来说，是多么方便。

直接在抽象语法上工作

Lisp 要求我们直接在抽象语法上工作。这个抽象的语法树用成对的括号表示。这样的结构在 Lisp 圈子里面被称为 sexp 表达式。

(simple sexp without deep structure)

上面列出的就是个很平板的 sexp 表达式。这样的 sexp 的第一个单词，是决定这个表达式含义的关键单词。

(expr with (deep (and deep (structure)) which makes) (everyone) panic)

上面这个 sexp，用嵌套的圆括号表达了一个复杂一点的树状结构。我们可以把它分解了来看。第一层的结构如下所示。

(expr with ( ) ( ) panic)

第二层的结构如下。

(deep ( ) which makes) (everyone)

第三层的结构如下。

(and deep ( ))

其实这样的 sexp 是很容易分析的。如果我们把 sexp 看成是函数调用的话，那么用通常的方式写出来就是下面这样。

(func arg1 arg2) ==> func(arg1, arg2)

嵌套的括号，相当于嵌套的函数调用。

(func1 arg1 (func2 arg2 arg3) arg4) ==> func1(arg1, func2(arg2, arg3), arg4)

从这个角度来说，可以把 Lisp 程序看成是完全由"函数调用"这个单一的语法结构构成。 Lisp 里面没有为了算术表达式、或者逻辑表达式、或者语言的关键字，比如 IF 和 THEN，来准备特别的语法结构。所有的语言元素在 Lisp 里面都是按照这个简单一致的语法结构来安排。不过和一般的程序语言里面不同的是下面这个表达式。

((meta-fun arg1) arg2 arg3) ==> (meta-fun(arg1))(arg2, arg3)

虽然可以像上面右半边那样，硬把左半边的 sexp 翻译过来，但是右边的这个式子在大多数普通程序语言里面是不合法的。深层次的原因，就是 Lisp 按照 Lambda 演算发展的计算模型有对高阶函数的支持。而高阶函数在一般程序语言里面是不存在的。关于这一点，我们以后还会讲到。还有，上面左半边的式子所体现出来的，把 sexp 第一个关键单词，变为可以由进一步的函数调用而生成，就像 sexp 后面其它的非关键的单词可以由函数调用生成一样，这是 Scheme 的发明。是由 Scheme 介绍到 Lisp 的大家族中来的。

如果读者朋友了解一些编译理论的知识，就会看出来，上面的 sexp 所描述的，其实就是一般的程序语言在经过语法分析这个步骤以后，编译器得到的抽象语法树的表示形式。后面讲到 Macro 的时候，可以看到语言语法上这样安排的好处。从简单而直接的角度来看，这样的安排，有一个明显的好处，还有一个明显的坏处。

明显的好处，就是程序员不用像在其它程序语言里面那样，去特别记忆各种不同的语法结构以及这些结构之间进行组合所要考虑的优先级的安排、结合律的安排、以及语法变形的安排。这些问题统统一去不复返。sexp 的第一个单词决定了 sexp 的意义，剩下的单词都是参数。记住这一条规则足够了。

明显的坏处，就是大量的括号，以及括号的深层嵌套，使得括号匹配成了件让人畏惧的事。这是为什么 Lisp 程序员几乎无一例外的喜欢 Emacs 编辑器的原因。因为在 Emacs 的帮助下，括号匹配对于 Lisp 程序员来说，就不再是一头拦路猛虎。关于 Emacs 和 Lisp 以及Scheme 的协调合作，我们在以后的文章中会详细的讲到。

List Processing

Lisp 是 List Processing 的缩写。意思是说这门语言是用来做 List Processing 的。可见 List 在 Lisp 当中是多么重要。List 是 Lisp 中最重要的数据结构。这个数据结构乍看起来，有点像 C 语言当中的链表。不过这里有些细微差别。我们下面详细的说明 Lisp 这个最重要的数据结构。

List 的基本构成元素是所谓的 Pair。什么是 Pair 呢？我们可以按照这个英语单词在日常生活中最常见的意思，就是一对夫妻，来想象 Lisp 这个最基础的数据结构。一对夫妻，比如说是王先生和王太太，就是一个 Pair。来设想一个"古怪"的场景。假设好多对夫妻，王先生和太太、沈先生和太太、张先生和太太、等等，他们一起玩一个叫做 List Processing 的游戏。在这个游戏中，每一对夫妻都始终聚在一起，永不分离。整个游戏过程中，先生和太太每个人都只能记住不超过一件事情。被记住的事情，可以是另一位先生或者太太，也可以是游戏现场的一张沙发、一个茶几、或者是游戏现场的一个位置，比如阳台或者厨房、又或者是当天报纸上的一条新闻、电视上的一个牙膏广告、等等。安排好以后，这些先生和太太们邀请现场的一位酒吧招待扮演 Lisp 中央处理器的角色。

下面介绍 List Processing 游戏的更进一步的规则。首先是 CAR 规则。如果扮演中央处理器的酒吧招待走到一对先生和太太面前，高喊一声"看啊！"那么，这一对先生和太太当中的太太，就要把自己记住的事情告诉酒吧招待。如果这位太太什么都没有记住，她就应该保持沉默，并且摇摇手，表示自己什么都不知道。

第二条规则是 CDR。和第一条规则类似，当酒吧招待走到一对先生和太太面前，高喊一声 "苦的！"那么这对夫妻当中的先生，就要把自己记住的事情告诉酒吧招待。如果这位先生什么都没有记住，他也应该要闭紧嘴巴，并且摇摇手，表示自己什么都没记住。

第三条规则是 CONS。在这条规则中，酒吧招待先要安排好两件要被记住的事情。然后，酒吧招待要从客厅里目前还在空闲着的先生和太太们当中随便选出一对，对他们大喊一声"看死！"然后，酒吧招待就把事先安排好的两件事情当中的第一件事情，交给这对先生和太太中的太太来记住。再把第二件事情，交给这对先生和太太中的先生来记住。

上面这三条规则，CAR、CDR 和 CONS 就是 List Processing 游戏里面最基础的三条规则。有了这三条规则，就可以玩一个"简单二叉树"游戏。但是这样的玩法一般比较费时间，所以通常大家都会用这三条基本规则，来定义一些更高级、也更复杂的规则，加快游戏进度。所以等到你和你女朋友以后结了婚，也想加入世界上数不清的 Lisp 程序员之间的夫妻周末聚会，也来玩 List Processing 游戏，仅知道上面的三条规则是不够的，你和你女朋友、未来的妻子，还要继续学习后面要讲的，更重要的 Macro 规则。

不过，Macro 规则不像 CAR、CDR 和 CONS 三条基本规则。这三条基本规则在世界上任何一个 Lisp 周末聚会上，都是一成不变的，不会引起任何有关规则的争吵。而 Macro 规则恰恰相反。就像扑克牌游戏里数不清的各种各样古怪规则一样，几乎只要每换一个晚会，就都会有不同的 Macro 规则，而且每个晚会的组织者都是只要一有机会，就对其它晚会上的 Macro 规则大加鞭挞，言论之间充满鄙夷和不屑。虽然这些不同风格的 Macro 规则本质上是一样的。但是大量微妙的细节，也会让新加入的先生和太太们感到困惑和不适应。而且，新来的先生和太太们往往因为怀念以往熟悉的 Macro 规则，而在新加入的社区遭到无情嘲笑。

不过，以后再详细讲 Macro。下面先看看"简单二叉树"游戏。

简单的二叉树

"简单二叉树"其实不是一个游戏，而是一个游戏策略。真正的游戏，叫"搜索和排序"。这是不同街道的 Lisp 晚会组织者经常在一起竞争的一个游戏，或者不如说是一个比赛。在比赛当晚，两个街道的 Lisp 周末聚会的参加者聚在一起，组成两个队伍，每一个队伍都按照前面说的那样各自安排好一个酒吧招待，然后两个队伍各自按照自己的游戏策略，开始进行运算，看哪一支队伍的运算速度快，能够抢先得到符合要求的结果。关于这样的比赛的具体安排，有兴趣的读者可以参考著名的计算机科学家 Donald Knuth 的"编程的艺术"，那套三卷本的巨著。这里不详细叙说了。下面来讲"简单二叉树"具体的游戏策略。

这个游戏策略需要数量相当多的、一对又一对的先生和太太们。而且还要在他们之间进行紧密合作。首先，要把这一对一对的先生和太太们分成小组。每个小组由三对先生和太太组成。这样的小组被称为节点。节点中的第一对先生和太太负责节点的维护和管理。这一对先生和太太当中的太太，要负责召集第二对先生和太太。而第一对当中的先生要负责召集第三对先生和太太。

前面在最基本的游戏规则中规定过，参加游戏的先生和太太每人只能记住不超过一件事情。在上面的安排中，节点中的第一对先生和太太，他们各自记住的唯一一件事情，就是如何分别找到第二对和第三对先生和太太。

节点当中的第二对先生和太太，他俩每人各自要负责记住这个节点要记忆的两件事情当中的一件。事情由酒吧招待交待给这个节点。这两件事情中，太太所记住的这件，称为"键"。先生记住的这件，被称为"值"。当酒吧招待走到他们这个节点前，如果酒吧招待大喊一声 "给我你们的键！"那么，这个节点中领头的那对先生和太太当中的太太，就要赶紧把节点中的第二对先生和太太召集来，然后，第二对中的太太，要把自己记住的事情汇报给酒吧招待。如果酒吧招待大喊"给我你们的值！"接下来应该发生的，读者应该能依葫芦画瓢，自己想出来了。

这里酒吧招待大喊的"给我你们的键！"或者"给我你们的值！"其实是两个 Macro。如果我们把这两个 Macro 扒开来仔细看，就会看到下面的情况。以"给我你们的值！"为例。

酒吧招待走到节点的第一对先生和太太面前，大喊"看啊！"于是这对中的太太，就把自己知道的事情告诉酒吧招待。这件事情，就是在客厅的哪个角落可以找到节点中的第二对先生和太太。酒吧招待于是自己找到第二对先生和太太，然后，对他们大喊一声"苦的！"于是第二对中的先生就把自己知道的事情，告诉酒吧招待。这件事情，就是这个节点的"值"。

所以，像"给我你们的键！"或者"给我你们的值！"这样的喊话，其实就是 CAR、CDR 和 CONS 的 Macro 组合。这里的这两句喊话没有用到 CONS，在以后的例子里面，能看到用到CONS 情况。

酒吧招待还有可能自己事先安排好一件事情，要分配给节点来记住。如果是这样，当她或者他走到节点的领头的先生和太太面前时，她或他就大喊"设置你们的键！"或者"设置你们的值！"然后，相应的，这个节点的第二对先生和太太被召集来以后，先生或者太太就要记住酒吧招待安排的事情。原来记住的事情就被忘掉了。

节点当中的第三对先生和太太，他俩也是每人各自要负责记住一件事情。太太负责记住的事情被称作为"左"。先生负责记住的事情，被称为"右"。太太负责记住的"左"，就是另一对先生和太太当中太太的位置。先生负责记住的"右"，也是一样类型，是另一对先生和太太当中太太的位置。

如果"简单二叉树"游戏没有出毛病，那么在正常的情况，上面第三对先生和太太各自记住的另外两个太太，她们各自都应该是另外某两个节点当中领头的那对先生和太太当中的太太。

讲了这么半天，如果再讲下去，可能大家真的会忘记我们是在讲 Lisp 和 Scheme！还是不要继续讲先生和太太了。还是回到平日常见的所谓"很 Dry"的计算机科学"专业语言"上来吧。^_^

上面的安排，其实就是用 Lisp 的三个 Pair 实现二叉树的一个 Node。换句话说，上面的例子，显示了如何使用这样看上去很简单、很原始的 Pair 数据结构，来表示复杂的、常见的数据结构。这一点是 Lisp 的精髓之一。在 Lisp 里面，所有的数据结构，最后都归结为 List，归结为 Pair，以及在 Pair 上进行的 CAR、CDR 和 CONS 操作。

许多程序语言的设计者都看不到这一点对于程序语言的重要影响。一个简单、一致、而且足够强大的数据模型，对于程序员来说，是非常重要的事情。可是这一点，偏偏就被绝大多数程序语言所忽视。以后的例子里，会反复看到对这个观点的一再强调。离开了具体的例子，的确很难让这个观点具有足够强的说服力。否则，也不会有那么多程序语言会忽略这个问题了。

Macro

下面讲 R5RS Scheme 中所谓卫生的 Macro。这个 Macro 被支持传统 Lisp Macro 的程序员强烈批评。这些批评中陈述的卫生的 Macro 的缺陷，在下面的例子程序里也会看到。不过本文并不打算详细分析这两个 Macro 系统的利弊。无论如何，这两个 Macro 系统都能恰如其分的体现 Lisp 这一族程序语言在全体程序语言世界里鹤立鸡群的地位。

可能有部分熟悉 C 语言的程序员，一听说 Macro，就想起 C 语言预处理器的噩梦。请这些读者大可放心。Lisp 的 Macro 无论是卫生的还是不够那么卫生的，都远非 C 语言预处理器所可以相提并论。

R5RS 中的 Macro 采用模式匹配的方式来定义和使用。首先用 Macro 编写者提供的模式，去匹配程序中相应的 sexp 表达式。如果发生匹配，则按照匹配的效果，给模式中的变量赋值。模式中这些变量得到相应的赋值后，就可以用这些变量，再按照由 Macro 编写者所提供的，和匹配的模式相对应的模板，来生成另一个 sexp 表达式。Macro 的效果就是由一个 sexp，翻译成另一个 sexp。用到一个模式匹配，再用到一个相应的模板改写。这就是 Macro 简单明了的语义。其实是很容易掌握的。可是在 Lisp 以外的语言里，却从来都没有把它做漂亮。想想 C 语言预处理器里那个恐怖的取消换行效果的"\"字符。

定义 Macro 要用到的语法结构如下。大写的字母表示 Scheme 关键字。在实际写程序时，可以用小写字母。一般都用小写字母。这里用大写字母不过是为了醒目。

(DEFINE-SYNTAX macro-name
(SYNTAX-RULES (literal ...)
匹配以及改写规则之一
匹配以及改写规则之二
匹配以及改写规则之三 等等))    

上面的"匹配以及改写规则"按下面这样来写。

(匹配用的模式 改写用的模板)

每个模式都对应一个模板。一个模式就是一个 sexp。第一个单词为"macro-name"或者简单写成"_"。表达式中出现的其它单词，不管位于层次多深的嵌套括号之中，只要不是在前面定义中出现的 literal 中的一员，就被当作当前模式的一个变量。如果这个模式确实发生了匹配，这些变量就被赋予相应的匹配所捕获的单词。

比如下面这个模式。

(_ (var1 var2 ...) var3 ...)

三个点的省略号含义是很直观的。简单的说，它表示后面可能还有若干个在同样的括号嵌套层次上的单词，或者是成对括号括起来的组合，可能也需要匹配。上面这个模式匹配起来就是像下面这样。

匹配 (macro-name (some wonderful roads to) 

                         gandor (the land of) the kings)
不匹配 (macro-name ())
不匹配 (macro-name dragon of the (iron hill))

上面第三行，不匹配的原因是，前面的模式要求 macro-name 后面必须紧跟着一对括号括起来的一个组合。而上面第三行，紧跟在 macro-name 后面的只是一个单词，并不是括号括起来的组合。

在上面第一行发生的匹配中，模式变量 var1 变成了单词 some，模式变量 var2 和后面的省略号，涵盖了 wonderful roads to 三个单词。模式变量 var3 和后面的省略号覆盖了四个元素。第一个元素是单词 gandor，第二个元素是一对括号中的全部内容"(the land o f)"，再后面的两个元素，是单词 the 和单词 kings。

前面讲了模式匹配，以及模式变量的赋值。下面看模板。模板和匹配的模式变量被一起用来重写原先的 sexp，生成另一个 sexp。来看和上面的模式一起的下面这个模板。

(if (+ var1 (beautify var2) ...) (quote var3) ...)

上面这个模板中用到了全部模式变量。按照这个模板，前面匹配的 sexp 就被改写成下面这样。

(if (+ some (beautify wonderful)
        (beautifu roads)
        (beautify to))
(quote gandor)
(quote (the land of))
(quote the)
(quote kings))
    

模板中，模式变量以外的单词，比如上面的 if、+、beautify 和 quote，这些单词被原封不动的拷贝到结果的 sexp。模板中的那些三个点的省略号所起的作用，直观上的含义是很清楚的。

看完这个例子，再来把上面 Macro 的定义在下面完整写出来。这个 Macro 的定义只用到一条模式匹配规则，以及相应的模板重写规则。一般的 Macro 定义，经常出现多条模式匹配规则。在后面模拟 CEC-I 型中华学习机 BASIC 语言的简单程序里能看到很多这样的例子。

     (define-syntax macro-name
  (syntax-rules ()
    ((_ (var1 var2 ...) var3 ...)
     (if (+ var1 (beautify var2) ...) (quote var3) ...))))
     

由于篇幅限制，只举了区区一个 Macro 的例子。更多的例子在程序里。

中华学习机 BASIC 语言

来看一个完整一点、复杂一点的例子。这个例子里，用标准的 R5RS Scheme 实现了一个变了形的中华学习机 BASIC。首先介绍一下中华学习机。这是上世纪八十年代末到九十年代初，国内生产的和当时美国著名的苹果 //e 型计算机兼容的家用教学型计算机。CPU 是 Motorola 八位的 6502。内存是 64K 字节。整个主机装在键盘下面。键盘加上主机，就是一个一寸多厚的盒子，长和宽比现在的笔记本电脑的键盘差不多。通常接一个黑白电视机做显示器。也能接彩色电视机，但是彩色的颜色太花，眼睛不舒服。

一开始用一个磁带录音机，担任现在计算机里硬盘的角色。录在磁带里的程序，在录音机里播放起来，吱吱尖叫。从录音机里读写数据时，音量要调整合适，还不太容易。否则，数据就读不出来。后来没多久，就有五英寸单面的大软盘可以用。运行的系统是 DOS 3.3。

中华学习机里装有 BASIC 语言环境，还有一个 LOGO 语言环境。可以在系统起动时选择，进入两个系统中的哪一个。LOGO 的小海龟可以用来轻松的画出各种各样递归花式的图形。 BASIC 环境下也有画图功能。不过它的编程接口比起 LOGO 来说，要更加原始、粗糙。LOGO 和 Lisp 和 Scheme 一样，也是诞生在 MIT 人工智能实验室。不过下面讲到的例子并不牵涉 LOGO。

这个例子在 Scheme 里实现一个内嵌的、变形的 BASIC 语言。这个 BASIC 是本文作者按照CEC-I 型中华学习机用户使用手册上面的介绍，花了一个晚上外加一个白天编写的。没有经过仔细设计。实现的功能也很简陋、很粗糙。主要目的，是作为一个例子程序而已。

BASIC 一个重要的、也是很有趣的特征，是在程序里面，每个语句都要分配有一个行号。而且这个行号可以在 GOTO 语句和 IF ... THEN ... 语句里使用。以控制程序运行流程。这是在实现 BASIC 语言解释器时，首先要考虑的。怎样才能方便的实现这个根据行号，在程序中任意往前或往后跳转的功能呢？首先想到的就是用 Scheme 的 Continuation 这个可以说是"终极"的实现程序流控制的结构，来实现 BASIC 当中按照行号来对程序流控制的功能。

基本的想法，就是在每一行 BASIC 程序前，把那一行 BASIC 语句行号代表的程序流的 Continuation 记录下来。等到在 GOTO 语句或者 IF ... THEN ... 语句里面要跳转到某个行号时，就转到相对应的 Continuation 继续执行。这样我们对 BASIC 里面最根本的特征的实现，已经有了一个基本思路。接下来，应该要想一想实现的"外观"。

所谓的"外观"，就是指我们想要做出一个什么样的用户界面。当然这个"用户界面"不是指什么图形用户界面，而是说，对于使用我们这个 Scheme 版本的 BASIC 语言的程序员来说，我们希望他们看到什么样的界面。最终的决定如下。我们希望两个语言之间能有紧密联系。当然以 Scheme 为主，并不希望做独立的 BASIC 语言解释器。我们希望我们的 BASIC 能够内嵌在 Scheme 宿主里面，作为一个"嵌入式"语言。程序员在使用 Scheme 编程的时候，可以方便的在宿主 Scheme 和"嵌入式"的 BASIC 之间方便的切换。这促使我们考虑用 sexp 加上 Macro 的方式来实现我们的目标 BASIC。而且，这样的设计，就让我们避免了对于程序语言的开发者来说，一定程度上是"穷极无聊"的语法分析的任务。

用 Continuation 加上 Macro 来实现一个嵌入式的 BASIC。我们的目标定下来了。接下来就是程序代码的编制工作。首先，是实现下面的 Macro。

		       (define basic-program
  (cec1-basic (10 some BASIC statement)
              (20 another BASIC statement)
		       (30 yet another BASIC statement)
		       (40 and some more BASIC stmt)
		       (50 yet some more ...)))
		       

我们希望能够像上面这样，让这个名为 cec1-basic 的 Macro 能够实现一个匿名函数，能够把括号内的变形的 BASIC 语句变成 Scheme 里面的匿名函数。然后，就可以用 Scheme 标准的方式来操作这个匿名函数。

上面的分析，带来一个很头疼的问题，就是这个名为 cec1-basic 的 Macro 必须十分的强大，能够完全识别，并且转换我们的稍微变形的 BASIC。要求这么高的一个 Macro，要自己做这么多事情，很难想象我们可以在一个屏幕的代码里就完成这么多工作。一个跨越多个屏幕的巨大的 Macro，仅仅是想一想，也让我们感到不太舒服。我们需要有个办法，能把这个巨大的 Macro 分解成若干个小小的 Macro，每个 Macro 定义都控制在二十行代码以内。这样，整个任务才不至于失控出轨。下面就来介绍所谓"Macro 级联"的技术。这个技术把一个大的 Macro 分解成若干个小的 Macro，并且把它们级联在一起，达到同样的运算效果。

级联的 Macro

来看程序中实际使用的例子。首先看到 basic-stmt 的定义。

     (define-syntax basic-stmt
  (syntax-rules ()
    ((_) "WHEN WE WERE YOUNG!!")
    ((_ stmt ...)
     (basic-stmt-let stmt ...))))
     

在这个 Macro 定义里，使用了两条"匹配-改写"的规则。第一条规则确保在这个 Macro 没有参数的时候，可以跳出 Macro 级联。第二条规则，只有在第一条规则没有发生匹配的时候，才会生效。一旦它生效，第二条规则就一定会匹配，这使得第二条规则中定义的"改写"一定会发生。这就引出下面定义的这个 Macro。

     (define-syntax basic-stmt-let
  (syntax-rules (let =)
    ((_ (num let var = expr) stmt ...)
     (decl-stmt (num stmt ...)
	 (save-machine-mem var (basic-expr expr))))
    ((_ stmt ...)
     (basic-stmt-print stmt ...))))
     

上面的这个 Macro 处理我们变了形的 BASIC 中的 LET 语句。就像前一个 Macro 定义一样，这个 Macro 定义也包括了两条"匹配-改写"规则。第一条规则负责处理 LET 语句。第二条规则，就像前面一样，也引入一个新的 Macro。这样，就依次引入了一系列的 Macro，一个跟在一个的后面发生作用。达到了"级联"的效果。如果不采用"级联"的写法，上面的这两个 Macro，可以被合并，放到单独的 Macro 定义里面。比如像下面这样。

(define-syntax big-macro
  (syntax-rules (let =)
    ((_) "WHEN WE WERE YOUNG!!")
    ((_ (num let var = expr) stmt ...)
     (decl-stmt (num stmt ...)
	 (save-machine-mem var (basic-expr expr))))
    ((_ stmt ...)
     (basic-stmt-print stmt ...))))

我们看到，这些所谓级联的 Macro，实际上就是把一个拥有 N 条规则的大 Macro，变为 N 个小 Macro，每一个小 Macro 只有两条规则。这样就可以确保这些小 Macro 在一个屏幕之内就能写完。这些小 Macro 里的第二条规则，是肯定发生匹配的规则，在这条规则的"改写"部分，就把控制传递给"级联"的下一级 Macro。乍看起来，总的规则数翻了一番。但是从另一个角度来说，由于每个 Macro 都相对简单，只完成一件明确的任务，整个程序就更容易维护了。从程序运行效率的角度来说，由于 Macro 耗用的完全是程序运行之前，编译时的开销，所以这样"级联"的 Macro，完全不会对程序运行速度造成坏影响。

读者朋友在提供下载的文件包中的 cec1-basic.scm 这个 Scheme 程序里，可以看到完整的 "级联"的 Macro 的定义。

注：本文原作者赵蔚 (zhaoway@public1.ptt.js.cn)