Scheme

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

語言標準

目前Scheme由IEEE負責標準管理，並由一個專門的委員會發表的「演算法語言Scheme報告，第N版」（Revisedⁿ Report on the Algorithmic Language Scheme）進行標準化。現在的標準是1998年的R5RS，並且R6RS已經在2007年被批准了。R6RS帶來了很大的變動，導致Scheme社群對其意見不一，更有一些使用者指責R6RS僅僅是在堆積華而不實的功能。
Scheme的標準委員會目前正在討論R7RS的事宜，並決定是否將Scheme分為兩個獨立的語言：一個為教育者提供精簡的語法，另一個為專業人士提供強大的功能。

語言特性

Scheme大體上是一個函數式程式語言，並支援其他編程範型。它的語法基於Lisp的S-表達式：函式調用在Scheme中表示為一個串列，其中第一個元素為函式名，而後的元素為函式的參數。一個Scheme程式是由巢狀串列表達而成，而串列又是Scheme的主要資料結構，這導致程式和資料在Scheme中基本上是等價的概念。因此每一個Scheme程式都可以被視為另一個Scheme程式的參數。Scheme程式可以輕易讀入並分析其他Scheme程式，就是所謂的同像性。該特性被用於「程式碼即資料」的設計思維中，它極大提高了語言表達性和靈活性。但也有批評認為對該特性的不當使用將造成反效果，將資料當作程式碼需要藉助eval在執行時求值，這不利於編譯最佳化；另外程式碼可以被當作資料一樣被修改（即所謂程式自修改）可能會造成程式邏輯混亂。
Scheme的列表與其他Lisp方言都是基於最基礎的資料結構「有序對」（pair）。Scheme提供cons，car，與cdr方法操作有序對與列表。
Scheme的變數都使用動態強型別系統，而函式被視為變數的一種，並可以作為參數提供給其他函式。換句話說，Scheme中的函式都是第一類物件。

極簡主義

Scheme的簡約性使它成為具備同級別功能的程式語言中最易於實現的語言。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中所有函數式控制語句都可以用λ演算的語言表示，例如有序對可以表示為
(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不僅是定義函式的功能，而是整個語言的控制結構與環境操作語句。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支援任意數目的尾端遞迴調用，而無需擔心堆疊溢位。如以下計算階乘的程式將自動最佳化為循環。
(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所定義的標準語句（R6RS在這一基礎上加入了大量標準過程，因此無法全部列出）。

實作

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的執行過程。