我们将研究一种叫作无类型 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, 字符串都可以利用以上实现来实现,此处略。