|
|
Scheme 是差不多三十年前诞生在 MIT 人工智能实验室的一门程序语言。它是 Lisp 语言的发展。今天的 Scheme 在程序语言的理论研究和工程应用两方面都发挥着持久和越来越重要的影响。本文作者在 IBM developerWorks 中国网站 Linux 技术专区上的另一个系列，专门介绍 Scheme 在 UNIX 上的应用。本文介绍 Scheme 的语言特性，不涉及具体的应用。在本文最后，我们开发了一个在 Scheme 环境里面模拟中华学习机上 BASIC 语言的简单的程序解释器。
简介
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
<function object at 10042ed0>
>>> 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。下面先看看"简单二叉树"游戏。
|
|
IP卡
狗仔卡
发表于 2006-9-27 16:36:34
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡
楼主
发表于 2007-2-8 23:24:22
