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年，麻省理工學院的Carl Hewitt提出的一種叫做演員模型的計算模型，並用Lisp開發當時叫做Planner (程式語言)-73的新語言來實現它

```
“For some years we have been constructing a series of languages to express our evolving understanding of the above semantic issues. The latest of these
```

```clojure
(send T
    (message M
        [#continuation C]))
```

```clojure
(receive
    (message the-body
        [#continuation =the-continuation])
    the-body)
```

傑拉德·薩斯曼與蓋伊·史提爾為了理解演員模型，決定在Maclisp工作環境中實現一個微型Lisp解釋器，並接著增加創建演員和發送消息的機制。兩人很快發現了演員模型與λ演算之間的相似性，所謂「演員」就是彼得·蘭丁提出的閉包，而Joel Moses在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報告中的形式語義描述所採用的概念和表示法，出自於Joe Stoy在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，它包含了各種提議被接納並進入凍結狀態的Scheme實現要求（SRFI），以此為實際編程場合提供對R6RS標準的繼續完善，現已發表了有關數據結構部份的R7RS-Large過渡草案紅色版。

## 命名法

在正式場合比如Scheme標準的命名法中，提及一個λ表達式或原始過程時，偏好使用詞語「過程」而非「函數」。在一般使用中，詞語「過程」和「函數」是可互換使用的。過程應用有時被正式稱呼為「組合」（combination）。

同其他Lisp一樣，在Scheme中使用術語「thunk」，來提及沒有實際參數的過程。術語「適當」（proper）尾遞歸，稱謂所有Scheme實現的一個性質，它們都進行尾遞歸優化，從而支持無限數目的活躍尾遞歸。

## 基礎特徵

Scheme大體上是一個函數式程式語言，並支援其他編程范型。它同其他Lisp程式語言家族語言共享了很多特徵。它的非常簡單的語法基於Lisp的S-表達式：即圓括號包圍的列表，其中的前綴是算符，而隨後那些的是實際參數。故而Scheme程序由嵌套的列表的序列構成。列表也是Scheme中的主要數據結構，這導致了在原始碼和數據格式之間的緊密等價性，即同像性。Scheme程序可以輕易的動態建立和求值Scheme代碼片段。

Scheme與其他Lisp方言的列表，都是基於最基礎的數據結構有序對（pair）。Scheme從它的Lisp先輩繼承了一組豐富的列表處理原始運算，比如`cons`、`CAR与CDR`和`CAR与CDR`。Scheme的變數都使用動態強型別系統，Scheme中的過程都是頭等物件，即頭等函數，因此過程可以作為值賦值給變量，或作為實際參數傳遞給過程。

本章主要集中於語言的創新特徵，它們使得Scheme區別於其他Lisp方言。除非專門指出，這裡描述的特徵都有關於R5RS標準。在本章例子中使用「`===> 结果`」表示法，來指示求值在緊前行上的表達式的結果。這同於R5RS中使用的約定。本章節描述的特徵使得Scheme不同於在它之前的其他程式語言。Scheme的這些方面強烈的影響了Scheme語言的所有產品，並共通於始自1975年最初的λ論文，特別是自從R2RS以來，所有版本的Scheme程式語言。

### 極簡主義

Scheme的簡約性，使它成為具備同級別功能的程式語言中最易於實現的語言，這得益於使用λ演算來從更原始的形式導出多數的語言語法。例如在R5RS標準中，定義了23個基於S-表達式的語法構造，其中14個被歸類為派生形式或庫形式，它們可以被寫為涉及原則上為lambdad的更基礎形式的宏。正如R5RS（§3.1）所說：「最基礎的變量綁定構造是lambda表達式，因為所有其他的變量綁定構造，都可以依據lambda表達式來做出解釋」。

基礎形式：`define`、`lambda`、`quote`、`if`、`define-syntax`、`let-syntax`、`letrec-syntax`、`syntax-rules`、`set!`

派生形式：`do`、`let`、`let*`、`letrec`、`cond`、`case`、`and`、`or`、`begin`、命名`let`、`delay`、`unquote`、`unquote-splicing`、`quasiquote`

下面是一個宏的例子，它將`let`實現為使用`lambda`來進行變量綁定的一個表達式：

```Scheme
(define-syntax let
  (syntax-rules ()
    ((let ((name val) ...) body1 body2 ...)
     ((lambda (name ...) body1 body2 ...) val ...))))
```

這裡在`define-syntax`之後出現的`let`是這個宏的「語法關鍵字」或簡稱「關鍵字」，隨後是變換規定：`syntax-rules`之後的空括號中可添入作為輔助關鍵字的叫做「文字」的標識符，稱為「模式」，模式起始於關鍵字`let`，`name`、`val`、`body1`和`body2`稱為「模式變量」，`...`是稱為「省略號」的標識符，它表示所跟隨的子模式可以匹配零或多個輸入中的元素；而稱為「模板」。使用上述定義的`let`，一個Scheme實現可以將，重寫為，這將實現任務縮減為編碼過程實例化的工作。

### 詞法作用域

不像更早期的Lisp比如Maclisp，Scheme像多數現代語言一樣，採用了詞法作用域：在一個程序單元中所有可能的變量綁定，都可以通過閱讀這個程序單元來分析出來，而不需要考慮到它可能在其中被調用的那些上下文。這對比於動態作用域，它是早期Lisp方言的特徵，因為在當時的編譯器和解釋器中，用來實現詞法作用域演算法的原始的文字替換方法，關聯著處理代價。在動態作用域的Lisp中，對一個過程內的自由變量的引用，依賴於這個調用的上下文，完全有可能引用到這個過程外部的相當不同的綁定。

下面是男人抑或男孩測試的例子：

```Scheme
(define (A k x1 x2 x3 x4 x5)
  (define (B)
    (set! k (- k 1))
    (A k B x1 x2 x3 x4))
  (if (<= k 0)
    (+ (x4) (x5))
    (B)))

(A 10 (lambda () 1) (lambda () -1) (lambda () -1) (lambda () 1) (lambda () 0))
```

### λ演算

邱奇的λ演算的數學表示法，啟發了Lisp使用`lambda`作為介入一個過程的關鍵字，並影響了Lisp中涉及到使用高階函數的函數式編程技術的發展。但是早期的Lisp由於對自由變量的處理方式，而不適合表達λ演算。

一個正式的λ系統，擁有一些公理和一個完備的推理規則。這有助於使用數理邏輯和工具來進行分析。在這個系統中，演算可以被看作直接的演繹。λ演算的語法，來自用`x, y, z, ...`、圓括號、空格、點號和符號λ形成的遞歸表達式。λ演算的功能包括：首先，充當強力的數理邏輯的起點。其次，它可以縮減編程者在考慮實現細節上的要求，因為它可以用於模擬機器求值。最後，λ演算建立了一個堅實的元理論。

在Scheme中，`lambda`關鍵字被用於定義匿名過程，並且使用`define`基礎形式來定義命名過程，即將一個`lambda`過程綁定到指名的全局變量。在Scheme中，與，在語法上是等同的。例如有序對可以表示為：

```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組合子。

詞法作用域的介入，通過在某些形式的λ表示法，和在工作程式語言中它們的實際表達之間做出等價，解決了早期Lisp的有關問題。Sussman和Steele展示了，通過將λ表達式用作「控制結構和環境修改器」，而非簡單的過程實例化，可以用這個新語言優雅的導出其他程式語言包括ALGOL和Fortran的，所有指令式和聲明式語義，和其他Lisp的動態作用域。他們在第一篇λ論文中，與對Scheme的首次描述一起，介入了續體傳遞風格，並在後續的論文中，他們推進演示了在這種實際使用中體現出的λ演算的原生能力。

### 過程應用中的求值次序

Scheme採用了傳值調用，但不同於多數Lisp規定了過程實際參數的求值次序，Scheme不規定求值次序。對比於其他Lisp，Scheme表達式在算符位置（第一個項目）上可以是一個表達式，只要在算符位置上的表達式的結果是一個過程，這種表示就是完全合法的。

在Scheme中，在算符和實際參數位置上的這些表達式的求值次序，可以在逐個調用的基礎上由實現來選擇，而唯一的約束是：「運算符和運算數表達式的任何並發求值的效果，被約束為一致於某種順序次序的求值。」（R5RS sec. 4.1.3）

```Scheme
(let
  ((ev (lambda (n)
    (display "Evaluating ")
    (display (if (procedure? n) "procedure" n))
    (newline)
    n)))
  ((ev +) (ev 1) (ev 2)))
```

`ev`是一個過程，它描述傳遞給它的實際參數，接著返回這個實際參數的值。在調用過程`+`來加`1`和`2`之中，表達式`(ev +)`、`(ev 1)`和`(ev 2)`可以按任何次序求值，只要效果上它們不像是並行求值的。因此在上述例子被執行的時候，標準Scheme可以按任何次序來顯示前三行：

```console
Evaluating procedure
Evaluating 1
Evaluating 2
3
```

然而一行的文本不可以同另一行的文本產生交錯，因為這會違反順序求值約束。

### 塊結構

Scheme的代碼塊結構，不同於早先Lisp的語言構造。自從R2RS開始，Scheme中的塊，是通過三個「綁定構造」來實現的：Let 表達式、`let*`和`letrec`。例如，下列構造建立一個塊，其中叫做`var`的符號被綁定到數`10`：

```Scheme
(define var "goose")
;; 这里任何到var的引用都会被绑定到"goose"
(let ((var 10))
  ;; 语句走到这里时，任何到var的引用都会绑定到10
  )
;; 这里任何到var的引用都会绑定到"goose"
```

依據編程者的需要，塊可以嵌套 (計算)來建立任意複雜的塊結構。使用塊結構來建立局部綁定，減輕了不然可能發生的命名衝突。

`let`的變體之一`let*`，允許綁定引用在前面相同構造中定義的變量，例如：

```Scheme
(let*
  ((var1 10)
   (var2 (+ var1 12)))
  ;; 但是var1的定义不可以引用var2
  )
```

`let`的另一個變體`letrec`，被設計用來確使互遞歸過程可綁定彼此。

下面的例子是侯世達侯世達序列：

```Scheme
;; 将侯世达雌雄序列计算为有序对的列表
(define (hofstadter-male-female n)
  (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))))))))
    (let loop ((i 0))
      (if (> i n)
	    '()
	    (cons (cons (female i) (male i))
		  (loop (+ i 1)))))))

(hofstadter-male-female 8)
===> ((1 . 0) (1 . 0) (2 . 1) (2 . 2) (3 . 2) (3 . 3) (4 . 4) (5 . 4) (5 . 5))
```

在一個單一的`letrec`中的所有過程，可以通過名字引用其他的過程，還有在相同的`letrec`中此前定義的變量的值，但是它們不可以引用在相同的`letrec`中此後定義的變量的值。

`let`的變體「命名`let`」形式，在`let`關鍵字之後有一個標識符。它將這些`let`變量綁定到一個過程的實際參數，這個過程的名字由這個標識符給出，它的過程體是`let`形式的主體。這個過程體可以通過調用這個過程達成想要的重複。命名`let`被廣泛用於實現迭代。

一個簡單的計數器例子:

```Scheme
(let loop ((n 1))
  (if (> n 10)
    '()
    (cons n
	  (loop (+ n 1)))))
===> (1 2 3 4 5 6 7 8 9 10)
```

就像Scheme中的任何過程一樣，在命名`let`中建立的這個過程是頭等對象。

### 適當尾遞歸

Scheme擁有一個迭代構造`do`，但是在Scheme中更推崇的編程慣用法，是使用尾遞歸來表達迭代。遵循標準的Scheme實現被要求優化尾遞歸，從而支持無限數量的活躍尾遞歸（R5RS sec. 3.5），這個性質被Scheme報告描述為「適當」（proper）尾遞歸，它使得Scheme編程者可以安全的使用遞歸結構來書寫迭代演算法，這在很多時候是更符合直覺的。尾遞歸過程和命名`let`形式，提供對使用尾遞歸的迭代的支持。

```Scheme
;; 建造从0到9的平方的列表：
;; 注意：loop简单的就是用作标签的一个任意符号。任何符号都行。
(define (list-of-squares n)
  (let loop ((i n) (res '()))
    (if (< i 0)
      res
      (loop (- i 1) (cons (* i i) res)))))

(list-of-squares 9)
===> (0 1 4 9 16 25 36 49 64 81)
```

### 頭等續體

在Scheme中續體是頭等對象。自從R2RS開始，Scheme提供了過程以當前續體調用，簡寫為`call/cc`，它捕獲當前續體，將其包裝成逃脫（escape）過程，再綁定到編程者提供的一個過程的唯一形式參數上。如果逃脫過程在後來某個時候被調用，它會放棄在後來時候正生效的任何續體，轉而使用在創建這個逃脫過程之時生效的那個續體。逃脫過程與原本調用`call/cc`的續體，接受相同數目的實際參數；除了用`call-with-values`創建的續體，所有續體恰好接受一個值（R5RS sec. 6.4）。

頭等續體使得編程者能夠建立非局部控制結構比如迭代器、協程和回溯。續體可以被用來模擬指令式程式語言中return語句的行為。下列函數`find-first`接受函數`func`和列表`lst`，返回`lst`中的第一個元素`x`，它使得`(func x)`返回真。

```scheme
(define (find-first func lst)
  (call/cc (lambda (return)
    (for-each (lambda (x)
      (if (func x)
        (return x)))
      lst)
    #f)))

(find-first integer? '(1/2 3/4 5.6 7 8/9 10 11))
===> 7
(find-first zero? '(1 2 3 4))
===> #f
```

David Madore在1999年提出的陰陽謎題，展示了Scheme可以將續體當作頭等對象處理，綁定它們到變量，和把它們作為給過程的實際參數來傳遞。

### 統一的命名空間

對比於Common Lisp，在Scheme中所有的數據和過程共享一個共同的命名空間，而Common Lisp中有函數和數據分離的命名空間，使得一個函數和一個變量可以有相同的名字，並且將一個函數作為值引用時要求特殊的表示法。這有時叫做「Lisp1與Lisp2」差異，二者分別稱謂Scheme的統一的命名空間，和Common Lisp的分立的命名空間。

在Scheme中，可以使用操縱和綁定數據的原始運算來綁定過程。沒有等價於Common Lisp的`defun`和`#'`的原始運算。

```Scheme
;; 变量绑定到一个数：
(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標準，除了`#f`的所有的值，包括在Scheme中寫為`'()`的`NIL`的等價者，在布爾表達式中求值為值真（R5RS sec. 6.3.1）。

在多數Lisp中表示布爾值真的常量是`T`，而在Scheme中它是`#t`。

### 乾淨宏

Scheme的語法可以輕易的通過宏系統來擴展。R5RS標準介入了強力的乾淨宏系統，它允許編程者使用一種簡單的模式匹配子語言，向語言增加的新的語法構造（R5RS sec 4.3）。在此前的R4RS標準中，乾淨宏系統已經作為「高級」系統，和「低級」宏系統一起被編排入標準的附錄中，二者都被當作對Scheme的擴展而非語言的本質部份。

乾淨宏的實現，也叫做`syntax-rules`, 被要求遵守語言的其餘部份的詞法作用域。這是通過針對宏展開的特殊命名和作用域規則來確保的，從而避免在其他程式語言的宏系統中可能出現的常見編程錯誤。R6RS規定了更加複雜的變換系統`syntax-case`，它已經作為對R5RS Scheme的一個語言擴展而能夠獲得到有一段時間了。例如：

```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開始，Scheme通過`delay`形式和過程`force`支持延遲求值。

```Scheme
(define a 10)
(define eval-aplus2 (delay (+ a 2)))
(set! a 20)
(force eval-aplus2)
===> 22
(define eval-aplus50 (delay (+ a 50)))
(let ((a 8))
  (force eval-aplus50))
===> 70
(set! a 100)
(force eval-aplus2)
===> 22
```

`delay`原始運算，產生叫做promise的一個對象，它在將來的某個時間點上被詢問從而遞交結果值，promise的原本定義的文字內容會被留存，並且在第一次使用`force`之後它的值也會被留存。promise永遠只求值一次。它們可以被用來實現高級的惰性求值構造比如串流。

在R5RS中，給出了`delay`和`force`的推薦實現，將promise實現為沒有實際參數的一個過程（thunk），並使用記憶化來確保它永遠只求值一次，與調用`force`的次數無關（R5RS sec. 6.4）。在R6RS標準中，它們不再是原始運算，轉而作為R5RS兼容庫的一部份提供（rnrs r5rs (6)）。

SRFI 41確使表達有限和無限序列能夠具有非凡的經濟性。例如，這是使用在SRFI 41中的函數定義的一個斐波那契數列：

```Scheme
;; 定义斐波那契序列
(define fibs
  (stream-cons 0
    (stream-cons 1
      (stream-map +
        fibs
        (stream-cdr fibs)))))

;; 计算这个序列的第一百个数
(stream-ref fibs 99)
===>  218922995834555169026
```

### eval及其運行環境

R5RS標準之前，在其他Lisp中無處不在的`eval`過程，在Scheme中沒有等價者。在第一篇λ論文中，曾經將`evaluate`描述為「類似於LISP函數EVAL」，但在具有詞法作用域的Scheme中，對這個表達式在哪個環境中求值存在困惑。例如，不明確求值下列表達式的結果應當是`5`還是`6`：

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

在求值實際參數`name`的時候，在外層環境中找到了它的定義；在求值結果表達式`(+ 2 3)`的時候，如果在外層環境中求值，結果是兩個運算數的總和；如果在內層環境中求值，這裡符號`+`已經被綁定到過程`*`的值，結果是兩個運算數的乘積。為此在1978年的最初修訂報告中，將`evaluate`替代為`enclose`，它接受分別為代碼和運行環境的兩個實際參數。由於各種技術和實際原因，第二次、第三次和第四次修訂報告省略了任何`eval`的等價者。

R5RS通過規定三個返迴環境的過程，並提供接受一個S-表達式和一個環境的過程`eval`，它在提供的這個環境內求值這個表達式（R5RS sec. 6.5），解決了這個困惑。R6RS通過提供叫做`environment`的一個過程進行了擴展，編程者通過它可以精確的指定將哪個對象導入到求值環境之內。

通過現代Scheme（通常兼容於R5RS）來求值表達式`expr`，你需要定義如下這樣的一個函數`evaluate`：

```Scheme
(define (evaluate expr)
  (eval expr (interaction-environment)))
```

`interaction-environment`是解釋器的全局環境。

### 數值塔

Scheme規定了數值數據類型的相較完全的集合，包括複數和有理數類型，這在Scheme中叫做「數值塔」（R5RS sec. 6.2）。標準對它們作抽象處理，而不委以任何特定的內部表示。

數可以有精確性品質。一個精確數只能從涉及其他精確數的精確運算產生，不精確是傳染的。標準規定任何兩個實現對產生精確數的所有運算都必須產生等價的結果。

R5RS標準規定了過程`exact->inexact`和`inexact->exact`，它們可以用於改變一個數的精確性。`inexact->exact`產生「在數值上最接近實際參數的精確數」。`exact->inexact`產生「在數值上最接近實際參數的不精確數」。R6RS標準在主報告中省略了這些過程，而是在標準庫中將它們規定為R5RS兼容過程（rnrs r5rs (6)）。

在R5RS標準中，不要求Scheme實現去實現整個數值塔，而是它們必須實現「符合實現用途和Scheme語言精神二者的連貫子集」（R5RS sec. 6.2.3）。新的R6RS標準要求實現整個數值塔，並且「精確整數對象和精確有理數對象實際上有無限的大小和精度，並且對於實現特定過程...所以它們在得到精確實際參數時總是返回精確結果」（R6RS sec. 3.4, sec. 11.7.1）。

在支持精確有理複數的實現中的精確算術例子：

```Scheme
;; 三个有理实数和两个有理复数的总和
(define x (+ 1/3 1/4 -1/5 -1/3i 405/50+2/3i))
x
===> 509/60+1/3i
;; 检查精确性
(exact? x)
===> #t
```

在既不支持精確有理數也不支持複數卻接受有理數表示法的實數的實現中相同算術的例子：

```Scheme
;; 四个有理实数的总和
(define xr (+ 1/3 1/4 -1/5 405/50))
;; 两个有理实数的总和
(define xi (+ -1/3 2/3))
xr
===> 8.48333333333333
xi
===> 0.333333333333333
;; 检查精确性
(exact? xr)
===> #f
(exact? xi)
===> #f
```

二者實現都符合R5RS標準，但是第二個實現不符合R6RS，因為它沒有實現完整的數值塔。

### 原始數據類型不相交

在Scheme中原始數據類型是不相交的。對於任何Scheme對象，下列謂詞中只有一個可以為真：`boolean?`、`pair?`、`symbol?`、`number?`、`char?`、>`string?`、`vector?`、`port?`和`procedure?`（R5RS sec 3.2）。

作為對比，在數值數據類型之內，對數值值是可以有交疊的。例如，一個整數值可以同時滿足如下謂詞：`integer?`、`rational?`、`real?`、`complex?`和`number?`（R5RS sec 6.2）。

### 等價謂詞

Scheme在任意對象之間有三種不同類型的等價，它們通過三種不同的「等價謂詞」來指示，即測試等式的關係算符`eq?`、`eqv?`和`equal?`：

- `eq?`求值為`#f`，除非它的實際參數表示在記憶體中相同的對象。
- `eqv?`大體上同於`eq?`，但是特殊處理原始對象（比如字符和數），使得表示相同值的數`eqv?`為真，即使它們不引用相同的對象。
- `equal?`比較數據結構比如列表、向量和字串，來確定它們是否有全等的結構並且其內容`eqv?`為真（R5RS sec. 6.1）。

在Scheme中還存在依賴於類型的等價運算：`string=?`和`string-ci=?`比較兩個字串（後者進行不依賴大小寫比較）；`char=?`和`char-ci=?`比較字符；`=`比較數。

### 輸入/輸出

Scheme的輸入和輸出基於了「埠」數據類型（R5RS sec 6.6）。R5RS定義了兩個預設埠，可通過過程`current-input-port`和`current-output-port`來訪問，它們對應於Unix概念的標準輸入和標準輸出。多數實現還提供`current-error-port`。標準通過標準過程比如`with-input-from-file`和`with-output-to-file`，支持輸入和標準輸出的重定向。多數實現提供有重定向能力的字串埠，使用在SRFI 6中描述的過程，確使很多常規的輸入-輸出運算能在字串緩衝區上進行而非在文件上。R6RS標準規定了更多複雜和有能力的埠過程和很多新的埠類型。

下面的例子是使用嚴格的R5RS Scheme書寫的。

例子1，預設輸出到`current-output-port`：

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

例子2，類似例子1但對輸出過程使用可選的埠參數的例子：

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

類似例子1，但是輸出被重定向到一個新建文件：

```Scheme
;; 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，但是具有顯式的文件打開和埠關閉來發送輸出到文件：

```Scheme
(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`來發送輸出到一個文件：

```Scheme
(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中，過程被綁定到變量。在R5RS中語言標準正式的授權編程者可以變更內建過程的變量綁定，在效果上重定義它們（R5RS "Language changes"）。例如，通過重定義`+`可以將它擴展為同接受數一樣接受字串：

```Scheme
(set! +
  (let ((original+ +))
    (lambda args
      (apply
        (if (or (null? args) (string? (car args)))
          string-append
          original+)
        args))))

(+ 1 2 3)
===> 6
(+ "1" "2" "3")
===> "123"
```

在R6RS中所有綁定，包括標準過程，都屬於某個庫，並且所有導出的綁定都是不可變的（R6RS sec 7.1）。因此，禁止通過變更進行標準過程的重定義。轉而，可以在標準過程的名字下導入不同的過程，這在效果上類似於重定義。

## 標準形式和過程概述

Scheme語言正式定義於1998年的R5RS和2007年R6RS標準之中。它們描述了標準「形式」，即關鍵字和隨同的語法，它們提供語言的控制結構，和執行通常任務的標準過程。

在標準Scheme中，從一個數據類型轉換到另一個數據類型的過程，在它們的名字中包含字串`->`，謂詞結束於一個`?`，而改變已經分配了數據的值的過程結束於一個`!`。Scheme編程者通常跟從這些命名約定。

### 標準形式

本表格描述Scheme中的標準形式。某些形式出現在不止一行之中，因為它們不能被輕易的歸類入語言中的一個單一功能。

在表格中標記了「L」的形式被歸類為標準中的派生的「庫」形式，並且在實踐中通常被實現為使用了更基礎形式的宏，這使得實現任務比在其他語言中要容易許多。

用途｜形式

定義｜define

綁定構造｜lambda, do (L), let (L), let、(L), letrec (L)

條件求值｜if, cond (L), case (L), and (L), or (L)

順序求值｜begin (、)

迭代｜lambda, do (L), 命名let (L)

語法擴展｜define-syntax, let-syntax, letrec-syntax, syntax-rules (R5RS), syntax-case (R6RS)

引述｜quote('), unquote, quasiquote(`), unquote-splicing(,@)

賦值｜set!

延遲求值｜delay (L)

注意`begin`在R5RS中被定義為庫語法，但是展開者需要知道它來完成分片功能。在R6RS中它不再是庫語法。

### 標準過程

下面兩個表格描述在R5RS Scheme中的標準過程。R6RS更加具有可擴展性而如此總結是不實際的。

某些過程出現在不止一行之中，因為它們不能輕易的分類入語言的一個單一功能。

用途｜過程

構造｜vector, make-vector, make-string, list

等價謂詞｜eq?, eqv?, equal?, string=?, string-ci=?, char=?, char-ci=?

類型轉換

數值｜參見獨立表格

字串字符

向量｜make-vector, vector, vector?, vector-length, vector-ref, vector-set!, vector->list, list->vector, vector-fill!

符號｜symbol->string, string->symbol, symbol?

有序對和列表

識別謂詞｜boolean?, pair?, symbol?, number?, char?, string?, vector?, port?, procedure?

續體｜call-with-current-continuation (call/cc), values, call-with-values, dynamic-wind

環境｜eval, scheme-report-environment, null-environment, interaction-environment (可選)

輸入/輸出

系統接口｜load (可選), transcript-on (可選), transcript-off (可選)

延遲求值｜force

函數式編程｜procedure?, apply, map, for-each

布爾邏輯｜boolean? not

在其名字中包含`-ci`的字串和字符過程，在它們的實際參數之間進行不依賴大小寫的比較：相同字符的大寫和小寫版本被認為是相等的。

用途｜過程

基本算術算符｜+, -,、, /, 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?

接受多於二個實際參數的`-`和`/`在R5RS中被定義了但留作為可選的。

## Scheme實現要求

由於Scheme的極簡主義，很多常見過程和語法形式不是由標準定義的。為了保持核心語言很小並促進擴展的標準化，Scheme社群擁有「Scheme實現要求」（SRFI）流程，通過對擴展提案的仔細研討來定義擴展庫。這提升了代碼可移植性。很多SRFI被幾乎所有Scheme實現支持。

在不同的實現中具有相當廣泛支持的SRFI包括：

- 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編寫既複雜又便於移植的程序，往往比較困難。R6RS和R7RS-Large，在核心語言之外製定了庫函數標準，使得編譯器開發者和貢獻者可以實現Scheme的可移植庫。

幾乎所有Scheme實作都有傳承自Lisp的「讀取-求值-輸出循環」交互模式，一些Scheme實作亦可作為編譯器。很多用C語言及衍生語言寫成的軟體，都利用Scheme作為腳本語言，很多嵌入式系統語言即是基於Scheme。Chez Scheme等實現，可以將Scheme程式編譯為本機二進制碼。Gambit和Chicken等實現，可將Scheme程式編譯為C代碼，Bigloo還能編譯成JVM字節碼或者.Net字節碼。

一些實現支持額外的特徵。比如Kawa (Scheme實現)提供與Java類的集成，而Scheme到C編譯器通常易於使用C寫成的外部庫，甚至允許將實際C代碼嵌入到Scheme原始碼中。

## 教科書

- 《電腦程式的構造和解釋》（SICP），由Scheme創始人之一傑拉德·薩斯曼與哈爾·阿伯爾森編寫，它是最著名的使用Scheme語言的電腦科學教科書。書中用Scheme自身實現了Scheme的自循環直譯器，其簡單的語法可以幫助使用者理解Scheme的執行過程。
- 《程式設計方法》，由馬蒂亞斯·費萊森等人編寫，它對SICP中的一些被認為過於艱澀的概念進行了改進。
- 《程式語言的本質》，由丹尼爾·福瑞得曼等人編寫，它是以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來教授。
- 耶魯大學
- 萊斯大學
- 香港科技大學
- 北京大學
- ProgramByDesign項目在美國超過600所高中教授Scheme語言。
- 滑鐵盧大學數學系（包括電腦科學系）的入門課程CS115、CS116、CS135利用Scheme來教授。
- 雲林科技大學

自由軟體影像處理程式GIMP利用Scheme為嵌入式腳本語言。GNOME中有到核心庫的一個GNU的擴展語言Guile包裝器。在2012年出現的Julia所採用的語法解析器，是用Scheme方言Femtolisp實現的。

## 外部連結

- Scheme Programming
- Write Yourself a Scheme in 48 Hours
- Scheme (programming language)
- Awesome Scheme
- Bookmarklet that add Interactive Scheme REPL to any website

## 基本資料

- 編程范型：多范型：函數式
- 語言家族：Lisp
- 發行時間：1975年
- 設計者：小蓋伊·史提爾、傑拉德·傑伊·薩斯曼
- 類型系統：強類型、動態類型
- 作用域：詞法
- 文件擴展名：.scm .ss
- 網站：https://www.scheme.org/
- 軟體實現：支持R7RS：BiwaScheme, Chibi, Chicken, Cyclone, Gambit, Gauche (Scheme實現), Gerbil, GNU Guile, Kawa (Scheme實現), LIPS, Loko, MIT/GNU Scheme, Mosh, Sagittarius, SKINT, STklos, s7, TR7, Ypsilon、其他：Bigloo, Chez, GNU Mes, Scheme 48, SCM, TinyScheme