Mixing
Scheme
body.skin-minerva .mw-parser-output table.infobox caption{text-align:center}
 | |
| 编程范型 | 多范型 |
|---|---|
| 設計者 | 蓋伊·史提爾二世和 傑拉德·傑伊·薩斯曼 |
| 发行时间 | 1970年（1970） |
| 穩定版本 | R7RS (ratified standard) （2013年（2013） ） |
| 型態系統 | 强类型，动态类型 |
| 文件扩展名 | .scm .ss |
| 網站 | www.scheme-reports.org |
| 主要實作產品 | |
PLT Scheme, MIT/GNU Scheme, Scheme 48, Chicken, Gambit, Guile, Bigloo, Chez scheme, STk, STklos, Larceny, SCM, Kawa | |
| 衍生副語言 | |
T | |
| 啟發語言 | |
Lisp, ALGOL | |
| 影響語言 | |
Clojure, Common Lisp, Dylan, JavaScript, Lua, Ruby | |
Scheme是一种函数式编程语言，是Lisp的两种主要方言之一（另一种为Common Lisp）。不同于Common Lisp，Scheme遵循極簡主義哲学，以一个小型语言核心作为标准，加上各种强力语言工具（语法糖）来扩展语言本身[1]。
麻省理工學院與其他院校曾采用Scheme教授计算机科学入門課程。著名的入門教材《计算机程序的构造和解释》（SICP）利用Scheme來解釋程序設計[2]。Scheme的廣泛受眾被視為一個主要優勢，然而不同實現之間的差異成為了它的一個劣勢[3]。
Scheme最早由麻省理工學院的蓋伊·史提爾二世與傑拉德·傑伊·薩斯曼在1970年代發展出來，並由兩人發表的「λ論文集」推廣開來。
Scheme語言與λ演算關係十分密切。小寫字母「λ」是Scheme語言的標誌。
Scheme的哲学是：设计计算机语言不应该进行功能的堆砌，而应该尽可能减少弱点和限制，使剩下的功能显得必要[4]。Scheme是第一個使用靜態作用域的Lisp方言，也是第一个引入“干净宏”和第一类续延的编程语言。
目录
1 歷史
1.1 Lisp
1.2 起源
1.3 λ論文集
2 語言標準
3 語言特性
3.1 極簡主義
3.2 λ演算
3.3 代碼塊結構
3.4 尾端遞迴優化
4 語言元素
4.1 標準模式
4.2 標準過程
5 實作
6 教科書
7 實際用處
7.1 電腦科學教育
7.2 指令碼語言
8 参见
9 註釋
10 外部链接
歷史
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大体上是一個函數式程式語言，並支援其他编程范型。它的語法基於Lisp的S-表达式：函數調用在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中，本地變數可以由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支援任意數目的尾端遞迴調用，而無需擔心堆疊溢位。如以下計算階乘的程式將自動優化為循環。[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），通常是用其他更加基礎的模式來實現的。
| 功能 | 模式 |
|---|---|
| 定義函數 | 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) |
標準過程
| 功能 | 過程 |
|---|---|
| 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 |
| 功能 | 過程 |
|---|---|
| 基本算術運算 | +, -, *, /, 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程式譯為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來教授的[16]。儘管現在Scheme已經不再被用於入門課程，麻省理工學院到目前為止還在教授SICP[17]。
柏克萊加州大學的入門課程61A到2010年為止利用Scheme與SICP教授入門課程，並利用Scheme來實作Logo，另一個基於Lisp的程式語言[18]。自2011年起，61A改用Python來教授SICP[19]。
西北大學的入門課程CS2500利用Scheme來教授另一本著名的教材《程序设计方法》。
印第安那大學的入門課程C211利用Scheme來教授。- 耶魯大學
- 萊斯大學
- 香港科技大學
- 北京大學
ProgramByDesign項目在美國超過600所高中教授Scheme語言。
滑铁卢大学数学系（包括 Computer Science）的入門課程CS115, CS116, CS135利用Scheme來教授。- 雲林科技大學
指令碼語言
自由軟體影像處理程式GIMP利用Scheme為指令碼語言[20]。
GNU的標準指令碼語言Guile是基於Scheme的，並被用於GNOME等軟體中[21] 。
参见
- 《计算机程序的构造和解释》
- 《程序设计方法》
註釋
^ Barbara Liskov, "A History of CLU", MIT Laboratory for Computer Science Technical Report 561 (1993)
^ 2.02.12.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.03.1 Will Clinger, Marc Feeley, Chris Hanson, Jonathan Rees and Olin Shivers. Position Statement, draft. Scheme Steering Committee. 2009-08-20 [2009-10-20] （英语）.
^ 4.04.14.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. doi:10.1023/A:1010051815785 （英语）. 已忽略未知参数|author-separator=(帮助)
^ 5.05.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）.
^ 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.
^ 7.07.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.08.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）.
^ 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]. 引文格式1维护：显式使用等标签 (link)
^ R6RS ratification-voting results. Scheme Steering Committee. 2007-08-13 [2009-10-20].
^ Revised6 Report on the Algorithmic Language Scheme, Appendix E: language changes. Scheme Steering Committee. 2007-09-26 [2009-10-20].
^
R6RS Electorate. Scheme Steering Committee. 2007 [2009-10-20].
^
Marc Feeley (compilation). Implementors' intentions concerning R6RS. Scheme Steering Committee, r6rs-discuss mailing list. 2007-10-26 [2009-10-20].
^ cons，car，與cdr的名稱來自於Lisp。這三者的含義分別為「construct」（意為「建立」），「Content of Address Register」（意為「記憶體地址暫存器內容」），與「Content of Decrement Register」（意為「記憶體減量暫存器內容」）。這些名稱反映了Lisp中有序對最早的實現方法。
^ 事實上，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].
^ Eric Grimson. 6.001 Structure and Interpretation of Computer Programs. MIT Open Courseware. Spring 2005 [2009-10-20].
^ Alex Vandiver, Nelson Elhage; 等. 6.184 - Zombies drink caffeinated 6.001. MIT CSAIL. January 2009 [2009-10-20]. 引文格式1维护：显式使用等标签 (link)
^ Brian Harvey. CS 61A Structure and Interpretation of Computer Programs. UC Berkeley Webcasts. Spring 2011 [2011-12-18]. （原始内容存档于2016-03-16）.
^ John DeNero. CS 61A Structure and Interpretation of Computer Programs. UC Berkeley. Fall 2011 [2011-12-18].
^ Dov Grobgeld. The GIMP Basic Scheme Tutorial. The GIMP Team. 2002 [2009-10-20].
^ guile-gnome. Free Software Foundation. [2009-10-20].
外部链接
- Scheme 语言的官方主页
- The Scheme programming language 3rd edition
| 1955 | 1960 | 1965 | 1970 | 1975 | 1980 | 1985 | 1990 | 1995 | 2000 | 2005 | 2010 | 2015 | 2020 | ||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Lisp 1.5 | Lisp 1.5 | ||||||||||||||
| Maclisp | Maclisp | ||||||||||||||
| Interlisp | Interlisp | ||||||||||||||
| ZetaLisp | Lisp Machine Lisp | ||||||||||||||
| Scheme | Scheme | ||||||||||||||
| NIL | NIL | ||||||||||||||
| Common Lisp | Common Lisp | ||||||||||||||
| T | T | ||||||||||||||
| Emacs Lisp | Emacs Lisp | ||||||||||||||
| AutoLISP | AutoLISP | ||||||||||||||
| OpenLisp | OpenLisp | ||||||||||||||
| PicoLisp | PicoLisp | ||||||||||||||
| EuLisp | EuLisp | ||||||||||||||
| ISLISP | ISLISP | ||||||||||||||
| newLISP | newLISP | ||||||||||||||
| Racket | Racket | ||||||||||||||
| Guile | GNU Guile | ||||||||||||||
| Visual LISP | Visual LISP | ||||||||||||||
| Clojure | Clojure | ||||||||||||||
| Arc | Arc | ||||||||||||||
| LFE | LFE | ||||||||||||||
| Hy | Hy | ||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Comments
Post a Comment