前幾周 C 開始了個快快樂樂寫 Haskell compiler 的活動。按傳統，學 FP 要從 lambda calculus 開始，前兩週的作業就是寫 lambda calculus interpreter ，再試著使用實作環境內建的 function 並想辦法加速計算過程。

據說 interpreter 比 parser 好寫，於是一開始大家一起操作著以 JSON 表示的 AST 。

λa λb b a

寫成：

\a \b b a

表示成：

["lam", "a",
	["lam", "b",
  	["app",
    	["var", "b"],
      	["var", "a"]]]]

已經有測資，但手寫 JSON 實在是太苦悶了，不管怎樣還是想弄個 parser 出來。技術不好，不追求 one-pass ，只求能動就好。

parsing

處理 lambda calculus 時，我沒想清楚 lambda application 該怎麼處理，繞了很多路。其實只要算好這層有哪些 lambda term ，就可以處理好。

例如在省略括號時：

(Y (\a \b a) c d \a \b b)

有五個 lambda term ： Y, \a \b a, c, d, \a \b b 。注意省略括號時，看到 lambda abstract 開頭的 \ ，就可以知道從這個字到最後，是一整個 lambda term ，先不用費心處理。

所有的 lambda abstract （可以說就是 function 啦）都 currying 化了，只有一個參數。於是只要把：

["Y", "\a \b a", "c", "d", "\a \b b"]

變成這樣的 binary tree ：

[[[["Y", "\a \b a"], "c"], "d"], "\a \b b"]

就好了！裡面的東西，再遞迴地做下去。

lazy evaluation （偽）

有了 parser 和照著教學做的 interpreter ，接下來要試著加速計算過程。

@LCamel 提供了個好測資：

(\w
  (w (w (w (w (w (w (w (w (\x x)))))))))
)(\x (x (x (x (x (x (x (x (x (x x))))))))))

如果不做任何加速，我的 interpreter 要跑 1m5.417s 。要是把算過的結果記下來，只要 0m0.325s ！

現在的作法是：

1. 先把 AST 中的變數名稱都丟掉，用不需要名稱的 De Bruijn index 來表示。
2. 把正要計算的 application serialize 成以 De Bruijn index 表示的字串，當成 key ，把計算結果當成 value 。
3. 存到 key-value map 裡。

於是：

(\a \b a)(\a \b b)(\a \b a)

會變成：

(\ \ 2)(\ \ 1)(\ \ 2)

其中 2 表示「跟我這個變數 bind 在一起的是，在我外面 2 層的 lambda abstract」， 1 同理。

計算結果是 (\a \b b) 則以：

["lam", "a",
	["lam", "b",
  		["var", "b"]]]

的形狀存下來，之後可以直接用。