以前為了開發KFP，特別學習了一下lambda calculus（也就是我的博客的標題啦）。lanbda calculus是一門神奇的語言，在計算機出現之前就已經被搞出來了。這門語言只有三種語法，然后可以用這個語法來構造整數（！！！）、布爾型和很多遞歸數據結構等。

    首先介紹一下語法。
    1、func arg代表一個函數調用，func是函數表達式，arg是參數。
    2、\param.value代表一個函數定義，參數是param，返回結果value。
    3、(expr)代表expr的優先級較高。

    上面就是所有的語法了。乍一看好像什么都沒有，其實不然。我們現在先看一個東西：函數定義。
    為一個函數定義一個名稱是很簡單的：
    let double = \num.inc (inc num)) in ...
    代碼“...”可以訪問到函數double，但是函數定義的內部卻不行。不過這并不會帶來什么問題（其實是可以遞歸的，有辦法）。當然let-in不是一個合法的lambda calculus程序，不過可以被翻譯為：
    (\double. ...) (\num.inc (inc num))
    根據語法規則1，可以將后面的整個函數當作實參傳入形參，將所有的double都替換成后面的那個東西，于是double的名稱就被定下來了。

    遞歸怎么辦呢？譬如說要寫個函數sum n來計算1+2+...+n的值：
    let sum n = if (n==0) 0 (n+(sum (n-1))) in ...
    這里為了方便，我們假設所有的運算符都是存在的。其實a op b可以看成函數調用op a b，如果我們給每一個運算符都分配一個名字，實際上就可以用正確的lambda calculus語法來說明了。所以這里為了方便先這么干。

    sum內部是看不見sum的，因為翻譯了之后變成：
    (\sum. ...) (if (n==0) 0 (n+(sum (n-1))))
    那怎么辦呢？既然看不見自己，我可以讓調用者再外部把它自己傳進去當參數總可以吧：
    let sum n = \SELF. if (n==0) 0 (n + (SELF (n-1))) in ...
    但是我們不能用(sum sum)的方法來調用，因為到了最后(SELF (n-1))變成(sum (n-1))，下一步就錯了。所以我們造了個Y函數：
    let Y = \f.(\t.f (t t)) (\t.f (t t)) in
    let sum = Y (\SELF. if (n==0) 0 (n + (SELF (n-1)))) in ...
    這樣函數\SELF. if (n==0) 0 (n+(SELF (n-1))))就被Y變成了一個真正的遞歸函數了。不過在這里我不想花很大篇幅解釋Y是怎么來的，有興趣的讀者看這里。

    于是我們可以這么定義數字：
    zero = \s.\z.z
    one = \s.\z.s z
    two = \s.\z.s (s z)
    three = \s.\z.s (s (s z))
    four = \s.\z.s (s (s (s z)))
    數字n是一個函數，這個函數接受兩個參數s和z，返回結果是拿s在z上應用n次的結果。所以我們可以很方便的實現乘法：拿“加法”函數當成第一個參數傳進a，然后去應用b，就變成乘法了。我們首先創造一個加1函數：
    inc = \a.\s.\z.a s (s z)
    然后是加法和乘法：
    add = \a.\b.\s.\z.a s (b s z)
    mul = \a.\b.\s.\z.a (b s) z
    所以對代碼mul (add (one two)) (add (three four))進行求值的時候，我們得到(1+2)*(3+4)=21：\s.\z.(s (s (s (s (s (s (s (s (s (s (s (s (s (s (s (s (s (s (s (s (s z)))))))))))))))))))))。

    布爾值也是一樣的。我們讓true接受兩個參數返回第一個，false接受兩個參數返回第二個：
    true = \a.\b.a
    false = \a.\b.b
    那么and or xor not可以分別寫成：
    and = \a.\b.a b false
    or = \a.\b.a true b
    not = \a.a false true
    xor = \a.\b.a (not b) b
    函數if cond t f跟cond t f等價，所以我們不需要if函數。

    接下來怎么實現數據結構呢？假設我們實現一個pair，讓pair 1 2將數字保存起來，讓first(pair 1 2)返回1，second(pair 1 2)返回2：
    pair = \a.\b.\c.c a b
    first = \p.p true
    second = \p.p false
    我們舉一個例子，讓p=pair 1 (pair 2 3)，然后求first (second p)：
    first (second p) =
    first (second (pair 1 (pair 2 3))) =
    first ((pair 1(pair 2 3)) false) =
    first (false 1 (pair 2 3)) =
    first (pair 2 3) =
    (pair 2 3) true =
    true 2 3 =
    2
    是不是很神奇捏，lambda calculus僅需那么幾條語法就可以實現所有東西了。將pair嵌套在一起可以構成一個列表。下面我們來寫一個完整的程序，構造列表[1,2,3,4,5]，然后對每一個元素求平方后相加：1*1 + 2*2 + 3*3 + 4*4 + 5*5 = 55：

    下面是完整的程序：

    然后是結果。首先我的lambda calculus虛擬機把let-in按照上面的方法重新轉換為標準的lambda calculus程序，最后求值：

    數一數吧，上面有55個"(s"，所以結果就是55了。

    我們添加一個計算a的b次方的函數：pow = \a.\b.b (mul a) one，將最后幾行改成：
    let one_to_five = list one (list two (list three (list four (list five empty)))) in
    let one_to_ten = join one_to_five (trans (add five) one_to_five) in
    let long_list = trans (pow two) one_to_ten in
    sum long_list
    這計算2^1 + 2^2 + ... + 2^9 + 2^10。結果太長，不截屏幕了，直接復制出來：

    下面是lambda calculus虛擬機的C++代碼。代碼使用了Vczh Combinator Parser組裝編譯器，然后用一個池來存放運行時需要的東西，速度很快：