跳转到内容

Scheme

本页使用了标题或全文手工转换
维基百科，自由的百科全书

这是本页的一个历史版本，由Njzjz（留言 | 贡献）在2020年12月19日 (六) 01:05 （Disambiguating links to 西北大学 (link changed to 西北大学 (伊利诺伊州)) using DisamAssist.）编辑。这可能和当前版本存在着巨大的差异。

Scheme
编程范型多范型：函数式, 指令式, 元编程
语言家族Lisp
設計者小蓋伊·史提爾和傑拉德·傑伊·薩斯曼
发行时间1970年，​54年前​（1970）
当前版本
  • R7RS-small（2013；穩定版本）[1]
編輯維基數據鏈接
型態系統强类型，动态类型
作用域词法
文件扩展名.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遵循極簡主義哲学，以一个小型语言核心作为标准，加上各种强力语言工具（语法糖）来扩展语言本身[2]。

麻省理工學院與其他院校曾采用Scheme教授计算机科学入門課程。著名的入門教材《计算机程序的构造和解释》（SICP）利用Scheme來解釋程序設計[3]。Scheme的廣泛受眾被視為一個主要優勢，然而不同實現之間的差異成為了它的一個劣勢[4]。

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

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

歷史

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方言[6]。史提爾與薩斯曼兩人很快發現演員模型與λ演算非常類似，而所謂「演員」不過是Peter J. Landin提出並由Joel Moses於1970年發表的閉包而已[7]。因此，兩人很快意識到這是將詞法變數範圍介入到Lisp中實現的關鍵[8]。基於這一見解，兩人很快開發出了一套精簡的程式語言，並命名為「Schemer」（後因作業系統字數限制改為Scheme）。儘管Hewitt認為Scheme抽象性的不足是一個倒退，它簡約的語法很快贏得廣泛接受，並成為最具影響力的程式語言之一。在Scheme被廣為接受後，史提爾與薩斯曼曾承認他們事實上沒有刻意實現Scheme的簡約性。兩人認為簡單而強大的λ演算最終使得Scheme得以實現極度的精簡化[6]。

λ論文集

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

λ論文集
  • Scheme: An Interpreter for Extended Lambda Calculus，1975年[8]
  • Lambda: The Ultimate Imperative，1976年[9]
  • 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[5]，並且R6RS[10]已經在2007年被批准了[11]。R6RS帶來了很大的變動[12]，導致Scheme社區對其意見不一，更有一些使用者指責R6RS僅僅是在堆積華而不實的功能[13][14]。

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

語言特性

Scheme大体上是一個函數式程式語言，並支援其他编程范型。它的語法基於Lisp的S-表达式：函數調用在Scheme中表示為一個串列，其中第一個元素為函數名，而後的元素為函數的參數。一個Scheme程式是由巢狀串列表達而成，而串列又是Scheme的主要資料結構，這導致程式和資料在Scheme中基本上是等價的概念。因此每一個Scheme程式都可以被視為另一個Scheme程式的參數。Scheme程式可以輕易讀入並分析其他Scheme程式，就是所谓的同像性。该特性被用于“代码即数据”的设计思维中，它极大提高了语言表达性和灵活性。但也有批评认为对该特性的不当使用将造成反效果，将数据当作代码需要借助eval在运行时求值，这不利于编译优化；另外代码可以被当作数据一样被修改（即所谓程序自修改）可能会造成程序逻辑混乱。

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

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

極簡主義

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

(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不僅是定義函數的功能，而是整個語言的控制結構與環境操作語句[9]。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支援任意數目的尾端遞迴調用，而無需擔心堆疊溢位。如以下計算階乘的程式將自動優化為循環。[3] 

(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所定義的標準語句[5]（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程式譯為C或Java，或甚至.Net。將Scheme譯作C的翻譯器往往可以在原始碼中利用C的特性。

最基本的Scheme實作是在《计算机程序的构造和解释》中實現的自循環直譯器。這一直譯器以Scheme寫成，並利用底層的Scheme功能來實現被執行的Scheme語言程式。儘管在實際上這一直譯器的意義不大（要想運行自循環直譯器，電腦中必須已經存在一個Scheme直譯器），它簡單的語法可以幫助使用者理解Scheme的執行過程。

教科書

實際用處

電腦科學教育

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

指令碼語言

参见

註釋

  1. ^ https://small.r7rs.org/.
  2. ^ Barbara Liskov, "A History of CLU", MIT Laboratory for Computer Science Technical Report 561 (1993)
  3. ^ 3.0 3.1 3.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） （英语）. 
  4. ^ 4.0 4.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） （英语）. 
  5. ^ 5.0 5.1 5.2 Richard Kelsey; William Clinger; Jonathan Rees; et al. 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= (帮助)
  6. ^ 6.0 6.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）. 
  7. ^ 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. 
  8. ^ 8.0 8.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）. 
  9. ^ 9.0 9.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）. 
  10. ^ Michael Sperber, R. Kent Dybvig, Matthew Flatt, Anton Van Straaten; et al. Revised6 Report on the Algorithmic Language Scheme (R6RS). Scheme Steering Committee. August 2007 [2009-10-20]. （原始内容存档于2013-06-25）. 
  11. ^ R6RS ratification-voting results. Scheme Steering Committee. 2007-08-13 [2009-10-20]. （原始内容存档于2009-09-28）. 
  12. ^ Revised6 Report on the Algorithmic Language Scheme, Appendix E: language changes. Scheme Steering Committee. 2007-09-26 [2009-10-20]. （原始内容存档于2010-04-09）. 
  13. ^ R6RS Electorate. Scheme Steering Committee. 2007 [2009-10-20]. （原始内容存档于2008-12-04）. 
  14. ^ Marc Feeley (compilation). Implementors' intentions concerning R6RS. Scheme Steering Committee, r6rs-discuss mailing list. 2007-10-26 [2009-10-20]. （原始内容存档于2008-08-20）. 
  15. ^ cons，car，與cdr的名稱來自於Lisp。這三者的含義分別為「construct」（意為「建立」），「Content of Address Register」（意為「記憶體地址暫存器內容」），與「Content of Decrement Register」（意為「記憶體減量暫存器內容」）。這些名稱反映了Lisp中有序對最早的實現方法。
  16. ^ 事實上，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）. 
  17. ^ Eric Grimson. 6.001 Structure and Interpretation of Computer Programs. MIT Open Courseware. Spring 2005 [2009-10-20]. （原始内容存档于2009-10-01）. 
  18. ^ Alex Vandiver, Nelson Elhage; et al. 6.184 - Zombies drink caffeinated 6.001. MIT CSAIL. January 2009 [2009-10-20]. （原始内容存档于2009-08-28）. 
  19. ^ Brian Harvey. CS 61A Structure and Interpretation of Computer Programs. UC Berkeley Webcasts. Spring 2011 [2011-12-18]. （原始内容存档于2016-03-16）. 
  20. ^ John DeNero. CS 61A Structure and Interpretation of Computer Programs. UC Berkeley. Fall 2011 [2011-12-18]. （原始内容存档于2011-12-29）. 
  21. ^ Dov Grobgeld. The GIMP Basic Scheme Tutorial. The GIMP Team. 2002 [2009-10-20]. （原始内容存档于2010-01-24）. 
  22. ^ guile-gnome. Free Software Foundation. [2009-10-20]. （原始内容存档于2016-03-04）. 

外部链接

Lisp时间轴
1955 1960 1965 1970 1975 1980 1985 1990 1995 2000 2005 2010 2015 2020
LISP I LISP 1.5
 Maclisp
 BBN Lisp  Interlisp（英语：Interlisp）
 Scheme IEEE 1178  R5RS  R6RS  R7RS-small
 Lisp Machine Lisp（英语：Lisp Machine Lisp）
 Franz Lisp
 Common Lisp  ANSI Common Lisp
 Emacs Lisp
 AutoLISP  Visual LISP
 PicoLisp
 newLISP
 PLT Scheme  Racket
 ISLISP
 Clojure
 Arc
 LFE（英语：LFE (programming language)）
 Hy
检索自“https://zh.wikipedia.org/w/index.php?title=Scheme&oldid=63305801”