2008年5月11日星期日

Scheme语言深入

一、关于符号类型

符号类型又称引用类型,在概要一文中本人介绍得非常的模糊,使很多初学者不理解。符号类型在Scheme语言中是最基础也是最重要的一种类型,这是因为Scheme语言的祖先Lisp语言的最初目的就是符号处理,在Scheme语言中几乎所有的东西都可以看做是符号或做为符号列表来处理,这也是我们把符号类型做为第一个问题研究的原因。

与符号类型相关的关键字有四个,分别是:quote, quasiquote, unquote和unquote-splicing,如下所示:

规范用法:(quote obj)
简化用法:'obj (注意,'为右单引号,"双引号下面的那个符号。)
意义:符号类型的定义,(quote obj)本身就是一个值,虽然它不如数字123这样直观。

规范用法:(quasiquote obj)
简化用法:`obj (注意,`为左单引号,~波浪号下面的那个符号。)
意义:"类似符号"类型的定义,最好称之为逆符号类型,它可以将符号类型转换为具有实际意义的东西。

规范用法:(unquote obj)
简化用法:,obj (注意,,逗号,<小于号下面的那个符号。)
意义:"非符号"类型的定义,非符号类型出现在符号类型或逆符号类型定义中间,它不直接做为符号类型使用,而是将运算结果做为符号类型的一部分。

规范用法:(unquote-splicing obj)
简化用法:,@obj
意义:非符号类型的拼接,注意:,@ 两个符号做为一个操作符来使用)。当非符号类型是一些复杂算法时,需要用它来做一下拼接,以达到符号类型的目的。
上面所说的所有规范用法和简化用法的功能都是相同的。

符号类型的意义在于,一个说明,英文单词zebra指的是活生生的斑马,而'zebra或(quote zebra)指的是由字母z、e、b、r、a构成的这串符号(不是字符串),就象我们定义变量(define x 100),这时x指的就是100这个数值,而'x或(quote x)则代表字母x构成的这个符号。

首先看一段代码:

guile> (define s '(good morning))
guile> s
(good morning)
guile> (symbol? s)
#f
guile> (list? s)
#t
guile> (symbol? (list-ref s 1))
#t



从此示例中可以看出,用quote定义的列表的类型仍是列表,而列表中的某一值的类型则是符号类型。还可以看出有点类似于如下:

(+ 1 (+ 2 (+ 3 (+ 4 5)))) ==> (+ 1 2 3 4 5)
(list 'a 'b 'c 'd 'e) ==> '(a b c d e)



两者有异曲同工之妙,减少了多余的操作符,使表达式更直观,更容易理解。

从 '(1 2 3 4 5) ==> (1 2 3 4 5) 可以看出,由符号类型的定义来形成列表,这是Scheme语言继承自LISP语言的传统。

下面是在guile中的用法示例:

guile> `(1 ,(+ 1 1) 3)
(1 2 3)
guile> (quasiquote (1 (unquote (+ 1 1)) 3))
(1 2 3)
;;;第一个是简化用法,第二个是标准用法。
guile> `(1 ,@(map + '(1 3) '(2 4)) 9)
(1 3 7 9)
guile> (quasiquote (1 (unquote-splicing (map + (quote (1 3)) (quote (2 4)))) 9))
(1 3 7 9)
;;;第一个是简化用法,第二个是标准用法(注意:,@ 两个符号做为一个操作符来使用)。



从示例中我们可以看出,这些应用多数与列表有关,而处理列表是Scheme语言的关键所在。符号类型的用法对深入理解Scheme语言也非常关键,因为Scheme语言本身就可以理解为是这种符号类型的列表,处理符号类型就是处理Scheme语言本身。






回页首




二、关于尾递归

数列问题是研究递归的非常好的范例,在王垠的主页中有关于用菲波那契数列来说明非尾递归与尾递归之间区别和尾递归的好处的一个例子,见 http://learn.tsinghua.edu.cn/homepage/2001315450/wiki/TailRecursion.html 。我们这里用更简单一点的问题,求累计的问题来说明,即求自然数1+2+3+4+ ... +n的和。事实上就是设计一个过程,给它一个参数n,求1+2+3+ ... +n的和,我们首设计一个suma过程,代码如下:

#! /usr/local/bin/guile -s
!#
(define suma
(lambda (n)
(if (= n 1)
1
(+ n (suma (- n 1))))))
(display "(suma 100) ==> ")
(display (suma 100)) (newline)
(display "(suma 818) ==> ")
(display (suma 818)) (newline)
运行这段代码,会出现如下结果:
(suma 100) ==> 5050
(suma 818) ==> 334971


说明:
以(suma 5)为例,表达式展开后:
(suma 5)
(+ 5 (suma 4))
(+ 5 4 (suma 3))
(+ 5 4 3 (suma 2))
(+ 5 4 3 2 (suma 1))
(+ 5 4 3 2 1) ==> 15


如果n为1000的话则会最终形成(+ 1000 999 ... 3 2 1)这样长度惊人的表达式,结果直接导致guile的崩溃。

为什么会是818呢?因为819是会溢出的,出错,得不到结果,这可能大出乎我们意料之外,因为如果用C来写这样功能的程序代码,可能会求到6位数而不出问题。这一过程是用非尾递归来完成的,它的扩张呈指数级增长。代码的迅速膨胀,使guile没有处理到1000就崩溃了。

我们再来看看采用尾递归的情况,代码如下:

#! /usr/local/bin/guile -s
!#
(define sumb
(lambda (n)
(let f ((i n) (a 1))
(if (= i 1)
a
(f (- i 1) (+ a i))))))
(display "(sumb 100) ==> ")
(display (sumb 100)) (newline)
(display "(sumb 1000) ==> ")
(display (sumb 1000)) (newline)
运行结果如下:
(sumb 100) ==> 5050
(sumb 1000) ==> 500500


还是以n为5的情况来说明: (sumb 5)
(f 5 1)
(f 4 6)
(f 3 10)
(f 2 13)
(f 1 15) ==> 15


这样的话,始终是依次计算,不会出现列表膨胀,所以n为1000时也不会出错,计算速度也很快。

此结果大超出了非尾递归的818限制,参数是10000也没问题,因它采用尾递归,代码根本没有膨胀,而是依次计算。首先是在过程内部绑定了一个过程f,它有两个参数,一个i的值来自sum过程的参数n,另一个参数a定义值为1,当i值不等于时,仍调用f,第一个参数(也就是i)减1,第二个参数(也就是a)的值在原来的基础上加上i,当i的值为1是返回a,也就此sum过程的结果。理解这些后,你会发现事实上尾递归是在过程的绑定和过程的参数上做文章,用参数来保存运算结果,递归调用绑定的过程,最终达到运算目的。






回页首




三、关于过程参数的问题

过程的多参数问题对初学者不太好理解,一般情况下我们处理过程时,过程参数的数量是固定的,当过程的参数数量不固定时怎么办呢?对了,时刻记住列表,把过程的参数做为一个列表来处理,如求和过程:(sum arg1 arg2 ...),(初学者可能对如何实现定义这样的过程无从下手不知所措),我们如何来求这些参数的和呢?看下面的代码:

guile> (define sum (lambda args (apply + args)))
guile> sum
#
guile> (sum 1 2 3 4 5)
15



从中可以看出,lambda的格式有所变化,由原来的((lambda arg1 arg2 ...) body ...)变成了(lambda args body ...),也就是将原来的多个项组成的列表,改成了用一个名称args来标识的列表,其本质并没有变,变的是我们的方法,由原来的单项处理变成了统一处理的列表。

这里还用到了for-each过程,通过下面代码来看一下for-each过程的一般用法:

guile> (define newdisplay (lambda (x) (begin (display x)(newline))))
guile> newdisplay
#
guile> (define tt (lambda args (for-each newdisplay args)))
guile> tt
#
guile> (tt 'abc 'efg 'tomson)
abc
efg
tomson



for-each过程的一般用法是(for-each 过程 列表),此中的过程可以是我们自定义的,也可以是系统提供的,还可以是lambda 表达式。

栈结构是一种简单而又有意义的数据结构,我们可以用列表来模拟一个简单的栈,下面是代码:

#! /usr/local/bin/guile -s
!#
(define stack '())
(define push!
(lambda (x)
(set! stack (cons x stack))))
(define pop!
(lambda ()
(let ((temp (car stack)))
(set! stack (cdr stack))
temp)))
(push! 9)
(push! 8)
(push! 7)
(display stack) (newline)
(display (pop!)) (newline)
(display stack) (newline)



结果如下:

(7 8 9)
7
(8 9)



这里面我们定义了一个变量stack来表示栈,定义一个过程push!向栈内压数据,同时还定义了一个过程pop!来从栈内弹出数据,完成了基本的栈功能。这段代码的缺点是要定义一个外部的变量来表示栈,同时还有两个过程,如果创建多个栈的话就需要更多的过程和变量了,这在某些情况下是不可想象的,如果程序中要用100个栈,我们就不得不100次复制和更改上面的代码。如何解决这一问题呢?看下面的代码:

#! /usr/local/bin/guile -s
!#
(define make-stack
(lambda ()
(let ((st '()))
(lambda (process arg)
(case process
((push!) (begin
(set! st (cons arg st))
st))
((pop!) (let ((temp (car st)))
(set! st (cdr st))
temp))
((view) (display st))
(else "error!"))))))
(define s (make-stack))
(display (s 'push! 9)) (newline)
(display (s 'push! 8)) (newline)
(display (s 'push! 7)) (newline)
(display (s 'pop! 0)) (newline)
(s 'view 0) (newline)



结果如下:

(9)
(8 9)
(7 8 9)
7
(8 9)



在上面代码中定义的make-stack过程,它的形式是一种特殊的情况,在lambda表达式里面又嵌有lambda表达式,在使用这类过程时,先要调用这一过程定义一个变量(这个变量其实就是第二个lambda表达式),然后将这个变量再做为一个过程来直接调用(事实上也就是生成了一个过程),就像代码中的(s 'push 9) 。

我们首先绑定了一个变量st为空值做为栈的基础,与栈有关的操作都围绕它展开,这样的话前面提到代码重复问题就不会出现了,你可以定义任意多个栈。这段代码里还用到了case结构,它有点像C语言中的switch语句,用它判断第二个lambda表达式的第一个参数,也就是要对栈的操作,在调用时要用符号变量来使用,否则会出错,因为'push结果就是push,所以在过程定义中直接使用push,而调用时用'push。从这段代码中你会意识到变量和符号的重要性了。

这段代码中我们仍用上面代码的形式,用列表来模拟栈,因为这更能体现栈的原理和列表这一Scheme语言的基础数据类型的做用。细心的读者朋友会发现我们对栈进行pop操作时的调用是(s 'pop! 0),而正确的操作应该是(s 'pop!),'view也同样;这是因为我们第二个lambda表达式是lambda (process arg),为了不出错,不得不用这样的调用,如果将第二个lambda表达式改为lambda (process . arg)就可以避免这种尴尬情况了,但结果可能并不是我们想要的,栈会变成((7) (8) (9))这种情况。

如何更好的实现一个栈呢?对了,改变现有的形式,使用list(不用原始的cons)或vector来模拟,将 lambda (process arg) 改成 (process . arg) 或 (process . args) (注意,这两者可不一样啊!),这就要看你对栈结构的理解和编码水平了,相信参照这一代码你会模拟出更实用更快捷的栈结构来的。(本文代码中有一个用list来模拟栈结构的稍完整的代码) 这里我们还会发现一个小小的惯例,如果过程要更改变量的值,那么它的过程名后一定要加一个!;而如果过程是一个判断,结果为逻辑值时,它的过程名后一定要加一个?,这会使别人很快理解你的代码。






回页首




四、关于continuation

Scheme语言相对Lisp语言的重要特征是提出并实现了continuation,这是让初学者最难理解,也是最让程序员心动的特征。那么Continuation到底是什么呢?在运算Scheme表达式过程中,我们必须跟踪两个东西:1、运算什么?2、什么与值相关?看一看下面表达式的计算: (if (null? x) (quote ()) (car x)) 。其中首先要运算的是(null? x),然后在这个值的基础上再运算(quote ())或(cdr x),要运算的是(null? x)而与值相关的是(quote ())和(car x);这里把与值相关的称为运算的continuation。我们看(null? x)表达式中与值相关的东西就有三个,1、表达式本身,结果为#t或#f;2、过程null?,它是一个lambda表达式;3、变量x,它应用当有一个值。那么上面的表达式里面有几个continuation呢?答案是六个,上面的表达式本身,我们说过的三个,car也是一个lambda表达式,还有它后面的x,也和值相关;而(car x)没有计算在内,因为它与上面表达式结果之一是相同的。

在任何表达式中,Continuation可以用一个叫call-with-current-continuation的过程来得到,多数情况下它被简化为call/cc。在guile的1.6.4或以前版本中,简化代码如下所示:

(define call/cc call-with-current-continuation)



而在其它的Scheme语言的实现版本中完全可以不用这样定义,而直接使用call/cc。

call/cc过程的唯一个参数应该是一个过程(或lambda表达式),而且这个过程只能有一个参数,continuation就绑定在这个参数上。看下面的代码:

guile> (define call/cc call-with-current-continuation)
guile> call/cc
#
guile> (call/cc (lambda (k) 5))
5
;;;此时过程参数k未用到,所以取过程的返回值5做为结果
guile> (call/cc (lambda (k) (* 5 (k 8))))
8
;;;此时过程参数k绑定为8,所以其结果为8
guile> (+ 2 (call/cc (lambda (k) (* 5 (k 8)))))
10
;;;此时结果在我们意料之中了



可以利用call/cc这一特点,让它从一个循环中跳出来,这有点像C语言中的break,看下面的代码:

guile> (call/cc (lambda (return)
(for-each (lambda (x) (if (< x 0) (return x)))
'(99 88 77 66 55))
#t))
#t



其结果为#t,因为for-each运算过程中未出现过(< x 0)的情况,所以(lambda (return ) ...)的结果为#t,call/cc取此值为最终结果。

guile> (call/cc (lambda (return)
(for-each (lambda (x) (if (< x 0) (return x)))
'(11 22 33 44 -55 66 77))
#t))
-55



其结果为-55,因为当遇到小于0的数时,return就绑定x,call/cc就返回此值,即从for-each处理过程中跳出来,这是call/cc的重要功能之一,也是最基本的功能。

call/cc 还可以这样操作:

guile> (define foo #f)
guile> (call/cc (lambda (bar) (set! foo bar) 123))
123
guile> (foo 456)
456
guile> (foo 'abc)
abc



上面的操作中,call/cc绑定了lambda表达式的参数bar,而后我们又设定foo的值为bar,此时foo即为一个灵活的continuation;最后我们又让lambda表达式的值为123,所以整个call/cc表达式的值为123,如果我们不加这个123而直接结束这个表达式的话,此表达式就没有结果,不返回任何值。

当foo成为一个continuation后,我们可以象调用过程那样来调用它(当然它并不是过程),其后面绑定的值即为此continuation的结果,如上面的代码运行所示。

这段代码的前提是有call/cc的定义,如果你直接运行guile后就输入上面的代码是肯定会出错的。

在赵蔚的文章 http://www.ibm.com/developerworks/cn/linux/l-scheme/part2/index.shtml中提到过由David Madore先生提出的"阴阳迷题",下面我们通过对它的研究来理解一下continuation,代码如下所示(为解释方便,稍做改动):

(let* ((yin ((lambda (foo) (display "@") foo) (call/cc (lambda (bar) bar))))
(yang ((lambda (foo) (display "*") foo) (call/cc (lambda (bar) bar)))))
(yin yang))



我们进行一些简化,将其中的lambda表达式定义为过程,使其看起来更清晰:

(define bar (lambda (bar) bar))
(define foox (lambda (foo) (display "@") foo))
(define fooy (lambda (foo) (display "*") foo))



则上面的繁琐的表达式可以变成为:

(let* ((yin (foox (call/cc bar)))
(yang (fooy (call/cc bar))))
(yin yang))



将let*改变成let,使其进一步简化为:

(let ((yin (foox (call/cc bar))))
(let ((yang (fooy (call/cc bar))))
(yin yang)))



最后将let去掉,继而成为:

((foox (call/cc bar)) (fooy (call/cc bar)))



经过这一翻简化处理(对初学者是有必要的),相信我们对Scheme语言会有新的认识。需要说明的是每一次简化后,都要运行一下,保证它的结果如下所示,否则说明我们简化过程中有错误:

@*@**@***@****@*****@******@*******@********@*********@********** ......



在理解continuation之前,这一结果是我们无论如何也想不到的,如果你有足够奈心的话,你会发现它会按这一规律无限的延长,在我的老机上从11:20一直到15:20仍无迹象表明要停止。

为什么会出现这一结果呢?首先看看我们为了简化而定义的三个过程bar、foox和fooy,bar是Scheme语言中最简单的过程,只有一个参数,并且返回这个参数;foox和fooy比它们只多了一步,执行完一个display过程后再返回这个参数;这样简单的两个过程确出现如此复杂的结果,原因全在call/cc身上。

首先,看(call/cc bar)表达式,它形成了一个灵活的continuation,用它来做foox的参数,表达式(foox (call/cc bar))则形成一个新的灵活的continuation,即显示一个@字符同时也是一个continuation。

再看,表达式((call/cc bar) (foox bar))的结果与表达式((foox bar) (foox bar))的结果相同,均为显示两个@字符,同时返回一个过程#,这就让我们在某种程度上理解了表达式(call/cc procedure?)的结果为#t了,因为(procedure? procedure?)也为#t;而(call/cc boolean?)则不然,因为(boolean? boolean?)为#f。

从上面我们可以看出表达式((call/cc bar) (foox (call/cc bar)))实际则是与表达式((foox (call/cc bar)) (foox (call/cc bar))),运行一下会发现,两者确实相同,显示@字符,无穷无尽,看来(call/cc bar)这个参数起到了关键作用。那么再看我们的阴阳表达式((foox (call/cc bar)) (fooy (call/cc bar))),前者(foox (call/cc bar))为一个显示字符@的continuation,我们表示为*cc;后者(fooy (call/cc bar))为一个显示字符*的continuation,我们表示为*cc;则在@cc的调动指挥下,每次*cc再加下一个(fooy (call/cc bar)),形成**cc,再加后,如此形成我们前面的效果。过程如下所示:

@cc *cc
@cc **cc
@cc ***cc
@cc ****cc 一直至无穷尽



前一段时间,"晕"这个字总会出现在网友的聊天中,相信现在不"晕"了。我们给上面的代码改动一下:

#! /usr/local/bin/guile -s
!#
(define call/cc call-with-current-continuation)
(define n 0)
(define bar (lambda (bar) bar))
(define foo (lambda (foo) (display n) (newline) (set! n (+ n 1)) foo))
((call/cc bar) (foo (call/cc bar)))



这样形成了,0 1 2 3 4 ......无限制的循环,由此我们解决了一个不用循环语句来形成循环的问题。






回页首




五、关于记录类型

在guile中提供了很多复杂的复合类型,如record,struct,hashtable,array等等,record类型是其中较简单的一种,我们这里称之为记录类型,这种类型有点像C语言中的结构,更像C++中的类。通过它我们可以了解一些面向对象思想在Scheme语言中的应用。记录类型包括九个相关过程,以下是简单介绍:

record? 记录类型的判断过程
make-record-type 创建记录类型,两个参数,类型的名称和类型的成员名称列表
record-constructor 创建记录类型构建过程,一个参数,类型
record-predicate 创建记录类型的判断过程,用此过程某一变量是否为已创建的记录类型
record-accessor 创建记录类型的get系列过程,两个参数,类型和表示成员名称的符号
record-modifier 创建记录类型的set系列过程,同上
record-type-descriptor 一般不用,可忽略
record-type-name 取得记录类型的名字,返回字符串
record-type-fields 取得记录类型的成员名字列表

要想知道如何定义一个记录类型和上面提到的相关过程的用法,具体代码是必不可少的,下面是一个简单的示例:

#! /usr/local/bin/guile -s
!#
(define girl (make-record-type "girl" '(name info)))
;;定义record类型girl,包含两个成员name和info,其中name为一字符串,info为一过程用来显示信息
(define girl-init! (record-constructor girl))
;;定义girl的初始化过程
(define girl-name-get (record-accessor girl 'name))
;;定义取得girl类型的name成员的值的过程
(define girl-name-set! (record-modifier girl 'name))
;;定义设定girl类型的name成员的值的过程
(define girl-info-get (record-accessor girl 'info))
;;定义取得girl类型的info成员的值的过程
(define girl-info-set! (record-modifier girl 'info))
;;定义设定girl类型的info成员的值的过程
(define hi
(lambda (name)
(display "Hi! I'm ")
(display name)
(display ".")))
;;定义hi过程,显示"Hi! I'm " 加字符串 name 加 "."
(define g (girl-init! "Lucy" hi))
;;定义一个girl类型的变量g,其成员name值为"Lucy",成员info值为上面定义的hi过程
((girl-info-get g) (girl-name-get g)) (newline)
;;取得girl类型变量g的info成员,做为过程来执行它,取得girl类型变量g的name成员做为此过程的参数



这段代码的运行结果为: Hi! I'm Lucy.

代码中的注释相信大家都能看懂,需要说的是当我们用定义一个用make-record-type创建的记录类型后,就可以用record?来判断此类型是否为记录类型了,即 (record? girl) ==> #t 。

还有就是可以用代码 (define girl? (record-predicate girl)) 来定义一个此记录类型girl的判断过程girl?,也就是 (girl? g) ==> #t 。

还有就是下面的结果也应该在我们的想象之中:

(record-type-name girl) ==> "girl"
(record-type-fields girl) ==> (name info)



从这个简单的例子来看,记录类型已经具备了面向对象的编程思想所要求的一些必备的东西,而且更具有Scheme语言自己的特色。相信在我的这个例子基础上你可以创建一个更优秀的girl来。






回页首




六、关于宏定义

Scheme语言中的宏定义类似于自己定义一个Scheme语言关键字,可以实现不同的功能,很多关键字都可以通过宏定义来实现,我们在多数参考资料中都可以看到这样的例子。

在多数Scheme语言的实现中,都提供了不同形式的宏定义功能,在guile中提供了用defmacro或define-macro来定义宏,defmacro的格式为:

(defmacro name (args ...) body ...)



它等同于

(define-macro (name args ...) body ...)



我们来看一个简单的宏定义:

#! /usr/local/bin/guile -s
!#
(define-macro (defobj name)
`(begin
(define ,(string->symbol (string-append "make-" name))
(lambda ()
(display "make object ok!\n")))
(define ,(string->symbol (string-append name "?"))
(lambda (obj)
(if (eq? obj 'name)
#t
#f)))))
(defobj "foo")
(make-foo)
(display (foo? 'name)) (newline)
这段程序的运行结果如下:
make object ok!
#t



从这段代码中你可能看到了逆符号(quasiquote)以及相关的操作的重要性了,这里我们定义了一个宏defobj,当运行完(defobj "boy")这个宏时,产生了两个过程定义即make-foo和foo?,从这一点上来看,高性能的宏定义可以大大减轻我们代码的重复使用的麻烦。还有就是guile系统中很多宏定义都是按上面的宏定义方式来进行的。

在Scheme语言中,R5RS中的宏定义是通用的标准,guile中通过调用syncase模块来实现这一功能,你需要在代码中加入:(use-modules (ice-9 syncase)) 来调用ice-9目录下的syncase模块。

下面的R5RS格式的宏定义实现了前面提到的sum功能和一个列表定义功能,它都有多参数的特点,这在R5RS宏观定义中很容易实现:

#! /usr/local/bin/guile -s
!#
(use-modules (ice-9 syncase))
(define-syntax sum
(syntax-rules ()
((_ exp1 exp2 ...)
(+ exp1 exp2 ...))))
(display (sum 1 2 3 4 5)) (newline)
(define-syntax ourlst
(syntax-rules ()
((_ exp)
(cons exp '()))
((_ exp1 exp2 ...)
(cons exp1 (ourlst exp2 ...)))))
(display (ourlst 1 2 3 4 5)) (newline)



上面代码的结果如下:

15
(1 2 3 4 5)



在sum宏定义中,如果附合规则(_ exp1 exp2 ...)或(sum exp1 exp2 ...)将按(+ exp1 exp2 ...)的方式来处理,其中exp1、exp2表示Scheme表达式,而省略号 ... 则表示更多的表达式。也就是说 (sum 1 2 3 4 5)将按(+ 1 2 3 4 5)来处理,其结果为15。在ourlst宏中则有两个规则,第一是只有一个参数的情况,第二是多参数的情况,在多参数情况下还用到了递归,相信大家都能理解。

这是按R5RS标准来实现的最简单的两个宏(当然还有我在概要一文中提到的糟糕的start宏),相信通过这两个宏的定义,您会理解并能进行宏定义了。






回页首




七、关于模块

上面提到的syncase模块是如何实现的呢?多数Scheme语言的实现版本都提供了一套模块系统,guile也不例外,看一看下面的简单的模块定义:

;;;file : tt.scm , a module test here .
(define-module (ice-9 tt)
:export (newdisplay))
(define newdisplay
(lambda (str)
(display str)
(newline)))



将其以tt.scm文件名保存。这段代码中,首先用define-module表示定义一个模块,而(ice-9 tt)则指明了模块的具体位置和名称,最后:export指出模块中要导出的过程等的名称,这们这里只有一个newdisplay,可以用列表来形成多个导出过程名。而下面的代码则和我们普通的过程定义代码相同,简单的定义了一个名为newdisplay的过程,功能是在要显示的东西后面加一个换行符。

我们再编写一段代码来测试一下这个模块:

#! /usr/local/bin/guile -s
!#
(use-modules (ice-9 tt))
(newdisplay "test use tt modules")



这段代码中用usemodules来调用我们上面定义的tt模块,以test_tt.scm文件名保存,运行后会出现错误信息: ERROR: no code for module (ice-9 tt) 。

这是因为,默认情况下,模块所在目录为/usr/local/share/guile/1.6/ice-9 或 /usr/share/guile/1.6/ice-9 。执行命令: cp tt.scm /usr/local/share/guile/1.6/ice-9/ ,将模块文件复制到相应目录,再执行test_tt.scm文件,其输出结果如下:(输出字符串自动换行了)

test use tt modules



这说明我们成功的定义了一个模块。我们在宏定义时用的syncase模块实际上就是在/usr/local/share/guile/1.6/ice-9目录中的syncase.scm文件,研究一下此目录中的scm文件会发现很多定义模块的技巧。






回页首




八、关于eval

在概要一文中还没有提到的是eval这个过程的用法,利用它可以实现用Scheme语言本身来解释Scheme表达式的功能,这对一个学习编译系统和Scheme语法功能的实现非常重要。下面是在guile中运行eval过程来解释Scheme表达式的情况:

guile> (primitive-eval '(+ 2 3))
5
guile> (eval '(+ 1 2) (interaction-environment))
3



这里面包含了两个版本的eval过程,首先是原始的guile内部使用的primitive-eval,它可以直接解释运行Scheme表达式;第二个是正常的eval过程,它需要两个参数,一个是要解释运行的要Scheme表达式,第二个是表达式运行的环境,可以由interaction-environment过程来获得,如此则eval过程正常运行。

可以想象用C语言来写C语言编译器对初学者来说的难度,但掌握Scheme语法和eval的用法后,你会发现用Scheme语言来写一个Scheme语言解释器并不是很难,这可能成为你理解编译原理的重要一步。

我们在感觉到Scheme语言的简单易用的同时,还应该意识到它是一门富于挑战意义的语言,相信现在我们能够真正理解Scheme挑战意义的所在了吧。(本文涉及到了Scheme语言中大多数的稍复杂一些的内容,还请热爱Scheme语言的朋友们多多指正。)

Scheme 语言概要

作为Lisp 变体,Scheme 是一门非常简洁的计算语言,使用它的编程人员可以摆脱语言本身的复杂性,把注意力集中到更重要的问题上,从而使语言真正成为解决问题的工具。本文分为上、 下两部分来介绍 scheme 语言。

一.Scheme语言的特点

Scheme语言是LISP语言的一个方言(或说成变种),它诞生于1975年的MIT,对于这个有近三十年历史的编程语言来说,它并没有象C++,java,C#那样受到商业领域的青睐,在国内更是显为人知。但它在国外的计算机教育领域内却是有着广泛应用的,有很多人学的第一门计算机语言就是Scheme语言。

它是一个小巧而又强大的语言,作为一个多用途的编程语言,它可以作为脚本语言使用,也可以作为应用软件的扩展语言来使用,它具有元语言特性,还有很多独到的特色,以致于它被称为编程语言中的"皇后"。

下面是洪峰对Scheme语言的编程特色的归纳:

词法定界(Lexical Scoping)
动态类型(Dynamic Typing)
良好的可扩展性
尾递归(Tail Recursive)
函数可以作为值返回
支持一流的计算连续
传值调用(passing-by-value)
算术运算相对独立
本文的目的是让有编程基础(那怕是一点点)的朋友能尽快的掌握Scheme语言的语法规则,如果您在读完本文后,发现自己已经会用Scheme语言了,那么我的目的就达到了。






回页首




二.Scheme语言的标准与实现

R5RS (Revised(5) Report on the Algorithmic Language Scheme)

Scheme语言的语法规则的第5次修正稿,1998年制定,即Scheme语言的现行标准,目前大多数Scheme语言的实现都将达到或遵循此标准,并且几乎都加入了一些属于自己的扩展特色。

Guile (GNU's extension language)

Guile是GNU工程的一个项目,它是GNU扩展语言库,它也是Scheme语言的一个具体实现;如果你将它作为一个库打包,可以把它链接到你的应用程序中去,使你的应用程序具有自己的脚本语言,这个脚本语言目前就是Scheme语言。

Guile可以在LINUX和一些UNIX系统上运行,下面是简单的安装过程:

下载guile-1.6.4版,文件名为guile-1.6.4.tar.gz,执行下面的命令:

tar xvfz guile-1.6.4.tar.gz
cd guile-1.6.4
./configure
make
make install



如此,即可以执行命令guile,进入guile>提示符状态,输入调试Scheme程序代码了,本文的所有代码都是在guile下调试通过。

其它实现

除了Guile外,Scheme语言的实现还有很多,如:GNU/MIT-Scheme, SCI,Scheme48,DrScheme等,它们大多是开源的,可以自由下载安装使用,并且跨平台的实现也很多。你会发现既有象basic的Scheme语言解释器,也有将Scheme语言编译成C语言的编译器,也有象JAVA那样将Scheme语言代码编译成虚拟机代码的编译器。






回页首




三.基本概念

注释

Scheme语言中的注释是单行注释,以分号[;]开始一直到行尾结束,其中间的内容为注释,在程序运行时不做处理,如:

; this is a scheme comment line.



标准的Scheme语言定义中没有多行注释,不过在它的实现中几乎都有。在Guile中就有多行注释,以符号组合"#!"开始,以相反的另一符号组合"!#"结束,其中内容为注释,如:

#!
there are scheme comment area.
you can write mulity lines here .
!#



注意的是,符号组合"#!"和"!#"一定分做两行来写。

Scheme用做脚本语言

Scheme语言可以象sh,perl,python等语言那样作为一种脚本语言来使用,用它来编写可执行脚本,在Linux中如果通过Guile用Scheme语言写可执行脚本,它的第一行和第二行一般是类似下面的内容:

#! /usr/local/bin/guile -s
!#


这样的话代码在运行时会自动调用Guile来解释执行,标准的文件尾缀是".scm"。

块(form)

块(form)是Scheme语言中的最小程序单元,一个Scheme语言程序是由一个或多个form构成。没有特殊说明的情况下 form 都由小括号括起来,形如:

(define x 123)
(+ 1 2)
(* 4 5 6)
(display "hello world")



一个 form 也可以是一个表达式,一个变量定义,也可以是一个过程。

form嵌套

Scheme语言中允许form的嵌套,这使它可以轻松的实现复杂的表达式,同时也是一种非常有自己特色的表达式。下图示意了嵌套的稍复杂一点的表达式的运算过程:




变量定义

可以用define来定义一个变量,形式如下:
(define 变量名 值)

如: (define x 123) ,定义一个变量x,其值为123。

更改变量的值

可以用set!来改变变量的值,格式如下:
(set! 变量名 值)

如: (set! x "hello") ,将变量x的值改为"hello" 。

Scheme语言是一种高级语言,和很多高级语言(如python,perl)一样,它的变量类型不是固定的,可以随时改变。






回页首




四.数据类型

1. 简单数据类型

逻辑型(boolean)

最基本的数据类型,也是很多计算机语言中都支持的最简单的数据类型,只能取两个值:#t,相当于其它计算机语言中的 TRUE;#f,相当于其它计算机语言中的 FALSE。

Scheme语言中的boolean类型只有一种操作:not。其意为取相反的值,即:

(not #f) => #t
(not #t) => #f



not的引用,与逻辑非运算操作类似

guile> (not 1)
#f
guile> (not (list 1 2 3))
#f
guile> (not 'a)
#f



从上面的操作中可以看出来,只要not后面的参数不是逻辑型,其返回值均为#f。

数字型(number)

它又分为四种子类型:整型(integer),有理数型(rational),实型(real),复数型(complex);它们又被统一称为数字类型(number)。

如:复数型(complex) 可以定义为 (define c 3+2i)
实数型(real)可以定义为 (define f 22/7)
有理数型(rational)可以定义为 (define p 3.1415)
整数型(integer) 可以定义为 (define i 123)

Scheme语言中,数字类型的数据还可以按照进制分类,即二进制,八进制,十进制和十六进制,在外观形式上它们分别以符号组合 #b、 #o、 #d、 #x 来作为表示数字进制类型的前缀,其中表示十进制的#d可以省略不写,如:二进制的 #b1010 ,八进制的 #o567,十进制的123或 #d123,十六进制的 #x1afc 。

Scheme语言的这种严格按照数学定理来为数字类型进行分类的方法可以看出Scheme语言里面渗透着很深的数学思想,Scheme语言是由数学家们创造出来的,在这方面表现得也比较鲜明。

字符型(char)

Scheme语言中的字符型数据均以符号组合 "#\" 开始,表示单个字符,可以是字母、数字或"[ ! $ % & * + - . / : %lt; = > ? @ ^ _ ~ ]"等等其它字符,如:
#\A 表示大写字母A,#\0表示字符0,
其中特殊字符有:#\space 表示空格符和 #\newline 表示换行符。

符号型(symbol)

符号类型是Scheme语言中有多种用途的符号名称,它可以是单词,用括号括起来的多个单词,也可以是无意义的字母组合或符号组合,它在某种意义上可以理解为C中的枚举类型。看下面的操作:

guile> (define a (quote xyz)) ; 定义变量a为符号类型,值为xyz
guile> a
xyz
guile> (define xyz 'a) ; 定义变量xyz为符号类型,值为a
guile> xyz
a



此处也说明单引号' 与quote是等价的,并且更简单一些。符号类型与字符串不同的是符号类型不能象字符串那样可以取得长度或改变其中某一成员字符的值,但二者之间可以互相转换。

2. 复合数据类型

可以说复合数据类型是由基本的简单数据类型通过某种方式加以组合形成的数据类型,特点是可以容纳多种或多个单一的简单数据类型的数据,多数是基于某一种数学模型创建的。

字符串(string) 由多个字符组成的数据类型,可以直接写成由双引号括起的内容,如:"hello" 。下面是Guile中的字符串定义和相关操作:

guile> (define name "tomson")
guile> name
"tomson"
guile> (string-length name) ; 取字符串的长度
6
guile> (string-set! name 0 #\g) ; 更改字符串首字母(第0个字符)为小写字母g (#\g)
guile> name
"gomson"
guile> (string-ref name 3) ; 取得字符串左侧第3个字符(从0开始)
#\s



字符串还可以用下面的形式定义:

guile> (define other (string #\h #\e #\l #\l #\o ))
guile> other
"hello"



字符串中出现引号时用反斜线加引号代替,如:"abc\"def" 。

点对(pair)

我把它译成"点对",它是一种非常有趣的类型,也是一些其它类型的基础类型,它是由一个点和被它分隔开的两个所值组成的。形如: (1 . 2) 或 (a . b) ,注意的是点的两边有空格。

这是最简单的复合数据类型,同是它也是其它复合数据类型的基础类型,如列表类型(list)就是由它来实现的。

按照Scheme语言说明中的惯例,以下我们用符号组合 "=>" 来表示表达式的值。

它用cons来定义,如: (cons 8 9) =>(8 . 9)

其中在点前面的值被称为 car ,在点后面的值被称为 cdr ,car和cdr同时又成为取pair的这两个值的过程,如:

(define p (cons 4 5)) => (4 . 5)
(car p) => 4
(cdr p) => 5



还可以用set-car! 和 set-cdr! 来分别设定这两个值:

(set-car! p "hello")
(set-cdr! p "good")



如此,以前定义的 p 又变成了 ("hello" . "good") 这个样子了。

列表(list)

列表是由多个相同或不同的数据连续组成的数据类型,它是编程中最常用的复合数据类型之一,很多过程操作都与它相关。下面是在Guile中列表的定义和相关操作:

guile> (define la (list 1 2 3 4 ))
guile> la
(1 2 3 4)
guile> (length la) ; 取得列表的长度
4
guile> (list-ref la 3) ; 取得列表第3项的值(从0开始)
4
guile> (list-set! la 2 99) ; 设定列表第2项的值为99
99
guile> la
(1 2 99 4)
guile> (define y (make-list 5 6)) ;创建列表
guile> y
(6 6 6 6 6)



make-list用来创建列表,第一个参数是列表的长度,第二个参数是列表中添充的内容;还可以实现多重列表,即列表的元素也是列表,如:(list (list 1 2 3) (list 4 5 6))。

列表与pair的关系

回过头来,我们再看看下面的定义:

guile> (define a (cons 1 (cons 2 (cons 3 '()))))
guile> a
(1 2 3)



由上可见,a本来是我们上面定义的点对,最后形成的却是列表。事实上列表是在点对的基础上形成的一种特殊格式。

再看下面的代码:

guile> (define ls (list 1 2 3 4))
guile> ls
(1 2 3 4)
guile> (list? ls)
#t
guile> (pair? ls)
#t



由此可见,list是pair的子类型,list一定是一个pair,而pair不是list。

guile> (car ls)
1
guile> (cdr ls)
(2 3 4)



其cdr又是一个列表,可见用于pair的操作过程大多可以用于list。

guile> (cadr ls) ; 此"点对"对象的cdr的car
2
guile> (cddr ls) ; 此"点对"对象的cdr的cdr
(3 4)
guile> (caddr ls) ; 此"点对"对象的cdr的cdr的car
3
guile> (cdddr ls) ; 此"点对"对象的cdr的cdr的cdr
(4)



上在的操作中用到的cadr,cdddr等过程是专门对PAIR型数据再复合形成的数据操作的过程,最多可以支持在中间加四位a或d,如cdddr,caaddr等。

下图表示了由pairs定义形成的列表:




这个列表可以由pair定义为如下形式:

(define x (cons 'a (cons 'b (cons 'c (cons 'd '())))))



而列表的实际内容则为:(a b c d)

由pair类型还可以看出它可以轻松的表示树型结构,尤其是标准的二叉树。

向量(vector)

可以说是一个非常好用的类型 ,是一种元素按整数来索引的对象,异源的数据结构,在占用空间上比同样元素的列表要少,在外观上:

列表示为: (1 2 3 4)
VECTOR表示为: #(1 2 3 4)
可以正常定义:(define v (vector 3 4 5))
也可以直接定义:(define v #(3 4 5))

vector是一种比较常用的复合类型,它的元素索引从0开始,至第 n-1 结束,这一点有点类似C语言中的数组。

关于向量表(vector)的常用操作过程:

guile> (define v (vector 1 2 3 4 5))
guile> v
#(1 2 3 4 5)
guile> (vector-ref v 0) ; 求第n个变量的值
1
guile> (vector-length v) ; 求vector的长度
5
guile> (vector-set! v 2 "abc") ; 设定vector第n个元素的值
guile> v
#(1 2 "abc" 4 5)
guile> (define x (make-vector 5 6)) ; 创建向量表
guile> x
#(6 6 6 6 6)



make-vector用来创建一个向量表,第一个参数是数量,后一个参数是添充的值,这和列表中的make-list非常相似。

我们可以看出,在Scheme语言中,每种数据类型都有一些基本的和它相关的操作过程,如字符串,列表等相关的操作,这些操作过程都很有规律,过程名的单词之间都用-号隔开,很容易理解。对于学过C++的朋友来说,更类似于某个对象的方法,只不过表现的形式不同了。

3. 类型的判断、比较、运算、转换与方法

类型判断

Scheme语言中所有判断都是用类型名加问号再加相应的常量或变量构成,形如:

(类型? 变量)



Scheme语言在类型定义中有比较严格的界定,如在C语言等一些语言中数字0来代替逻辑类型数据False,在Scheme语言中是不允许的。

以下为常见的类型判断和附加说明:

逻辑型:

(boolean? #t) => #t
(boolean? #f) => #t 因为#t和#f都是boolean类型,所以其值为#t
(boolean? 2) => #f 因为2是数字类型,所以其值为 #f



字符型

(char? #\space) => #t
(char? #\newline) => #t 以上两个特殊字符:空格和换行
(char? #\f) => #t 小写字母 f
(char? #\;) => #t 分号 ;
(char? #\5) => #t 字符 5 ,以上这些都是正确的,所以返回值都是 #t
(char? 5) => #f 这是数字 5 ,不是字符类型,所以返回 #f



数字型

(integer? 1) => #t
(integer? 2345) => #t
(integer? -90) => #t 以上三个数均为整数
(integer? 8.9) => #f 8.9不整数
(rational? 22/7) => #t
(rational? 2.3) => #t
(real? 1.2) => #t
(real? 3.14159) => #t
(real? -198.34) => #t 以上三个数均为实数型
(real? 23) => #t 因为整型属于实型
(number? 5) => #t
(number? 2.345) => #t
(number? 22/7) => #t



其它型

(null? '()) => #t ; null意为空类型,它表示为 '() ,即括号里什么都没有的符号
(null? 5) => #f
(define x 123) 定义变量x其值为123
(symbol? x) => #f
(symbol? 'x) => #t ; 此时 'x 为符号x,并不表示变量x的值



在Scheme语言中如此众多的类型判断功能,使得Scheme语言有着非常好的自省功能。即在判断过程的参数是否附合过程的要求。

比较运算

Scheme语言中可以用<,>,<=,>=,= 来判断数字类型值或表达式的关系,如判断变量x是否等于零,它的形式是这样的:(= x 0) ,如x的值为0则表达式的值为#t,否则为#f。

还有下面的操作:

(eqv? 34 34) => #t
(= 34 34) => #t



以上两个form功能相同,说明 eqv? 也可以用于数字的判断。

在Scheme语言中有三种相等的定义,两个变量正好是同一个对象;两个对象具有相同的值;两个对象具有相同的结构并且结构中的内容相同。除了上面提到的符号判断过程和eqv?外,还有eq?和equal?也是判断是否相等的过程。

eq?,eqv?,equal?

eq?,eqv?和equal?是三个判断两个参数是否相等的过程,其中eq?和eqv?的功能基本是相同的,只在不同的Scheme语言中表现不一样。

eq?是判断两个参数是否指向同一个对象,如果是才返回#t;equal?则是判断两个对象是否具有相同的结构并且结构中的内容是否相同,它用eq?来比较结构中成员的数量;equal?多用来判断点对,列表,向量表,字符串等复合结构数据类型。

guile> (define v (vector 3 4 5))
guile> (define w #(3 4 5)) ; w和v都是vector类型,具有相同的值#(3 4 5)
guile> (eq? v w)
#f ; 此时w和v是两个对象
guile> (equal? v w)
#t ; 符合equal?的判断要求



以上操作说明了eq? 和equal? 的不同之处,下面的操作更是证明了这一点:

guile> (define x (make-vector 5 6))
guile> x
#(6 6 6 6 6)
guile> (eq? x x) ; 是同一个对象,所以返回#t
#t
guile> (define z (make-vector 5 6))
guile> z
#(6 6 6 6 6)
guile> (eq? x z) ; 不是同一个对象
#f
guile> (equal? x z) ; 结构相同,内容相同,所以返回#t
#t



算术运算

Scheme语言中的运算符有:
+ , - , * , / 和 expt (指数运算)
其中 - 和 / 还可以用于单目运算,如:

(- 4) => -4
(/ 4) => 1/4



此外还有许多扩展的库提供了很多有用的过程,

max 求最大 (max 8 89 90 213) => 213
min 求最小 (min 3 4 5 6 7) => 3
abs 求绝对值 (abs -7) ==> 7



除了max,min,abs外,还有很多数学运算过程,这要根据你用的Scheme语言的运行环境有关,不过它们大多是相同的。在R5RS中规定了很多运算过程,在R5RS的参考资料中可以很容易找到。

转换

Scheme语言中用符号组合"->"来标明类型间的转换(很象C语言中的指针)的过程,就象用问号来标明类型判断过程一样。下面是一些常见的类型转换过程:

guile> (number->string 123) ; 数字转换为字符串
"123"
guile> (string->number "456") ; 字符串转换为数字
456
guile> (char->integer #\a) ;字符转换为整型数,小写字母a的ASCII码值为96
97
guile> (char->integer #\A) ;大写字母A的值为65
65
guile> (integer->char 97) ;整型数转换为字符
#\a
guile> (string->list "hello") ;字符串转换为列表
(#\h #\e #\l #\l #\o)
guile> (list->string (make-list 4 #\a)) ; 列表转换为字符串
"aaaa"
guile> (string->symbol "good") ;字符串转换为符号类型
good
guile> (symbol->string 'better) ;符号类型转换为字符串
"better"







回页首




五.过程定义

过程(Procedure)

在Scheme语言中,过程相当于C语言中的函数,不同的是Scheme语言过程是一种数据类型,这也是为什么Scheme语言将程序和数据作为同一对象处理的原因。如果我们在Guile提示符下输入加号然后回车,会出现下面的情况:

guile> +
#



这告诉我们"+"是一个过程,而且是一个原始的过程,即Scheme语言中最基础的过程,在GUILE中内部已经实现的过程,这和类型判断一样,如boolean?等,它们都是Scheme语言中最基本的定义。注意:不同的Scheme语言实现环境,出现的提示信息可能不尽相同,但意义是一样的。

define不仅可以定义变量,还可以定义过程,因在Scheme语言中过程(或函数)都是一种数据类型,所以都可以通过define来定义。不同的是标准的过程定义要使用lambda这一关键字来标识。

Lambda关键字

Scheme语言中可以用lambda来定义过程,其格式如下:
(define 过程名 ( lambda (参数 ...) (操作过程 ...)))

我们可以自定义一个简单的过程,如下:

(define add5 (lambda (x) (+ x 5)))



此过程需要一个参数,其功能为返回此参数加5 的值,如:

(add5 11) => 16



下面是简单的求平方过程square的定义:

(define square (lambda (x) (* x x)))



与lambda相同的另一种方式

在Scheme语言中,也可以不用lambda,而直接用define来定义过程,它的格式为:
(define (过程名 参数) (过程内容 …))

如下面操作:

(define (add6 x) (+ x 6))
add6
# 说明add6是一个过程,它有一个参数x
(add6 23) => 29



再看下面的操作:

guile> (define fun
(lambda(proc x y)
(proc x y)))
guile> fun
#
guile> (fun * 5 6)
30
guile> (fun / 30 3)
10



更多的过程定义

上面定义的过程fun有三个参数,其中第一个参数proc也是一个操作过程(因为在Scheme语言中过程也是一种数据,可以作为过程的参数),另外两个参数是数值,所以会出现上面的调用结果。

guile> (define add
(lambda (x y)
(+ x y)))
guile> add
#
guile> (fun add 100 200)
300



继续上面操作,我们定义一个过程add,将add作为参数传递给fun过程,得出和(fun + 100 200)相同的结果。

guile> ((lambda (x) (+ x x)) 5)
10



上面的 (lambda(x) (+ x x)) 事实上是简单的过程定义,在后面直接加上操作参数5,得出结果10,这样实现了匿名过程,直接用过程定义来操作参数,得出运算结果。

通过上面的操作,相信你已初步了解了过程的用法。既然过程是一种数据类型,所以将过程作为过程的参数是完全可以的。以下过程为判断参数是否为过程,给出一个参数,用 procedure? 来判断参数是否为过程,采用if结构(关于if结构见下面的介绍):

guile> (define isp
(lambda (x)
(if (procedure? x) 'isaprocedure 'notaprocedure)))
guile> isp
#
guile> (isp 0)
notaprocedure
guile> (isp +)
isaprocedure



上面的过程就体现了Scheme语言的参数自省(辨别)能力,'0'是数字型,所以返回notaprocedure;而'+'是一个最基础的操作过程,所以返回isaprocedure。

过程的嵌套定义

在Scheme语言中,过程定义也可以嵌套,一般情况下,过程的内部过程定义只有在过程内部才有效,相当C语言中的局部变量。

如下面的代码的最终结果是50:

(define fix
(lambda (x y z)
(define add
(lambda (a b) (+ a b)))
(- x (add y z))))
(display (fix 100 20 30))



此时过程add只在fix过程内部起做用,这事实上涉及了过程和变量的绑定,可以参考下面的关于过程绑定(let,let* 和letrec)的介绍。

过程是初学者难理解的一个关键,随着过程参数的增加和功能的增强,过程的内容变得越来越复杂,小括号也会更多,如果不写出清晰的代码的话,读代码也会成为一个难题。

熟悉了 scheme 基本概念、数据类型和过程(函数)后, 下一部分我们来学习 scheme 的结构、递归调用和其他扩展功能。
一.常用结构

顺序结构

也可以说成由多个form组成的form,用begin来将多个form放在一对小括号内,最终形成一个form。格式为:(begin form1 form2 …)

如用Scheme语言写成的经典的helloworld程序是如下样子的:

(begin
(display "Hello world!") ; 输出"Hello world!"
(newline)) ; 换行



if结构

Scheme语言的if结构有两种格式,一种格式为:(if 测试 过程1 过程2),即测试条件成立则执行过程1,否则执行过程2。例如下面代码:

(if (= x 0)
(display "is zero")
(display "not zero"))



还有另一种格式:(if 测试 过程) ,即测试条件成立则执行过程。例如下面代码:

(if (< x 100) (display "lower than 100"))



根据类型判断来实现自省功能,下面代码判断给定的参数是否为字符串:

(define fun
(lambda ( x )
(if (string? x)
(display "is a string")
(display "not a string"))))



如执行 (fun 123) 则返回值为"not a string",这样的功能在C++或JAVA中实现的话可能会很费力气。

cond结构

Scheme语言中的cond结构类似于C语言中的switch结构,cond的格式为:

(cond ((测试) 操作) … (else 操作))



如下是在Guile中的操作:

guile> (define w (lambda (x)
(cond ((< x 0) 'lower)
((> x 0) 'upper)
(else 'equal))))
guile> w
#
guile> (w 9)
upper
guile> (w -8)
lower
guile> (w 0)
equal



上面程序代码中,我们定义了过程w,它有一个参数x,如果x的值大于0,则返回符号upper,如x的值小于0则返回符号lower,如x 的值为0则返回符号equal。

下载已做成可执行脚本的 例程。

cond可以用if形式来写,上面的过程可以如下定义:

guile> (define ff
(lambda (x)
(if (< x 0) 'lower
(if (> x 0) 'upper 'zero))))
guile> ff
#
guile> (ff 9)
upper
guile> (ff -9)
lower
guile> (ff 0)
zero



这在功能上是和cond一样的,可以看出cond实际上是实现了if的一种多重嵌套。

case结构

case结构和cond结构有点类似,它的格式为:

(case (表达式) ((值) 操作)) ... (else 操作)))

case结构中的值可以是复合类型数据,如列表,向量表等,只要列表中含有表达式的这个结果,则进行相应的操作,如下面的代码:

(case (* 2 3)
((2 3 5 7) 'prime)
((1 4 6 8 9) 'composite))



上面的例子返回结果是composite,因为列表(1 4 6 8 9)中含有表达式(* 2 3)的结果6;下面是在Guile中定义的func过程,用到了case结构:

guile> (define func
(lambda (x y)
(case (* x y)
((0) 'zero)
(else 'nozero))))
guile> func
#
guile> (func 2 3)
nozero
guile> (func 2 0)
zero
guile> (func 0 9)
zero
guile> (func 2 9)
nozero



可以下载另一个脚本文件 te.scm,参考一下。

and结构

and结构与逻辑与运算操作类似,and后可以有多个参数,只有它后面的参数的表达式的值都为#t时,它的返回值才为#t,否则为#f。看下面的操作:

guile> (and (boolean? #f) (< 8 12))
#t
guile> (and (boolean? 2) (< 8 12))
#f
guile> (and (boolean? 2) (> 8 12))
#f



如果表达式的值都不是boolean型的话,返回最后一个表达式的值,如下面的操作:

guile> (and (list 1 2 3) (vector 'a 'b 'c))
#(a b c)
guile> (and 1 2 3 4 )
4
guile> (and 'e 'd 'c 'b 'a)
a



or结构

or结构与逻辑或运算操作类似,or后可以有多个参数,只要其中有一个参数的表达式值为#t,其结果就为#t,只有全为#f时其结果才为#f。如下面的操作:

guile> (or #f #t)
#t
guile> (or #f #f)
#f
guile> (or (rational? 22/7) (< 8 12))
#t
guile> (rational? 22/7)
#t
guile> (real? 22/7)
#t
guile> (or (real? 4+5i) (integer? 3.22))
#f



我们还可以用and和or结构来实现较复杂的判断表达式,如在C语言中的表达式:

((x > 100) && (y < 100)) 和 ((x > 100) || (y > 100))



在Scheme中可以表示为:

guile> (define x 123)
guile> (define y 80)
guile> (and (> x 100) (< y 100))
#t
guile> (or (> x 100) (> y 100))
#t



Scheme语言中只有if结构是系统原始提供的,其它的cond,case,and,or,另外还有do,when,unless等都是可以用宏定义的方式来定义的,这一点充分体现了Scheme的元语言特性,关于do,when等结构的使用可以参考R5RS。






回页首




二.递归调用

用递归实现阶乘

在Scheme语言中,递归是一个非常重要的概念,可以编写简单的代码很轻松的实现递归调用,如下面的阶乘过程定义:

(define factoral (lambda (x)
(if (<= x 1) 1
(* x (factoral (- x 1))))))



我们可以将下面的调用(factoral 4),即4的阶乘的运算过程图示如下:




以下为factoral过程在Guile中的运行情况:

guile> (define factoral (lambda (x) (if (<= x 1) 1 (* x (factoral (- x 1))))))
guile> factoral
#
guile> (factoral 4)
24



另一种递归方式

下面是一另一种递归方式的定义:

(define (factoral n)
(define (iter product counter)
(if (> counter n)
product
(iter (* counter product) (+ counter 1))))
(iter 1 1))
(display (factoral 4))



这个定义的功能和上面的完全相同,只是实现的方法不一样了,我们在过程内部实现了一个过程iter,它用counter参数来计数,调用时从1开始累计,这样它的展开过程正好和我们上面的递归过程的从4到1相反,而是从1到4。

循环的实现

在Scheme语言中没有循环结构,不过循环结构可以用递归来很轻松的实现(在Scheme语言中只有通过递归才能实现循环)。对于用惯了C语言循环的朋友,在Scheme中可以用递归简单实现:

guile> (define loop
(lambda(x y)
(if (<= x y)
(begin (display x) (display #\\space) (set! x (+ x 1))
(loop x y)))))
guile> loop
#
guile> (loop 1 10)
1 2 3 4 5 6 7 8 9 10



这只是一种简单的循环定义,过程有两个参数,第一个参数是循环的初始值,第二个参数是循环终止值,每次增加1。相信读者朋友一定会写出更漂亮更实用的循环操作来的。






回页首




三.变量和过程的绑定

let,let*,letrec

在多数编程语言中都有关于变量的存在的时限问题,Scheme语言中用let,let*和letrec来确定变量的存在的时限问题,即局部变量和全局变量,一般情况下,全局变量都用define来定义,并放在过程代码的外部;而局部变量则用let等绑定到过程内部使用。

用let可以将变量或过程绑定在过程的内部,即实现局部变量:

guile> let
#



从上面的操作可以看出let是一个原始的宏,即guile内部已经实现的宏定义。

下面的代码显示了let的用法(注意多了一层括号):

guile> (let ((x 2) (y 5)) (* x y))
10



它的格式是:(let ((…)…) …),下面是稍复杂的用法:

guile> (let ((x 5))
(define foo (lambda (y) (bar x y)))
(define bar (lambda (a b) (+ (* a b) a)))
(foo (+ x 3)))
45



以上是Guile中的代码实现情况。它的实现过程大致是:(foo 8) 展开后形成 (bar 5 8),再展开后形成 (+ (* 5 8) 5) ,最后其值为45。

再看下面的操作:

guile> (let ((iszero?
(lambda(x)
(if (= x 0) #t #f))))
(iszero? 9))
#f
guile> (iszero? 0) ;此时会显示出错信息



let的绑定在过程内有效,过程外则无效,这和上面提到的过程的嵌套定是一样的,上面的iszero?过程在操作过程内定义并使用的,操作结束后再另行引用则无效,显示过程未定义出错信息。

下面操作演示了let*的用法:

guile> (let ((x 2) (y 5))
(let* ((x 6)(z (+ x y))) ;此时x的值已为6,所以z的值应为11,如此最后的值为66
(* z x)))
66



还有letrec,看下面的操作过程:

guile> (letrec ((even?
(lambda(x)
(if (= x 0) #t
(odd? (- x 1)))))
(odd?
(lambda(x)
(if (= x 0) #f
(even? (- x 1))))))
(even? 88))
#t



上面的操作过程中,内部定义了两个判断过程even?和odd?,这两个过程是互相递归引用的,如果将letrec换成let或let*都会不正常,因为letrec是将内部定义的过程或变量间进行相互引用的。看下面的操作:

guile> (letrec ((countdown
(lambda (i)
(if (= i 0) 'listoff
(begin (display i) (display ",")
(countdown (- i 1)))))))
(countdown 10))
10,9,8,7,6,5,4,3,2,1,listoff



letrec帮助局部过程实现递归的操作,这不仅在letrec绑定的过程内,而且还包括所有初始化的东西,这使得在编写较复杂的过程中经常用到letrec,也成了理解它的一个难点。

apply

apply的功能是为数据赋予某一操作过程,它的第一个参数必需是一个过程,随后的其它参数必需是列表,如:

guile> (apply + (list 2 3 4))
9
guile> (define sum
(lambda (x )
(apply + x))) ; 定义求和过程
guile> sum
#
guile> (define ls (list 2 3 4 5 6))
guile> ls
(2 3 4 5 6)
guile> (sum ls)
20
guile> (define avg
(lambda(x)
(/ (sum x) (length x)))) ; 定义求平均过程
guile> avg
#
guile> (avg ls)
4



以上定义了求和过程sum和求平均的过程avg,其中求和的过程sum中用到了apply来绑定"+"过程操作到列表,结果返回列表中所有数的总和。

map

map的功能和apply有些相似,它的第一个参数也必需是一个过程,随后的参数必需是多个列表,返回的结果是此过程来操作列表后的值,如下面的操作:

guile> (map + (list 1 2 3) (list 4 5 6))
(5 7 9)
guile> (map car '((a . b)(c . d)(e . f)))
(a c e)



除了apply,map以外,Scheme语言中还有很多,诸如:eval,delay,for-each,force,call-with-current-continuation等过程绑定的操作定义,它们都无一例外的提供了相当灵活的数据处理能力,也就是另初学者望而生畏的算法,当你仔细的体会了运算过程中用到的简直妙不可言的算法后,你就会发现Scheme语言设计者的思想是多么伟大。






回页首




四.输入输出

Scheme语言中也提供了相应的输入输出功能,是在C基础上的一种封装。

端口

Scheme语言中输入输出中用到了端口的概念,相当于C中的文件指针,也就是Linux中的设备文件,请看下面的操作:

guile> (current-input-port)
# ;当前的输入端口
guile> (current-output-port)
# ;当前的输出端口



判断是否为输入输出端口,可以用下面两个过程:input-port? 和output-port? ,其中input-port?用来判断是否为输入端口,output-port?用来判断是否为输出端口。

open-input-file,open-output-file,close-input-port,close-output-port这四个过程用来打开和关闭输入输出文件,其中打开文件的参数是文件名字符串,关闭文件的参数是打开的端口。

输入

打开一个输入文件后,返回的是输入端口,可以用read过程来输入文件的内容:

guile> (define port (open-input-file "readme"))
guile> port
#
guile> (read port)
GUILE语言



上面的操作打开了readme文件,并读出了它的第一行内容。此外还可以直接用read过程来接收键盘输入,如下面的操作:

guile> (read) ; 执行后即等待键盘输入
12345
12345
guile> (define x (read)) ; 等待键盘输入并赋值给x
12345
guile> x
12345



以上为用read来读取键入的数字,还可以输入字符串等其它类型数据:

guile> (define name (read))
tomson
guile> name
tomson
guile> (string? name)
#f
guile> (symbol? name)
#t



此时输入的tomson是一个符号类型,因为字符串是用引号引起来的,所以出现上面的情况。下面因为用引号了,所以(string? str)返回值为#t 。

guile> (define str (read))
"Johnson"
guile> str
"Johnson"
guile> (string? str)
#t



还可以用load过程来直接调用Scheme语言源文件并执行它,格式为:(load "filename"),还有read-char过程来读单个字符等等。

输出

常用的输出过程是display,还有write,它的格式是:(write 对象 端口),这里的对象是指字符串等常量或变量,端口是指输出端口或打开的文件。下面的操作过程演示了向输出文件temp中写入字符串"helloworld",并分行的实现。

[root@toymouse test]# guile
guile> (define port1 (open-output-file "temp")) ; 打开文件端口赋于port1
guile> port1
#
guile> (output-port? port1)
#t ; 此时证明port1为输出端口
guile> (write "hello\\nworld" port1)
guile> (close-output-port port1)
guile> (exit) ; 写入数据并关闭退出
[root@toymouse test]# more temp 显示文件的内容,达到测试目的
"hello
world"



在输入输出操作方面,还有很多相关操作,读者可以参考R5RS的文档。






回页首




五.语法扩展

Scheme语言可以自己定义象cond,let等功能一样的宏关键字。标准的Scheme语言定义中用define-syntax和syntax-rules来定义,它的格式如下:

(define-syntax 宏名
(syntax-rules()
((模板) 操作))
. . . ))



下面定义的宏start的功能和begin相同,可以用它来开始多个块的组合:

(define-syntax start
(syntax-rules ()
((start exp1)
exp1)
((start exp1 exp2 ...)
(let ((temp exp1)) (start exp2 ...))) ))



这是一个比较简单的宏定义,但对理解宏定义来说是比较重要的,理解了他你才会进一步应用宏定义。在规则 ((start exp1) exp1) 中,(start exp1) 是一个参数时的模板,exp1是如何处理,也就是原样搬出,不做处理。这样 (start form1) 和 (form1) 的功能就相同了。

在规则 ((start exp1 exp2 ...) (let ((temp exp1)) (start exp2 ...))) 中,(start exp1 exp2 …) 是多个参数时的模板,首先用let来绑定局部变量temp为exp1,然后用递归实现处理多个参数,注意这里说的是宏定义中的递归,并不是过程调用中的递归。另外在宏定义中可以用省略号(三个点)来代表多个参数。

在Scheme的规范当中,将表达式分为原始表达式和有源表达式,Scheme语言的标准定义中只有原始的if分支结构,其它均为有源型,即是用后来的宏定义成的,由此可见宏定义的重要性。附上面的定义在GUILE中实现的 代码。






回页首




六. 其它功能

1. 模块扩展

在R5RS中并未对如何编写模块进行说明,在诸多的Scheme语言的实现当中,几乎无一例外的实现了模块的加载功能。所谓模块,实际就是一些变量、宏定义和已命名的过程的集合,多数情况下它都绑定在一个Scheme语言的符号下(也就是名称)。在Guile中提供了基础的ice-9模块,其中包括POSIX系统调用和网络操作、正则表达式、线程支持等等众多功能,此外还有著名的SFRI模块。引用模块用use-modules过程,它后面的参数指定了模块名和我们要调用的功能名,如:(use-modules (ice-9 popen)),如此后,就可以应用popen这一系统调用了。如果你想要定义自己的模块,最好看看ice-9目录中的那些tcm文件,它们是最原始的定义。

另外Guile在面向对象编程方面,开发了GOOPS(Guile Object-Oriented Programming System),对于喜欢OO朋友可以研究一下它,从中可能会有新的发现。

2. 如何输出漂亮的代码

如何编写输出漂亮的Scheme语言代码应该是初学者的第一个问题,这在Guile中可以用ice-9扩展包中提供的pretty-print过程来实现,看下面的操作:

guile> (use-modules (ice-9 pretty-print)) ; 引用漂亮输出模块
guile> (pretty-print '(define fix (lambda (n)
(cond ((= n 0) 'iszero)
((< n 0) 'lower)
(else 'upper))))) ; 此处是我们输入的不规则代码
(define fix
(lambda (n)
(cond ((= n 0) 'iszero)
((< n 0) 'lower)
(else 'upper)))) ; 输出的规则代码



3. 命令行参数的实现

在把Scheme用做shell语言时,经常用到命令行参数的处理,下面是关于命令行参数的一种处理方法:

#! /usr/local/bin/guile -s
!#
(define cmm (command-line))
(display "应用程序名称:")
(display (car cmm))
(newline)
(define args (cdr cmm))
(define long (length args))
(define loop (lambda (count len obj)
(if (<= count len)
(begin
(display "参数 ")
(display count)
(display " 是:")
(display (list-ref obj (- count 1)))
(newline)
(set! count (+ count 1))
(loop count len obj)))))
(loop 1 long args)



下面是运行后的输出结果:

[root@toymouse doc]# ./tz.scm abc 123 ghi
应用程序名称:./tz.scm
参数 1 是:abc
参数 2 是:123
参数 3 是:ghi



其中最主要的是用到了command-line过程,它的返回结果是命令参数的列表,列表的第一个成员是程序名称,其后为我们要的参数,定义loop递归调用形成读参数的循环,显示出参数值,达到我们要的结果。

4. 特殊之处

一些精确的自己计算自己的符号

数字 Numbers 2 ==> 2
字符串 Strings "hello" ==> "hello"
字符 Charactors #\\g ==> #\\g
辑值 Booleans #t ==> #t
量表 Vectors #(a 2 5/2) ==> #(a 2 5/2)



通过变量计算来求值的符号

如:



x ==> 9
-list ==> ("tom" "bob" "jim")
factoral ==> #
==> #



define 特殊的form

(define x 9) ,define不是一个过程, 它是一个不用求所有参数值的特殊的form,它的操作步骤是,初始化空间,绑定符号x到此空间,然后初始此变量。

必须记住的东西

下面的这些定义、过程和宏等是必须记住的:

define,lambda,let,lets,letrec,quote,set!,if,case,cond,begin,and,or等等,当然还有其它宏,必需学习,还有一些未介绍,可参考有关资料。

走进Scheme语言的世界,你就发现算法和数据结构的妙用随处可见,可以充分的检验你对算法和数据结构的理解。Scheme语言虽然是古老的函数型语言的继续,但是它的里面有很多是在其它语言中学不到的东西,我想这也是为什么用它作为计算机语言教学的首选的原因吧。

在 Linux 上运行 VLM 环境 (Part 2)

本文简要说明在 Open Genera 图形环境运行起来以后在虚拟机上的配置部分.

[理论]

1. 每个 VLM 实例都需要先定义一个站点 (site), 然后运行在这个 site 上. Lisp Machine 原本是支持分布式计算的, 多个 site 之间可以互相跨 site 操作.

2. 一个 VLM site 在定义的同时也定义了与宿主机的文件系统映射关系, VLM 实际上并不管理文件系统, 它通过 NFS 访问宿主机的文件系统. 当然, 这和原始 Lisp Machine 上是不一样的. 文件系统映射带来的另外一个好处是, VLM 可以访问到几乎所有源代码了. opengenera2.tar.bz2 里含有 130 万行 Lisp 源代码, 采用 ANSI Common Lisp 或者 ZetaLisp 语法写成. 值得注意的是这并不是全部的源代码, 仅仅是分发给最终用户的可用来扩展系统的那部分源代码.

[实践]

1. 首次启动 Open Genera 环境时, 可以看到如下屏幕提示:
Symbolics Open Genera(TM) 2.0

This machine is Distribution DIS-LOCAL-HOST, a Symbolics Virtual Lisp Machine(TM),
running on Distribution DIS-EMB-HOST, a DEC Alpha workstation.

Symbolics Open Genera 2.0
Loaded from HOST:Genera-8-5.vlod
409.0M words virtual memory requested, 398.0M words still available.

Open Genera 2.0
Genera 8.5
Genera program 9.0
DEC OSF/1 V127
其中 DIS-LOCAL-HOST 是 VLM 的初始 site 名称, 这是软件分发时提供的初始 site, 最后要被改掉.
另外我们可以看到一些版本信息:

DEC OSF/1 大概是最初 VLM 所运行的操作系统信息 (DEC OSF/1 on Alpha)
Genera program 是作为操作系统接口的启动程序, 版本 9.0
Genera 是 Lisp Machine 系统映像, 版本 8.5
Open Genera 是 Genera 在 DEC Tru64 UNIX 上的移植, 版本 2.0

(OSF/1 和 Tru64 是 DEC 的两种不同的操作系统, 前者跟 Lisp Machine 的关系我不是很清楚...)

最后的屏幕提示是

Please login.
Command:

2. 下面新建一个 site, 可以取任何名字, 不区分大小写, 命名规则跟 Lisp Symbol 一致. 这里我用的是 "testing"

:Define Site (site name) testing

注意我首先输入的是 :define 然后我输入空格, :define 就自动变成 :Define 了, 然后我输入 site 再按空格就得到了 :Define Site (site name), 这时我再输入 testing 然后回车, 可以看到下列信息:

Defining site TESTING with the local host as the Primary Namespace Server
Namespace Server Name: /the name of the primary namespace server/
aborts, uses these values.

Lisp Machine 的 UI 设计很有意思, 它提示你没有设置 Namespace Server, 设置的方法是用鼠标点一个那些斜体小字 /the name of the primary namespace server/, 然后就可以得到一个输入焦点了.

由于 Linux 移植本身的限制, 这个地方必须填 wide-vlm, 是符号名, 不区分大小写. Linux 移植版本认为 VLM 所在的主机名是 wide-vlm, 而宿主机的主机名是 wide.

输入了所需的 Namespace Server Name (wide-vlm) 以后回车, 就会出现更多的信息:

System File Directory: HOST:/var/lib/symbolics/sys.sct/site/
Namespace Descriptor File: HOST:/var/lib/symbolics/sys.sct/site/testing-namespace.text
Unix Host Name: /the name of the DEC AXP host on which Open Genera is running
Default Login: Lisp-Machine
Host for Bug Reports: wide-vlm
Local Timezone: EDT
Standalone Site: [Yes] No
aborts, uses these values.

和前面一样, 需要用鼠标点击每个需要修改的属性, 填写正确的信息. 如果需要在原值的基础上修改, 一个方法是把鼠标移到需要修改的条目上, 等到该条目周围出现了边框, 按鼠标右键就能得到一个弹出式菜单:

+----------------------------------------------+
|Operation on #:|
|----------------------------------------------+
|Edit this field |
|Remove this field |
|Replace this field |
|/Presentation debugging menu/ |
|/System menu/ |
|/Window operation menu/ |
+----------------------------------------------+

左键选择第一项 "Edit this field" 就可以直接编辑当前内容了. 注意, 编辑环境的键绑定是类 Emacs 的.

假设我在宿主机上把 og2 目录解压在 /home/binghe/og2, 我宿主机的真实主机名 ddb-3.lab.163.org, IP 地址为
172.16.3.3 (IP 地址信息可以自动检测到, 如果正确配置了 NIS), 默认登录用户为 binghe, 那么最后的屏幕上应该是这个样子:

:Define Site (site name) testing
Defining site TESTING with the local host as the Primary Namespace Server
Namespace Server Name: wide-vlm
System File Directory: WIDE:/home/binghe/og2/sys.sct/site/
Namespace Descriptor File: WIDE:/home/binghe/og2/sys.sct/site/testing-namespace.text
Unix Host Name: ddb-3.lab.163.org
System Type for WIDE: UNIX42
Address for WIDE: INTERNET 172.16.3.3
File Protocol for accessing WIDE: NFS
Default Login: binghe
Host for Bug Reports: wide-vlm
Local Timezone: EDT
Standalone Site: [Yes] No
aborts, uses these values.

当这些输入都完成以后, 按键盘 END 或者鼠标点击一下屏幕上的 就可以开始执行命令了, 如果没有问题的话, 会得到如下屏幕输出:

The local host is now WIDE-VLM
[09:50:12 Namespace on DIS-LOCAL-HOST: Reloading namespace TESTING.
Recent servers contacted are DIS-LOCAL-HOST]
[09:50:13 Namespace TESTING has become unloaded:
No longer server for this namespace.]

3. 然后重启一下网络:
Command: :Reset Network
[09:50:23 Namespace on WIDE-VLM: Reloading namespace TESTING.
Recent servers contacted are WIDE-VLM]
[09:50:23 The local host WIDE-VLM did not have address 10.0.0.2 on network INTERNET with name eth0 but it was specified in the FEP. The namespace needs to be fixed.]

4. 接下来要做的是映射文件系统, 以便日后能方便地访问源代码和文档:

Command: (si:login-to-sys-host)
NIL
Command: (fs:set-logical-pathname-host "SYS" :translations '(("**;*.*" "WIDE:/home/binghe/og2/sys.sct/**/*.*")))
#

5. 然手利用源码重建调试信息数据库:

Command: (si:enable-who-calls :all-remake)
Scanning all compiled functions...
Scanning all symbols...
Loading macro callers from SYS:PATCH;SYSTEM-452;MACRO-CALLS.VBIN.8.
Who calls database made.
New definitions will be added automatically.
:ALL

6. 安装结束之前的最后一步是把所有成果保存到一个新的文件里 (binghe.vlod)

Command: :Save World (on file [default WIDE:Genera-8-5.vlod]) WIDE:/home/binghe/snap4/binghe.vlod
Estimated size is 54092 blocks.

Symbolics System, /home/binghe/snap4/binghe.vlod
Virtual Lisp Machine Processor, 409.0M words virtual memory requested, 396.0M words still available.
Open Genera 2.0
Genera 8.5
Genera program 9.0
DEC OSF/1 V127

Testing WIDE-VLM

Are you satisfied with this herald? (Y or N) Yes.

The title for this world on the disk label is
"Open Genera 2.0, Genera 8.5".
OK? (Y or N)

然后我只要按一下 Y, 就开始 dump 整个 world 了. 窗口一度消失, 然后再恢复.

7. 接下来测试 New World 的可用性. 首先要把当前环境退出, 我还不知道怎么用命令退出, 所以直接在宿主机上面 Ctrl+C 把 genera 程序中断了...

然后修改 .VLM 文件, 把
genera.world: Genera-8-5.vlod
改为
genera.world: binghe.vlod
然后用 sudo ./genera 重新启动.

8. 新的图形窗口如果顺利产生了, 那么可能将会是这个样子:
Symbolics Open Genera(TM) 2.0

This machine is Testing WIDE-VLM, a Symbolics Virtual Lisp Machine(TM),
running on Testing WIDE, a DEC Alpha workstation.

Symbolics Open Genera 2.0
Loaded from HOST:Genera-8-5.vlod
409.0M words virtual memory requested, 398.0M words still available.

Open Genera 2.0
Genera 8.5
Genera program 9.0
DEC OSF/1 V127
注意到宿主机和虚拟机的名字都发生变化了. 接下来最重要的操作是看文档, 有两种方法: 一是用快捷键, 先按 F1, 再按字母 d. 或者通过右键的系统菜单选择 Document Examiner.

文档窗口里分为三部分, 左边是文档浏览窗口, 右上是文档入口, 右下是书签. 选择一个文档入口, 然后在左边窗口里就可以浏览该文档了. 翻页的快捷键是 键, 也就是目前键盘上的 PageDown. 或者用鼠标点窗口左边的滚动条翻页, 左键下翻, 右键上翻.

文档里可以学到关于 Lisp Machine 的几乎所有知识, 所以从这里开始就不需要我再多做说明了.

9. 我还不太清楚用户登录的具体作用, 不过我知道如何登录:

Command: :Login (user name) binghe (keywords) :Host (the name of a host) WIDE
Password for logging in to WIDE as binghe (or Escape to change user id): ********
No init file: Unable to find any of the files ......
Command:

登录时所需的密码是该用户在宿主机上的系统密码, VLM 通过 NIS 来做认证的. 然后可以看到状态栏里当前登录用户是 binghe 了.

在 Linux 上运行 VLM 环境 (Part 1)

本文介绍如何在 64 位 Linux 系统上运行 Symbolics Virtual Lisp Machine 环境。

[准备工作]

1. 一台 x86_64 兼容的服务器或工作站, 只有 x86 平台的话可用 qemu 配 x86_64 虚拟机;
2. 64 位 Linux 系统, 推荐采用经过测试的版本 (Debian 或 Ubuntu);
3. opengenera2.tar.bz2 和 snap4.tar.gz 这两个安装文件.

[理论]

1. Virtual Lisp Machine(VLM) 运行环境由三部分组成:
启动程序是操作系统接口, 负责 lisp machine 指令到 alpha 指令的转换, 并加载映像文件;
操作系统映像文件, 包括全部 Lisp 层面的实现;
源代码以及文档(sys.sct目录);

2. 难以得到的 opengenera2.tar.bz2 实际上只提供最后一部分: 源代码以及文档.
这个压缩包里含有的其余两部分是用于 Alpha 处理器的 DEC Tru64 UNIX 环境下的, 对 x86_64 环境没有用的.

3. snap4.tar.gz 里包括三个东西:
启动程序(genera), 操作系统接口, 估计完成了从 lisp machine 指令到 x86_64 的转换.
映像文件(Genera-8-5.vlod)
调试器映像(VLM_debugger)

4. VLM 是一台虚拟机, 运行 VLM 的真实服务器称为宿主机. 虚拟机访问宿主机资源是通过网络来完成的. 对于文件来说, 使用的是 NFS. VLM 可以将宿主机的文件系统映射到 Lisp 的 SYS 逻辑路径上.

5. VLM 的系统时间是在启动时通过宿主机提供的 UNIX 时间服务以 UDP 协议获得的, 实践表明不存在千年虫.

6. VLM 的 Linux 移植版本把 IP 地址固定在 10.0.0.2 上,它在运行时建立了一个 TUN 通道,连接到宿主机 10.0.0.1 上,宿主机上的这个地址是自动创建的,无须事先修改任何网络有关的配置文件。但要确保宿主机本身不要配置任何通道网络设备。

[实践]

1. 安装宿主机上必须的一些软件, 包括 INETD, NFS 和 NIS:

# aptitude install openbsd-inetd nfs-user-server nis

注意, 安装 NIS 时系统会提示输入 NIS 服务器所在的网络域, 默认值是当前 Linux 主机所在的 DNS 域, 建议接受这一默认值.

1.1. INETD 为 VLM 提供时间服务, 它的配置文件 /etc/inetd.conf 里要包括下列 4 行:

daytime stream tcp nowait root internal
daytime dgram udp wait root internal
time stream tcp nowait root internal
time dgram udp wait root internal

然后重启 inetd:

# /etc/init.d/openbsd-inetd restart
Restarting internet superserver: inetd.

1.2. NFS 的配置方法是在 /etc/exports 里加入下列一行:

/ 10.0.0.2(rw,no_root_squash)

然后重启 NFS:

# /etc/init.d/nfs-user-server restart
Stopping NFS servers: mountd nfsd.
Starting NFS servers: nfsd mountd.

NFS 的正确访问还需要在宿主机上建立一个 lispm 组和 lispm 用户:

# groupadd -g 4294967294 lispm
# useradd -g lispm -u 4294967294 -s /bin/false -d /tmp lispm

上述用户和组在 /etc/passwd 以及 /etc/group 里是这个样子的:
lispm:!:4294967294:4294967294::/tmp:/bin/false
lispm:!:4294967294:

1.3. NIS 提供的配置文件在 /etc/default/nis 里, 主要修改的内容如下:

NISSERVER=master
NISCLIENT=false

然后重启 nis:

# /etc/init.d/nis restart
Starting NIS services: ypserv yppasswdd ypxfrd ypbind.

NIS 服务所需的数据使用下列方法生成:

1.3.1. 修改系统密码加密方式, 取消 md5 特性. 方法是修改 /etc/pam.d/common-password, 把
password required pam_unix.so nullok obscure min=4 max=8 md5
改为
password required pam_unix.so nullok obscure min=4 max=8 # md5
这相当于把 md5 部分注释掉了.

1.3.2. 将 shadow 密码转换为传统密码, 这样会降低密码安全性, 但这是 nis 所要求的, 没有办法:
# pwunconv
# grpunconv
这两个命令的精确含义可以通过 man 查询到:
pwunconv creates passwd from passwd and shadow and then removes shadow.
grpunconv creates group from group and gshadow and then removes gshadow.

1.3.3. 进入 /var/yp 目录, 执行 make:

ddb-3:/var/yp# make
make[1]: Entering directory `/var/yp/lab.163.org'
Updating passwd.byname...
Updating passwd.byuid...
Updating group.byname...
Updating group.bygid...
Updating hosts.byname...
Updating hosts.byaddr...
Updating rpc.byname...
Updating rpc.bynumber...
Updating services.byname...
Updating services.byservicename...
Updating netid.byname...
Updating protocols.bynumber...
Updating protocols.byname...
Updating netgroup...
Updating netgroup.byhost...
Updating netgroup.byuser...
make[1]: Leaving directory `/var/yp/lab.163.org'

2. 安装 VLM 所需文件

在主目录里, 解压两个安装文件: (以下假设我的主目录是 /home/binghe, 这个假设会多次用到)

$ tar xvjf opengenera2.tar.bz2
$ tar xvzf snap4.tar.gz

解压 opengenera2.tar.bz2 能得到一个 og2 目录, 对我们来说, 唯一需要的是 og2/sys.sct 目录.
解压 snap4.tar.gz 能得到 snap4 目录, 内容如下:

-rw-r--r-- 1 binghe staff 733 2006-08-08 dot.VLM
-rwxr-xr-x 1 binghe staff 1533760 2006-08-08 genera
-rw-r--r-- 1 binghe staff 54804480 2006-08-08 Genera-8-5.vlod
-rw-r--r-- 1 binghe staff 2902 2006-08-08 README
-rw-r--r-- 1 binghe staff 934 2006-08-08 .VLM
-rw-r--r-- 1 binghe staff 346880 2006-08-08 VLM_debugger

唯一的配置文件是 .VLM 文件, 确保它的内容是这样的:

genera.network: 10.0.0.2;mask=255.255.255.0; gateway=10.0.0.1
genera.virtualMemory: 2048
genera.world: Genera-8-5.vlod
genera.debugger: VLM_debugger
genera.coldLoad.geometry: 800x600

由于 genera 需要打开一个 TUN/TAP 网络设备, 普通用户没有这个权限, 所以 VLM 必须以 root 权限启动, 一个比较好的方法是使用 sudo, 给当前用户设置一个 sudo 的特权. 方法是安装 sudo:

# aptitude install sudo

然后用 visudo 命令修改 sudo 的配置文件, 加上下面一行: (我当前的用户是 binghe, 读者请自行调整配置文件里的用户名部分)

binghe ALL=NOPASSWD: ALL

最后, 如果一切顺利的话, 在 snap4 目录里执行 sudo ./genera 就可以看到 Open Genera 窗口了. 需要注意的是 Lisp Machine 的窗口尺寸非常大,在我的桌面环境下,加上 Linux 自身的窗口边框以后,尺寸达到了 1512x976,幸好我的显示器是 1680x1050 的……

还有一种可能, 那就是这台 64 位机, 并不是工作站, 而是一台远程的服务器. 这种情况下只需通过 SSH 登录时打开 X 转发选项 (ssh 加 -X 参数), 同时确保从一个运行了 X Server 的客户机登录过去就可以了 (所有的 Linux 桌面环境都满足条件, Windows 的话难度较大, 需要安装 Cygwin 并启动 X Server 才行)

启动 Open Genera 窗口以后还需要大量配置工作才能得到一个可用的 Lisp Machine 环境,

Ansi Common Lisp

序言
约翰麦卡锡和他的学生于1958年开始Lisp的首个实现工作. Lisp是Fortran之后仍然在使用的最古老的语言.1 更值得一提的是,它仍然处在编程语言技术的最前沿. 懂 Lisp的程序员会告诉你,这种语言有某种东西使得它与众不同.
部分使Lisp与众不同的原因是它被设计成能够自己演变. 你能用Lisp定义新的 Lisp操作符. 随着新的抽象概念越来越流行(比如面向对象编程),我们总是发现在Lisp中实现它们很容易. 就象DNA, 这样的语言不会过时.


新的工具
为什么要学Lisp? 因为它能让你做其它语言中不能做的事情. 如果你仅想写一个函数返回小于n的非负整数的总和, 那么用Lisp和C是差不多的:
; Lisp /* C */
(defun sum (n) int sum(int n){
(let ((s 0)) int i, s = 0;
(dotimes (i n s) for(i = 0; i < n; i++)
(incf s i)))) s += i;
return(s);
}

如果你只想做这样简单的事,那用哪种语言是无关紧要的. 假设你想写一个函数接受数n, 返回一个函数: 它把n增加到它的自变量上去:
; Lisp
(defun addn (n)
#'(lambda (x)
(+ x n)))

在C语言中addn会是怎样的? 你根本写不出来.
你可能会想,谁会想要做这样的事情? 编程语言教你不要试图去做它们不提供的事. 你用某种语言写程序的时候,你得用那种语言思考问题,而且想要你不能描述的东西是很因难的. 我刚开始写程序--用Basic--的时候,我并不想要递归,因为我根本不知道有这么回事. 我用Basic思考. 我只有递推算法的概念,为什么我想要递归呢?

如果你不渴望逻辑封装(上面的例子中就使用了它),请相信, 目前Lisp程序员一直在使用它. 很难找到任意长度的Lisp代码不利用封装的. 到112页你会自己使用它.

封装只是我们不能在其它语言中找到的抽象概念之一. 另外一个更有价值的Lisp 的独特特征是Lisp程序是用Lisp的数据结构来表示的. 这意味着你可以编写能写程序的程序. 人们真的需要这个吗? 是的--它们叫做宏, 有经验的程序员也一直在使用它. 到173页你就可以写自己的宏了.

有了宏,封装,和运行时类型,Lisp超过了面向对象编程. 如果你理解上面这句话, 也许你不需要读这本书了. 你得相当理解Lisp才能看到为什么这不是假话. 但这不仅仅是说说而已. 这是一个重要的论点,它的证明在第17章用代码明确地写出来了.

第2章到第13章会逐渐地介绍所有你需要理解第17章的代码的概念. 你的努力会有所回报,打个比方: 你在C++中编程会感觉到窒息,就象有经验的C++程序员用 Basic编程会感到窒息一样. 更令人鼓舞的可能是,如果我们思考一下这种感觉从何而来. Basic令习惯C++的人窒息是因为有经验的C++程序员知道有无法在Basic 中表达的技术. 同样地, 学习Lisp不仅是让你学会了一门新的语言--它会教你新的更强大的考虑程序的方法.


新的技术
就象上一节提到的,Lisp提供其它语言不能提供的工具. 但远远不止这些. 单独地讲,伴随Lisp的新东西--自动内存管理,显式的类型,封装,等等--每一项都使编程更加容易. 它们合在一起组成了一个临界值使得产生一种新的编程方法成为可能.
Lisp被设计成可扩展的: 它让你定义自己的操作符. 因为Lisp是由和你的程序一样的函数和宏构成的. 所以扩展Lisp和写一段Lisp程序一样容易. 事实上它是这么容易(和有用)以至于扩展这种语言成了标准的实践. 当你写程序向下逼近语言的时候, 你也在构造语言向上逼近你的程序. 你不但至上而下也至下而上工作.

几乎所有的程序都可以从让语言裁剪得以适应自己的需要中获得好处, 但程序越复杂, 自下而上设计法就显得越有价值. 一个自下而上的程序可以写成一系列的层, 每一层担当上一层的编程语言. TEX是最早用这种方法写的程序之一. 你可以用任何语言自下而上设计程序,但对这种风格来说,Lisp是最最自然的运载工具.

自下而上编程法自然而然地产生可扩展的软件. 如果你始终坚持自下而上编程原则直到你程序的最高层, 那么这一层就成为用户的可编程语言. 可扩展性的思想深深地扎根于Lisp, 使得它成为编写可扩展软件的理想语言. 1980年代最成功的程序中的三个提供了Lisp作为扩展语言: Gnu Emacs, Autocad, 和Interleaf.

自下而上也是获得可重复使用软件的最好方法. 编写可复用软件的本质是把共性从个性中分离出来. 而自下而上法天然就创造了这种分离. 不是把你所有的精力花在编写一个巨大的应用上, 而是用部分精力去构造一种语言, 用部分精力(比例相对小些)在这种语言上面写你的应用. 和应用有关的特性都集中在最上层, 以下的层可以组成一种语言, 用来编写和这个应用类似的应用--还有什么会比编程语言更具可复用性的呢?

Lisp让你不仅写出更复杂的程序, 而且写得更快. Lisp程序往往很短--这种语言给了你更大的概念, 所以你不需要用多少. 就象Frederick Brooks指出的,写程序所花的时间通常取决于它的长度. 因此这个单独的事实意味着编写Lisp程序花的时间较少. 这种效应被Lisp的动态特性放大: 在Lisp中, 编辑-编译-测试循环是如此之短, 以致编程是实时的.

更大的抽象和交互式的环境能改变各种组织开发软件的方式. 术语``快速原型'' 描述了一种首先在Lisp中使用的编程法: 在Lisp中, 你可以用比写一个规格说明更少的时间写出一个原型来, 而且这种原型如此抽象, 可以作为一个比用英语写的更好的规格说明. 还有Lisp让你做出从原型到产品软件的平*的转变. 当编写 Lisp程序时考虑到速度,经过现代编译器的编译,它们和任何用其它高级语言写的程序跑得一样快.

除非你相当熟悉Lisp,本序言象是一堆夸夸其谈和没有意义的声明. Lisp胜过面向对象编程? 你构造语言逼近你的程序? Lisp编程是实时的? 这些话是什么意思? 现在这些说法就象一些空的湖泊. 随着你学到更多实际的Lisp特点,看到更多的有指导意义的程序范例, 它们就会被实际经验装满, 而有了明确的形状.


新的方法
本书的目标之一是不仅仅解释Lisp语言,而是一种由Lisp造成的新方法. 这是一种你在将来会见得更多的方法. 随着编程环境变得更强大, 编程语言变得更抽象, Lisp编程风格正逐渐取代旧的计划-然后-实现的模式.
在旧的模式中, 错误(bug)永远不该出现. 事先辛苦作出的周密规格说明被期望来保证程序完美地运行. 理论上听起来不错. 不幸的是, 规格说明都是人写的, 也是由人来实现的. 实际的结果是, 计划-然后-实现方法工作得不太好.

作为OS/360工程的经理, Frederick Brooks非常熟悉这种传统的方法. 他也非常熟悉它的后果:

任何OS/360的用户很快意识到它还应该做得多好...而且产品已经晚了, 它用了比原计划多的内存,成本是估计的好几倍,而且运行一直不太好,直到第一个版本之后的好几个版本.2
这就是对那个时代最成功系统之一的描述.
旧模式的问题是它忽略人的局限性. 在旧模式中,你打赌规格说明不会有严重的缺陷,实现它们是一桩把它们翻译成代码的简单事情. 经验证明这实在是一个糟糕的打赌. 如果赌规格说明会搞错, 代码充满错误会更保险些.

这其实就是新编程模式所假定的. 它设法尽量降低错误的成本,而不是希望人们不犯错误. 错误的成本是改正它所花的时间. 使用强大的语言和优秀的编程环境, 这种成本会极大地降低. 编程设计可以较少地依赖于计划,更多地依赖于探索.

计划是一种必要的恶. 它是对风险的反应: 工作越是危险,预先做好计划也就越重要. 强大的工具降低了风险, 也降低了计划的需要. 程序的设计可以从实现它的经验中受益--这可能是最有用的信息来源.

Lisp风格自1960年代以来一直朝这个方向演化. 你在Lisp中可以如此快速地写出原型,以至于你能经历好几个设计和实现的循环, 而在旧的模式中,你可能刚写完规格说明. 你不必过于担心设计缺陷,因为你会更早地发现它们. 你也不必过于担心错误(bugs). 当你用函数风格编程,错误只有局部的影响. 当你使用一种很抽象的语言,某些错误(例如孤悬指针)就永远不会出现了,而剩下的错误很容易找, 因为你的程序更短了. 当你有交互式开发环境时,你能立即修正错误,不必经历编辑,编译,测试的漫长过程.

Lisp风格这么发展是因为它结出了成果. 听起来有点奇怪,少些计划意味着更好的设计. 技术史上相似的例子不胜枚举. 一个类似的事件发生在十五世纪的绘画界里. 在油画颜料流行之前,画家用一种叫蛋彩的物质作画,它不能混合或覆盖. 出错的高昂代价使画家变得保守. 后来随着油画颜料的出现,作画风格有了极大的改变. 油画颜料``允许第二次思考.''3它为因难主题的处理,例如人物画等提供了决定性的有利条件.

新介质不仅使画家作画更容易了. 它使新的更有抱负的作画方式成为可能. Janson写到:

如果没有油画颜料,佛兰德大师们的征服可见的现实的口号就会大打折扣. 于是从技术的角度来看,他们也当之无愧地称得上``现代绘画之父'',因为油画颜料从此成为画家的基本介质.4
作为一种材料,蛋彩并不比油画颜料逊色. 但油画颜料的弹性给了想象力更大的空间--这是决定性的因素.
程序设计正经历着相似的变革. 新的介质是``面向对象的动态语言''--即 Lisp. 不是说我们所有的软件在几年内都要用Lisp来写. 从蛋彩到油彩的过渡也不是一夜之间完成的; 油彩开始只在一些领风气之先的艺术中心流行,而且经常结合着蛋彩使用. 我们现在似乎正处在这个阶段. Lisp在大学,实验室和一些处于前沿的公司中使用. 同时从Lisp那儿借用的思想越来越多地出现在主流中: 交互式开发环境,无用单元收集,运行时类型仅是其中几例.

强大的工具正在减轻探索的风险. 这对程序员来说是个好消息,因为它意味着我们能进行更有抱负的项目. 油彩的应用的确有这样的效果. 它被采用后的时期正是绘画的黄金年代. 类似的迹象已经发生在程序设计领域.

About this document ...
This document was generated using the LaTeX2HTML translator Version 2K.1beta (1.48)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split=0 acl1.tex

The translation was initiated by Dai Yuwen on 2004-04-03



--------------------------------------------------------------------------------

Footnotes
... 仍然在使用的最古老的语言.1
McCarthy, John. Recursive Functions of Symbolic Expressions and their Computation by Machine, Part I. CACM, 3:4 (April 1960),pp. 184-195.
... 本之后的好几个版本.2
Brooks, Frederick P. The Mythical Man-Month. Addison-Wesley, Reading (MA), 1975, p. 16.

快速原型法不仅是一种更快或更好地写程序的方法, 有些程序可能不用此法就根本写不出来.

即使是最有雄心的人也会在巨大的工作面前退缩. 如果能使自己相信某件事不用费很大劲儿(哪怕从表面上看),从它做起就会容易些. 这就是为什么这么多大事是从小事开始的. 快速原型法让我们从小事做起.
... 油画颜料``允许第二次思考.''3
Murray, Peter and Linda. The Art of the Renaissance. Thames and Hudson, London, 1963, p. 85.
... 成为画家的基本介质.4
Janson, W. J. History of Art, 3rd Edition. Abrams, New York, 1986, p. 374.

这个类比只适用于作在画布上的画. 画在墙上的画仍旧用壁画颜料. 我也不是说绘画风格是由技术变迁驱动的; 相反的说法可能更接近事实.

欢迎来到Lisp的世界
本章的目标是尽快让你编程. 在本章结束的时候,你会掌握足够的Common Lisp的知识,可以开始写程序了.
范式(form)
你可以通过使用Lisp而学习它,这是千真万确的,因为Lisp是交互式语言. 任何 Lisp系统都包含一个叫做顶层(toplevel)的交互式前端. 你在顶层中输入Lisp表达式,系统打印它们的值. Lisp通常打印一个提示符表示它正在等待你的输入. 许多Common Lisp的实现用 作为顶层提示符. 我们在这儿也用此符号. 最简单的Lisp表达式之一是一个整数. 如果我们在提示符后面输入1,
> 1
1
>

系统会打印它的值,跟着另一个提示符,表示它在等待更多的输入. 在这种情况下,打印出来的值和我们输入的一样. 象1这样的数叫做自身求值的. 当我们输入一个需要做些求值工作的表达式时,事情变得有趣起来. 例如,如果想把两个数加起来,我们输入:
> (+ 2 3)
5

在表达式(+ 2 3)中,+叫做操作符,数2和3叫做变元. 在日常生活中我们会把此表达式写为2 + 3,但在Lisp中我们把+写在最前面,后面跟着变元,整个表达式被一对括号围住:(+ 2 3). 因为操作符在前,这叫做前缀表示法. 一开始这样写表达式有点怪,但事实上这种表示法是 Lisp最好的东西之一. 比如,我们想把三个数加起来,用通常的表示法我们要写+两次:
2 + 3 + 4

而在Lisp中我们仅需增加一个变元:
> (+ 2 3 4)

通常我们用+,它必须有两个变元:一个在左边,一个在右边. 前缀表示法的弹性意味着,在Lisp中,+可以接受任意数目的变元,包括零个:
> (+)
0
> (+ 2)
2
> (+ 2 3)
5
> (+ 2 3 4)
9
> (+ 2 3 4 5)
14

因为操作符可以接受不同数目的变元,我们需要用括号指示表达式的开始和结束. 表达式可以嵌套. 即表达式中的变元本身可能是个复杂的表达式:
> (/ (- 7 1) (- 4 2))
3

用自然语言来说,七减一的结果被四减二的结果除. 另一个Lisp表示法的漂亮之处是:它无所不包. 所有的Lisp表达式要么是象1这样原子(atom),要么是放在括号中由零个或多个表达式组成的表(list). 这些是合法的Lisp表达式:
2 (+ 2 3) (+ 2 3 4) (/ (- 7 1) (- 4 2))

正如我们将要看到的,所有的Lisp代码都采取这种形式. 象C这样的语言有着更复杂的语法:算术表达式用中缀表示法;函数调用类似前缀表示法,自变量用逗号隔开;表达式用分号隔开;而代码块用花括号分隔. 在Lisp中我们用单一的记号表达所有这些概念.
求值
在上一节中,我们在顶层里输入表达式,Lisp显示它们的值. 在这节里我们仔细观察一下表达式是如何求值的. 在Lisp中,+是一个函数,形如(+ 2 3)的表达式是函数调用. 当Lisp对函数调用求值时,它做这样两步:
首先变元从左至右被求值. 在此例中,每个变元求值到自身,所以变元的值分别是2和3.
变元的值传给以操作符命名的函数. 在此例中,即+函数,它返回5.
如果任何变元本身是函数调用,它们按上述规则求值. 这是对(/ (- 7 1) (- 4 2))求值时发生的情况:
Lisp计算(- 7 1): 7求值为7,1求值为1. 它们被传给函数-,它返回6.
Lisp计算(- 4 2): 4求值为4,2求值为2. 它们被传给函数-,它返回2.
6和2的值传给函数/,它返回3.
并不是所有的Lisp操作符都是函数,但大多数都是. 而函数总是按这种方式求值的. 变元从左至右被求值,它们的值被传给函数,函数返回整个表达式的值. 这叫做Common Lisp的求值规则. 一个不遵守上述规则的操作符是quote. quote是一个特殊操作符,这意味着它有自己独特的求值规则. 这个规则是:什么也不做. quote接受一个变元,并且一字不差地返回它:
> (quote (+ 3 5))
(+ 3 5)

为了方便,Common Lisp定义'作为quote的简记法. 通过在任何表达式前面加上' 你能获得与调用quote同样的效果:
> '(+ 3 5)
(+ 3 5)

用简记法比用quote普遍得多. Lisp提供quote作为一种保护表达式以防被求值的手段. 下一节会解释这种保护是多么有用.

从麻烦中解脱出来 如果你输入了一些Lisp不能理解的东西,它会打印一条出错信息并把你带到一个叫中断循环(break loop)的顶层中去. 中断循环给了有经验的程序员弄清出错原因的机会, 不过一开始你唯一需要知道的事是如何从中断循环中出来. 如何返回顶层取决于你用的Lisp环境. 在这个假设的环境里,用:abort出来:
> (/ 1 0)
Error: Division by zero.
Options: :abort, :backtrace
>> :abort
>

附录A展示了如何调试Lisp程序,以及一些最常见错误的例子.
数据
Lisp提供所有我们能在其它语言中找得到的数据类型,和一些我们找不到的. 一种我们早已使用的数据类型是整数,它写为一列数字:256. 另一种和其它语言一样有的是字符串,它表示为一列用双引号括起来的字符:"ora et labora". 整数和字符串都求值到自身. 另两种我们不常在其它语言中发现的是符号和表. 符号是单词. 通常它们被转换成大写,不管你如何输入:
> 'Artichoke
ARTICHOKE

符号(通常)不求值为自身,因此如果你想引用一个符号,请象上面那样用'引用它. 表表示为被括号包围的零个或多个元素. 元素可以是任何类型,包括表. 你必须引用表,否则Lisp会以为它是函数调用:
> '(my 3 "Sons")
(MY 3 "Sons")
> '(the list (a b c) has 3 elements)
(THE LIST (A B C) HAS 3 ELEMENTS)

请注意一个引号保护整个表达式,包括里面的表达式. 你可以调用list来构造表. 因为list是一个函数,它的变元被求值. 这是+调用在 list调用里的例子:
> (list 'my (+ 2 1) "Sons")
(MY 3 "Sons")

现在我们处于欣赏Lisp最非同寻常特征之一的位置上. Lisp程序表达为表. 如果变元的机动性和优雅性没能说服你Lisp记号是一种有价值的工具,这点应该能使你信服. 这意味着Lisp程序可以生成Lisp代码. Lisp程序员能(而且经常)为自己编写能写程序的程序. 我们到第10章才考虑这种程序,但即使在现阶段理解表达式和表的关系也是很重要的,而不是被它们弄糊涂. 这就是为何我们使用quote. 如果一个表被引用了, 求值返回它本身; 如果没有被引用,它被认为是代码,求值返回它的值:
> (list '(+ 2 1) (+ 2 1))
((+ 2 1) 3)

此处第一个变元被引用了,所以生成了一个表. 第二个变元没有被引用,视之为函数调用,得出一个数字. 在Common Lisp中有两种方法表示空表. 你可用一对不包含任何东西的括号来表示空表,或用符号nil来表示它. 你用哪种方法表示空表都没有关系,不过它会被显示成nil:
> ()
NIL
> nil
NIL

你不必引用nil(虽然这也没什么害处)因为nil求值到自身.
表的操作
函数cons构造表. 如果它的第二个变元是表,它返回一个新表,新表的第一个元素就是第一个变元:
> (cons 'a '(b c d))
(A B C D)

我们可以通过把新元素cons到空表来构造新表. 我们在上一节见到的list函数只不过是一个把几样东西cons到nil上去的方便办法:
> (cons 'a (cons 'b nil))
(A B)
> (list 'a 'b)
(A B)

基本的提取表中元素的函数是car和cdr.1 表的car就是它的第一个元素,而 cdr是第一个元素后面的所有东西:
> (car '(a b c))
A
> (cdr '(a b c))
(B C)

你能用car和cdr的组合来取得表中任何元素. 如果你想取第三个元素,可以这样:
> (car (cdr (cdr '(a b c d))))
C

但是,你可以用third更容易地做同样的事:
> (third '(a b c d))
C

真值
符号t是Common Lisp中表示真的缺省值. 就象nil,t求值到自身. 函数listp返回真如果它的变元是一个表:
> (listp '(a b c))
T

一个函数叫做断言如果它的返回值被解释成真或假. Common Lisp的断言的名字通常以p结尾. 假在Common Lisp中用nil(空表)来表示. 如果我们传给listp的变元不是表,它返回nil:
> (listp 27)
NIL

因为nil扮演两个角色,函数null返回真如果它的变元是空表:
> (null nil)
T

而函数not返回真如果它的变元是假:
> (not nil)
T

它们完全做的是同样的事情. 要if是Common Lisp中最简单的条件语句. 它一般接受三个变元:一个测试表达式, 一个then表达式和一个else表达式. 测试表达式被求值. 如果它返回真,则then 表达式被求值并返回结果. 如果它返回假,则else表达式被求值并返回它的结果:
> (if (listp '(a b c))
(+ 1 2)
(+ 5 6))
3
> (if (listp 27)
(+ 1 2)
(+ 5 6))
11

就象quote,if是特殊操作符. 它不能用函数来实现,因为函数调用的变元总是要求值的,而if的特点是只有最后两个变元中的一个被求值. if的最后一个变元是可选的. 如果你省略它,它缺省为nil:
> (if (listp 27)
(+ 2 3))
NIL

虽然t是真的缺省表示,任何不是nil的东西在逻辑上下文中被认为是真:
> (if 27 1 2)
1

逻辑操作符and和or就象条件语句. 两者都接受任意数目的变元,但只求值能够确定返回值的数目的变元. 如果所有的变元都是真(不是nil),那么and返回最后变元的值:
> (and t (+ 1 2))
3

但如果其中一个变元是假,所有它后面的变元都不求值了. or也类似,只要它碰到一个是真的变元就继续求值了. 这两个操作符是宏. 就象特殊操作符,宏可以规避通常的求值规则. 第10章解释如何编写你自己的宏.
函数
你可以用defun来定义新的函数. 它通常接受三个以上变元:一个名字,一列参数, 和组成函数体的一个或多个表达式. 这是我们定义third的一种可能:
> (defun our-third (x)
(car (cdr (cdr x))))
OUR-THIRD

第一个变元表示函数名将是our-third. 第二个变元,表(x),说明函数将接受一个变元:x. 象这样用作占位符的符号叫做变量. 当变量代表传给函数的变元, 就象x所做的,它又叫做参数. 定义的其余部分,(car (cdr (cdr x))),即通常所说的函数体. 它告诉Lisp,为了计算函数的返回值,它该做些什么. 所以,对我们给出的作为变元的任何x,调用 our-third会返回(car (cdr (cdr x))):
> (our-third '(a b c d))
C

既然我们看到了变量,就更容易理解什么是符号了. 他们是变量名,是一种有自己名称的对象. 这就是为什么符号要象表一样必须被引用. 表必须被引用是因为不如此的话,它就会被当作代码;符号必须被引用是因为不如此的话,它就会被当作变量. 你可以把函数定义想象成某个Lisp表达式的一般形式. 下面的表达式测试1和4之和是否大于3:
> (> (+ 1 4) 3)
T

通过把这些特殊数字换成变量,我们可以写一个函数测试任何两个数之和是否大于第三个:
> (defun sum-greater (x y z)
(> (+ x y) z))
SUM-GREATER
> (sum-greater 1 4 3)
T

Lisp对程序,过程或函数不加区别. 函数做了所有的事情(事实上构成了语言本身的大部分). 你可以认为你的函数中的一个是主函数,但通常你能在顶层里调用任何一个函数. 这意味着,当你写程序的时候,你能一小段一小段地测试它们.
递归
我们在上一节中定义的函数还调用了其它函数为自己服务. 比如sum-greater调用了+和>. 函数可以调用任何函数,包括它本身. 自己调用自己的函数是递归的. Common Lisp函数member测试某样东西是否是一个表的元素. 这是定义成递归函数的简化版本:
(defun our-member (obj lst)
(if (null lst)
nil
(if (eql (car lst) obj)
lst
(our-member obj (cdr lst)))))

断言eql测试它的两个变元是否相同;除此之外,定义中所有东西我们以前都见过. 这是它的运行情况:
> (our-member 'b '(a b c))
(B C)
> (our-member 'z '(a b c))
NIL

our-member的定义符合下面的自然语言描述. 为了测试一个对象obj是否是表lst 的成员,我们
首先检查lst是否为空. 如果是空的,显然obj不是它的成员,我们做完了.
否则如果obj是lst的第一个元素,它就是成员
否则只有当obj是lst其余部分的成员时,它才是lst的成员.
当你设法理解一个递归函数是如何工作的时候,把它翻译成这样的描述会有帮助的. 许多人一开始觉得递归函数很不好理解. 很多困难来自对函数的一个错误的比喻. 有一种趋势把函数想象成某种形式的机器. 原料就象参数一样到来;一些工作被转包给其它函数;最后完成的产品被组装好运出去,就象返回一个值. 如果我们用这种比喻,递归就自相矛盾了. 机器怎么能把活儿转包给自己? 它已经忙着干活了. 一个更好的比喻是把函数想象成经历的过程. 在过程中递归是很自然的事情. 我们经常在日常生活中看到递归过程. 比如,假设一个历史学家对欧洲历史上的人口变化感兴趣. 检查文献的过程可能是这样的:
取得一份文献
查找有关人口变化的信息
如果该文献提到其它可能有用的文献,检查它们
这个例子简单得足以理解,但它是递归的,因为第三步可以伴有一个或多个同样的过程. 因此不要把our-member想象为测试某样东西是否在表中的机器,而是把它理解为决定某样东西是否在表中的规则. 如果我们以这种见解看待函数,递归的悖论就不存在了.2
阅读Lisp
上一节我们定义的our-member以五个括号结尾. 更加复杂的函数定义可能以七八个括号结尾. 初学Lisp的人看到这么多括号会感到气馁. 这叫人如何去读这样的代码? 更不用说写了. 我怎么分辨括号之间的匹配? 回答是,你不需要做这些. Lisp程序员通过缩进,而不是括号来读写程序. 当他们写代码的时候,他们让文本编辑器显示哪个括号匹配哪个. 任何一个优秀的编辑器,特别是Lisp系统附带的,应该能做到括号匹配. 在这样的编辑器中,当你输入了一个括号,它会指示和它匹配的那个括号. 如果你的编辑器不做括号匹配,现在就停下来,研究一个如何使它做这件事,因为没有这个功能,事实上不可能写Lisp 程序的. 在vi中,你可以用:set sm来打开括号匹配. 在emacs中,M-x lisp-mode是获得该功能的好办法. 有了好的编辑器,当你写程序的时候,括号匹配不再是个问题. 而且因为Lisp缩进有通用的惯例,你阅读Lisp代码也不是个问题了. 因为人人都用相同的习惯,你可以通过缩进阅读代码,忽略括号. 不管多么有经验的Lisp黑客,会发现our-member的定义很难读懂,如果它写成这个样子:
(defun our-member (obj lst) (if (null lst) nil (if
(eql (car lst) obj) lst (our-member obj (cdr lst)))))

如果代码适当地缩进,他就没有困难了. 你可以忽略大部分的括号而读懂它:
defun our-member (obj lst)
if null lst
nil
if eql (car lst) obj
lst
our-member obj (cdr lst)

事实上,当你在纸上写Lisp代码的时候,这就是一个可行的办法. 以后你输入的时候,可以充分利用编辑器的匹配括号的功能.
输入和输出
到目前为止,我们一直在利用顶层暗中使用i/o. 对实际的交互式的程序,这可能还不够. 在这一节中,我们看一些输入输出函数. Common Lisp中最一般的输出函数是format. 它接受两个以上变元:第一个表示输出到哪儿,第二个是字符串模板,剩下的变元通常是对象,它们的打印表示 (printed representation)将被插入到模板中去. 这是个典型的例子:
> (format t "~A plus ~A equals ~A.~%" 2 3 (+ 2 3))
2 plus 3 equals 5.
NIL

注意两样东西打印在这儿. 第一行是format打印的. 第二行是format调用的返回值,就象通常一样由顶层打印. 通常象format这样的函数不会直接在顶层,而是在程序内部被调用,因此返回值就不会被看见. format的第一个变元t表示输出将被送到缺省的地方去. 通常这会是顶层. 第二个变元是充当输出模板的字符串. 在它里面,每个 A*表示一个将被填充的位置, 而 %表示新行符. 这些位置依次被后面的变元的值填充. 标准的输入函数是read. 当没有变元时,它从缺省的地方--通常是顶层--读入. 下面这个函数提示用户输入,然后返回任何输入的东西:
(defun askem (string)
(format t "~A" string)
(read))

它运行如下:
> (askem "How old are you? ")
How old are you? 29
29

请记住read会永远等在那儿直到你输入什么东西并(通常要)敲入回车. 因此调用 read而不打印明确的提示信息是不明智的,否则你的程序会给人以已经死掉的印象,但实际上它在等待输入. 第二个要了解read的是它非常强大:它是一个完整的Lisp语法分析器. 它并不是读入字符再把它们当作字符串返回. 它分析所读到的东西,并返回所产生的Lisp 对象. 在上例中, 它返回一个数. askem虽然很短,但它展示了一些我们以前在函数定义中没有看到的内容. 它的函数体包含多个表达式. 函数体可以包含任意多个表达式,当函数被调用时,它们依次被求值,函数会返回最后一个表达式的值. 在以前的章节中,我们坚持所谓的``纯粹''的Lisp--即没有副作用的Lisp. 副作用是指作为表达式求值的后果改变了外部世界的状态. 当我们对一个纯粹的Lisp 表达式,例如(+ 1 2)求值,没有出现副作用;它仅返回一个值. 但当我们调用 format,它不仅返回值,还打印了一些东西. 这是一种副作用. 如果我们要写没有副作用的代码,那么定义有多个表达式的函数体就没有什么意义. 最后一个表达式的值作为函数的返回值被返回了,但前面的表达式的值都被扔掉了. 如果这些表达式没有副作用,你就不知道为什么Lisp要费劲去计算它们.
变量
let是Common Lisp里最常用的操作符之一,它让你引入新的局部变量:
> (let ((x 1) (y 2))
(+ x y))
3

一个let表达式有两部分. 第一部分是一列创造新变量的指令,每个形如(变量 表达式). 每个变量会被赋予相应的表达式的值. 在上例中,我们创造了两个变量x 和y,它们分别被赋予初值1和2. 这些变量只在let的体内有效. 变量和值的列表的后面是一组表达式,它们将被依次求值. 在此例中,只有一个表达式:对+的调用. 最后一个表达式的值作为let的值被返回. 下面是一个使用let 的更具选择性的askem的版本:
(defun ask-number ()
(format t "Please enter a number. ")
(let ((val (read)))
(if (numberp val)
val
(ask-number))))

此函数造了变量val来存放read返回的对象. 因为它有此对象的名称,它可以在作出是否要返回对象之前察看一下你的输入值. 你可能已经猜到,numberp是测试它的自变量是否是数字的断言. 如果用户输入的不是数字,ask-number调用它自己. 结果产生了一个坚持要得到一个数的函数:
> (ask-number)
Please enter a number. a
Please enter a number. (ho hum)
Please enter a number. 52
52

象目前我们看到的变量都叫做局部变量. 它们只在特定的环境中是有效的. 另外有一类叫做全局变量的变量,它们在任何地方都是可见的.3 通过传给defparameter一个符号和一个值,你可以构造全局变量:
> (defparameter *glob* 99)
*GLOB*

这样的变量可以在任何地方存取,除非在一个表达式中,定义了一个相同名字的局部变量. 为了避免这种情况的出现,习惯上全局变量的名字以星号开始和结束. 我们刚才定义的变量可读作``星-glob-星''. 你还可以用defconstant定义全局常数:
(defconstant limit (+ *glob* 1))

你不需要给常数起一个与众不同的名字,因为如果使用相同的名字作为变量,就会出错. 如果你想知道某个符号是否是全局变量或常数的名字,请用boundp:
> (boundp '*glob*)
T

赋值
Common Lisp中最普通的赋值操作符是setf. 我们可以用它对全局或局部变量进行赋值:
> (setf *glob* 98)
98
> (let ((n 10))
(setf n 2)
n)
2

如果第一个自变量不是局部变量的名字,它被认为是全局变量:
> (setf x (list 'a 'b 'c))
(A B C)

即你可以通过赋值隐含地新建全局变量.不过在源文件中明确地使用 defparameter
是较好的风格. 你能做的远不止给变量赋值. setf的第一个自变量不但可以是变量名,还可以是表达式. 在这种情况下,第二个自变量的值被插入到第一个所涉及到的位置:
> (setf (car x) 'n)
N
> x
(N B C)

setf的第一个自变量几乎可以是任何涉及特定位置的表达式. 所有这样的操作符在附录D中都被标记为``settable''. 你可以给setf偶数个自变量. 形如
(setf a b
c d
e f)

的表达式相当于连续三个单独的setf调用:
(setf a b)
(setf c d)
(setf e f)

函数化编程法
函数化编程法的意思是编写通过返回值来工作的程序,而不是修改什么东西. 它是 Lisp中占支配地位的范例. 大多数Lisp内置函数被调用是为了得到它们的返回值, 而不是它们的副作用. 例如函数remove,它接受一个对象和一个表,返回一个排除了那个对象的新表:
> (setf lst '(c a r a t))
(C A R A T)
> (remove 'a lst)
(C R T)

为什么不说remove从表中删除一个对象? 因为这不是它所做的事情. 原来的表没有被改变:
> lst
(C A R A T)

那么如果你真想从表中删掉一些元素怎么办? 在Lisp中,你通常这样做类似的事情:把表传给某个函数,然后用setf来处理返回值. 为了把所有的a从表x中删掉, 我们这样做:
(setf x (remove 'a x))

函数化编程法本质上意味着避免使用诸如setf的函数. 乍一看连想象这种可能性都很因难,别说试着去做了. 怎么能仅凭返回值就能构造程序? 完全不利用副作用是有困难的. 但随着学习的深入,你会惊讶地发现真正需要副作用的地方极少. 你使用副作用越少,你也就越进步. 函数化编程最重要的优点之一是它允许交互式测试. 在纯粹的函数化代码中,当你写函数的时候就可以测试它们. 如果它返回期望的值,你可以肯定它是正确的. 这些额外的信心,聚集在一起会产生巨大的影响. 当你在程序中修改了任何地方, 你会得到即时的转变. 而这种即时的转变会带来一种全新的编程风格. 就象电话与信件相比,赋予我们新的通讯方式.
迭代
当我们想做一些重复的事情时,用迭代比用递归更自然些. 典型的例子是用迭代生成某种表格. 函数
(defun show-squares (start end)
(do ((i start (+ i 1)))
((> i end) 'done)
(format t "~A ~A~%" i (* i i))))

打印从start到end之间的整数的平方:
> (show-squares 2 5)
2 4
3 9
4 16
5 25
DONE

do宏是Common Lisp中最基本的迭代操作符. 就象let,do也会产生变量,它的第一个自变量是关于变量规格的表. 表中的每个元素具有如下形式:
(variable initial update)

其中variable是符号,而initial和update是表达式. 一开始每个变量会被赋予相应的initial的值;在迭代的时候它会被赋予相应的update的值. show-squares中的do仅产生了一个变量i. 第一次迭代的时候,i被赋予start的值,在以后的迭代中它的值会每次增加1. do的第二个自变量是包含一个或多个表达式的表. 第一个表达式用来测试迭代是否应该停止. 在上例中,测试是(> i end). 其余的表达式会在迭代停止后依次计算,并且最后一个的值作为do的返回值. 因此show-squares总是会返回done. 余下的自变量组成了循环体. 它们在每次迭代的时候依次被求值. 在每次迭代的时候变量先被更新,然后终止测试被计算,再是(如果测试失败)循环体被计算. 作为对比,这是递归版本的show-squares:
(defun show-squares (i end)
(if (> i end)
'done
(progn
(format t "~A ~A~%" i (* i i))
(show-squares (+ i 1) end))))

此函数中的唯一新面孔是progn. 它接受任意数量的表达式,对它们依次求值,然后返回最后一个的值. 对一些特殊情况Common Lisp有更简单的迭代操作符. 比如,为了遍历表的所有元素,你更可能用dolist. 这个函数返回表的长度:
(defun our-length (lst)
(let ((len 0))
(dolist (obj lst)
(setf len (+ len 1)))
len))

此处dolist接受形如(variable expression)的自变量,然后是表达式块. variable相继与expression返回的表中元素绑定,表达式块被计算. 因此上面的循环在意思是,对lst中的每个obj,len增加1. 此函数的一个显然的递归版本是:
(defun our-length (lst)
(if (null lst)
0
(+ (our-length (cdr lst)) 1)))

即,如果表为空,它的长度就是0;否则它的长度是它的cdr的长度加上1. 此版本清楚一些,但因为它不是尾递归的(见13.2节),它的效率不那么高.
函数作为对象
函数在Lisp中就象符号,字符串和表一样,是常规的对象. 如果我们给function一个函数的名字,它会返回相关的对象. 就象quote,function是特殊操作符,因此我们不必引用自变量:
> (function +)
#

这个模样很奇怪的返回值是函数在典型Common Lisp实现中可能的显示方式. 到目前为止我们涉及到的对象具有这样的特点:Lisp显示它们与我们输入的模样是一致的. 此惯例不适合函数. 一个象+这样的内置函数在内部可能是一段机器码. Common Lisp的实现可以选择任何它喜欢的外部表示方式. 就象我们用'作为quote的简记法,我们可以用#'作为function的简写:
> #'+
#

此简记法叫做sharp-quote. 就象其它的对象,函数可以作为自变量传递. 一个接受函数作为自变量的是 apply. 它接受一个函数和一列自变量,并返回那个函数应用这些自变量后的结果:
> (apply #'+ '(1 2 3))
6
> (+ 1 2 3)
6

它能接受任意数目的自变量,只要最后一个是表:
> (apply #'+ 1 2 '(3 4 5))
15

函数funcall能做同样的事情,不过它不需要把自变量放在表中:
> (funcall #'+ 1 2 3)
6

宏defun创造一个函数并给它一个名字. 但函数并不是必须需要名字,因此我们也不需要用defun来定义它们. 就象其它Lisp对象一样,我们可以直接引用函数. 为了直接引用一个整数,我们用一列数字;为了直接引用函数,我们用所谓的 lambda表达式. 一个lambda表达式是包含以下元素的表:符号lambda,一列参数, 然后是零个或多个表达式组成的函数体. 这个lambda表达式代表接受两个数并返回它们之和的函数:
(lambda (x y)
(+ x y))

(x y)是参数表,跟在它后面的是函数体. 可以认为lambda表达式是函数的名称. 就象普通的函数名,lambda表达式可以是函数调用的第一个元素:
> ((lambda (x) (+ x 100)) 1)
101

而通过在lamda表达式之前附加#',我们得到了相应的函数:
> (funcall #'(lambda (x) (+ x 100))
1)
101

此种表达法让我们使用匿名函数.

lambda是什么? lambda表达式中的lambda不是操作符. 它仅是个符号.4 它在早期的Lisp方言里有一种作用:函 数的内部形态是表,因此区别函数和普通表的唯一办法是查看第一个元素是否是 符号lambda. 在Common Lisp中你能把函数表示为表,但它们在内部被表示成独特的函数对象. 因此lambda不再是必需的. 如果要求把函数
(lambda (x) (+ x 100))

表示成
((x) (+ x 100))

也没有什么矛盾,但Lisp程序员已经习惯了函数以符号lambda开始,因此Common Lisp保留了此传统.
类型
Lisp用非同寻常的灵活手段来处理类型. 在许多语言中,变量是有类型的,你得指定变量的类型才能使用它. 在Common Lisp中,值具有类型,而不是变量. 你可以假想每个对象都贴了指明它的类型的标签. 这种方法叫做显示类型. 你不需要去声明变量的类型,因为变量可以装任何类型的对象. 虽然类型声明不是必需的,为了效率的缘故你可能会用到它们. 类型声明在13.3 节中讨论. Common Lisp的内置类型构成了一个类型的层次结构. 一个对象通常具有多种类型. 比如,数27是类型fixnum,integer,rational,real,number,atom,和t,以一般性的增长为序. (Numeric类型在第9章中讨论)类型t是所有类型的超集,因此任何对象都是类型t. 函数typep接受一个对象和一个类型说明符,如果对象是那种类型就返回真:
> (typep 27 'integer)
T

当我们碰到各种内置类型时,我们会介绍它们.
展望
本章仅蜻蜓点水般地介绍了一下Lisp. 然而一种非同寻常的语言的形象已经浮现出来了. 首先,该语言有单一的语法来表达所有的程序结构. 此语法基于一种Lisp 的对象--表. 函数,作为独特的Lisp对象,可以表示为表. 而且Lisp本身就是 Lisp程序,几乎全是由与你自己定义的函数没有任何区别的函数组成的. 如果你还不完全清楚所有这些概念之间的关系,请不必担心. Lisp引入了这么多新颖的概念,你得花时间去熟悉它们. 不过至少得说明一件事: 令人吃惊的优雅思想蕴藏其中. Richard Gabriel曾半开玩笑地说C是适合写Unix的语言.5 我们也可以说Lisp是编写Lisp的语言. 但这是两种不同的陈述. 一种可以用自己来编写的语言是和一种擅长编写某些特定类型的应用的语言完全不同的. 它开启了新的编程方法:你不但在语言中编程,你还可以改进语言以适合你程序的需要. 如果你想理解Lisp编程的本质,这个思想是个很好的起点.

总结
Lisp是交互式语言. 如果你在顶层输入表达式,Lisp会打印它的值.
Lisp程序由表达式组成. 表达式可以是一个原子,或是一个表, 表的第一个元素是操作符,后面跟着零个或多个自变量. 前缀表达式意味着操作符可接受任意多个自变量.
Common Lisp函数调用的求值规则:从左至右对自变量求值,然后把这些值传给由操作符表示的函数. quote有它自己的求值规则:它原封不动地返回自变量.
除了通常的数据类型,Lisp还有符号和表. 由于Lisp程序由表组成,很容易编写能写程序的程序.
三个基本的表处理函数是cons:它创造一个表;car:它返回表的头一个元素; cdr:它返回第一个元素之后的所有东西.
在Common Lisp里, t表示真,nil表示伪. 在逻辑上下文中,除了nil之外的任何东西都算作真. 基本的条件语句是if. and和or操作符就象条件语句.
Lisp主要是由函数构成的. 你可用defun来定义新的函数.
调用自己的函数是递归的. 递归函数应该被认为是一个过程而不是机器.
括号不是个问题,因为程序员利用缩进来读写Lisp.
基本的i/o函数是read:它包含了完整的Lisp语法分析器,和format:它基于模板产生输出.
你可以用let创造新的局部变量,用defparameter创造新的全局变量.
赋值操作符是setf. 它的第一个自变量可以是表达式.
函数化编程法--它意味着避免副作用--是Lisp中占支配地位的范例.
基本的循环操作符是do.
函数是常规的Lisp对象. 它们可以作为自变量被传递,可以表示成lambda 表达式.
值有类型,而变量没有类型

练习
解释以下表达式求值后的结果:
a. (+ (- 5 1) (+ 3 7))
b. (list 1 (+ 2 3))
给出3种不同的能返回(a b c)的cons表达式
用car和cdr定义一个函数,它返回表的第四个元素.
定义一个函数,它接受两个自变量,返回两个中较大的一个.
这些函数做了什么?
a. (defun enigma (x)
(and (not (null x))
(or (null (car x))
(enigma (cdr x)))))

b. (defun mystery (x y)
(if (null y)
nil
(if (eql (car y) x)
0
(let ((z (mystery x (cdr y))))
(and z (+ z 1))))))

在下面的表达式中,x处应该是什么可得出结果?
a. > (car (x (cdr '(a (b c) d))))
B

b. > (x 13 (/ 1 0))
13

c. > (x #'list 1 nil)
(1)

只用本章介绍的操作符,定义一个函数,它接受一个表作为自变量,并返回t 如果表的元素中至少有一个类型是表.
给出函数的迭代和递归版本:它
a. 接受一个正整数,并打印这么多数目的点.

b. 接受一个表,返回符号a在表中出现的次数.

一位朋友想写一个函数,它返回表中所有非nil元素之和. 他写了此函数的两个版本, 但没有一个能正确工作. 请指出错误在哪里,并给出正确的版本:
a. (defun summit (lst)
(remove nil lst)
(apply #'+ lst))

b. (defun summit (lst)
(let ((x (car lst)))
(if (null x)
(summit (cdr lst))
(+ x (summit (cdr lst))))))

About this document ...
This document was generated using the LaTeX2HTML translator Version 2K.1beta (1.48)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split=0 acl2.tex

The translation was initiated by Dai Yuwen on 2003-07-29



--------------------------------------------------------------------------------

Footnotes
... 基本的提取表中元素的函数是car和cdr.1
car和cdr的名字来源于表在第一个Lisp实现中的内部表示. car表示``contents of the address part of the registe''而cdr表示``contents of the decrement part of the register.''
... 不存在了.2
理解递归有困难的读者可以参考以下文献中的任何一种: Touretzky, David S. Common Lisp: A Gentle Introduction to Symbolic Computation. Benjamin/Cummings, Redwood City (CA), 1990, Chapter 8. Friedman, Daniel P., and Matthias Felleisen. The Little Lisper. MIT Press, Cambridge, 1987.
... 有一类叫做全局变量的变量,它们在任何地方都是可见的.3
真正的区别在于词法变量和特殊变量的不同,不过我们得到第六章才会考虑它.
... 它仅是个符号.4
在Ansi Common Lisp中还有一个lambda宏,它能让你把#'(lambda (x) x)写成(lambda (x) x). 由于使用这个宏模糊了lambda表达式和符号化的函数名(其中你得作用#') 的对称性,它最多不过具有美观的外表.
... Gabriel曾半开玩笑地说C是适合写Unix的语言.5
Gabriel, Richard P. Lisp: Good News, Bad News, How to Win Big. AI Expert, June 1991, p. 34.

Lisp之根源

Lisp之根源
保罗格雷厄姆


约翰麦卡锡于1960年发表了一篇非凡的论文,他在这篇论文中对编程的贡献有如欧几里德对几何的贡献.1 他向我们展示了,在只给定几个简单的操作符和一个表示函数的记号的基础上, 如何构造出一个完整的编程语言. 麦卡锡称这种语言为Lisp, 意为List Processing, 因为他的主要思想之一是用一种简单的数据结构表(list)来代表代码和数据.

值得注意的是,麦卡锡所作的发现,不仅是计算机史上划时代的大事, 而且是一种在我们这个时代编程越来越趋向的模式.我认为目前为止只有两种真正干净利落, 始终如一的编程模式:C语言模式和Lisp语言模式.此二者就象两座高地, 在它们中间是尤如沼泽的低地.随着计算机变得越来越强大,新开发的语言一直在坚定地趋向于Lisp模式. 二十年来,开发新编程语言的一个流行的秘决是,取C语言的计算模式,逐渐地往上加Lisp模式的特性,例如运行时类型和无用单元收集.

在这篇文章中我尽可能用最简单的术语来解释约翰麦卡锡所做的发现. 关键是我们不仅要学习某个人四十年前得出的有趣理论结果, 而且展示编程语言的发展方向. Lisp的不同寻常之处--也就是它优质的定义--是它能够自己来编写自己. 为了理解约翰麦卡锡所表述的这个特点,我们将追溯他的步伐,并将他的数学标记转换成能够运行的Common Lisp代码.


七个原始操作符
开始我们先定义表达式.表达式或是一个原子(atom),它是一个字母序列(如 foo),或是一个由零个或多个表达式组成的表(list), 表达式之间用空格分开, 放入一对括号中. 以下是一些表达式:


foo
()
(foo)
(foo bar)
(a b (c) d)

最后一个表达式是由四个元素组成的表, 第三个元素本身是由一个元素组成的表.
在算术中表达式 1 + 1 得出值2. 正确的Lisp表达式也有值. 如果表达式e得出值v,我们说e返回v. 下一步我们将定义几种表达式以及它们的返回值.

如果一个表达式是表,我们称第一个元素为操作符,其余的元素为自变量.我们将定义七个原始(从公理的意义上说)操作符: quote,atom,eq,car,cdr,cons,和 cond.


(quote x) 返回x.为了可读性我们把(quote x)简记 为'x.

> (quote a)
a
> 'a
a
> (quote (a b c))
(a b c)


(atom x)返回原子t如果x的值是一个原子或是空表,否则返回(). 在Lisp中我们按惯例用原子t表示真, 而用空表表示假.

> (atom 'a)
t
> (atom '(a b c))
()
> (atom '())
t

既然有了一个自变量需要求值的操作符, 我们可以看一下quote的作用. 通过引用(quote)一个表,我们避免它被求值. 一个未被引用的表作为自变量传给象 atom这样的操作符将被视为代码:


> (atom (atom 'a))
t

反之一个被引用的表仅被视为表, 在此例中就是有两个元素的表:


> (atom '(atom 'a))
()

这与我们在英语中使用引号的方式一致. Cambridge(剑桥)是一个位于麻萨诸塞州有90000人口的城镇. 而``Cambridge''是一个由9个字母组成的单词.

引用看上去可能有点奇怪因为极少有其它语言有类似的概念. 它和Lisp最与众不同的特征紧密联系:代码和数据由相同的数据结构构成, 而我们用quote操作符来区分它们.


(eq x y)返回t如果x和y的值是同一个原子或都是空表, 否则返回().

> (eq 'a 'a)
t
> (eq 'a 'b)
()
> (eq '() '())
t


(car x)期望x的值是一个表并且返回x的第一个元素.

> (car '(a b c))
a


(cdr x)期望x的值是一个表并且返回x的第一个元素之后的所有元素.
> (cdr '(a b c))
(b c)


(cons x y)期望y的值是一个表并且返回一个新表,它的第一个元素是x的值, 后面跟着y的值的各个元素.

> (cons 'a '(b c))
(a b c)
> (cons 'a (cons 'b (cons 'c '())))
(a b c)
> (car (cons 'a '(b c)))
a
> (cdr (cons 'a '(b c)))
(b c)

(cond (...) ...(...)) 的求值规则如下. p表达式依次求值直到有一个返回t. 如果能找到这样的p表达式,相应的e表达式的值作为整个cond表达式的返回值.

> (cond ((eq 'a 'b) 'first)
((atom 'a) 'second))
second

当表达式以七个原始操作符中的五个开头时,它的自变量总是要求值的.2 我们称这样 的操作符为函数.


函数的表示
接着我们定义一个记号来描述函数.函数表示为(lambda (...) e),其中 ...是原子(叫做参数),e是表达式. 如果表达式的第一个元素形式如上
((lambda (...) e) ...)

则称为函数调用.它的值计算如下.每一个表达式先求值,然后e再求值.在e的求值过程中,每个出现在e中的的值是相应的在最近一次的函数调用中的值.


> ((lambda (x) (cons x '(b))) 'a)
(a b)
> ((lambda (x y) (cons x (cdr y)))
'z
'(a b c))
(z b c)

如果一个表达式的第一个元素f是原子且f不是原始操作符
(f ...)

并且f的值是一个函数(lambda (...)),则以上表达式的值就是

((lambda (...) e) ...)

的值. 换句话说,参数在表达式中不但可以作为自变量也可以作为操作符使用:


> ((lambda (f) (f '(b c)))
'(lambda (x) (cons 'a x)))
(a b c)

有另外一个函数记号使得函数能提及它本身,这样我们就能方便地定义递归函数.3 记号

(label f (lambda (...) e))

表示一个象(lambda (...) e)那样的函数,加上这样的特性: 任何出现在e中的f将求值为此label表达式, 就好象f是此函数的参数.

假设我们要定义函数(subst x y z), 它取表达式x,原子y和表z做参数,返回一个象z那样的表, 不过z中出现的y(在任何嵌套层次上)被x代替.

> (subst 'm 'b '(a b (a b c) d))
(a m (a m c) d)

我们可以这样表示此函数
(label subst (lambda (x y z)
(cond ((atom z)
(cond ((eq z y) x)
('t z)))
('t (cons (subst x y (car z))
(subst x y (cdr z)))))))

我们简记f=(label f (lambda (...) e))为
(defun f (...) e)

于是

(defun subst (x y z)
(cond ((atom z)
(cond ((eq z y) x)
('t z)))
('t (cons (subst x y (car z))
(subst x y (cdr z))))))

偶然地我们在这儿看到如何写cond表达式的缺省子句. 第一个元素是't的子句总是会成功的. 于是
(cond (x y) ('t z))

等同于我们在某些语言中写的

if x then y else z


一些函数
既然我们有了表示函数的方法,我们根据七个原始操作符来定义一些新的函数. 为了方便我们引进一些常见模式的简记法. 我们用cxr,其中x是a或d的序列,来简记相应的car和cdr的组合. 比如(cadr e)是(car (cdr e))的简记,它返回e的第二个元素.

> (cadr '((a b) (c d) e))
(c d)
> (caddr '((a b) (c d) e))
e
> (cdar '((a b) (c d) e))
(b)

我们还用(list ...)表示(cons ...(cons '()) ...).
> (cons 'a (cons 'b (cons 'c '())))
(a b c)
> (list 'a 'b 'c)
(a b c)

现在我们定义一些新函数. 我在函数名后面加了点,以区别函数和定义它们的原始函数,也避免与现存的common Lisp的函数冲突.


(null. x)测试它的自变量是否是空表.

(defun null. (x)
(eq x '()))

> (null. 'a)
()
> (null. '())
t


(and. x y)返回t如果它的两个自变量都是t, 否则返回().

(defun and. (x y)
(cond (x (cond (y 't) ('t '())))
('t '())))

> (and. (atom 'a) (eq 'a 'a))
t
> (and. (atom 'a) (eq 'a 'b))
()


(not. x)返回t如果它的自变量返回(),返回()如果它的自变量返回t.

(defun not. (x)
(cond (x '())
('t 't)))

> (not. (eq 'a 'a))
()
> (not. (eq 'a 'b))
t


(append. x y)取两个表并返回它们的连结.

(defun append. (x y)
(cond ((null. x) y)
('t (cons (car x) (append. (cdr x) y)))))

> (append. '(a b) '(c d))
(a b c d)
> (append. '() '(c d))
(c d)


(pair. x y)取两个相同长度的表,返回一个由双元素表构成的表,双元素表是相应位置的x,y的元素对.

(defun pair. (x y)
(cond ((and. (null. x) (null. y)) '())
((and. (not. (atom x)) (not. (atom y)))
(cons (list (car x) (car y))
(pair. (cdr) (cdr y))))))

> (pair. '(x y z) '(a b c))
((x a) (y b) (z c))


(assoc. x y)取原子x和形如pair.函数所返回的表y,返回y中第一个符合如下条件的表的第二个元素:它的第一个元素是x.

(defun assoc. (x y)
(cond ((eq (caar y) x) (cadar y))
('t (assoc. x (cdr y)))))

> (assoc. 'x '((x a) (y b)))
a
> (assoc. 'x '((x new) (x a) (y b)))
new


一个惊喜
因此我们能够定义函数来连接表,替换表达式等等.也许算是一个优美的表示法, 那下一步呢? 现在惊喜来了. 我们可以写一个函数作为我们语言的解释器:此函数取任意Lisp表达式作自变量并返回它的值. 如下所示:

(defun eval. (e a)
(cond
((atom e) (assoc. e a))
((atom (car e))
(cond
((eq (car e) 'quote) (cadr e))
((eq (car e) 'atom) (atom (eval. (cadr e) a)))
((eq (car e) 'eq) (eq (eval. (cadr e) a)
(eval. (caddr e) a)))
((eq (car e) 'car) (car (eval. (cadr e) a)))
((eq (car e) 'cdr) (cdr (eval. (cadr e) a)))
((eq (car e) 'cons) (cons (eval. (cadr e) a)
(eval. (caddr e) a)))
((eq (car e) 'cond) (evcon. (cdr e) a))
('t (eval. (cons (assoc. (car e) a)
(cdr e))
a))))
((eq (caar e) 'label)
(eval. (cons (caddar e) (cdr e))
(cons (list (cadar e) (car e)) a)))
((eq (caar e) 'lambda)
(eval. (caddar e)
(append. (pair. (cadar e) (evlis. (cdr e) a))
a)))))

(defun evcon. (c a)
(cond ((eval. (caar c) a)
(eval. (cadar c) a))
('t (evcon. (cdr c) a))))

(defun evlis. (m a)
(cond ((null. m) '())
('t (cons (eval. (car m) a)
(evlis. (cdr m) a)))))

eval.的定义比我们以前看到的都要长. 让我们考虑它的每一部分是如何工作的.
eval.有两个自变量: e是要求值的表达式, a是由一些赋给原子的值构成的表,这些值有点象函数调用中的参数. 这个形如pair.的返回值的表叫做环境. 正是为了构造和搜索这种表我们才写了pair.和assoc..

eval.的骨架是一个有四个子句的cond表达式. 如何对表达式求值取决于它的类型. 第一个子句处理原子. 如果e是原子, 我们在环境中寻找它的值:


> (eval. 'x '((x a) (y b)))
a

第二个子句是另一个cond, 它处理形如(a ...)的表达式, 其中a是原子. 这包括所有的原始操作符, 每个对应一条子句.


> (eval. '(eq 'a 'a) '())
t
> (eval. '(cons x '(b c))
'((x a) (y b)))
(a b c)

这几个子句(除了quote)都调用eval.来寻找自变量的值.
最后两个子句更复杂些. 为了求cond表达式的值我们调用了一个叫 evcon.的辅助函数. 它递归地对cond子句进行求值,寻找第一个元素返回t的子句. 如果找到了这样的子句, 它返回此子句的第二个元素.


> (eval. '(cond ((atom x) 'atom)
('t 'list))
'((x '(a b))))
list

第二个子句的最后部分处理函数调用. 它把原子替换为它的值(应该是lambda 或label表达式)然后对所得结果表达式求值. 于是


(eval. '(f '(b c))
'((f (lambda (x) (cons 'a x)))))

变为
(eval. '((lambda (x) (cons 'a x)) '(b c))
'((f (lambda (x) (cons 'a x)))))

它返回(a b c).
eval.的最后cond两个子句处理第一个元素是lambda或label的函数调用.为了对label 表达式求值, 先把函数名和函数本身压入环境, 然后调用eval.对一个内部有 lambda的表达式求值. 即:


(eval. '((label firstatom (lambda (x)
(cond ((atom x) x)
('t (firstatom (car x))))))
y)
'((y ((a b) (c d)))))

变为
(eval. '((lambda (x)
(cond ((atom x) x)
('t (firstatom (car x)))))
y)
'((firstatom
(label firstatom (lambda (x)
(cond ((atom x) x)
('t (firstatom (car x)))))))
(y ((a b) (c d)))))

最终返回a.
最后,对形如((lambda (...) e) ...)的表达式求值,先调用evlis.来求得自变量(...)对应的值(...),把()...()添加到环境里, 然后对e求值. 于是


(eval. '((lambda (x y) (cons x (cdr y)))
'a
'(b c d))
'())

变为
(eval. '(cons x (cdr y))
'((x a) (y (b c d))))

最终返回(a c d).

后果
既然理解了eval是如何工作的, 让我们回过头考虑一下这意味着什么. 我们在这儿得到了一个非常优美的计算模型. 仅用quote,atom,eq,car,cdr,cons,和cond, 我们定义了函数eval.,它事实上实现了我们的语言,用它可以定义任何我们想要的额外的函数.

当然早已有了各种计算模型--最著名的是图灵机. 但是图灵机程序难以读懂. 如果你要一种描述算法的语言, 你可能需要更抽象的, 而这就是约翰麦卡锡定义 Lisp的目标之一.

约翰麦卡锡于1960年定义的语言还缺不少东西. 它没有副作用, 没有连续执行 (它得和副作用在一起才有用), 没有实际可用的数,4 没有动态可视域. 但这些限制可以令人惊讶地用极少的额外代码来补救. Steele和Sussman在一篇叫做``解释器的艺术''的著名论文中描述了如何做到这点.5

如果你理解了约翰麦卡锡的eval, 那你就不仅仅是理解了程序语言历史中的一个阶段. 这些思想至今仍是Lisp的语义核心. 所以从某种意义上, 学习约翰麦卡锡的原著向我们展示了Lisp究竟是什么. 与其说Lisp是麦卡锡的设计,不如说是他的发现. 它不是生来就是一门用于人工智能, 快速原型开发或同等层次任务的语言. 它是你试图公理化计算的结果(之一).

随着时间的推移, 中级语言, 即被中间层程序员使用的语言, 正一致地向Lisp靠近. 因此通过理解eval你正在明白将来的主流计算模式会是什么样.


注释
把约翰麦卡锡的记号翻译为代码的过程中我尽可能地少做改动. 我有过让代码更容易阅读的念头, 但是我还是想保持原汁原味.
在约翰麦卡锡的论文中,假用f来表示, 而不是空表. 我用空表表示假以使例子能在Common Lisp中运行. (fixme)

我略过了构造dotted pairs, 因为你不需要它来理解eval. 我也没有提apply, 虽然是apply(它的早期形式, 主要作用是引用自变量), 被约翰麦卡锡在1960年称为普遍函数, eval只是不过是被apply调用的子程序来完成所有的工作.

我定义了list和cxr等作为简记法因为麦卡锡就是这么做的. 实际上 cxr等可以被定义为普通的函数. List也可以这样, 如果我们修改eval, 这很容易做到, 让函数可以接受任意数目的自变量.

麦卡锡的论文中只有五个原始操作符. 他使用了cond和quote,但可能把它们作为他的元语言的一部分. 同样他也没有定义逻辑操作符and和not, 这不是个问题, 因为它们可以被定义成合适的函数.

在eval.的定义中我们调用了其它函数如pair.和assoc.,但任何我们用原始操作符定义的函数调用都可以用eval.来代替. 即

(assoc. (car e) a)

能写成

(eval. '((label assoc.
(lambda (x y)
(cond ((eq (caar y) x) (cadar y))
('t (assoc. x (cdr y))))))
(car e)
a)
(cons (list 'e e) (cons (list 'a a) a)))

麦卡锡的eval有一个错误. 第16行是(相当于)(evlis. (cdr e) a)而不是(cdr e), 这使得自变量在一个有名函数的调用中被求值两次. 这显示当论文发表的时候, eval的这种描述还没有用IBM 704机器语言实现. 它还证明了如果不去运行程序, 要保证不管多短的程序的正确性是多么困难.

我还在麦卡锡的论文中碰到一个问题. 在定义了eval之后, 他继续给出了一些更高级的函数--接受其它函数作为自变量的函数. 他定义了maplist:


(label maplist
(lambda (x f)
(cond ((null x) '())
('t (cons (f x) (maplist (cdr x) f))))))

然后用它写了一个做微分的简单函数diff. 但是diff传给maplist一个用x做参数的函数, 对它的引用被maplist中的参数x所捕获.6
这是关于动态可视域危险性的雄辩证据, 即使是最早的更高级函数的例子也因为它而出错. 可能麦卡锡在1960年还没有充分意识到动态可视域的含意. 动态可视域令人惊异地在Lisp实现中存在了相当长的时间--直到Sussman和Steele于 1975年开发了Scheme. 词法可视域没使eval的定义复杂多少, 却使编译器更难写了.


About this document ...
Lisp之根源
This document was generated using the LaTeX2HTML translator Version 2K.1beta (1.48)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split=0 roots_of_lisp.tex

The translation was initiated by Dai Yuwen on 2003-10-24



--------------------------------------------------------------------------------

Footnotes
... 欧几里德对几何的贡献.1
``Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part1.'' Communication of the ACM 3:4, April 1960, pp. 184-195.
...当表达式以七个原始操作符中的五个开头时,它的自变量总是要求值的.2
以另外两个操作符quote和cond开头的表达式以不同的方式求值. 当 quote表达式求值时, 它的自变量不被求值,而是作为整个表达式的值返回. 在 一个正确的cond表达式中, 只有L形路径上的子表达式会被求值.
... 数.3
逻辑上我们不需要为了这定义一个新的记号. 在现有的记号中用 一个叫做Y组合器的函数上的函数, 我们可以定义递归函数. 可能麦卡锡在写 这篇论文的时候还不知道Y组合器; 无论如何, label可读性更强.
... 没有实际可用的数,4
在麦卡锡的1960 年的Lisp中, 做算术是可能的, 比如用一个有n个原子的表表示数n.
... 的艺术''的著名论文中描述了如何做到这点.5
Guy Lewis Steele, Jr. and Gerald Jay Sussman, ``The Art of the Interpreter, or the Modularity Complex(Parts Zero,One,and Two),'' MIT AL Lab Memo 453, May 1978.
... 对它的引用被maplist中的参数x所捕获.6
当代的Lisp程序 员在这儿会用mapcar代替maplist. 这个例子解开了一个谜团: maplist为什 么会在Common Lisp中. 它是最早的映射函数, mapcar是后来增加的.