Scheme

Scheme是一種函數語言程式設計語言，是Lisp的兩種主要方言之一，不同於與之並列的Common Lisp，Scheme遵循哲學，以一個小型語言核心作為標準，加上各種強力語言工具來擴充套件語言本身。Scheme是第一個使用靜態作用域的Lisp方言，也是第一個引入頭等續體和“乾淨宏”的程式語言。簡介.在1975年，麻省理工學院的傑拉德·傑伊·薩斯曼與蓋伊·史提爾二世，開發出了Scheme語言最初版本，隨後兩人透過發表「λ論文集」而不斷對它進行完善和推廣。Scheme與λ演算關係十分密切，故將小寫字母「λ」用作標誌。麻省理工學院與其他一些院校，曾採用Scheme教授計算機科學入門課程。著名的入門教材《-{zh-hans:計算機程式的構造和解釋;zh-hant:電腦程式的構造和解釋}-》，利用Scheme來詮釋程式設計。Scheme有眾多實現可視為一個主要優勢，然而不同實現之間的差異成為了它的一個劣勢，Scheme掌控委員會聲稱，它是“世上最不可移植的程式語言”，並且是一個“程式語言家族”而非一個單一的語言。歷史.起源.Guy Lewis Steele Jr.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的一系列論文，最早作為麻省理工學院的內部備忘錄發表。通常認定λ論文集包括：標準化.Scheme的業界標準，是由專門的掌控委員會發表的《第n次修訂的演演算法語言Scheme報告》，這種標題形式參照了ALGOL 60標準文件的標題。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的實現。命名法.在正式場合比如Scheme標準的中，提及一個λ表示式或原始過程時，偏好使用詞語“過程”而非“函式”。在一般使用中，詞語“過程”和“函式”是可互換使用的。過程應用有時被正式稱呼為“組合”。同其他Lisp一樣，在Scheme中使用術語“”，來提及沒有實際引數的過程。術語“適當”尾遞迴，稱謂所有Scheme實現的一個性質，它們都進行尾遞迴最佳化，從而支援無限數目的活躍尾遞迴。基礎特徵.Scheme大體上是一個函式式程式語言，並支援其他程式設計範型。它同其他Lisp程式語言家族語言共享了很多特徵。它的非常簡單的語法基於Lisp的S-表示式：即圓括號包圍的列表，其中的字首是算符，而隨後那些的是實際引數。故而Scheme程式由巢狀的列表的序列構成。列表也是Scheme中的主要資料結構，這導致了在原始碼和資料格式之間的緊密等價性，即同像性。Scheme程式可以輕易的動態建立和求值Scheme程式碼片段。Scheme與其他Lisp方言的列表，都是基於最基礎的資料結構有序對。Scheme從它的Lisp先輩繼承了一組豐富的列表處理原始運算，比如codice_1、codice_2和codice_2。Scheme的變數都使用動態強型別系統，Scheme中的過程都是頭等物件，即頭等函式，因此過程可以作為值賦值給變數，或作為實際引數傳遞給過程。本章主要集中於語言的創新特徵，它們使得Scheme區別於其他Lisp方言。除非專門指出，這裡描述的特徵都有關於R5RS標準。在本章例子中使用“codice_4”表示法，來指示求值在緊前行上的表示式的結果。這同於R5RS中使用的約定。本章節描述的特徵使得Scheme不同於在它之前的其他程式語言。Scheme的這些方面強烈的影響了Scheme語言的所有產品，並共通於始自1975年最初的λ論文，特別是自從R2RS以來，所有版本的Scheme程式語言。極簡主義.Scheme的簡約性，使它成為具備同級別功能的程式語言中最易於實現的語言，這得益於使用λ演算來從更原始的形式匯出多數的語言語法。例如在R5RS標準中，定義了23個基於S-表示式的語法構造，其中14個被歸類為派生形式或庫形式，它們可以被寫為涉及原則上為lambdad的更基礎形式的宏。正如R5RS所說：“最基礎的變數繫結構造是lambda表示式，因為所有其他的變數繫結構造，都可以依據lambda表示式來做出解釋”。基礎形式：codice_5、codice_6、codice_7、codice_8、codice_9、codice_10、codice_11、codice_12、codice_13派生形式：codice_14、codice_15、codice_16、codice_17、codice_18、codice_19、codice_20、codice_21、codice_22、命名codice_15、codice_24、codice_25、codice_26、codice_27下面是一個宏的例子，它將codice_15實現為使用codice_6來進行變數繫結的一個表示式：(define-syntax let(syntax-rules ()((let ((var expr) ...) body ...)((lambda (var ...) body ...) expr ...))))使用上述定義的codice_15，一個Scheme實現可以將codice_31，重寫為codice_32，這將實現任務縮減為編碼過程例項化的工作。詞法作用域.不像更早期的Lisp比如Maclisp，Scheme像多數現代語言一樣，採用了詞法作用域：在一個程式單元中所有可能的變數繫結，都可以透過閱讀這個程式單元來分析出來，而不需要考慮到它可能在其中被呼叫的那些上下文。這對比於動態作用域，它是早期Lisp方言的特徵，因為在當時的編譯器和直譯器中，用來實現詞法作用域演算法的原始的文字替換方法，關聯著處理代價。在動態作用域的Lisp中，對一個過程內的自由變數的引用，依賴於這個呼叫的上下文，完全有可能引用到這個過程外部的相當不同的繫結。λ演算.邱奇的λ演算的數學表示法，啟發了Lisp使用codice_6作為介入一個過程的關鍵字，並影響了Lisp中涉及到使用高階函式的函數語言程式設計技術的發展。但是早期的Lisp由於對自由變數的處理方式，而不適合表達λ演算。一個正式的λ系統，擁有一些公理和一個完備的推理規則。這有助於使用數理邏輯和工具來進行分析。在這個系統中，演算可以被看作直接的演繹。λ演算的語法，來自用codice_34、圓括號、空格、點號和符號λ形成的遞迴表示式。λ演算的功能包括：首先，充當強力的數理邏輯的起點。其次，它可以縮減程式設計者在考慮實現細節上的要求，因為它可以用於模擬機器求值。最後，λ演算建立了一個堅實的元理論。在Scheme中，codice_6關鍵字被用於定義匿名過程，並且使用codice_5基礎形式來定義命名過程，即將一個codice_6過程繫結到指名的全域性變數。在Scheme中，codice_38與codice_39，在語法上是等同的。例如有序對可以表示為：(lambda (m) (m x y)))(z (lambda (p q) p)))(z (lambda (p q) q)))這樣定義出來的codice_1、codice_41和codice_42，滿足恆等式codice_43等於codice_44，和codice_45等於codice_46。甚至遞迴也可以表示為利用λ演算的Y組合子。詞法作用域的介入，透過在某些形式的λ表示法，和在工作程式語言中它們的實際表達之間做出等價，解決了早期Lisp的有關問題。Sussman和Steele展示了，透過將λ表示式用作“控制結構和環境修改器”，而非簡單的過程例項化，可以用這個新語言優雅的匯出其他程式語言包括ALGOL和Fortran的，所有指令式和宣告式語義，和其他Lisp的動態作用域。他們在第一篇λ論文中，與對Scheme的首次描述一起，介入了，並在後續的論文中，他們推進演示了在這種實際使用中體現出的λ演算的原生能力。過程應用中的求值次序.Scheme採用了傳值呼叫，但不同於多數Lisp規定了過程實際引數的求值次序，Scheme不規定求值次序。對比於其他Lisp，Scheme表示式在算符位置上可以是一個表示式，只要在算符位置上的表示式的結果是一個過程，這種表示就是完全合法的。在Scheme中，在算符和實際引數位置上的這些表示式的求值次序，可以在逐個呼叫的基礎上由實現來選擇，而唯一的約束是：“運算子和運算數表示式的任何併發求值的效果，被約束為一致於某種順序次序的求值。”(let((ev(lambda (n)(display "Evaluating ")(display (if (procedure? n) "procedure" n))(newline)n)))((ev +) (ev 1) (ev 2)))===&gt; 3codice_47是一個過程，它描述傳遞給它的實際引數，接著返回這個實際引數的值。在呼叫過程codice_48來加codice_49和codice_50之中，表示式codice_51、codice_52和codice_53可以按任何次序求值，只要效果上它們不像是並行求值的。因此在上述例子被執行的時候，下列三行可以被標準Scheme按任何次序來顯示，然而一行的文字不可以同另一行的文字產生交錯，因為這會違反順序求值約束。Evaluating 1Evaluating 2Evaluating procedure塊結構.Scheme的程式碼塊結構，不同於早先Lisp的語言構造。自從R2RS開始，Scheme中的塊，是透過三個“繫結構造”來實現的：、codice_16和codice_17。例如，下列構造建立一個塊，其中叫做codice_56的符號被繫結到數codice_57：;; 語句走到這裡時，任何到var的引用都會繫結到10依據程式設計者的需要，塊可以來建立任意複雜的塊結構。使用塊結構來建立區域性繫結，減輕了不然可能發生的。codice_15的變體之一codice_16，允許繫結引用在前面相同構造中定義的變數，例如：(let*((var1 10)(var2 (+ var1 12)));; 但是var1的定義不可以引用var2codice_15的另一個變體codice_17，被設計用來確使互遞迴過程可繫結彼此。下面的例子是侯世達：===&gt; ((1 . 0) (1 . 0) (2 . 1) (2 . 2) (3 . 2) (3 . 3) (4 . 4) (5 . 4) (5 . 5))在一個單一的codice_17中的所有過程，可以透過名字引用其他的過程，還有在相同的codice_17中此前定義的變數的值，但是它們不可以引用在相同的codice_17中此後定義的變數的值。codice_15的變體“命名codice_15”形式，在codice_15關鍵字之後有一個識別符號。它將這些codice_15變數繫結到一個過程的實際引數，這個過程的名字由這個識別符號給出，它的過程體是codice_15形式的主體。這個過程體可以透過呼叫這個過程達成想要的重複。命名codice_15被廣泛用於實現迭代。一個簡單的計數器例子:(if (&gt; n 10)(cons n(loop (+ n 1)))))===&gt; (1 2 3 4 5 6 7 8 9 10)就像Scheme中的任何過程一樣，在命名codice_15中建立的這個過程是頭等物件。適當尾遞迴.Scheme擁有一個迭代構造codice_14，但是在Scheme中更推崇的，是使用尾遞迴來表達迭代。遵循標準的Scheme實現被要求最佳化尾遞迴，從而支援無限數量的活躍尾遞迴尾遞迴，它使得Scheme程式設計者可以安全的使用遞迴結構來書寫迭代演算法，這在很多時候是更符合直覺的。尾遞迴過程和命名codice_15形式，提供對使用尾遞迴的迭代的支援。(let loop ((i n) (res '()))(if ( "123"在R6RS中所有繫結，包括標準過程，都屬於某個庫，並且所有匯出的繫結都是不可變的。因此，禁止透過變更進行標準過程的重定義。轉而，可以在標準過程的名字下匯入不同的過程，這在效果上類似於重定義。標準形式和過程概述.Scheme語言正式定義於1998年的R5RS和2007年R6RS標準之中。它們描述了標準“形式”，即關鍵字和隨同的語法，它們提供語言的控制結構，和執行通常任務的標準過程。在標準Scheme中，從一個數據型別轉換到另一個數據型別的過程，在它們的名字中包含字串codice_171，謂詞結束於一個codice_172，而改變已經分配了資料的值的過程結束於一個codice_173。Scheme程式設計者通常跟從這些命名約定。標準形式.本表格描述Scheme中的標準形式。某些形式出現在不止一行之中，因為它們不能被輕易的歸類入語言中的一個單一功能。在表格中標記了“L”的形式被歸類為標準中的派生的“庫”形式，並且在實踐中通常被實現為使用了更基礎形式的宏，這使得實現任務比在其他語言中要容易許多。注意codice_22在R5RS中被定義為庫語法，但是展開者需要知道它來完成分片功能。在R6RS中它不再是庫語法。標準過程.下面兩個表格描述在R5RS Scheme中的標準過程。R6RS更加具有可擴充套件性而如此總結是不實際的。某些過程出現在不止一行之中，因為它們不能輕易的分類入語言的一個單一功能。在其名字中包含codice_175的字串和字元過程，在它們的實際引數之間進行不依賴大小寫的比較：相同字元的大寫和小寫版本被認為是相等的。接受多於一個實際引數的codice_176和codice_177在R5RS中被定義了但留作為可選的。Scheme實現要求.由於Scheme的極簡主義，很多常見過程和語法形式不是由標準定義的。 為了保持核心語言很小並促進擴充套件的標準化，Scheme社群擁有“Scheme實現要求”流程，透過對擴充套件提案的仔細研討來定義擴充套件庫。這提升了程式碼可移植性。很多SRFI被幾乎所有Scheme實現支援。在不同的實現中具有相當廣泛支援的SRFI包括：實作.Scheme的精簡設計，使得程式語言設計人士與愛好者，特別鍾愛研究它，故而它有不斷湧現的新實作，而活躍開發的實作也在持續跟進語言標準更新。儘管Scheme有眾多實現是它的一個主要長處，但是由於Scheme沒有庫函式標準，造成了很多不可互通的實作互相競爭，試圖使用Scheme編寫既複雜又便於移植的程式，往往比較困難。R6RS和R7RS-Large，在核心語言之外製定了庫函式標準，使得編譯器開發者和貢獻者可以實現Scheme的可移植庫。幾乎所有Scheme實作都有傳承自Lisp的「讀取﹣求值﹣輸出迴圈」互動模式，一些Scheme實作亦可作為編譯器。很多用C語言及衍生語言寫成的軟體，都利用Scheme作為指令碼語言，很多嵌入式系統語言即是基於Scheme。Chez Scheme和Larceny等實現，可以將Scheme程式編譯為本機二進位制碼。Gambit和Chicken等實現，可將Scheme程式編譯為C程式碼，還能編譯成JVM位元組碼或者.Net位元組碼。一些實現支援額外的特徵。比如提供與Java類的整合，而Scheme到C編譯器通常易於使用C寫成的外部庫，甚至允許將實際C程式碼嵌入到Scheme原始碼中。另一個例子是用java書寫的，它提供了支援Scheme學習的一組可視工具。實際用處.很多著名的電腦科學院校都利用Scheme來教授入門級課程。以下為一些最為著名的教授Scheme的學校：自由軟體影像處理程式GIMP利用Scheme為嵌入式指令碼語言。GNOME中有到核心庫的一個GNU的擴充套件語言Guile包裝器。在2012年出現的Julia所採用的語法解析器，是用Scheme方言Femtolisp實現的。