第一章 简介
Scheme是一种通用编程语言。它是一种高级语言,支持字符串、列表、向量这样的结构化数据,以及数字、字符这样的传统数据。虽然Scheme通常被用于符号运算,但得益于丰富的数据类型集和灵活的控制结构,它可以说是一种真正的通用语言。Scheme已被用来编写文本编辑器,优化编译器,操作系统,图形处理,专家系统,数值运算,金融分析,虚拟现实系统和几乎所有可以想到的程序类型。scheme非常简单,因为它只基于少数语法形式和语义概念,而且大多数实现都能交互,鼓励用户去尝试。但scheme也很难,想发挥其全部潜能,离不开钻研和实践。
在同一实现下,scheme程序可移植性很强,因为底层几乎完全被隐藏了。scheme也可以在不同实现间移植,这归功于一群语言设计者的共同努力,他们发表了一系列报告,称为Revised Reports on Scheme,简称RnRS。最新的第6版报告,即R6RS,强调要借助标准库和标准机制,定义新的可移植库和顶层程序。
尽管一些早期实现效率低下,但是许多基于编译器的新实现都很快,可以与低级语言相媲美。有时仍然存在的相对的低效率,那是因为运行时的检查,它们支持通用运算,能帮程序员检测、纠正各种常见的错误。在许多实现中,都可以禁用检查。
Scheme支持多种类型的数据,或者说对象 ,比如字符,字符串,符号,列表和向量,以及所有数字类型,包括复数、实数和任意精度有理数。
程序会根据需要,动态分配储存空间来存放对象,并保留空间,直到不再需要为止,然后使用垃圾回收器,定期回收无效对象的空间。简单的原始值,例如小整数,字符,布尔值和空表,通常表示为立即数,因此不会产生分配或回收的开销。
不论怎么表示,所有对象都是第一类对象,又称为头等公民。因为他们可以永久保留,所以可以作为参数自由传递,作为返回值形成新对象。这与许多语言形成鲜明对比,它们的复合数据——比如数组——是静态分配的,而且从不释放,在代码块的入口分配,在出口无条件释放,或者由程序员手动分配或释放。
Scheme是一种传值调用的语言,但是至少对于可变对象,值储存的是地址。但这些地址被隐藏起来了,程序员不需要知道这些,只需要知道的是,当一个对象被传递或者返回时,并没有复制对象,只是传递了地址。
Scheme的核心是一个很小的语法内核,是所有其他语法形式的基础。这些核心形式、派生的扩展语法形式以及一组原始过程共同构成了完整的Scheme语言。Scheme的编译器或者解释器可以很小,并且有潜力做到高效而可靠。许多拓展的语法形式和原始过程,都可以在Scheme本身中定义,这简化了实现,提高了可靠性。
Scheme程序和数据结构共享通用的表示形式。结果是,任何Scheme程序都可以自然地作为对象。例如,变量和关键字都用符号表示,结构化语法形式用列表表示。这些表示形式是Scheme语法扩展功能的基础,可以根据现有语法形式和过程,定义出新的语法形式。它还有助于用Scheme实现自身的解释器、编译器和其他程序转换工具,包括其它语言的程序转换工具。
Scheme的变量和关键字使用词法作用域,Scheme程序使用块结构。标识符可以导入到程序或者库中,也可以被局部绑定到给定代码块内部,比如库、程序或者过程体内部。局部绑定只在特定的代码块中可见。同名标识符如果出现在代码块外部,则指向不同的绑定,如果在外部没有绑定,那么外部的引用无效。代码块可以嵌套,并且内层的绑定可以屏蔽外层的同名绑定。一个绑定的作用域,是该绑定所在的代码块减去屏蔽该绑定的内层代码块。模块化程序用块结构和词法作用域构造,容易阅读,维护简单,而且可靠。用词法作用域的代码可以很高效,因为编译器可以在执行程序之前,确定所有绑定的作用域,解析出每个标识符引用的绑定。当然,这并不并不是说编译器能确定所有变量的值,因为除非执行程序、计算变量,它们在大多数情况下都是未知的。
在大多数语言中,过程的定义只是简单地关联过程名和代码块,代码块的局部变量就是过程的参数。在有些语言里,过程可以在另一个过程或代码块中定义,但只能在封闭的代码块被执行时才能调用。在另外一些语言,过程只能定义成全局的。对于Scheme来说,过程可以定义在另一个过程或者代码块中,在定义后可以随时调用,甚至在外层代码结束之后也没问题。为了支持词法作用域,Scheme的过程携带了词法上下文(环境)。
另外,Scheme的过程不是都有名字。它的过程是第一类数据对象,和字符串、数字一样,变量可以像绑定其它数据对象一样绑定过程。
和大多数语言一样,Scheme的过程也可以递归调用,也就是说,过程可以直接或间接的调用自己。很多算法用递归的方式来实现,会更优雅、更高效。有一种特殊的递归,叫做尾递归,它用来实现迭代——或者说循环——算法。尾递归发生在过程直接返回调用另一个过程的结果时,或者是过程直接或间接的尾调用自己时。Scheme的实现需要将尾调用实现为跳转,即goto,这样可以避免和递归相关的内存开销。
通过continuations,Scheme可以定义任意的控制结构。continunation是一种过程,在给程序中给定的位置声明程序剩下的部分。可以在程序执行的任意时刻捕获continuation。和其它过程一样,continuation也是第一类数据对象,可以在创建后随时调用。不管什么时候被调用,程序都会立即从捕获它的位置开始执行。通过continuaion,可以实现复杂的控制机制,包括回溯,多线程及协同程序。
在Scheme中,通过编写转换过程,确定每一个新的语法形式如何映射到现有的语法形式中,程序员可以定义新的语法形式,或者说语法拓展。这些转换过程可以用Scheme写,这得力于Scheme是方便的高级模式语言,可以自动执行语法检查,解析输入并重新构造输出。默认情况下,转换过程保持词法作用域,但是程序员可以控制所有标识符在转换后的作用域。语法扩展很有用,可以定义新的语言结构,用来模仿其它语言里的语法结构,从而达到内联代码的效率,甚至用Scheme模拟整个语言。大型的Scheme程序一般混合使用语法扩展和过程定义。
Scheme从Lisp语言演化而来,是Lisp的方言之一。Scheme从Lisp那里继承了许多东西:将值作为第一类对象的处理方式,一些重要的数据类型——包括符号和列表,将程序表示为对象等。词法作用域及块结构继承自Algol 60[21]。在Lisp的方言中,Scheme第一个支持词法作用域、块结构、第一类过程、尾递归、continuation,以及词法作用域限定的语法扩展。
Common Lisp[27]和Scheme是Lisp的现代方言,并且相互影响。Common Lisp像Scheme一样,不同于以前的Lisp语言,采用了词法作用域和第一类过程,不过它的语法扩展不遵守词法作用域。Common Lisp对过程的求值规则和其它对象的规则不同,它在一个单独的命名空间里维护过程变量,从而限制了将过程作为第一类对象。Common Lisp也不支持continuation和尾调用,但是它支持几种Scheme没有的控制结构。这两种语言比较相似,Common Lisp有更多专门的结构,而 Scheme包括更多通用模块,可以构建各种结构。
本章剩下的部分描述Scheme的语法、命名规约,以及贯穿与本书中的排版规则。
1.1 Scheme语法
Scheme程序包括关键字、变量、结构形式、常数(数字,字符,字符串,带引号的向量,带引号的列表,带引号的符号等)、空格和注释。
关键字、变量和符号统称标识符。标识符可以由字母,数字和某些特殊字符组成,包括? ! 。 + - * / < = > : $ % ^ & _ 〜 @
,以及其它Unicode字符。标识符不能以@符号开头,也不能以任何前面可以加数字的字符开头,例如,数字,加号,减号或者小数点。加号、减号、省略号和以->开头的是例外,它们都是有效的标识符。例如,hi,Hello,n,x,x3,x + 2,?$&* !!!
都是标识符。标识符由空格、注释、括号、方括号、字符串、引号、双引号、井号分割。分隔符或者其它任何Unicode字符都可以被转义为\xsv;
的形式,其中sv
是字符的十六进制标量值。
Scheme标识符没有长度限制;程序员需要多长就能写多长。然而,长标识符不能替代注释,频繁使用会使程序难以排版,不好阅读。一个好的原则是,当作用域较小时,用短标识符,而当作用于大时,用长标识符。
标识符可以大小写混用,并且区分大小写,也就是说,即使两个标识符仅在大小写上有所不同,它们也不一样。例如,abcde
,Abcde
,AbCdE
和ABCDE
都是不同的标识符。这跟以前的标准不同。
结构形式和列表常量括在括号里,例如(a b c)
和(*(-x 2)y)
。空列表被写为 ()
。 匹配的中括号[]
可以代替括号,通常用于某些标准语法形式的子表达式,可以提高可读性,整本书中的示例就是这样写的。向量的写法与列表类似,不同之处在于,向量之前带有#,例如#(这是符号的向量)
。字节向量被写为无符号字节值(在0到255之间的整数)的序列,并用#vu8(
和)
括起来,例如#vu8(3 250 45 73)
。
字符串用双引号引起来,例如"I am a string"
。字符以#\
开头,例如#\a
。在标识符中时,字符符常量和字符串常量的大小写很重要。数字可以写为整数,例如-123
,也可以写成分数,如1/2
,写成浮点数或者科学计数法,如1.3
或者1e23
,或者写成以直角坐标系或极坐标表示的复数,例如1.3-2.7i
,-1.2@73
。在数字的语法中,大小写并不重要。布尔值代表真和假,写成#t
和#f
。在Scheme的条件表达式中,#f
为假,#f
外的其他对象都为真,所以3,0,(),"false",nill
都为真。
在第6章的各个部分,以及从455页开始的Scheme的正式语法中,有每种常量语法的详细信息。
Scheme表达式可以跨行,不需要显式终止符。因为表达式之间的空白字符(空格和换行符)并不重要,应该缩进Scheme程序代码,展示代码结构,从而增加可读性。注释可以出现在Scheme程序的任何一行,在分号和行尾之间。解释特定表达式的注释通常放在同一缩进级别上,写在表达式的前一行。解释过程或一组过程的注释通常放在过程之前,不缩进。前面通常使用多个注释字符,例如;;; 下面的过程...
。
Scheme也支持两种其他形式的注释:块注释和数据注释 (Datum Comments)。块注释用#|
和|#
分割,并且可以嵌套。数据注释由前缀#;
和要输出的数据组成。数据注释通常用于注释单个定义或表达式。例如,(Three #;(not four) elements list)
。数据注释也可以嵌套,#;#;(a)(b)
把(a)
和(b)
都注释了。
某些Scheme值,例如过程和端口,没有标准的输出形式,因此在程序的输出语法中永远不会显示为常量。在显示返回这类值的过程的输出时,本书使用了符号#<description>
,例如#<procedure>
或#<port>
。
1.2 Scheme命名规定
Scheme的命名规定很有规律。下面是命名规定:
- 以问号结尾的谓词,代表返回正确或错误的过程,例如
eq?
,zero?
和string=?
。常用的数字比较符号=,<,>,<=,>=
是例外。 - 类型谓词,例如
pair?
,由类型名加上问号组成。 - 大多数字符、字符串和向量过程的名称,都以前缀
char-
,string-
和vector-
开头,例如string-append
。某些列表过程的名称以list-
开头,但大多数不是。 - 类型转换过程的名称写为
类型1->类型2
,例如vector->list
。 - 有副作用的过程和语法形式的名称以感叹号结尾。比如
set!
和vector-set!
。从技术上说,执行输入输出的过程也有副作用,但它们不遵守这条规则。
程序员应尽可能在自己的代码中遵守这些规定。
1.3 排版和符号规定
如果一个标准过程或者语法形式的唯一功能是产生一些副作用——比如set!
,那么它的返回值是未定义的。这意味着实现可以返回任何数值、任何Scheme对象,以作为过程或语法形式的值。不要指望不同实现返回相同的值,同一实现的不同版本也不用指望,甚至是过程或语法形式的两次使用中,值都可能不一样。某些Scheme系统会使用特殊对象来表示未指定的值。交互式Scheme系统通常会禁止输出此对象,因此返回未指定值的表达式的值无法输出。
虽然大多数标准过程只返回一个值,但使用5.8节中描述的机制,Scheme过程可以不返回值,或者返回一个、多个,甚至可变数量的值。如果某些标准表达式的子表达式之一能求多个值,比如调用返回多值的过程,则它们也可以求多个值。这种情况下,一般说表达式返回“多个值”,而不是简单地说返回子表达式的“值”。同样,将返回“调用参数所返回的值”的标准过程称为“返回过程参数返回的多个值”。
本书使用词语“必须”和“应该”来描述程序要求,例如在调用vector-ref
时,要求提供小于矢量长度的索引 。如果使用“必须”,则表示该要求由实现强制执行,即一定会引发异常,通常使用条件类型&assertion
。如果使用了“应该”一词,则可能会引发异常,也可能不会。如果未引发异常,则程序的行为是未定义的。
短语“语法错误”用于形容程序格式错误。语法冲突会在程序执行之前被检测到。一但出现, 会引发&syntax
类型的异常,并且程序不执行。
本书中使用的排版规定非常简单。所有Scheme对象均以打印字体
输出,就像要在键盘上输入一样。Scheme对象包括语法关键字,变量,常量对象,Scheme表达式和示例程序。斜体用于在语法形式的描述中突出语法变量,在过程的描述中突出参数。斜体还可以突出首次出现的专业词汇。一般而言,即使在句子开头,语法形式和过程的名称也不会大写,用斜体写的语法变量也一样。
在语法形式或过程的描述中,原型模式会显示语法形式或正确的参数个数。关键字或过程名称,包括括号,都以打印字体给出。剩下的语法或自变量以斜体显示,用的名称包含语法形式或过程所期望的表达式或自变量的类型。省略号用于表示子表达式或参数零次或多次出现。例如,(or expr ...)
描述了具有零个或多个子表达式的or
语法形式,而 (member obj list)
描述了member
过程,它需要两个参数——一个对象和一个列表。
如果语法形式的结构与其原型不匹配,则会发生语法错误。同样,如果传递给标准过程的参数数量与指定要接收的数量不匹配,则会引发条件类型为&assertion
的异常。如果标准过程接接收到的参数类型不符合要求,也会引发&assertion
异常。例如,vector-set!
的原型是:
(vector-set! vecotr n obj)
描述说,n必须是一个小于vector
长度的精确非负整数。这样,vector-set!
必须接收三个参数,第一个参数必须是向量,第二个参数必须是小于向量长度的精确非负整数,第三个参数可以是任何Scheme值。否则,将引发条件类型为&assertion
的异常。
在大多数情况下,所需的参数类型很明显,例如vector
,obj
或binary-input-port
。其他情况下,主要在数字例程的描述中,可以使用缩写,例如int
表示整数,exint
表示精确整数,fx
表示固定整数。在包含受影响条目的各节开头,对这些缩写进行了说明。