Scheme

Scheme是一种函数式编程语言，是Lisp的两种主要方言之一，不同于与之并列的Common Lisp，Scheme遵循哲学，以一个小型语言核心作为标准，加上各种强力语言工具（语法糖）来扩展语言本身。Scheme是第一個使用靜態作用域的Lisp方言，也是第一个引入头等续体和“干净宏”的编程语言。

简介
在1975年，麻省理工學院的傑拉德·傑伊·薩斯曼與蓋伊·史提爾二世，開發出了Scheme語言最初版本，隨後兩人通過發表「λ論文集」而不斷對它進行完善和推廣。Scheme與λ演算關係十分密切，故將小寫字母「λ」用作標誌。

麻省理工學院與其他一些院校，曾采用Scheme教授计算机科学入門課程。著名的入門教材《電腦程式的構造和解釋}-》（SICP），利用Scheme來詮釋程序設計。Scheme有眾多實現可視為一個主要優勢，然而不同實現之間的差異成為了它的一個劣勢，Scheme掌控委员会声称，它是“世上最不可移植的编程语言”，并且是一个“编程语言家族”而非一个单一的语言。

歷史
起源
Scheme起源於1958年由約翰·麥卡錫提出的Lisp語言。麥卡錫通過Lisp證明了，經由幾個簡單的算子，與用作匿名函數的借鑒自阿隆佐·邱奇的λ表示法，就可以構建出圖靈完備的系統。麥卡錫提出的S-表达式，可以将程序与数据用相同的结构存储，这被称为同像性。Scheme的語法即來自S-表达式，這一特性使得在Scheme中實現自循環直譯器變得非常簡單。

在1973年，麻省理工學院的提出的一種叫做演員模型的計算模型，并用Lisp开发当时叫做-73的新语言来实现它。傑拉德·薩斯曼與蓋伊·史提爾为了理解演员模型，決定在Maclisp工作环境中實現一個微型Lisp解释器，并接着增加创建演员和发送消息的机制。兩人很快發現了演員模型與λ演算之間的相似性，所謂「演員」就是彼得·兰丁提出的閉包，而在1970年已将它介入Lisp用来解决；故而實現演員的關鍵，是將詞法作用域介入到Lisp中。

在1975年，基於对λ演算表达能力的理解，傑拉德·薩斯曼與蓋伊·史提爾開發出了新型Lisp解释器，并将在其上完成的微缩版的演员实现命名為「Schemer」，後因作業系統文件名的字符數限制而改為Scheme。儘管Hewitt指出了Scheme不能表达特定类型的原语演员，Scheme解释器本身采用的簡約的語法和语义，很快贏得廣泛接受。

在1978年，蓋伊·史提爾二世和傑拉德·傑伊·薩斯曼发表了《修订的Scheme报告：一种LISP方言》，从而完善了Scheme的功能，并正式将其确立为Lisp的一种主要方言。在1998年，二人在总结Scheme历史时指出，簡單而強大的λ演算，使得Scheme最終得以實現極度的精簡化。

λ論文集
「λ論文集」是傑拉德·薩斯曼與蓋伊·史提爾撰寫的關於Scheme的一系列論文，最早作為麻省理工學院的內部備忘錄發表。通常認定λ論文集包括：

• 1975年: Scheme: An Interpreter for Extended Lambda Calculus.
• 1976年: Lambda: The Ultimate Imperative.
• 1976年: Lambda: The Ultimate Declarative.
• 1977年: Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO.
• 1978年: The Art of the Interpreter or, the Modularity Complex (Parts Zero, One, and Two).
• 1978年: RABBIT: A Compiler for SCHEME.
• 1979年: Design of LISP-based Processors, or SCHEME: A Dialect of LISP, or Finite Memories Considered Harmful, or LAMBDA: The Ultimate Opcode.
• 1980年: Compiler Optimization Based on Viewing LAMBDA as RENAME + GOTO. AI: An MIT Perspective.
• 1980年: Design of a Lisp-based Processor. CACM. 23. 11.

標準化
Scheme的業界標準，是由專門的掌控委員會發表的《第n次修訂的演算法語言Scheme報告》（Revisedn Report on the Algorithmic Language Scheme），这种标题形式参照了ALGOL 60标准文档的标题。Scheme报告中的形式语法描述采用了具有星号和加号扩展的巴科斯范式。Scheme报告中的形式语义描述所采用的概念和表示法，出自于在1977年的著作《指称语义：Scott-Strachey编程语言理论途径》。Scheme曾經由IEEE標準化為IEEE 1178–1990，它于2019年11月07日停用。

1998年通过的R5RS是現在被普遍接受的標準。2007年通過的R6RS，做出了很大的變動，Scheme社區中有使用者指責它在堆積華而不實的功能。Scheme掌控委員會決定在R7RS中，將Scheme分化為兩個獨立而兼容的語言：一個是2013年通過的R7RS-small，它為教學場合提供对IEEE/R5RS標準的及时更新，R7RS-small目前已经有了一些实现支持；而另一個是作为标准库合集的R7RS-Large，它包含了各种提议被接纳并进入冻结状态的（SRFI），以此為實際編程場合提供对R6RS標準的继续完善，现已发表了有关数据结构部份的R7RS-Large过渡草案红色版。

命名法
在正式场合比如Scheme标准的命名法中，提及一个λ表达式或原始过程时，偏好使用词语“过程”而非“函数”。在一般使用中，词语“过程”和“函数”是可互换使用的。过程应用有时被正式称呼为“组合”（combination）。

同其他Lisp一样，在Scheme中使用术语“”，来提及没有实际参数的过程。术语“适当”（proper）尾递归，称谓所有Scheme实现的一个性质，它们都进行尾递归优化，从而支持无限数目的活跃尾递归。

基础特征
Scheme大体上是一個函數式程式語言，並支援其他编程范型。它同其他Lisp编程语言家族语言共享了很多特征。它的非常简单的語法基於Lisp的S-表达式：即圆括号包围的列表，其中的前缀是算符，而随后那些的是实际参数。故而Scheme程序由嵌套的列表的序列构成。列表也是Scheme中的主要数据结构，这导致了在源代码和数据格式之间的紧密等价性，即同像性。Scheme程序可以轻易的动态建立和求值Scheme代码片段。

Scheme與其他Lisp方言的列表，都是基於最基礎的數據結構有序對（pair）。Scheme从它的Lisp先辈继承了一组丰富的列表处理原始运算，比如cons、和。Scheme的變數都使用動態強型別系統，Scheme中的过程都是頭等物件，即头等函数，因此过程可以作为值赋值给变量，或作为实际参数传递给过程。

本章主要集中于语言的创新特征，它们使得Scheme区别于其他Lisp方言。除非专门指出，这里描述的特征都有关于R5RS标准。在本章例子中使用“===> 结果”表示法，来指示求值在紧前行上的表达式的结果。这同于R5RS中使用的约定。本章节描述的特征使得Scheme不同于在它之前的其他编程语言。Scheme的这些方面强烈的影响了Scheme语言的所有产品，并共通于始自1975年最初的λ论文，特别是自从R2RS以来，所有版本的Scheme编程语言。

極簡主義
Scheme的簡約性，使它成為具備同級別功能的程式語言中最易於實現的語言，这得益于使用λ演算来从更原始的形式导出多数的语言语法。例如在R5RS标准中，定义了23个基于S-表达式的语法构造，其中14个被归类为派生形式或库形式，它们可以被写为涉及原则上为lambdad的更基础形式的宏。正如R5RS（§3.1）所说：“最基础的变量绑定构造是lambda表达式，因为所有其他的变量绑定构造，都可以依据lambda表达式来做出解释”，Scheme像多数现代语言一样，采用了词法作用域：在一个程序单元中所有可能的变量绑定，都可以通过阅读这个程序单元来分析出来，而不需要考虑到它可能在其中被调用的那些上下文。这对比于动态作用域，它是早期Lisp方言的特征，因为在当时的编译器和解释器中，用来实现词法作用域算法的原始的文字替换方法，关联着处理代价。在动态作用域的Lisp中，对一个过程内的自由变量的引用，依赖于这个调用的上下文，完全有可能引用到这个过程外部的相当不同的绑定。

下面是男人抑或男孩测试的例子：

(define (A k x1 x2 x3 x4 x5)
(define (B)
(set! k (- k 1))
(A k B x1 x2 x3 x4))
(if (

λ演算
邱奇的λ演算的数学表示法，启发了Lisp使用lambda作为介入一个过程的关键字，并影响了Lisp中涉及到使用高阶函数的函数式编程技术的发展。但是早期的Lisp由于对自由变量的处理方式，而不适合表达λ演算。λ演算的功能包括：首先，充当强力的数理逻辑的起点。其次，它可以缩减编程者在考虑实现细节上的要求，因为它可以用于模拟机器求值。最后，λ演算建立了一个坚实的元理论。

在Scheme中，lambda關鍵字被用於定義匿名过程，并且使用define基础形式来定义命名过程，即将一个lambda过程绑定到指名的全局变量。在Scheme中，與，在語法上是等同的。例如有序對可以表示為：

(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采用了传值调用，但不同于多数Lisp规定了过程实际参数的求值次序，Scheme不规定求值次序。对比于其他Lisp，Scheme表达式在算符位置（第一个项目）上可以是一个表达式，只要在算符位置上的表达式的结果是一个过程，这种表示就是完全合法的。

在Scheme中，在算符和实际参数位置上的这些表达式的求值次序，可以在逐个调用的基础上由实现来选择，而唯一的约束是：“运算符和运算数表达式的任何并发求值的效果，被约束为一致于某种顺序次序的求值。”（R5RS sec. 4.1.3）。自从R2RS开始，但是在Scheme中更推崇的，是使用尾递归来表达迭代。遵循标准的Scheme实现被要求优化尾递归，从而支持无限数量的活跃尾递归（R5RS sec. 3.5。自从R2RS开始，展示了Scheme可以将续体当作头等对象处理，绑定它们到变量，和把它们作为给过程的实际参数来传递。

统一的命名空间
对比于Common Lisp，在Scheme中所有的数据和过程共享一个共同的命名空间，而Common Lisp中有函数和数据分离的命名空间，使得一个函数和一个变量可以有相同的名字，并且将一个函数作为值引用时要求特殊的表示法。这有时叫做“Lisp1与Lisp2”差异，二者分别称谓Scheme的统一的命名空间，和Common Lisp的分立的命名空间。

在Scheme中， 可以使用操纵和绑定数据的原始运算来绑定过程。没有等价于Common Lisp的defun和#'的原始运算。

;; 变量绑定到一个数：
(define f 10)
f
===> 10
;; 变化（改变绑定值）
(set! f (+ f f 6))
f
===> 26
;; 将一个过程赋值给相同的变量：
(set! f (lambda (n) (+ n 12)))
(f 6)
===> 18
;; 将一个表达式的结果赋值给相同的变量：
(set! f (f 1))
f
===> 13
;; 函数式编程：
(apply + '(1 2 3 4 5 6))
===> 21
(set! f (lambda (n) (+ n 100)))
(map f '(1 2 3))
===> (101 102 103)

实现标准
本章归档多年来做出的给与Scheme特定特征的设计决定，它们不是最初设计的直接产物。

注释
直到R5RS标准，在Scheme中的标准注释是分号，它使得这行余下部份对Scheme不可见。许多实现支持可替代的约定，允许注释扩展为多于一行，而R6RS标准允许其中的两种：一个完整的S-表达式，可以通过前导#; 而变成一个注释（介入于SRFI 62），和通过用#|和|#围绕文本，产生的“多行注释”或“块注释”。

在布尔表达式中非布尔值的处理
在多数Lisp方言包括Common Lisp中，布尔表达式中的值NIL按照惯例被求值为值假。在Scheme中，自从1991年的IEEE标准。R5RS标准介入了强力的干净宏系统，它允许编程者使用一种简单的模式匹配子语言，向语言增加的新的语法构造（R5RS sec 4.3），二者都被当作对Scheme的扩展而非语言的本质部份。

干净宏的实现，也叫做syntax-rules, 被要求遵守语言的其余部份的词法作用域。这是通过针对宏展开的特殊命名和作用域规则来确保的，从而避免在其他编程语言的宏系统中可能出现的常见编程错误。R6RS规定了更加复杂的变换系统syntax-case，它已经作为对R5RS Scheme的一个语言扩展而能够获得到有一段时间了。例如：

;; 定义一个宏来实现“if”的具有多个表达式的变体
;; 有真分支而无假分支
(define-syntax when
(syntax-rules ()
((when pred exp exps ...)
(if pred (begin exp exps ...)))))

宏和过程的调用看起来非常相似，二者都是S-表达式，但是它们被不同的对待。在编译器遇到程序中的一个S-表达式的时候，它首先查看这个符号是否被定义为在当前词法范围内的语法关键字。如果是这样，它接着尝试展开这个宏，将在这个S-表达式尾部的项目当作实际参数，而不用编译代码来求值它们，递归的重复这个处理过程直到没有余留的宏调用。如果它不是一个语法关键字，编译器编译代码来求值在这个S-表达式尾部的实际参数，并接着求值在这个S-表达式头部的符号所表示的变量，把它作为过程来调用，并把最终的尾部表达式作为实际参数传递给它。

多数Scheme实现还提供额外的宏系统。其中最流行是语法闭包、显式重命名宏和define-macro，它是类似于Common Lisp中提供的defmacro系统的非干净宏。

不能指定一个宏是否为干净的，是宏系统的一个缺点。可作为替代的展开模型比如作用域集合，提供一种潜在的解决方案。

延迟求值
自从R2RS开始。

在R5RS中，给出了delay和force的推荐实现，将promise实现为没有实际参数的一个过程（），并使用记忆化来确保它永远只求值一次，与调用force的次数无关（R5RS sec. 6.4），但在具有词法作用域的Scheme中，对这个表达式在哪个环境中求值存在困惑。例如，不明确求值下列表达式的结果应当是5还是6：

(let ((name '+))
(let ((+ *))
(evaluate (list name 2 3))))

在求值实际参数name的时候，在外层环境中找到了它的定义；在求值结果表达式(+ 2 3)的时候，如果在外层环境中求值，结果是两个运算数的总和；如果在内层环境中求值，这里符号+已经被绑定到过程*的值，结果是两个运算数的乘积。为此在1978年的最初修订报告中，将evaluate替代为enclose，它接受分别为代码和运行环境的两个实际参数。由于各种技术和实际原因，第二次、第三次和第四次修订报告省略了任何eval的等价者，确使很多常规的输入-输出运算能在字符串缓冲区上进行而非在文件上。R6RS标准规定了更多复杂和有能力的端口过程和很多新的端口类型。

下面的例子是使用严格的R5RS Scheme书写的。

例子1，缺省输出到current-output-port：

(let ((hello0 (lambda() (display "Hello world") (newline))))
(hello0))

例子2，类似例子1但对输出过程使用可选的端口参数的例子：

(let ((hello1 (lambda (p) (display "Hello world" p) (newline p))))
(hello1 (current-output-port)))

类似例子1，但是输出被重定向到一个新建文件：

;; NB: with-output-to-file is an optional procedure in R5RS
(let ((hello0 (lambda () (display "Hello world") (newline))))
(with-output-to-file "helloworldoutputfile" hello0))

类似例子2，但是具有显式的文件打开和端口关闭来发送输出到文件：

(let ((hello1 (lambda (p) (display "Hello world" p) (newline p)))
(output-port (open-output-file "helloworldoutputfile")))
(hello1 output-port)
(close-output-port output-port))

类似例子2，但是使用call-with-output-file来发送输出到一个文件：

(let ((hello1 (lambda (p) (display "Hello world" p) (newline p))))
(call-with-output-file "helloworldoutputfile" hello1))

对输入提供了类似的过程。R5RS Scheme提供了谓词input-port?和output-port?。对于字符输入和输出提供了write-char、read-char、peek-char和char-ready?。为了书写和阅读Scheme表达式，Scheme提供了read和write。在读运算时，如果输入端口到达了文件的结束处，则返回的结果是end-of-file对象，并且这可以使用谓词eof-object?来测试。

除了标准之外，SRFI 28定义了一个基本的格式化过程，类似Common Lisp的format并以此命名。

标准过程的重定义
在Scheme中，过程被绑定到变量：

• 0: 基于特征的条件展开构造
• 1: 列表库
• 4: 同质数值向量数据类型
• 6: 基本字符串端口
• 8: 接收、绑定到多个值
• 9: 定义记录类型
• 13: 字符串库
• 14: 字符集库
• 16: 可变元数过程的语法
• 17: 广义set!
• 18: 多线程支持
• 19: 时间数据类型和过程
• 25: 多维数组原语
• 26: 不用柯里化的特殊化形式参数的表示法
• 27: 随机数位的来源
• 28: 基本格式化字符串
• 29: 本地化
• 30: 嵌套的多行注释
• 31: 递归求值的特殊形式
• 37: args-fold：程序实际参数处理器
• 39: 形式参数对象
• 41: 串流
• 42: 及早推导式
• 43: 向量库
• 45: 表达迭代式惰性算法的原语
• 60: 作为位元的整数
• 61: 更一般性的cond子句
• 66: 八位组向量
• 67: 比较过程

實作
Scheme的精簡設計，使得程式語言設計人士與愛好者，特別鍾愛研究它，故而它有不斷湧現的新實作，而活躍開發的實作也在持續跟進語言標準更新。儘管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來教授。
• 耶魯大學
• 萊斯大學
• 香港科技大學
• 北京大學
• 項目在美國超過600所高中教授Scheme語言。
• 滑铁卢大学数学系（包括计算机科学系）的入門課程CS115、CS116、CS135利用Scheme來教授。
• 雲林科技大學

自由軟體影像處理程式GIMP利用Scheme為嵌入式脚本語言。GNOME中有到核心库的一个GNU的扩展語言Guile包装器。在2012年出现的Julia所采用的语法解析器，是用Scheme方言Femtolisp实现的。

参见
*LISP
*Racket

註釋
延伸阅读
*
*

外部链接
*
*
*
*[https://github.com/schemedoc/awesome-scheme Awesome Scheme]
*[https://lips.js.org/#bookmark Bookmarklet that add Interactive Scheme REPL to any website]