Scheme

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的簡約性使它成為具備同級別功能的程式語言中最易於實現的語言[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))

標註為「L」的模式為庫模式（Library form），通常是用其他更加基礎的模式來實現的。

很多著名的電腦科學院校都利用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] 。