我们将研究一种叫作无类型 lambda 演算（untyped lambda calculus）的极小编程语言。首先，我们将用尽可能少的语言特性写（用 Ruby）一些接近 lambda 演算的程序。

这将仍然仅仅是在用 Ruby 编程，但施加虚构的约束之后，我们便能很轻松地探索一个受限的语义，而不需要学习一门新语言。然后，我们了解到这些非常有限的特性集合能做什么以后，就将利用这些特性把它们实现为一种语言（使用它自己的解析器、抽象语法和操作语义）—— 使用我们在之前章节中学到的技术。

模拟lambda演算

proc
-> x { -> y { x.call(y) } }

问题

写一个程序输出数字 1 到 100。但如果数字是 3 的倍数，就不输出数字而是输出“Fizz” ， 如果是 5 的倍数就输出 “Buzz” 。 对于那些 3 和 5 的公倍数， 就输出 “FizzBuzz” 。

完整特性的 Ruby 实现：

1
2
3
4
5
6
7
8
9
10
(1..100).map do |n|
  if (n % 15).zero?
    'FizzBuzz' 
  elsif (n % 3).zero?     
    'Fizz'   
  elsif (n % 5).zero?     
    'Buzz'   
  else     
    n.to_s   
end

实现数字

描绘数字特征的一种方式是某个动作的重复（或者叫迭代）。

1
2
3
def one(proc, x)
    proc[x]
end
1
2
3
def two(proc, x)
  proc[proc[x]]
end

以此类推。
按照这种模式，可以很自然地把 #zero 定义为一个带有 proc 和另一个参数的方法，这个方法完全忽略 proc（换句话说，对其调用零次） ，并且会原封不动地返回第二个参数。

1
2
3
def zero(proc, x)
   x 
end

把 数 据 表 示 为 纯 代 码 的 技 术 称 为 邱 奇 编 码（Church encoding） ， 它 是 以lambda 演算（http://dx.doi.org/10.2307/2371045）的发明者阿隆佐·邱奇的名字命名的。这些数字是邱奇数（Church numeral） ，而且我们很快将会看到邱奇布尔值（Church Boolean）和邱奇有序对（Church pair）的例子。

实现布尔值

1
2
3
4
5
6
7
def true(x, y)   
    x 
end  

def false(x, y)
   y 
end
1
2
3
4
5
6
7
8
IF =
   -> b {     
       -> x {       
           -> y { 
                   b[x][y]       
            }     
       }   
   }

实现谓词

IS_ZERO = -> n { n[-> x { FALSE }][TRUE] }

有序对

最简单的数据结构是有序对（pair） ，它跟二元数组类似。有序对实现起来非常容易。

1
2
3
PAIR  = -> x { -> y { -> f { f[x][y] } } } 
LEFT  = -> p { p[-> x { -> y { x } } ] } 
RIGHT = -> p { p[-> x { -> y { y } } ] }

数值运算

现在有了数字，布尔值，条件，谓词以及有序对，下面实现数值运算。

递增:
INCREMENT = -> n { -> p { -> x { p[n[p][x]] } } }

我们调用这个新的 proc 的时候它会做什么呢？首先它会以 p 和 x 作为参数调用 n——因为n 是一个数字，所以这意味着就像原始的数字那样， “在 x 上对 p 进行 n 次调用”——然后对结果再调用一次 p。那么总体说来，这个 proc 的第一个参数会在它的第二个参数上调用n+1 次，这恰好是表示数字 n+1 的方法。

递减呢？这看起来是个更难的问题。

一个解决办法就是设计一个 proc，在对某个初始参数调用 n 次的时候返回数字 n-1。幸运的是，有序对正好可以帮助我们实现这种方法。思考一下这个 Ruby 方法所做的：

1
2
3
def slide(pair)   
    [pair.last, pair.last + 1] 
end

在我们用数字组成的二元数组为参数调用 slide 时，它会返回一个新的二元数组，这个二元数组包含第二个数字还有比第二个数字大 1 的数字；如果输入的数组包含的是连续数字，那么效果就是向上“滑动”一个数字窗口：

1
2
3
4
>> slide([3, 4]) 
=> [4, 5] 
>> slide([8, 9]) 
=> [9, 10]

这很有用，因为通过在 -1 处开始一个窗口，我们可以安排一种情况，让数组里的第一个数字比我们调用 slide 的次数小 1，即使我们只是在递增数据 :

1
2
3
4
5
6
7
8
>> slide([-1, 0])
=> [0, 1] 
>> slide(slide([-1, 0])) 
=> [1, 2] 
>> slide(slide(slide([-1, 0]))) 
=> [2, 3] 
>> slide(slide(slide(slide([-1, 0])))) 
=> [3, 4]

我们不能只用基于 proc 的数字完成，因为没法表示 -1，但 side 的有趣之处是不管怎样它只关注数组中的第二个数，因此我们可以放入任意的哑值（dummy value）——比如说0——替换掉 -1，这样仍然能得到同样的结果：

1
2
3
4
5
6
7
8
>> slide([0, 0]) 
=> [0, 1] 
>> slide(slide([0, 0])) 
=> [1, 2] 
>> slide(slide(slide([0, 0]))) 
=> [2, 3] 
>> slide(slide(slide(slide([0, 0])))) 
=> [3, 4]

这是让 DECREMENT 工作的关键：我们可以把 slide 转成一个 proc，使用数字 n 的 proc 表示对由 ZERO 组成的有序对调用 slide n 次，然后使用 LEFT 从结果的有序对中拉出左边的数来：

1
2
SLIDE     = -> p { PAIR[RIGHT[p]][INCREMENT[RIGHT[p]]] } 
DECREMENT = -> n { LEFT[n[SLIDE][PAIR[ZERO][ZERO]]] }

注：DECREMENT[ZERO] 的结果实际上只是最初的 PAIR[ZERO][ZERO] 值的左边元素，在这种情况下根本就没有对其调用过 SLIDE。既然没有负值，0 就是我们能提供给 DECREMENT[ZERO] 的最合理的答案，因此使用 0 作为哑值是个好主意。

有了 INCREMENT 和 DECREMENT，就可能实现类似加法、减法、乘法和取幂这样的数字运算了：

1
2
3
4
ADD      = -> m { -> n { n[INCREMENT][m] } } 
SUBTRACT = -> m { -> n { n[DECREMENT][m] } } 
MULTIPLY = -> m { -> n { n[ADD[m]][ZERO] } } 
POWER    = -> m { -> n { n[MULTIPLY[m]][ONE] } }

其他实现

MOD，map, range, 字符串都可以利用以上实现来实现，此处略。