mal 是 GitHub 上的一個開源項目，這是關(guān)于它的簡單的介紹:使用75種語言編寫一個 Lisp 解釋器。
這是 mal 語言的語法簡介和由 JS 實現(xiàn)的一個在線 repl。

在這篇文章中，我們會依托 mal 提供的步驟說明，講講如何實現(xiàn)一個簡單的 Lisp 解釋器。在步驟說明中介紹的內(nèi)容，我們不會過多重復(fù)。

簡單了解解釋器

解釋器是將一種編程語言的代碼逐句解釋執(zhí)行的軟件。要實現(xiàn)解釋器的功能，至少要實現(xiàn)以下的功能：

輸入

讀取輸入字符串：程序代碼是以字符串的形式輸入的。

預(yù)處理

• 詞法解析：把字符串轉(zhuǎn)化為 token，類似于自然語言中的分詞、斷句。例如把 (+ 1 2)轉(zhuǎn)化為 (， +， 1， 2 和 )。
• 語法解析：把 token 的序列轉(zhuǎn)化為解釋器內(nèi)部能夠理解的數(shù)據(jù)結(jié)構(gòu)，即抽象語法樹（AST）。例如，把由 ( def a ( - (+ 1 2 ) 3 ) ) 組成的序列轉(zhuǎn)化為：

// 示意：
( def a 
  ( - 
    (+ 1 2 )
    3 ))

當(dāng)然，上面的形式只是個示意，假如實現(xiàn)解釋器的語言是 Java，數(shù)據(jù)結(jié)構(gòu)可能會是一個嵌套的數(shù)組，每層數(shù)組可能會表示一個運算（例如 def, - 或者 +）。

解釋執(zhí)行

解釋器的核心，將抽象語法樹解釋為目標(biāo)語言（在本項目里就是你用來實現(xiàn)解釋器的語言）的程序，并執(zhí)行。

輸出

將程序運行的結(jié)果（可能是字符串、數(shù)值或者其他的數(shù)據(jù)形式）轉(zhuǎn)化為字符串的形式輸出。

相比其它語言的解釋器，Lisp 解釋器的優(yōu)勢是詞法解析和語法解析的過程非常簡單，因為一個 Lisp 程序本身幾乎就是一個抽象語法樹了，而像 Java、Swift 之類語法更復(fù)雜的語言，詞法解析和語法解析的過程會復(fù)雜的多。這樣，從學(xué)習(xí)的角度出發(fā)，實現(xiàn)一個 Lisp 解釋器可以更專注于解釋器的核心功能上。

第0步：搭建框架

建立 READ, EVAL, PRINT 三個主要模塊，以及把他們連起來的 rep()。
只是搭建一個骨架而已，編碼毫無難度。

問題有可能出現(xiàn)在命令行操作和寫 Makefile 上，好在用到的也都是基本操作，可以簡單看一下教學(xué)，如果你用的語言已經(jīng)由別人實現(xiàn)過，也可以借用別人寫好的 Makefile。

參考資料：
The Linux Command Line (英文版)
The Linux Command Line (中文版)
跟我一起寫 Makefile
Make 命令教程

第1步：讀取和打印

前面講了解釋器的四項工作：輸入、預(yù)處理、解釋執(zhí)行、輸出。這一步完成輸入、預(yù)處理、和輸出部分，其中預(yù)處理部分包含在輸入中。
tokenizer() 函數(shù)負(fù)責(zé)詞法分析。
read_form() 函數(shù)負(fù)責(zé)語法分析。

可能遇到的問題：正則表達(dá)式。這個我沒有網(wǎng)上資源推薦給你，你可以自己找一下；我使用的是實體書《精通正則表達(dá)式》。注意：正則表達(dá)式有不同流派，項目 guide 中使用的是 PCRE 。

注意：
項目中的任務(wù)有的被標(biāo)識為 optional 或者 deferable。
跳過 optional（可選的）任務(wù)不會影響后續(xù)任務(wù)，但有可能導(dǎo)致單元測試中出現(xiàn)錯誤。
跳過 deferable （可推遲）的任務(wù)可能會導(dǎo)致后面的步驟執(zhí)行不暢，而且將來返工可能會更麻煩一點，所以建議盡最大努力完成，如果確定要跳過，也請盡早回頭補上。
這一步中的 deferable 任務(wù)可能顯得難一點，如果你要跳過，至少看一眼這項任務(wù)都是什么，心理先有個數(shù)。

第2步：求值

Lisp 程序需要遞歸地執(zhí)行兩個相互調(diào)用的步驟：求值 eval 和應(yīng)用 apply。解釋器對一個列表（List）求值，首先要對這個列表的每個元素求值，然后將操作符（第一個元素）應(yīng)用到被操作數(shù)（其它元素）上。

例如，對于列表 (+ a ( + 1 2 ))求值：

• 需要先分別求值 +，a，( + 1 2 )，然后將 + 的值應(yīng)用到 a 和 ( + 1 2 )的值上。
• + 的求值結(jié)果為 "將操作數(shù)加到一起的操作"；a 如果有定義，它的求值結(jié)果就是變量 a 綁定的值；而( + 1 2 )并不能直接得到，需要將求值應(yīng)用循環(huán)對( + 1 2 )執(zhí)行一次。
• 求值：分別求出 +， 1， 2 的值，+ 的值已經(jīng)知道了，1， 2作為整數(shù)是自求值對象，對它們求值的結(jié)果是它們本身。這樣，所有的值都得到了。
• 應(yīng)用：將 + 應(yīng)用到 1， 2 上，得到 3。
• 回到外層的 List ，假設(shè) a 的值為 5。那么 將 + 應(yīng)用到 5， 3 上，得到 8。
• 8 就是這個 List 求值的結(jié)果。

在 mal 項目中，基本上 EVAL() 函數(shù)負(fù)責(zé)的是應(yīng)用的部分，eval_ast()函數(shù)負(fù)責(zé)的是求值的部分。

第3步：環(huán)境

在上一步的例子中，有個未解決的問題。解釋器是怎么知道變量a的值？更進(jìn)一步，解釋器是怎么知道 + 代表求和的運算的？
在上一步中定義的 repl_env 就相當(dāng)于一個全局的環(huán)境 Environment。解釋器如果想知道任何變量（包括函數(shù)名）的值，都可以在 repl_env 中查找。但在大多數(shù)真實存在的編程語言中，并不是所有的變量都是全局變量，變量是有自己的作用域的。例如：

function foo() {
  var x = 1
  {
    var y = 0
    print(x)
  }
  print(y)
}

上面的實例語言和很多真實的語言一樣，使用大括號作為作用域的開始和結(jié)束。
對于大多數(shù)語言，print(x)會打印 1，因為第一個 print()在自己的作用域中找不到 x 的值，它會繼續(xù)逐級向上層尋找，在上一層找到 x = 1 ；而print(y) 很可能會報錯，因為它找不到 y 的定義。

在 mal 中 let* 會生成新的環(huán)境，而 def! 會修改當(dāng)前的環(huán)境。除了全局環(huán)境外，每個環(huán)境都有它的外層環(huán)境。大多數(shù)其他語言的工作原理也是類似的，只不過它們實現(xiàn)環(huán)境的方法一般會高效的多。

第4步：函數(shù)定義和控制流

之前實現(xiàn)的求值和環(huán)境組成了一個解釋器最核心的部分，而有了這一步實現(xiàn)函數(shù)定義和控制流功能后，mal 看起來已經(jīng)像一個能用的真正的編程語言了。

如何實現(xiàn)定義函數(shù)閉包略微有一點燒腦：
以當(dāng)前環(huán)境為外層環(huán)境，創(chuàng)建一個新的環(huán)境。在新的環(huán)境中，函數(shù)的每個形參作為鍵，調(diào)用函數(shù)使用的實參作為值。將函數(shù)體在這個新的環(huán)境中求得的值作為返回值。
而上面說的的這一切不是即刻執(zhí)行的，而是定義在一個閉包之中，直到對這個閉包求值時才會執(zhí)行。
通過一個簡單的例子想一下：

function bar (left, right) {
  return left * right + left
}

上面定義了一個將兩個數(shù)相乘再加上第一個數(shù)的函數(shù)，并給這個函數(shù)起名字叫 bar，相當(dāng)于 mal 中的 :

(def! (fn (left right) 
          (函數(shù)體...) ) 
      bar)

定義一個函數(shù)會保存兩個信息：參數(shù)列表(left, right) 和函數(shù)體 { return left * right + left }。除了這些數(shù)據(jù)，還要告訴函數(shù)的執(zhí)行者使用函數(shù)時怎么繼續(xù)操作：

• 在函數(shù)體中，把所有形參 (left, right) 替換為實參，例如當(dāng)執(zhí)行 bar (3, 5) 時，就是把函數(shù)體變成 { return 3 * 5 + 3 }。
• 對替換后的函數(shù)體求值就得到了想要的值。

第5步：尾調(diào)用優(yōu)化

遞歸和迭代是程序設(shè)計領(lǐng)域中兩個重要的概念。一般來說遞歸程序更容易設(shè)計，但由于大量的遞歸調(diào)用會消耗更多的?？臻g，所以在執(zhí)行時時間和空間效率往往低于程序的迭代版本，而且有可能導(dǎo)致棧溢出。
尾調(diào)用優(yōu)化（尾遞歸優(yōu)化）可以將符合特定條件的遞歸過程轉(zhuǎn)化為迭代過程，這樣可以提高程序的性能。
尾調(diào)用優(yōu)化的條件是，外層函數(shù)執(zhí)行的最后一步是調(diào)用內(nèi)層函數(shù)，符合這種條件時，解釋器可以自動執(zhí)行尾調(diào)用優(yōu)化。
例子（來源：阮一峰的博客）：
寫一個求階乘的函數(shù)

function factorial (n) {
  if (n == 1) return 1;
  return n * factorial(n - 1);
}

factorial(5) // 120

上面的函數(shù)是一個遞歸函數(shù)，但不是尾遞歸，因為它的最后一步不是調(diào)用factorial(n - 1)，而是一個乘法。
把它改寫成尾遞歸的形式：

function factorial(n, total) {
  if (n === 1) return total;
  return factorial(n - 1, n * total);
}

factorial(5, 1) // 120

這樣它就變成了一個可以優(yōu)化的尾遞歸函數(shù)了。
總結(jié)一下，這個求遞歸函數(shù)的核心就是反復(fù)地使用 n 和部分積相乘，在第一個例子中是 n * factorial(n - 1)，在第二個例子中是 n * total 。程序的其他部分都是用于保證相乘能正確地繼續(xù)執(zhí)行和恰當(dāng)?shù)赝Ｖ埂?/p>

按著這個思路，手動把尾遞歸變成迭代過程：

function factorial(n, total) {
  while ( n > 1 ) {
    total = n * total
    n = n - 1
  }
  return total;
}
factorial(5, 1) // 120

把函數(shù)的核心部分用一個 while 循環(huán)包裹起來，在合適的時候結(jié)束迭代。mal 解釋器實現(xiàn)的尾調(diào)用優(yōu)化，大致也是這個原理。

待續(xù)。