JavaScript 中的 Lambda 演算

Cover Image

序幕

判定性问题和可计算性

在形式化语言中,如何有效地接收并且验证一个命题的正确性?

邱奇 - 图灵猜想

邱奇 - 图灵猜想是一个关于可计算性理论的假设。该假设论述了关于函数特性的,可有效计算的函数值。简单来说,邱奇 - 图灵猜想认为「任何在算法上可计算的问题同样可由图灵机计算」。

兰布达演算

早在 1936 年,数学家阿隆佐・邱奇(Alonzo Church)就创造了一种称为 Lambda 演算(λ-calculus)的 计算模型 来定义函数。Lambda 演算是一套从数学逻辑中发展,以变量绑定和替换的规则来研究函数如何抽象化定义、如何被应用以及递归的 形式系统。在 Lambda 演算中,他定义了一种叫 邱奇数 的自然数编码。若邱奇数上对应的函数可以被 Lambda 项 表示,则称该函数自然数上 Lambda 可计算(λ-computable)。

The idea that you can describe something as fundamental as natural numbers in a purely functional method is powerful.

本文将结合 JavaScript 来简单介绍 Lambda 演算。

表达式

Lambda 演算是一个基于 Lambda 项 研究函数如何抽象化定义的形式系统。Lambda 项可以是 变量(variable),抽象体(abstraction)或 应用(application)。

变量

即表示数学、逻辑值或参数的字符或字符串变量。如 xx 就是一个 Lambda 项。

抽象体

即函数定义。Lambda 演算中的函数是用 λ\lambda 表示的匿名函数。匿名函数只包含标识符和函数体。若 xx 为变量,EE 为表达式,则称
λx.E\lambda x.E
为一个 抽象体(函数)。其中 xx 是参数标识符,并且 Lambda 项绑定了参数 xx,表达式 EE 是函数体,返回值为 EE 的计算结果。例如 λx.x3\lambda x.x^3 用 JavaScript 表示就是

1
2
3
4
5
function (x) {
return x ** 3;
}
// 进一步的写成箭头函数
x => x ** 3;

应用

函数可以作用于表达式。若 ff 为函数, EE 为表达式,则称 fEfE 为一个 应用,它的输出为 f(E)f(E)。令 f=λx.x3f=\lambda x.x^3
ffE=f(E)=(λx.x3)(E)f
fE=f(E)=(\lambda x.x^3)(E)

再令 E=4E=4
fE=(λx.x3)(E)=x[x:=E]=E3=64fE=(\lambda x.x^3)(E)=x[x:=E]=E^3=64
用 JavaScript 表示就是

1
2
3
cosnt f = x => (x ** 3);
var E = 4
f(E);

多参与柯里化

通过抽象体的定义可知:在 Lambda 演算中,抽象体只接受一个参数。通过多重应用,即让函数返回一个函数才能让函数得到多个参数。有这么一个多参函数

f(x,y)=x+yf(x,y)=x+y
我们一般习惯写作

1
const f = (x, y) => (x + y);

在 Lambda 演算中,我们需要先定义一个接受参数 xx 的函数,这个函数将返回另一个函数,再由返回的函数接受参数 yy。这个函数可以写作

λx(λy.(x+y))(λx.(λy.(x+y)))(1926)=x[x:=1926]=λy.(1926+y)(λy.(1926+y))(817)=y[y:=817]=2743\begin{aligned}
& \lambda x(\lambda y.(x+y)) \
\Rightarrow & (\lambda x.(\lambda y.(x+y)))(1926)=x[x:=1926]=\lambda y.(1926+y) \
\Rightarrow & (\lambda y.(1926+y))(817)=y[y:=817]=2743
\end{aligned}

用 JavaScript 写作

1
2
const f = x => (y => (x + y));
f(1926)(817);

这种把接受多个参数的函数变换成接受一个单一参数(最初函数的第一个参数)的函数,并且返回接受余下的参数并回结果的新函数的技术就称为 柯里化(currying)。类似地,我们可以写出一个柯里化的快速幂:

1
2
3
4
5
6
7
8
const mod = 998244353;

var qpow = a => (b => {
var ans = 1;
for(; b; b >>= 1, a = a * a % mod)
if(b & 1) ans = ans * a % mod;
return ans;
});

邱奇编码

Lambda 演算可以用函数构建数据和算术。邱奇编码(Church encoding)是把数据和运算符嵌入 Lambda 演算的一种方式。通过邱奇编码,其他符号系统中通常被认定为 基本的项(整数、布尔值、有序对、列表等)都会被映射到 高阶函数。在无类型(untyped) Lambda 演算中,函数是唯一的原始类型。

邱奇数

在 Lambda 演算中有多种方式定义自然数,最常见的方式是 邱奇数(Church numerals)。邱奇数是使用邱奇编码的自然数表示法,它的定义如下:

自然数 函数定义 Lambda 表达式
00 0fx=x0fx=x 0=λf.λx.x0=\lambda f.\lambda x.x
11 1fx=f(x)1fx=f(x) 1=λf.λx.fx1=\lambda f.\lambda x.fx
22 2fx=f(f(x))2fx=f(f(x)) 2=λf.λx.f(fx)2=\lambda f.\lambda x.f(fx)
33 3fx=f(f(f(x)))3fx=f(f(f(x))) 3=λf.λx.f(f(fx))3=\lambda f.\lambda x.f(f(fx))
\vdots \vdots \vdots
nn nfx=fnxnfx=f^nx n=λf.λx.fnxn=\lambda f.\lambda x.f^n x

邱奇数的「值」等价于参数被函数包裹的次数,或者说自然数 nn 会将 ff 执行 nn 次。于是我们可以用 JavaScript 将 1 表示出来

1
2
3
4
const print = console.log;

var one = f => (x => f(x));
one(print('LambdaScript'));

这样 LambdaScript 会被打印 1 次,代表 1。

邱奇数的运算

邱奇数可以进行四则运算。

加法

由上表易知

fm+nx=fm(fnx)=mf(nfx)m+n=λm.λn.λf.λx.mf(nfx)\begin{aligned}
& f^{m+n}x=f^m(f^nx)=mf(nfx) \
\Rightarrow & m+n=\lambda m.\lambda n.\lambda f.\lambda x.mf(nfx)
\end{aligned}

写成 JavaScript 就是

1
2
3
function plus(n, m) {
return f => (x => m(f)(n(f)(x)));
}

乘法

由上表易知

fmnx=(fm)n=mf(nfx)mn=λm.λn.λf.n(mf)\begin{aligned}
& f^{mn}x=(f^m)^n=mf(nfx) \
\Rightarrow & mn=\lambda m.\lambda n.\lambda f.n(mf)
\end{aligned}

写成 JavaScript 就是

1
2
3
function mult(n, m) {    
return f => (x => m(n(f))(x));
}

实践

下面我们来看廖雪峰的例子

很久很久以前,有个叫阿隆佐・邱奇的帅哥,发现只需要用函数,就可以用计算机实现运算,而不需要 0123 这些数字和 +-*/ 这些符号。
JavaScript 支持函数,所以可以用 JavaScript 用函数来写这些计算。来试试:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
"use strict";
const print = console.log;

var zero = f => (x => x);
var one = f => (x => f(x));

function plus(n, m) {
return f => (x => m(f)(n(f)(x)));
}

function mult(n, m) {
return f => (x => m(n(f))(x));
}

var two = plus(one, one);
var three = plus(one, two);

var six = mult(two, three);

(six(() => { // f
print('Lambda rules.');
}))(); // x

// Lambda rules. 被打印 6 次

参考资料

本站所有原创内容采用 CC-BY-NC-ND 4.0 International 协议进行许可,附加条款亦可能应用。部分非原创内容版权为 上海アリス幻楽団黄昏フロンティア 等同人创作者所有。

笔记 数学

评论

您需要成为穿墙的邪仙以加载 Disqus。