深入lambda演算

最顶级的抽象！

id函数

实际上，前文我们讨论的id函数，表明了一种态度。任意的数据都是函数

// λx.x
const id = x => x;

也就是说这里的x 也是一个函数，我们将使用函数的方式，推导我们所有的程序（lambda演算和图灵状态机是等价的，一个用状态转移演算「计算」，一个用函数推演、归约来演算「计算」）

逻辑运算

最基本的演算是逻辑演算，它需要定义两个基元。

• True
• False

然后我们可以用逻辑基本量来表示一些运算

• 与 a && b
• 或 a || b
• 非 ~a

基元

现在，我们尝试用函数（演算式）表示逻辑基本量，并通过归约得到更多的操作符。

// λx.λy.x
const True = x => y => x;
// λx.λy.y
const False = x => y => y;

我们用函数表示了True和False的概念。True得到两个参数，但永远只取第一个，False得到两个参数，但永远只取第二个。注意：这里的x和y可以是任意数据，就像我们在前文说的，在lambda演算中我们不关心数据本身，只关心这种「抽象形式」。虽然大多数情况下我们的数据都是「函数」。

逻辑与

再次声明，我们只关注这种「抽象形式」。逻辑与是这样的

• True True -> True
• True False -> False
• False True -> False
• False False -> False

在这个逻辑世界里，我们只能使用基元：True和False。

// λb1.λb2.b1 b2 b1
const And = b1 => b2 => b1(b2)(b1);

console.log(And(True)(False)); // False
console.log(And(True)(True)); // True
console.log(And(False)(True)); // False
console.log(And(False)(False)); // False

逻辑与And操作，得到两个参数，他们都是基元类型（布尔值）。这里的运算很巧妙，我们调用第一个基元，给他传入两个操作，当他本身为True时，返回第二个参数（True的性质），当他本身为False时，返回他自己（False）。

如果看不明白，建议再多看几次，或者在浏览器里面跑一下上面的代码。

这样我们就得到了一个逻辑与操作。

逻辑非

逻辑或和逻辑与类似，我们需要表示这种运算规则

• True False -> True
• True True -> True
• False True -> True
• False False -> False

参照逻辑与的代码，可以得到

// λb1.λb2.b1 b1 b2
const Or = b1 => b2 => b1(b1)(b2);

console.log(Or(True)(False)); // True
console.log(Or(True)(True)); // True
console.log(Or(False)(True)); // True
console.log(Or(False)(False)); // False

如果不明白，可以跑一下这段代码。

逻辑非

逻辑非是一个一元运算。一元运算指的是运算符只操作一个数据，而上面的逻辑与和逻辑或都需要两个数据参与，是二元运算。

既然是一元运算，就只需要用到基元就行了。

// λb.b False True
const Not = b => b(False)(True);


console.log(Not(True)); // False
console.log(Not(False)); // True

直接调用参数（是的，你可以理解为我们在进行归约了。），给两个参数值设置相反数据。非常棒！

条件运算

你还在惊讶函数能表示逻辑运算吗？函数不仅能做这件事，它还能表示条件运算。

在JavaScript中，我们这么做。

function Condition(bool, left, right) {
       return bool ? right : left;
}

还记得monad的时候我们讲Either吗？现在我们推演一下Either。

// λb.λleft.λright.b left right
const Either = b => left => right => b(right)(left);

const Left = x => console.log('error:', x);
const Right = x => console.log('success:', x);


console.log(Either(True)(Left)(Right)); // Left
console.log(Either(False)(Left)(Right)); // Right

非常棒！这样的流程，就是在做lambda演算了。

但你还需要注意，我们现在所有的演算都是「抽象形式」，是在一个抽象的概念内运算的，我们不关心x、y、left、right等演算参数究竟是什么，但我们的归约行为，可以一直进行下去。

程序既然可以用状态机来表示，那么，我们现在也能用λ表示了！

计算

终于涉及到「计算」了。小孩子学习自然数都是从1开始，然后一个数字一个数字地数上去，稍微大一点后，才会在自然数的基础上去学习运算。

注意我刚才说的话

• 数
• 运算

实际上，我们的一个系统，都是由这样的两个概念构成的。

• 集合 = 基本集合定义 + 集合运算
• 自然数 = 基本数字 + 数字运算
• 社会 = 人 + 人与人之间的相互作用
• ...

如何用lambda演算去抽象这种概念？

基元 + 操作！

// λf.λx.x
const Zero = f => x => x;
// λf.λx. f x
const One = f => x => f(x);
// ....
// λf.λx. f...f x
// const N = f => x => f...f(x)

定义一个基本元素x => x，这就是我们的id函数（identity）。定义个操作f不论f表示什么，在自然数里面，它表示+1，在负数里面它表示-1，在阶乘里面，它表示!(n-1)......总之，一个基元，对它重复执行操作，就得到了无数的数据。

这里的抽象仍然有效！我们不断地提取抽象的形式，这种思维方式，让我们不限于去做数字的加减乘除，有这个框架，可以表达一个域的概念！

是的，这会不会让你想起：monad，Just和map就代表了数据和行为，这两个特性。有这两个特性，就可以表示一个范畴（又回到了范畴论）

总结

学函数式编程，有兴趣的，一定要学一下haskell，去体会美！