以前为了开发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组装编译器，然后用一个池来存放运行时需要的东西，速度很快：