標籤：

用 Swift 寫個`函數式`的解釋器（1）

04-11

開通專欄了，之後會主要寫一些 iOS開發和函數式編程的內容。尤其是探索在 Swift 上面應用純函數編程思想，比如現在這個系列的文章。

所謂函數式的解釋器，並不是函數式語言的解釋器，而是用函數式的方法來設計的解釋器（Parser Combinator）。

之前為了準備 SwiftGG 的分享會，嘗試用 Swift 以純函數的方式寫個一個簡單的解釋器。事實證明 Swift 提供了友好的函數式特性，用來實現 FP 世界裡一些簡單的模型完全沒有問題（比如State Monad）。只用了不到400行代碼，就完全了基本功能的實現，並且非常易於擴展。

當時的直播講得比較倉促，很多東西並沒有講清楚。乾脆開個系列文章慢慢說吧。需要讀者事先有一點 Swift 語言的基礎，不需要編譯原理的基礎。

完整的項目地址點這裡

關於 Parser Combinator 的理論，可以參考這裡，這篇論文里第一次提出了用「組合子」思想來設計解釋器，並且給出了 Haskell 的實現。

解釋器實現的三個步驟

  1. 定義AST（抽象語法數）
  2. 把程序源代碼解析成 AST
  3. 解釋執行 AST

今天先介紹如何定義 AST。

定義 AST

要定義 AST，首先我們需要確定語言支持哪些功能，這裡我們一切從簡，假設我們要設計的語言長這樣：

i = 0 print i sum = 0 while i<100 { sum=sum+i i=i+1 } print sum

沒錯……就是長得跟數據結構課本里的偽代碼似得。我們就叫他 PLang 語言吧！（Pseudo Language）（逃

從這段簡短的代碼里能發現程序其實是由兩種基本元素組成：表達式和命令。比如上面的i<100, sum+i,i+1 都屬於表達式。而像 i=0,print i,while ...則是一條一條需要執行的命令。一個簡單的區別是，表達式都是有一個結果值的，而命令一般沒有。

表達式

現在我們就可以來設計 AST 了。鑒於 Swift 的 enum 的種種牛逼特性，自然非常適合用來建模我們的 AST。我們用 Exp 來代表表達式：

indirect enum Exp{ case Constant (Int) case Var (String) case Add (Exp,Exp) case Times (Exp,Exp) case Equal (Exp,Exp) case Greater (Exp,Exp) case Less (Exp,Exp)}

  • indirect代表這個結構是遞歸的，什麼意思呢？比如我們定義的 Add (加法)類型，他接受兩個參數，參數的類型也是 Exp，代表加法不僅僅是兩個數字的相加，而是兩個表達式的相加。
  • Constant 代表常量，比如3 也算一個合法的表達式，用 AST 表示就是 Constant(3)。
  • Var 代表變數，接受的 String 類型的參數就代表變數的名字，比如上面例子的i+1，用我們的 AST 表示為 Add(Var(i), Constant(1)),注意這裡的 Add()並不是函數調用，只是構造了一個 Exp.Add 的實例。
  • Times 表示乘法，Equal 代表判等（對應 C 語言中的==），Greater對應>,Less 對應<。

為了簡化設計過程，本語言僅支持 Int 類型

命令

接下來我們來設計命令對應的 AST，和表達式一樣，命令也是遞歸的結構。比如while ... {...} 是一個命令，但其內部會包含其他命令（循環體）。

indirect enum Com{ case Assign (String,Exp) case Seq (Com,Com) case Cond (Exp,Com,Com) case While (Exp,Com) case Print (Exp)}

  • Assign，代表賦值命令。參數1是 String 類型，代表要賦值到變數的名字，參數2是 Exp 類型，代表變數的值，為什麼用 Exp 呢？ 因為賦值可能並不一定是簡單的i=0，而是有可能是i= 3 * (33+sum)這樣複雜的表示。i=0表示為 AST 就是 Assign("i", Constant(0))。
  • Seq, 順序執行的命令，通過Seq 來把我們整個程序串起來。比如 i=0 s=1可以用 seq 表示為Seq(Assign(..) , Assign(..))，那如果是像i=0 s=1 b=2這樣三個命令該怎麼連呢？只需要嵌套使用 seq 就可以： Seq(Assign(..) , Seq(Assign(..) , Assign(...)))
  • Cond 也就是條件判斷，常見的形式就是 if s then a else b, s a b 分別對應 Cond 的三個參數，不難明白為什麼 s 是 Exp 類型，而 a b 是 Com 類型
  • While 表示了形式：while s { a } ， 代表循環的結構，在 s 的值為真的前提下循環執行 a 對應的命令。
  • Print 就是把一個表達式的值列印出來啦。方便我們測試程序

應用 AST

把上面我們 PLang 語言的片段用 AST 表示的話，就是像這樣：

Seq( Assign("i", Constant(0) ) , Seq( Print(i), Seq(Assign("sum",Constant(0) ), Seq(While( Less("i",Constant(100)) , Seq(Assign("sum", Add("sum" + "i"), Assign("i", Add("i", Constant(1)))), Print(i)) ) ) )

看上去比較蛋疼（手寫起來更蛋疼），不過其實還是很易懂的，之後我們要做的就是通過程序來自動生成這樣的 AST 的結構。

在下一篇文章中，會開始介紹如何從零開始構建一個優雅的解析器（Parser）來幫助我們完成這個過程。

推薦閱讀：

TAG:Swift語言 | iOS開發 | 函數式編程 |