Scheme
历史
Lisp
Scheme起源于约翰·麦卡锡于1958年提出的Lisp语言。通过Lisp,麦卡锡证明了图灵完备的系统可以仅仅由几个简单的算子与函数定义功能组成。这一设计对Scheme的影响非常深刻。
麦卡锡最早提出两套语法:所谓“M表示式”是通常熟知的函数语法,如 car[cons[A,B]] 。在麦卡锡原本的设计中,用M表示式写成的程序将自动译至“S表示式”,如 (car (cons A B)) ,然而由于S表示式具备同像性(即程序与数据由相同的结构存储),实际应用中一般只使用S表示式。Scheme的语法即来自S表示式。这一特性使得在Scheme中实现自循环解释器变得非常简单。
起源
Scheme的灵感来自麻省理工学院的Carl Hewitt提出的一种叫做参与者模式的数学模型。Hewitt当时正在试图将参与者模式加入Planner语言,而受其影响的史提尔与萨斯曼决定在Maclisp中实现一个支持参与者模式的Lisp方言 。史提尔与萨斯曼两人很快发现参与者模式与λ演算非常类似,而所谓“参与者”不过是Peter J. Landin提出并由Joel Moses于1970年发表的闭包而已 。因此,两人很快意识到λ演算是在Lisp中实现变量范围的关键 。基于这一见解,两人很快开发出了一套精简的编程语言,并命名为“Schemer”(后因操作系统字数限制改为Scheme)。尽管Hewitt认为Scheme抽象性的不足是一个倒退,它简约的语法很快赢得广泛接受,并成为最具影响力的编程语言之一。在Scheme被广为接受后,史提尔与萨斯曼曾承认他们事实上没有刻意实现Scheme的简约性。两人认为简单而强大的λ演算最终使得Scheme得以实现极度的精简化 。
λ论文集
“λ论文集”是Scheme的发明人史提尔与萨斯曼所撰写的关于编程语言设计的一系列论文,最早作为麻省理工学院的内部备忘录发表。Scheme的功能很大一部分是由这些论文确立的。 通常认为λ论文集包括:
λ论文集
语言标准
目前Scheme由IEEE负责标准管理,并由一个专门的委员会发表的“算法语言Scheme报告,第N版”(Revised Report on the Algorithmic Language Scheme)进行标准化。现在的标准是1998年的R5RS ,并且R6RS 已经在2007年被批准了 。R6RS带来了很大的变动 ,导致Scheme社区对其意见不一,更有一些用户指责R6RS仅仅是在堆积华而不实的功能 。
Scheme的标准委员会目前正在讨论R7RS的事宜,并决定是否将Scheme分为两个独立的语言:一个为教育者提供精简的语法,另一个为专业人士提供强大的功能 。
语言特性
Scheme大体上是一个函数式编程语言,并支持其他编程范型。它的语法基于Lisp的S-表达式:函数调用在Scheme中表示为一个串列,其中第一个元素为函数名,而后的元素为函数的参数。一个Scheme程序是由嵌套串列表达而成,而串列又是Scheme的主要数据结构,这导致程序和数据在Scheme中基本上是等价的概念。因此每一个Scheme程序都可以被视为另一个Scheme程序的参数。Scheme程序可以轻易读入并分析其他Scheme程序,就是所谓的同像性。该特性被用于“代码即数据”的设计思维中,它极大提高了语言表达性和灵活性。但也有批评认为对该特性的不当使用将造成反效果,将数据当作代码需要借助eval在运行时求值,这不利于编译优化;另外代码可以被当作数据一样被修改(即所谓程序自修改)可能会造成程序逻辑混乱。
Scheme的列表与其他Lisp方言都是基于最基础的数据结构“有序对”(pair)。Scheme提供cons,car,与cdr方法 操作有序对与列表。
Scheme的变量都使用动态强类型系统,而函数被视为变量的一种,并可以作为参数提供给其他函数。换句话说,Scheme中的函数都是第一类对象。
极简主义
Scheme的简约性使它成为具备同级别功能的编程语言中最易于实现的语言 。Scheme的很多结构源于λ演算,例如let可以写作创造并调用一个匿名函数:
(define-syntax let(syntax-rules ()((let ((varexpr)...)body...)((lambda (var...)body...)expr...))))
换句话说,调用let语句如 (let ((a 1) (b 2)) (+ a b)) 等同于λ演算语句 ((lambda (a b) (+ a b)) 1 2) 。 基于这一特性,Scheme的解释器可以得到极大的精简。
λ演算
Scheme的函数式范型主要受到了邱奇的λ演算的影响。在Scheme中,“ lambda ”关键词被用于定义匿名函数,且所有非匿名函数都可以被视作取值为 lambda 函数的变量。(换句话说, (define (foo x) (+ x 1)) 与 (define foo (lambda (x) (+ x 1))) 在语法上是等同的,而前者在解释器中会被译为后者。)这一设置在历史上推动了函数式编程语言的发展。事实上,Scheme中所有函数式控制语句都可以用λ演算的语言表示,例如有序对可以表示为
(define (cons xy)(lambda (m)(mxy)))(define (car z)(z(lambda (pq)p)))(define (cdr z)(z(lambda (pq)q)))
只要这样定义出来的cons、car和cdr满足恒等式 (car (cons x y)) 等于x和 (cdr (cons x y)) 等于y。
甚至递归也可以利用λ演算的“Y算子”表示。用Scheme创始人的话讲,Scheme中的 lambda 不仅是定义函数的功能,而是整个语言的控制结构与环境操作语句 。Scheme的这一特性使得形式化证明变得非常容易。
代码块结构
Scheme的代码块结构来自更早时候的ALGOL语言。在Scheme中,本地变量可以由 let , let* ,与 letrec 产生。这些语句实际上与 lambda 等同:它们都通过函数的形式参数来实现本地变量。例如,
(define foo5);; foo 現在取值 5(let ((foo10));; foo 現在取值 10);; foo 現在取值 5
这三者的区别在于, let 所绑定的变量仅在它的区块内有效,而 let* 所绑定的变量可以在以下的绑定中使用,例如,
(let* ((var110)(var2(+ var15)))var2);; 返回 15;; 如果僅使用 let,程式會出錯。
letrec 所绑定的变量可以互相引用。因此, letrec 通常被用于双重递归:
(letrec ((female(lambda(n)(if (= n0)1(- n(male(female(- n1)))))))(male(lambda(n)(if (= n0)0(- n(female(male(- n1))))))))(display "i male(i) female(i)")(newline)(do ((i0(+ i1)))((> i8)#f)(display i)(display " ")(display (malei))(display " ")(display (femalei))(newline)))
这一程序可以列出侯世达的阴阳数列。
尾部递归优化
Scheme是最早实现尾部递归优化的Lisp方言。换句话说,Scheme中所有尾部递归都会被自动作为循环解释(Scheme支持 do 语句,但是一般Scheme中循环都会写作递归)。尾部递归优化使得Scheme支持任意数目的尾部递归调用,而无需担心堆栈溢出。如以下计算阶乘的程序将自动优化为循环。
(define (factorialn)(define (iterproductcounter)(if (> countern)product(iter(* counterproduct)(+ counter1))))(iter11))
语言元素
根据Scheme语言规范,Scheme中的标准语句可分为“标准模式”(Standard form)与“标准过程”(Standard procedure),其中标准模式提供语言的控制结构,而标准过程提供一些常用的功能。 下表给出所有R5RS所定义的标准语句 (R6RS在这一基础上加入了大量标准过程,因此无法全部列出)。
标准模式
标注为“L”的模式为库模式(Library form),通常是用其他更加基础的模式来实现的。
标准过程
实现
Scheme的精简设计使得编程语言设计人士与爱好者特别钟爱研究它的实现,很多嵌入式系统语言与脚本语言即是基于Scheme。Scheme的实现一般小而精简,造成了很多不可互通的实现互相竞争。尽管Scheme的精简性是它的一个主要长处,但试图使用Scheme编写既复杂又便于移植的程序往往比较困难,主要原因之一,是因为Scheme没有库函数标准。而R6RS试图完成这样的工作,它定义了两套标准,核心语言以及标准库。这使得Scheme第一次有了库函数标准,也使得编译器开发者和贡献者可以实现Scheme的可移植库。
几乎所有Scheme实现都是基于Lisp的“读取–求值–输出循环”(read–eval–print loop)模式。一些Scheme实现亦可作为编译器,并将Scheme程序译为二进制码。很多用类似C的基础语言写成的软件都利用Scheme作为脚本语言。还有一些Scheme翻译器(例如Gambit,Chicken,Bigloo等)可将Scheme程序译为C或Java,或甚至.Net。将Scheme译作C的翻译器往往可以在源代码中利用C的特性。
最基本的Scheme实现是在《计算机程序的构造和解释》中实现的自循环解释器。这一解释器以Scheme写成,并利用底层的Scheme功能来实现被运行的Scheme语言程序。尽管在实际上这一解释器的意义不大(要想运行自循环解释器,计算机中必须已经存在一个Scheme解释器),它简单的语法可以帮助用户理解Scheme的运行过程。
教科书
《计算机程序的构造和解释》(SICP)是最著名的使用Scheme语言的计算机科学教科书,由Scheme创始人之一萨斯曼与Harold Abelson编写。
《程序设计方法》对SICP中的一些被认为过于艰涩的概念进行了改进,由Felleison等人编写。
Simply Scheme是一本专为中学级别,无计算机科学基础的学生编写的入门书,由伯克利加州大学资深讲师布莱恩·哈维编写。
实际用处
计算机科学教育
很多著名的计算机科学院校都利用Scheme来教授入门级课程。以下为一些最为著名的教授Scheme的学校:
麻省理工学院是Scheme与SICP的诞生地。直到2008年为止,麻省理工学院的入门课程6.001即是用Scheme来教授的 。尽管现在Scheme已经不再被用于入门课程,麻省理工学院到目前为止还在教授SICP 。
伯克利加州大学的入门课程61A到2010年为止利用Scheme与SICP教授入门课程,并利用Scheme来实现Logo,另一个基于Lisp的编程语言 。自2011年起,61A改用Python来教授SICP 。
西北大学的入门课程CS2500利用Scheme来教授另一本著名的教材《程序设计方法》。
印第安那大学的入门课程C211利用Scheme来教授。
耶鲁大学
莱斯大学
北京大学
ProgramByDesign ( 英语 : ProgramByDesign ) 项目在美国超过600所高中教授Scheme语言。
滑铁卢大学数学系(包括computer science)的入门课程CS115,CS116利用Scheme来教授。
云林科技大学
脚本语言
自由软件视频处理程序GIMP利用Scheme为脚本语言 。
GNU的标准脚本语言Guile是基于Scheme的,并被用于GNOME等软件中 。
参见
《计算机程序的构造和解释》
《程序设计方法》
免责声明:以上内容版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。感谢每一位辛勤著写的作者,感谢每一位的分享。
相关资料
- 有价值
- 一般般
- 没价值