Scheme

维基百科，自由的百科全书
跳转至： 导航、 搜索
Scheme
Lambda lc.svg
多范型
发行时间
 1975
設計者
 蓋伊·史提爾二世 和 傑拉德·傑伊·薩斯曼
强类型，动态类型
主要實作產品
 PLT Scheme, MIT/GNU Scheme, Scheme 48, Chicken, Gambit, Guile, Bigloo, Chez scheme, STk, STklos, Larceny, SCM, Kawa
衍生副語言
 T
啟發語言
 Lisp, ALGOL
影響語言
 Common Lisp, JavaScript, Ruby, Dylan

Scheme是一種多範型的程式語言，並主要支援函數式範型。它是Lisp兩種主要的方言之一（另一種為Common Lisp）。與Common Lisp不同的是，Scheme強調極簡主義設計與簡約而可擴展的語言特性。它的精簡性與優雅的語法廣受電腦科學教育者以及語言設計學者的歡迎，並經常被用於基礎電腦科學教育上。麻省理工學院與其他院校曾利用Scheme教授入門課程，並且著名的入門教材《计算机程序的构造和解释》（SICP，或稱「魔法書」）就是利用Scheme來解釋程式設計[1]。Scheme的廣泛受眾被視為它的一個主要優勢，然而不同實現之間的差異成為了它的一個劣勢[2]。

Scheme最早由麻省理工學院的蓋伊·史提爾二世與傑拉德·傑伊·薩斯曼在1970年代發展出來，並由兩人發表的「λ論文集」推廣開來。 Scheme語言與λ演算關係十分密切。小寫字母「λ」是Scheme語言的標誌。

Scheme的哲学是：设计计算机语言不应该进行功能的堆砌，而应该尽可能减少弱点和限制，使剩下的功能显得必要[3]。Scheme是第一個使用靜態而非動態變數作用域的Lisp方言，也是第一个引入“干净宏”和第一类续延的编程语言。

目录

歷史[编辑]

Lisp[编辑]

Scheme起源於約翰·麥卡錫於1958年提出的Lisp語言。通過Lisp，麥卡錫證明了圖靈完備的系統可以僅僅由幾個簡單的算子與函數定義功能組成。這一設計對Scheme的影響非常深刻。

麥卡錫最早提出兩套語法：所謂「M表示式」是通常熟知的函數語法，如car[cons[A,B]]。在麥卡錫原本的設計中，用M表示式寫成的程式將自動譯至「S表示式」，如(car (cons A B))，然而由於S表示式具備homoiconic的特性（即程式與資料由同樣的結構儲存），實際應用中一般只使用S表示式。Scheme的語法即來自S表示式。這一特性使得在Scheme中實現自循環直譯器變得非常簡單。

起源[编辑]

Scheme的靈感來自麻省理工學院的Carl Hewitt提出的一種叫做參與者模式的數學模型。Hewitt當時正在試圖將參與者模式加入Planner語言，而受其影響的史提爾與薩斯曼決定在MacLisp中實現一個支援參與者模式的Lisp方言[4]。史提爾與薩斯曼兩人很快發現參與者模式與λ演算非常類似，而所謂「參與者」不過是Peter J. Landin提出並由Joel Moses於1970年發表的閉包而已[5]。因此，兩人很快意識到λ演算是在Lisp中實現變數範圍的關鍵[6]。基於這一見解，兩人很快開發出了一套精簡的程式語言，並命名為「Schemer」（後因作業系統字數限制改為Scheme）。盡管Hewitt認為Scheme抽象性的不足是一個倒退，它簡約的語法很快贏得廣泛接受，並成為最具影響力的程式語言之一。在Scheme被廣為接受後，史提爾與薩斯曼曾承認他們事實上沒有刻意實現Scheme的簡約性。兩人認為簡單而強大的λ演算最終使得Scheme得以實現極度的精簡化[4]。

λ論文集[编辑]

「λ論文集」是Scheme的發明人史提爾與薩斯曼所撰寫的關於程式語言設計的一系列論文，最早作為麻省理工學院的內部備忘錄發表。Scheme的功能很大一部分是由這些論文確立的。 通常認為λ論文集包括：

語言標準[编辑]

目前Scheme由IEEE負責標準管理，並由一個專門的委員會發表的「演算法語言Scheme報告，第N版」（Revisedn Report on the Algorithmic Language Scheme）進行標準化。現在的標準是1998年的R5RS[3]，並且R6RS[8]已經在2007年被批准了[9]。R6RS帶來了很大的變動[10]，導致Scheme社區對其意見不一，更有一些使用者指責R6RS僅僅是在堆積華而不實的功能[11][12]。

Scheme的標準委員會目前正在討論R7RS的事宜，並決定是否將Scheme分為兩個獨立的語言：一個為教育者提供精簡的語法，另一個為專業人士提供強大的功能[2]。

語言特性[编辑]

Scheme主要是一個函數式程式語言，並支援其他程式設計範型。它的語法基於Lisp的S表示式：函數調用在Scheme中表示為一個列表，其中第一個元素為函數名，而後的元素為函數的參數。由於Scheme的資料存儲也是基於列表，實際上每一個Scheme程式都可以被視為程式輸入資料。因此，Scheme程式可以輕易讀入並分析其他Scheme程式。

Scheme的列表與其他Lisp方言都是基於最基礎的數據結構「有序對」（pair）。Scheme提供cons，car，與cdr方法[13]操作有序對與列表。

Scheme的變數都使用動態強型別系統，而函數被視為變數的一種，並可以作為參數提供給其他函數。換句話說，Scheme中的函數都是第一類物件。

極簡主義[编辑]

Scheme的簡約性使它成為具備同級別功能的程式語言中最易於實現的語言[14]。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中所有函數式控制語句都可以用λ演算的語言表示，例如有序對可以表示為[1]

(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)))

甚至遞歸也可以利用λ演算的「Y算子」表示。用Scheme創始人的話講，Scheme中的lambda不僅是定義函數的功能，而是整個語言的控制結構與環境操作語句[7]。Scheme的這一特性使得形式化證明變得非常容易。

代碼塊結構[编辑]

Scheme的代碼塊結構來自更早時候的ALGOL語言。在Scheme中，本地變數可以由let，let*，與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支援任意數目的尾端遞迴調用，而無需擔心堆疊溢位。如以下計算階乘的程式將自動優化為循環。[1]

(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所定義的標準語句[3]（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)
函數式方法 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實作都是基於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的執行過程。

教科書[编辑]

實際用處[编辑]

電腦科學教育[编辑]

很多著名的電腦科學院校都利用Scheme來教授入門級課程。以下為一些最為著名的教授Scheme的學校：

指令碼語言[编辑]

参见[编辑]

註釋[编辑]

  1. ^ 1.0 1.1 1.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 （英文）. 
  2. ^ 2.0 2.1 Will Clinger, Marc Feeley, Chris Hanson, Jonathan Rees and Olin Shivers. Position Statement, draft. Scheme Steering Committee. 2009-08-20 [2009-10-20] （英文）. 
  3. ^ 3.0 3.1 3.2 Richard Kelsey, William Clinger, Jonathan Rees et al. Revised5 Report on the Algorithmic Language Scheme. Higher-Order and Symbolic Computation. 1998.August, 11 (1): 7–105. doi:10.1023/A:1010051815785 （英文）. 
  4. ^ 4.0 4.1 Gerald Jay Sussman and Guy L. Steele, Jr.. The First Report on Scheme Revisited (PDF). Higher-Order and Symbolic Computation. 1998.December, 11 (4): 399–404 [2006-06-19]. doi:10.1023/A:1010079421970. ISSN 1388-3690. 
  5. ^ 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, "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." 
  6. ^ 6.0 6.1 Gerald Jay Sussman and Guy Lewis Steele, Jr. Scheme: An Interpreter for Extended Lambda Calculus (postscript or PDF). AI Memos (MIT AI Lab). 1975.December,. AIM-349 [2009-10-20] 
  7. ^ 7.0 7.1 Gerald Jay Sussman and Guy Lewis Steele, Jr. Lambda: The Ultimate Imperative (postscript or PDF). AI Memos (MIT AI Lab). 1976.March,. AIM-353 [2009-10-20] 
  8. ^ Michael Sperber, R. Kent Dybvig, Matthew Flatt, Anton Van Straaten et al. Revised6 Report on the Algorithmic Language Scheme (R6RS). Scheme Steering Committee. 2007.August [2009-10-20]. 
  9. ^ R6RS ratification-voting results. Scheme Steering Committee. 2007-08-13 [2009-10-20]. 
  10. ^ Revised6 Report on the Algorithmic Language Scheme, Appendix E: language changes. Scheme Steering Committee. 2007-09-26 [2009-10-20]. 
  11. ^ R6RS Electorate. Scheme Steering Committee. 2007 [2009-10-20]. 
  12. ^ Marc Feeley (compilation). Implementors' intentions concerning R6RS. Scheme Steering Committee, r6rs-discuss mailing list. 2007-10-26 [2009-10-20]. 
  13. ^ cons，car，與cdr的名稱來自於Lisp。這三者的含義分別為「construct」（意為「建立」），「Content of Address Register」（意為「記憶體地址暫存器內容」），與「Content of Decrement Register」（意為「記憶體減量暫存器內容」）。這些名稱反映了Lisp中有序對最早的實現方法。
  14. ^ 事實上，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]. 
  15. ^ Eric Grimson. 6.001 Structure and Interpretation of Computer Programs. MIT Open Courseware. Spring, 2005 [2009-10-20]. 
  16. ^ Alex Vandiver, Nelson Elhage, et al. 6.184 - Zombies drink caffeinated 6.001. MIT CSAIL. January 2009 [2009-10-20]. 
  17. ^ Brian Harvey. CS 61A Structure and Interpretation of Computer Programs. UC Berkeley Webcasts. Spring 2011 [2011-12-18]. 
  18. ^ John DeNero. CS 61A Structure and Interpretation of Computer Programs. UC Berkeley. Fall 2011 [2011-12-18]. 
  19. ^ Dov Grobgeld. The GIMP Basic Scheme Tutorial. The GIMP Team. 2002 [2009-10-20]. 
  20. ^ guile-gnome. Free Software Foundation. [2009-10-20]. 

外部链接[编辑]
.NET框架平台语言
C/C++语言
BASIC语言
有行号
无行号
Pascal/Delphi语言
数据库相关编程语言
GPU用着色器语言
函数式编程语言
Lisp家族
ML家族
专业工具语言
科学与统计计算
工业与辅助设计
计算机软件
置标语言
SGML家族
XML家族
Java虚拟机上的语言
视觉化程式设计语言
脚本语言
ECMAScript衍生语言
Shell语言
其他编程语言
来自“http://zh.wikipedia.org/w/index.php?title=Scheme&oldid=26611116”