以前為了開發(fā)KFP，特別學(xué)習(xí)了一下lambda calculus（也就是我的博客的標(biāo)題啦）。lanbda calculus是一門神奇的語言，在計算機(jī)出現(xiàn)之前就已經(jīng)被搞出來了。這門語言只有三種語法，然后可以用這個語法來構(gòu)造整數(shù)（！！！）、布爾型和很多遞歸數(shù)據(jù)結(jié)構(gòu)等。

    首先介紹一下語法。
    1、func arg代表一個函數(shù)調(diào)用，func是函數(shù)表達(dá)式，arg是參數(shù)。
    2、\param.value代表一個函數(shù)定義，參數(shù)是param，返回結(jié)果value。
    3、(expr)代表expr的優(yōu)先級較高。

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

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

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

    于是我們可以這么定義數(shù)字：
    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)))
    數(shù)字n是一個函數(shù)，這個函數(shù)接受兩個參數(shù)s和z，返回結(jié)果是拿s在z上應(yīng)用n次的結(jié)果。所以我們可以很方便的實現(xiàn)乘法：拿“加法”函數(shù)當(dāng)成第一個參數(shù)傳進(jìn)a，然后去應(yīng)用b，就變成乘法了。我們首先創(chuàng)造一個加1函數(shù)：
    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))進(jìn)行求值的時候，我們得到(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接受兩個參數(shù)返回第一個，false接受兩個參數(shù)返回第二個：
    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
    函數(shù)if cond t f跟cond t f等價，所以我們不需要if函數(shù)。

    接下來怎么實現(xiàn)數(shù)據(jù)結(jié)構(gòu)呢？假設(shè)我們實現(xiàn)一個pair，讓pair 1 2將數(shù)字保存起來，讓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僅需那么幾條語法就可以實現(xiàn)所有東西了。將pair嵌套在一起可以構(gòu)成一個列表。下面我們來寫一個完整的程序，構(gòu)造列表[1,2,3,4,5]，然后對每一個元素求平方后相加：1*1 + 2*2 + 3*3 + 4*4 + 5*5 = 55：

    下面是完整的程序：

    然后是結(jié)果。首先我的lambda calculus虛擬機(jī)把let-in按照上面的方法重新轉(zhuǎn)換為標(biāo)準(zhǔn)的lambda calculus程序，最后求值：

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

    我們添加一個計算a的b次方的函數(shù)：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。結(jié)果太長，不截屏幕了，直接復(fù)制出來：

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