是 $\lambda$ 演算不是入演算[滑稽]

简介

lambda 表达式可以简单理解为匿名函数。

现在不少语言都加入了 lambda 表达式。就连名词王国 Java 也忍不住参与了。

一个普通的送命函数

1
2
3
4
int Plus(int x)
{
  return x + 1;
}

用 Java 中的 lambda 表达式是这样的

1
x -> x + 1

用 JavaScript 中的 lambda 表达式是这样的

1
x => x + 1

用 Scheme 中的 lambda 表达式是这样的

1
(lambda (x) (+ x 1))

用 C++ 中的 lambda 表达式是这样的（没错就是要和别的妖艳贱货不一样）

1
[=](int x){return x + 1;};

使用 lambda 表达式能够方便函数的创建，传递，返回等，大大方便了编程，就不说某不思进取语言之前只能传递匿名类的故事了。

实际上 lambda 表达式源于 $\lambda$ 演算。

对编程有基本了解的人都应该知道图灵机，图灵机是目前能实现的最强计算模型。图灵机的运算是读写头在纸带上运动，可以说是非常工程派了。相应地，学术派中用于研究计算的是 $\lambda$ 演算，它拥有图灵机一样的运算能力。

语法

$\lambda$ 演算的语法定义为

1
2
3
<exp> ::= <var>
<exp> ::= (λ<var>.<exp>)
<exp> ::= (<exp> <exp>)

第一条是变量抽象，即一个 $\lambda$ 项可以是一个变量。

第二条是函数抽象，即一个 $\lambda$ 项可以接收一个变量，返回一个 $\lambda$ 项。

第三条是函数应用，即一个 $\lambda$ 项可以应用一个 $\lambda$ 项。

比如对于 JavaScript 的 lambda 表达式 x => x + 1 可以表示为 $\lambda x. x + 1$ 。（假设 + 和 $1$ 都是良定的）。

第二条函数抽象限制了函数只有一个参数，那么遇到多个参数怎么办呢？

这里需要用到老生常谈的柯里化。

简单的说是将多参函数转化成多个单参函数的组合。

例如对于 (x, y) => x + y 相应的 $\lambda$ 项是 $\lambda x. (\lambda y. x + y)$ 。

为了手写方便，可以省略括号 $\lambda x . \lambda y . x + y$ 。

再次为了手写方便，可以省略为 $\lambda x y . x + y$ 。

规约

光有语法肯定是不够的。还需要规约规则。

$\lambda$ 演算有三条规约规则。

$\alpha$ 替换（重命名）：替换被绑定变量不改变结果。如 $\lambda x. x + 1$ 和 $\lambda t . t + 1$ 是一样的。类似于编程语言中的函数参数重命名。

$\beta$ 规约（函数应用）：函数应用为函数形参替换为实参的过程。如 $((\lambda x. x + 1) 2)$ 的结果为 $2 + 1 = 3$ 。类似于编程语言中的函数应用。

$\eta$ 转换（外延性相等）：两个函数对于所有的参数得到的结果都一致。之所以称为外延性相等是如果把两个函数当作黑盒，那么它们是一致的。如果查看黑盒中的内容就会发现内容可能不一样。如 $\lambda x . f x$ 与 $f$ 外延性相等。举一个 JavaScript 的例子

1
2
3
[1,2,3].forEach(x => console.log(x))
// 外延性相等于
[1,2,3].forEach(console.log)

例子

说了那么多可能只是知道一些概念，可以在线运算一些例子来加深理解。

想要更加深入了解可以前往维基百科。