柯里化的前生今世（四）：編譯器與解釋器

03-06

關於

本文是系列文章中的第四篇，發布在業餘程序員的個人修養這個專欄中：

柯里化的前生今世（一）：函數面面觀

柯里化的前生今世（二）：括弧神教

柯里化的前生今世（三）：語言和同像性

在上一篇中，我們提到了形式語言與文法，S表達式與M表達式，同像性。

本文將開始寫一個簡單的解釋器，

通過具體實現，我們來理解求值環境，動態作用域和靜態作用域，還有閉包等概念。

當然，一篇文章來寫完這些肯定是不夠的，我們可以慢慢來，循序漸進。

寫完了這個解釋器之後，我們會增加一些新的功能。

編譯器與解釋器

編譯器會將源代碼轉換成另一種語言的代碼，然後在支持後一種語言的機器上執行。

而解釋器則不同，它會逐行分析源代碼，直接執行分析結果。

值得一提的是，編譯和解釋是執行代碼的兩種手段，

具體的語言實現很可能採用兩者的混合形式。

例如，一段Java程序，會首先經過javac編譯為位元組碼，

位元組碼再交由Java虛擬機來解釋執行。（JIT和RTSJ，略。。

編譯器包含以下三個部分，

編譯器前端：詞法分析，語法分析，最終生成抽象語法樹這種中間代碼。

編譯器優化：中間代碼多次轉換，多種優化，

編譯器後端：目標代碼生成，優化目標代碼。

解釋器不包含目標代碼生成階段，將優化結果直接執行。

前端和優化，是編譯器和解釋器共有的。

抽象語法樹

編譯器前端會分析源代碼文本，生成一棵抽象語法樹。

假如，我們有如下源代碼，(1+2*3)*(4-5)。

使用ANTLR，我們得到了（具體）語法樹，

語法文件如下：

我們看到語法樹包含了產生式的名稱，這在後續處理過程中是不需要的，

因此，編譯器前端會將具體語法樹轉換成一種中間形式——抽象語法樹。

(* (+ 1 (* 2 3)) (- 4 5))

這不就是S表達式嗎？

對的，編譯器前端會將任何語言的源代碼轉換成與具體語法無關的抽象語法樹，

而S表達式正是這種抽象語法樹的線性編碼。

（因此，你寫任何語言，本質上都是在寫Lisp。。

格林斯潘第十定律：

任何C或Fortran程序複雜到一定程度之後，都會包含一個臨時開發的、不合規範的、充滿程序錯誤的、運行速度很慢的、只有一半功能的Common Lisp實現。

簡化解釋器的實現

為了簡化解釋器的實現，我們會直接分析S表達式（抽象語法樹），並且略過優化環節。我們也不解釋四則運算表達式，因為這涉及到了操作符的定義問題。

我們將直接實現lambda表達式和函數的調用。

(define (eval-exp exp) (handle-decision-tree `((,is-symbol? ,eval-symbol) (,is-self-eval-exp? ,eval-self-eval-exp) (,is-list? ((,is-lambda? ,eval-lambda) (,is-function-call-list? ,eval-function-call-list)))) exp))

和其他解釋器的教材不同的是，我沒有寫那麼多的if-else，

而是把決策模式提取出來了，這樣會更清晰一些。

eval-exp會根據exp的具體形式，尋找相應的處理方式，

而各個處理方式中，還有可能再用到eval-exp來處理子表達式。

因此，這是一個遞歸執行的過程。

下文，我們會剖析這個簡單的解釋器，

把每個處理分支都實現一下。

關於寫作意圖

本系列文章的寫作目的是想借著柯里化這個概念，

把函數式編程相關的知識點串聯起來。

為什麼選擇柯里化呢，因為柯里化首先和高階函數相關，

我可以藉此來引入作用域的概念，

continuation本身就是一個單參函數，順便就可以介紹了，

hygienic macro也涉及到了標識符的查找，學了求值環境也容易理解了。

其次，帶參數的類型，可以類比函數的柯里化來理解，

要想理解帶參數的類型，我們就得學習類型，以及代數數據類型，

從而繼續深入下去，學習Functor，Applicative，Monad這些類型類。

這樣類型系統就揭開了神秘的面紗。

當然，這些都是偏工業應用的，並沒有涉及理論基礎，

自動機理論，可計算性理論，形式語義，也不適合在本系列中提及，

寫完本系列後，我會嘗試寫其他系列，希望能覆蓋掉某些點，

以此來督促自己努力學習，小心求證。

參考

程序設計語言：實踐之路

編程語言實現模式

The Definitive ANTLR 4 Reference

Lisp in Small Pieces

Java 是編譯型語言還是解釋型語言？

Abstract vs. Concrete Syntax Trees