Scheme - Wikiwand
For faster navigation, this Iframe is preloading the Wikiwand page for Scheme.

Scheme

维基百科,自由的百科全书

Scheme
编程范型多范型函数式, 指令式, 元编程
语言家族Lisp
设计者小盖伊·史提尔杰拉德·杰伊·萨斯曼
发行时间1970年,​51年前​(1970
稳定版本
R7RS
(2013年,​8年前​(2013
类型系统强类型动态类型
作用域词法
文件扩展名.scm   .ss
网站www.scheme-reports.org 编辑维基数据链接
主要实现产品
PLT Scheme, MIT/GNU Scheme, Scheme 48, Chicken, Gambit, Guile, Bigloo, Chez scheme, JScheme, STk, STklos, Larceny, SCM, Kawa
启发语言
ALGOL, Lisp, MDL
影响语言
Clojure, Common Lisp, Dylan, EuLisp, Haskell, Hop, JavaScript, Julia, Lua, R, Racket, Ruby, Rust, S, Scala, T

Scheme是一种函数式编程语言,是Lisp的两种主要方言之一(另一种为Common Lisp)。不同于Common Lisp,Scheme遵循极简主义哲学,以一个小型语言核心作为标准,加上各种强力语言工具(语法糖)来扩展语言本身[1]

麻省理工学院与其他院校曾采用Scheme教授电脑科学入门课程。著名的入门教材《计算机程序的构造和解释》(SICP)利用Scheme来解释程序设计[2]。Scheme的广泛受众被视为一个主要优势,然而不同实现之间的差异成为了它的一个劣势[3]

Scheme最早由麻省理工学院盖伊·史提尔二世杰拉德·杰伊·萨斯曼在1970年代发展出来,并由两人发表的“λ论文集”推广开来。 Scheme语言与λ演算关系十分密切。小写字母“λ”是Scheme语言的标志

Scheme的哲学是:设计电脑语言不应该进行功能的堆砌,而应该尽可能减少弱点和限制,使剩下的功能显得必要[4]。Scheme是第一个使用静态作用域的Lisp方言,也是第一个引入“干净宏英语Hygienic macro”和第一类续延的编程语言。

历史

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方言[5]。史提尔与萨斯曼两人很快发现演员模型与λ演算非常类似,而所谓“演员”不过是Peter J. Landin提出并由Joel Moses于1970年发表的闭包而已[6]。因此,两人很快意识到这是将词法变量范围介入到Lisp中实现的关键[7]。基于这一见解,两人很快开发出了一套精简的编程语言,并命名为“Schemer”(后因操作系统字数限制改为Scheme)。尽管Hewitt认为Scheme抽象性的不足是一个倒退,它简约的语法很快赢得广泛接受,并成为最具影响力的编程语言之一。在Scheme被广为接受后,史提尔与萨斯曼曾承认他们事实上没有刻意实现Scheme的简约性。两人认为简单而强大的λ演算最终使得Scheme得以实现极度的精简化[5]

λ论文集

“λ论文集”是Scheme的发明人史提尔与萨斯曼所撰写的关于编程语言设计的一系列论文,最早作为麻省理工学院的内部备忘录发表。Scheme的功能很大一部分是由这些论文确立的。 通常认为λ论文集包括:

λ论文集
  • Scheme: An Interpreter for Extended Lambda Calculus,1975年[7]
  • Lambda: The Ultimate Imperative,1976年[8]
  • Lambda: The Ultimate Declarative,1976年
  • Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO,1977年
  • The Art of the Interpreter or, the Modularity Complex (Parts Zero, One, and Two),1978年
  • RABBIT: A Compiler for SCHEME,1978年
  • Design of LISP-based Processors, or SCHEME: A Dielectric LISP, or Finite Memories Considered Harmful, or LAMBDA: The Ultimate Opcode,1979年
  • Compiler Optimization Based on Viewing LAMBDA as RENAME + GOTO,1980年
  • Design of a Lisp-based Processor,1980年

语言标准

目前Scheme由IEEE负责标准管理,并由一个专门的委员会发表的“算法语言Scheme报告,第N版”(Revisedn Report on the Algorithmic Language Scheme)进行标准化。现在的标准是1998年的R5RS[4],并且R6RS[9]已经在2007年被批准了[10]。R6RS带来了很大的变动[11],导致Scheme社区对其意见不一,更有一些用户指责R6RS仅仅是在堆积华而不实的功能[12][13]

Scheme的标准委员会目前正在讨论R7RS的事宜,并决定是否将Scheme分为两个独立的语言:一个为教育者提供精简的语法,另一个为专业人士提供强大的功能[3]

语言特性

Scheme大体上是一个函数式编程语言,并支持其他编程范型。它的语法基于LispS-表达式:函数调用在Scheme中表示为一个串列,其中第一个元素为函数名,而后的元素为函数的参数。一个Scheme程序是由嵌套串列表达而成,而串列又是Scheme的主要数据结构,这导致程序和资料在Scheme中基本上是等价的概念。因此每一个Scheme程序都可以被视为另一个Scheme程序的参数。Scheme程序可以轻易读入并分析其他Scheme程序,就是所谓的同像性。该特性被用于“代码即数据”的设计思维中,它极大提高了语言表达性和灵活性。但也有批评认为对该特性的不当使用将造成反效果,将数据当作代码需要借助eval在运行时求值,这不利于编译优化;另外代码可以被当作数据一样被修改(即所谓程序自修改)可能会造成程序逻辑混乱。

Scheme的列表与其他Lisp方言都是基于最基础的数据结构“有序对”(pair)。Scheme提供cons,car,与cdr方法[14]操作有序对与列表。

Scheme的变量都使用动态强类型系统,而函数被视为变量的一种,并可以作为参数提供给其他函数。换句话说,Scheme中的函数都是第一类对象

极简主义

Scheme的简约性使它成为具备同级别功能的编程语言中最易于实现的语言[15]。Scheme的很多结构源于λ演算,例如let可以写作创造并调用一个匿名函数

(define-syntax let
  (syntax-rules ()
    ((let ((var expr) ...) 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中所有函数式控制语句都可以用λ演算的语言表示,例如有序对可以表示为[2]

(define (cons x y)
  (lambda (m) (m x y)))

(define (car z)
  (z (lambda (p q) p)))

(define (cdr z)
  (z (lambda (p q) q)))

只要这样定义出来的cons、car和cdr满足恒等式(car (cons x y))等于x和(cdr (cons x y))等于y。

甚至递归也可以利用λ演算的“Y算子”表示。用Scheme创始人的话讲,Scheme中的lambda不仅是定义函数的功能,而是整个语言的控制结构与环境操作语句[8]。Scheme的这一特性使得形式化证明变得非常容易。

代码块结构

Scheme的代码块结构来自更早时候的ALGOL语言。在Scheme中,本地变量可以由letlet*,与letrec产生。这些语句实际上与lambda等同:它们都通过函数的形式参数来实现本地变量。例如,

(define foo 5)
;; foo 現在取值 5
(let ((foo 10))
  ;; foo 現在取值 10
  )
;; foo 現在取值 5

这三者的区别在于,let所绑定的变量仅在它的区块内有效,而let*所绑定的变量可以在以下的绑定中使用,例如,

(let* ((var1 10)
       (var2 (+ var1 5)))
  var2)
;; 返回 15
;; 如果僅使用 let,程式會出錯。

letrec所绑定的变量可以互相引用。因此,letrec通常被用于双重递归:

(letrec ((female (lambda(n)
                   (if (= n 0) 1
                       (- n (male (female (- n 1)))))))
         (male (lambda(n)
                 (if (= n 0) 0
                     (- n (female (male (- n 1))))))))
  (display "i male(i) female(i)")(newline)
  (do ((i 0 (+ i 1)))
      ((> i 8) #f)
    (display i) (display "   ")(display (male i))(display "         ")(display (female i))
    (newline)))

这一程序可以列出侯世达的阴阳数列。

尾部递归优化

Scheme是最早实现尾部递归优化的Lisp方言。换句话说,Scheme中所有尾部递归都会被自动作为循环解释(Scheme支持do语句,但是一般Scheme中循环都会写作递归)。尾部递归优化使得Scheme支持任意数目的尾部递归调用,而无需担心堆栈溢出。如以下计算阶乘的程序将自动优化为循环。[2]

(define (factorial n)
  (define (iter product counter)
    (if (> counter n)
        product
        (iter (* counter product)
              (+ counter 1))))
  (iter 1 1))

语言元素

根据Scheme语言规范,Scheme中的标准语句可分为“标准模式”(Standard form)与“标准过程”(Standard procedure),其中标准模式提供语言的控制结构,而标准过程提供一些常用的功能。 下表给出所有R5RS所定义的标准语句[4](R6RS在这一基础上加入了大量标准过程,因此无法全部列出)。

标准模式

标注为“L”的模式为库模式(Library form),通常是用其他更加基础的模式来实现的。

R5RS Scheme的标准模式
功能 模式
定义函数 define
Binding constructs lambda, do (L), let (L), let* (L), letrec (L)
条件判断 if, cond (L), case (L), and (L), or (L)
顺序运行 begin (L)
循环运行 lambda, do (L), named let (L)
语法延伸 define-syntax, let-syntax, letrec-syntax, syntax-rules (R5RS), syntax-case (R6RS)
引用符号 quote('), unquote(,), quasiquote(`), unquote-splicing(,@)
赋值 set!
延缓运行 delay (L)

标准过程

R5RS Scheme的标准过程
功能 过程
Construction vector, make-vector, make-string, list
相等判断 eq?, eqv?, equal?, string=?, string-ci=?, char=?, char-ci=?
类型转换 vector->list, list->vector, number->string, string->number, symbol->string, string->symbol, char->integer, integer->char, string->list, list->string
数学运算 参见下表
字符串操作 string?, make-string, string, string-length, string-ref, string-set!, string=?, string-ci=?, string<? string-ci<?, string<=? string-ci<=?, string>? string-ci>?, string>=? string-ci>=?, substring, string-append, string->list, list->string, string-copy, string-fill!
字符操作 char?, char=?, char-ci=?, char<? char-ci<?, char<=? char-ci<=?, char>? char-ci>?, char>=? char-ci>=?, char-alphabetic?, char-numeric?, char-whitespace?, char-upper-case?, char-lower-case?, char->integer, integer->char, char-upcase, char-downcase
数组(vector)操作 make-vector, vector, vector?, vector-length, vector-ref, vector-set!, vector->list, list->vector, vector-fill!
符号操作 symbol->string, string->symbol, symbol?
有序对与列表 pair?, cons, car, cdr, set-car!, set-cdr!, null?, list?, list, length, append, reverse, list-tail, list-ref, memq. memv. member, assq, assv, assoc, list->vector, vector->list, list->string, string->list
类型判断 boolean?, pair?, symbol?, number?, char?, string?, vector?, port?, procedure?
Continuations call-with-current-continuation (call/cc), values, call-with-values, dynamic-wind
环境操作 eval, scheme-report-environment, null-environment, interaction-environment (optional)
输入输出 display, newline, read, write, read-char, write-char, peek-char, char-ready?, eof-object? open-input-file, open-output-file, close-input-port, close-output-port, input-port?, output-port?, current-input-port, current-output-port, call-with-input-file, call-with-output-file, with-input-from-file(optional), with-output-to-file(optional)
系统操作 load (optional), transcript-on (optional), transcript-off (optional)
延缓运行 force
函数式方法 procedure?, apply, map, for-each
布尔操作 boolean? not
R5RS Scheme的标准数学运算过程
功能 过程
基本算术运算 +, -, *, /, abs, quotient, remainder, modulo, gcd, lcm, expt, sqrt
分数运算 numerator, denominator, rational?, rationalize
近似值 floor, ceiling, truncate, round
精确性 inexact->exact, exact->inexact, exact?, inexact?
不等判断 <, <=, >, >=
其他判断 zero?, negative?, positive? odd? even?
最大与最小值 max, min
三角函数 sin, cos, tan, asin, acos, atan
幂与对数 exp, log
复数运算 make-rectangular, make-polar, real-part, imag-part, magnitude, angle, complex?
输入与输出 number->string, string->number
类型判断 integer?, rational?, real?, complex?, number?

实现

Scheme的精简设计使得编程语言设计人士与爱好者特别钟爱研究它的实现,很多嵌入式系统语言与脚本语言即是基于Scheme。Scheme的实现一般小而精简,造成了很多不可互通的实现互相竞争。尽管Scheme的精简性是它的一个主要长处,但试图使用Scheme编写既复杂又便于移植的程序往往比较困难,主要原因之一,是因为Scheme没有库函数标准。而R6RS试图完成这样的工作,它定义了两套标准,核心语言以及标准库。这使得Scheme第一次有了库函数标准,也使得编译器开发者和贡献者可以实现Scheme的可移植库。

几乎所有Scheme实现都是基于Lisp的“读取﹣求值﹣输出循环”(Read-Eval-Print Loop)模式。一些Scheme实现亦可作为编译器,并将Scheme程序译为二进制码。很多用类似C的基础语言写成的软件都利用Scheme作为脚本语言。还有一些Scheme翻译器(例如Gambit,Chicken,Bigloo等)可将Scheme程序译为CJava,或甚至.Net。将Scheme译作C的翻译器往往可以在原始码中利用C的特性。

最基本的Scheme实现是在《计算机程序的构造和解释》中实现的自循环解释器。这一解释器以Scheme写成,并利用底层的Scheme功能来实现被运行的Scheme语言程序。尽管在实际上这一解释器的意义不大(要想运行自循环解释器,电脑中必须已经存在一个Scheme解释器),它简单的语法可以帮助用户理解Scheme的运行过程。

教科书

实际用处

电脑科学教育

很多著名的电脑科学院校都利用Scheme来教授入门级课程。以下为一些最为著名的教授Scheme的学校:

脚本语言

参见

注释

  1. ^ Barbara Liskov, "A History of CLU", MIT Laboratory for Computer Science Technical Report 561 (1993)
  2. ^ 2.0 2.1 2.2 Harold Abelson and Gerald Jay Sussman with Julie Sussman. Structure and Interpretation of Computer Programs. Cambridge, MA: MIT Press. 1996 [2011]. ISBN 0-262-01153-0. (原始内容存档于2018-03-09) (英语). 
  3. ^ 3.0 3.1 Will Clinger, Marc Feeley, Chris Hanson, Jonathan Rees and Olin Shivers. Position Statement, draft. Scheme Steering Committee. 2009-08-20 [2009-10-20]. (原始内容存档于2009-08-26) (英语). 
  4. ^ 4.0 4.1 4.2 Richard Kelsey; William Clinger; Jonathan Rees; 等. Revised5 Report on the Algorithmic Language Scheme. Higher-Order and Symbolic Computation. August 1998, 11 (1): 7–105 [2007-01-04]. doi:10.1023/A:1010051815785. (原始内容存档于2007-01-05) (英语).  已忽略未知参数|author-separator= (帮助)
  5. ^ 5.0 5.1 Gerald Jay Sussman and Guy L. Steele, Jr. The First Report on Scheme Revisited (PDF). Higher-Order and Symbolic Computation. December 1998, 11 (4): 399–404 [2006-06-19]. ISSN 1388-3690. doi:10.1023/A:1010079421970. (原始内容 (PDF)存档于2006-06-15). 
  6. ^ Joel Moses, The Function of FUNCTION in LISP, or Why the FUNARG Problem Should Be Called the Environment Problem (pdf), June 1970 [2009-10-27], AI Memo 199, (原始内容存档于2010-05-23), A useful metaphor for the difference between FUNCTION and QUOTE in LISP is to think of QUOTE as a porous or an open covering of the function since free variables escape to the current environment. FUNCTION acts as a closed or nonporous covering (hence the term "closure" used by Landin). Thus we talk of "open" Lambda expressions (functions in LISP are usually Lambda expressions) and "closed" Lambda expressions. [...] My interest in the environment problem began while Landin, who had a deep understanding of the problem, visited MIT during 1966-67. I then realized the correspondence between the FUNARG lists which are the results of the evaluation of "closed" Lambda expressions in LISP and ISWIM's Lambda Closures. 
  7. ^ 7.0 7.1 Gerald Jay Sussman and Guy Lewis Steele, Jr. Scheme: An Interpreter for Extended Lambda Calculus. AI Memos (MIT AI Lab). December 1975,. AIM-349 [2009-10-20]. (原始内容 (postscript or PDF)存档于2016-05-10). 
  8. ^ 8.0 8.1 Gerald Jay Sussman and Guy Lewis Steele, Jr. Lambda: The Ultimate Imperative. AI Memos (MIT AI Lab). March 1976,. AIM-353 [2009-10-20]. (原始内容 (postscript or PDF)存档于2016-05-10). 
  9. ^ Michael Sperber, R. Kent Dybvig, Matthew Flatt, Anton Van Straaten; 等. Revised6 Report on the Algorithmic Language Scheme (R6RS). Scheme Steering Committee. August 2007 [2009-10-20]. (原始内容存档于2013-06-25). 
  10. ^ R6RS ratification-voting results. Scheme Steering Committee. 2007-08-13 [2009-10-20]. (原始内容存档于2009-09-28). 
  11. ^ Revised6 Report on the Algorithmic Language Scheme, Appendix E: language changes. Scheme Steering Committee. 2007-09-26 [2009-10-20]. (原始内容存档于2010-04-09). 
  12. ^ R6RS Electorate. Scheme Steering Committee. 2007 [2009-10-20]. (原始内容存档于2008-12-04). 
  13. ^ Marc Feeley (compilation). Implementors' intentions concerning R6RS. Scheme Steering Committee, r6rs-discuss mailing list. 2007-10-26 [2009-10-20]. (原始内容存档于2008-08-20). 
  14. ^ cons,car,与cdr的名称来自于Lisp。这三者的含义分别为“construct”(意为“创建”),“Content of Address Register”(意为“存储器地址寄存器内容”),与“Content of Decrement Register”(意为“存储器减量寄存器内容”)。这些名称反映了Lisp中有序对最早的实现方法。
  15. ^ 事实上,Richard Kelsey与Jonathan Rees曾在1986年8月6日仅用48小时写作过一个Scheme解释器,并命名为Scheme 48。详见Richard Kelsey, Jonathan Rees, Mike Sperber. The Incomplete Scheme 48 Reference Manual for release 1.8. Jonathan Rees, s48.org. 2008-01-10 [2009-10-20]. (原始内容存档于2009-02-01). 
  16. ^ Eric Grimson. 6.001 Structure and Interpretation of Computer Programs. MIT Open Courseware. Spring 2005 [2009-10-20]. (原始内容存档于2009-10-01). 
  17. ^ Alex Vandiver, Nelson Elhage; 等. 6.184 - Zombies drink caffeinated 6.001. MIT CSAIL. January 2009 [2009-10-20]. (原始内容存档于2009-08-28). 
  18. ^ Brian Harvey. CS 61A Structure and Interpretation of Computer Programs. UC Berkeley Webcasts. Spring 2011 [2011-12-18]. (原始内容存档于2016-03-16). 
  19. ^ John DeNero. CS 61A Structure and Interpretation of Computer Programs. UC Berkeley. Fall 2011 [2011-12-18]. (原始内容存档于2011-12-29). 
  20. ^ Dov Grobgeld. The GIMP Basic Scheme Tutorial. The GIMP Team. 2002 [2009-10-20]. (原始内容存档于2010-01-24). 
  21. ^ guile-gnome. Free Software Foundation. [2009-10-20]. (原始内容存档于2016-03-04). 

外部链接

{{bottomLinkPreText}} {{bottomLinkText}}
Scheme
Listen to this article