完成一個Scheme解釋器需要哪些知識？實現各功能都有哪些東西需要理解？

01-13

目前只接觸到SICP第四章那樣的元循環解釋器，感覺很簡陋，畢業設計想用C++實現一個，具體需要哪些知識呢？可以給出文檔，資料和書籍推薦嗎？
最好能給出每個實現功能與所需知識的相關性。
自己現在的水平是只看了SICP前四章，習題大部分都完成了。可能不同完整程度需要的技術水平有差別，我想有個大概的概念自己能做到什麼程度，比如說什麼程度能理解CPS變換，實現宏或者其他的一些東西。

謝謝！

我前段時間順便給我的虛擬機做了個Scheme的前端，如果基礎知識都具備的情況下，既然知道要實現的是Scheme，果然還是得看標準文檔。

Scheme (programming language)，概略的介紹。

schemers.org: Documents: Standards: R5RS，最經典的標準了，有很多實現

R6RS：R5RS的基礎上增加了一些庫和修訂了一些規範，但我覺得還不如先把5做出來

Scheme Requests for Implementation：這個我之前以為是實現了Scheme基礎部分的情況下有餘力才實現的，後來才覺得其實裡面一些內容也對實現Scheme基本部分有幫助，比如：SRFI 9: Defining Record Types，實現了這個後很多多餘的類型就不需要用低級語言堆重複代碼了

The Scheme Programming Language, 4th Edition：Chez Scheme作者寫的書，每個特性都給出例子，最新版似乎針對的是R6RS+

你既然都決定用C++實現了，說明C++水平已經不是問題。

Scheme也是一種Lisp，所以前端大概不是難點，直接弄成語法樹然後封裝car、cdr系列介面就能訪問各個結點了。

後端的話實現方法有不同分支，如果從沒實現過編程語言，還得計劃一樣到底用哪種分支實現Scheme。

直接解釋運行
編譯到機器碼
編譯到C|C++|其他高級語言代碼
位元組碼虛擬機

分支2得具備對應機器體系結構的相關知識。

分支4可以自己設計虛擬機，也可以用現有的JVM之類的虛擬機。自己設計虛擬機簡單，靈活性大，使用現有虛擬機則需要閱讀規格文檔，各有各的麻煩。

實現編程語言和使用該語言寫一些「看似炫目實際上幾乎沒有多少實際作用的低效的難以理解」的代碼不是一回事。

對照Essentials of Programming Languages的目錄，按順序來寫，寫到後面完整的解釋器就有了。

先寫能解釋算術表達式的解釋器；

然後加入let，能製造局部變數；

然後加入lambda，能製造非遞歸的函數；

然後加入letrec，能製造遞歸的函數；

前幾個任務完成了，first class function和 closure理解/實現到位了，接下來是：

加if-else等語法糖；

把cons/cat/cdr改為內建函數（原來用lambda calculus可以模擬），改善內存管理；

加quote和eval；

加set!，引入賦值；

加CPS變換，實現call/cc並支持尾遞歸；

加define-syntax支持宏；

然後再接再厲，加點非scheme標準的東西：

加record/set/map等數據類型，並實現對應的match（模式匹配）

還不能滿足的話就做帶類型的lisp：

加類型標記，支持基本類型/函數類型；

支持ADT；

支持mu-type；

加類型推導；

支持泛型（Hindley-Milner）；

支持type class/constructor class；

還有一些周邊工作可以做：

加FFI，使語言能和C互相調用。

技能表列好了，按照這個順序來准沒錯。另外不考慮後端效率（不做虛擬機只做解釋）的話，不推薦用C++寫解釋器，還是用函數式語言寫比較爽。

解釋器相關的文獻推薦：

Lisp in small pieces

Essentials of Programming Languages

Types and Programming Languages（做帶類型的才需要看）

Matt Might的博客

作為 @邵成答案的補充，關於如何高效實現Scheme？？

一、如何執行

源碼級解釋器

在詞法、語法分析的過程中解釋執行其語義，不需要生成抽象語法樹

對於簡單的語言（如各種Scheme子集。。），實現起來比較方便，間接層少，但是模塊耦合度大，不方面調試。

基於語法樹解釋

生成抽象語法樹（AST）再解釋。AST形式不唯一（事實上，，Scheme源代碼已經很AST了。。）語法樹解釋器的執行效率仍然不高。

位元組碼解釋器

可以邊解析邊生成位元組碼，也可以基於AST生成位元組碼。

位元組碼是一種IR（中間表示），可以把位元組碼轉換為SSA、CPS等其他IR的形式，方面優化。

生成機器碼

全部編譯成機器碼：從源代碼直接生成。。；從AST生成；從位元組碼生成

JIT技術：baseline JIT，tracing JIT。。。JIT可以考慮用LLVM輔助

二、優化點

基於各種IR的優化

SSA、CPS等。。這一塊比較「底層」，或者說背景比較多、雜。。

其實構造SSA的過程就會進行常量摺疊、公共子表達式消除等優化。構造完後可以再基於SSA做優化。

循環相關的優化主要在這一層面，太多了。。

其實也有很多優化是設計上的選擇，或者tricks，或者說宏觀需要考慮的，比如下面這些：

Value representation

如何表示scheme的值？最naive的

enum type { integer, pair, string, vector, ... }; typedef struct value *SCM; struct value { enum type type; union { int integer; struct { SCM car, cdr; } pair; struct { int length; char *elts; } string; struct { int length; SCM *elts; } vector; ... } value; };

int類型的數需要打包在value裡面，獲取它的值要進行那麼多操作：x-&>value.integer。時空複雜度都比較高。bootstrap-scheme/scheme.c at v0.21 · petermichaux/bootstrap-scheme · GitHub 中就是類似的做法。

比較現代的方式有：tagging pointer, nan-boxing, num-boxing。Ruby, V8，Lua等都是用第一種。Lua JIT，IronJS是第二種

Type Specialization

動態的type feedback和靜態的type inference。Scheme是動態類型語言，可以通過類型反饋/推導，減少運行時類型檢查/轉換。在JIT中，可以根據類型預測的結果生成一條快速路徑。。

虛擬機相關

位元組碼的指令設計？

位元組碼解釋器的指令分派方式（switch-threading，token-threading等）？

虛擬機用棧式還是寄存器式？

GC用引用計數還是tracing？。。當然GC還有很多可講的。。

盡量用native stack實現VM stack

。。。

函數式語言相關

uncurring，inlining switch continuations.，stream fusion。。說不完了。。

PS：JavaScript/Ruby語法已經很函數式了，但是基本無此類優化，因為實際使用起來函數式特性造成的問題不如其他方面：做好傳統的優化，解決部分動態類型造成的問題，已經很不錯了。。

想到再補充。。。

附：

bootstrap-scheme 這是最直接的實現

Lisp-In-Small-Pieces Lisp in Small Piece書上的實現

petermichaux/bootstrap-scheme · GitHub

從這個最最簡單的開始吧，在這個基礎上慢慢改。

這個還沒CPS轉換，沒宏，而且實現也沒考慮什麼效率，

先做出來再修改。

話說這程序也是學新語言一個不錯的練習，:)

另外你確定要自己生成機器碼嗎？

直接解釋運行難度小很多，這樣可以使用一些抽象層次更高的語言。

或者實現一個虛擬機也可以。

王垠的《怎樣寫一個解釋器》，就可以教入門了大概。

。。。答完才看見LZ說SICP看了四章了。如果LZ看得認真，當我什麼都沒說過。

Write Yourself a Scheme in 48 Hours

別問我細節，我不懂 Haskell。

lifta42/simple-lisp也許這還不能算是一個「完成了」的，也不能算是一個「Scheme」解釋器，不過拿來說明問題應該夠用了。

個人認為，已經完成部分的代碼（以及構思中的部分），其核心思想和知識點全部來自於SICP第四章和龍書前兩章，而到現在為止去掉注釋不到700行的代碼量也從側面說明這不是一項需要大量積累的工作。進一步說，寫出這個解釋器最重要的，並不是與解釋運行直接相關的知識。之所以我現在有進一步完善這個解釋器的計劃，正是因為Scheme本身的簡潔使得我輕易地「繞過」了編寫解釋器部分的困難，而深入地思考有關於語言的更多方面。

在我看來，LISP存在的某一個理由，就是讓我們每人寫一個自己的LISP。在我的這個解釋器所能解釋的語言圖靈完全之前，我還認真地按照SICP上的Scheme的形狀去堆特性。現在呢？今天上午，我刪掉了特殊形式cond，取而代之的是以下這個對內建函數if調用：

(if (= 42 42) (lambda () 0) (lambda () (save this-world) ) )

注意，不同於Scheme，這個if是一個和+、display一樣的內建函數，它接受的參數都是經過求值的，而不是像cond那樣直接接觸語法樹。乍一看，這樣做除了使代碼變醜以外沒有任何目的。但其實，它使我的LISP可以遵循我對於「特性正交」的追求。原本cond的作用（控制流、避免部分代碼被求值），後者已經被我通過lambda特殊形式實現了，那麼就不應該有另一個特殊形式同樣具有這一能力。

通過上面的例子我想說，「完成一個Scheme解釋器」這種活動，其重點不應當落在「復刻」上，任何技術棧近看都是坑，完成一個完全遵循Scheme標準的解釋器的過程（以我的妄想）應該同樣要填大量的坑，那麼這就與做一個別的語言的編譯器只有工作量上的區別了。這項活動最大的意義和成果應該是藉助「類Scheme語言很好寫解釋器」這個特點，完成一門由自己設計、符合自己「審美」的語言，並在這個過程中，深刻地體會到語言特性對使用者以及設計者的影響，站在過往的、作為一個「用」語言的自己的對立面，去理解為什麼自己用的語言會長成這個樣子。這樣一來，所需要的知識乃至語言本身的功能就完全由題主自己來確定了，僅僅是解釋器通用部分的實現是不需要太偏僻的知識的。

順便班門弄斧自己的項目lifta42/simple-lisp（不要臉地再放一遍）。這對於我來說也只是一時之樂，要是這就能作為畢業項目了那就太好了233。注意，這已經不是一個Scheme解釋器了，甚至不是一個LISP解釋器，因為它違背了LISP的一個特徵「程序即數據「。我不希望「欽定」一種數據結構，用作quote的返回類型以及綁定變長參數列表的變數類型，因此通過一些方式繞過了這兩個類型。比如我的quote要這樣使用

(quote list (1 (2 3) 4 ((5)) 6 7) )

這樣，list就會被依次作用在(1 2)，(5)（兩次）和(1 2 3 4 5 6 7)上，最終的返回結果和list的返回值類型一致。

為什麼要這樣做？因為我的語言里沒有數據結構！眾所周知，列表是可以通過普通的函數實現的：

(define cons (lambda (h t) (lambda (f) (f h t)) )) (define car (lambda (c) (c (lambda (h t) h)) )) (define cdr (lambda (c) (c (lambda (h t) t)) ))

因此我就有機會不在我的語言中包含除了六種基本類型（整數、布爾值、名字、閉包函數、內建函數、nil）和一種內部類型（語法樹）以外的任何類型，雖然效率有點低就是了……這種精簡對我來說，比「程序即數據」這一概念上精簡更有吸引力。

另外，這篇代碼作為C語言的入門示例，應該也是相當恰當的。

最後附上我計劃接下來實現的特性：

內建函數load。創建一個新的作用域，載入一篇代碼並將其作用在這一作用域上，可以接受一個在這一作用域內執行的閉包。
加入一個最小化的標記清除垃圾收集。畢竟全篇代碼沒有free的確是石樂志233
完成一整套的標準庫prelude模塊。

之後如果能力允許，我會在這個新語言上寫完SICP的例題，並完成一個更加魔幻主義的類Scheme語言到彙編語言的編譯器，歡迎圍觀。

把第五章也看了，裡面還包含了編譯部分，垃圾回收以及尾調用優化。不過總地看來還是一個比較玩具的東西。同時寫的時候注意一下quotation部分。

用scheme寫scheme編譯器多好。

http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf

看jscheme第一版，以及更加精簡的lispy