函数式编程

#00 | 初识Lambda演算
#01 | Lambda演算中的自然数
#02 | Lambda演算中的循环与递归

Lambda演算 #02

在C语言中，循环的实现是基于跳转指令以及状态存储的，对于Lambda演算而言这些是不存在的，那么我们如何实现循环呢？

使用递归实现循环

在理论上而言，任何循环都可以重写为递归形式。我们可以考虑一个最简单的递归——它什么也不做，只是循环：

$loop = loop$

你可以试着去运行它：从左侧开始，于是你转到右侧，它要运行的依然是loop，所以回到左侧，不断继续下去……一直递归下去，然后——什么也不做。

这大概是最简单的递归的例子，那么下一个问题便是——我们如何在Lambda演算中去实现这种行为？这个问题的关键在于：如何将某一函数应用于自身。
首先，我们定义一个有趣的Lambda项：

$\omega := \lambda \ x. x \ x$

它接受一个输入 $x$ ，并将 $x$ 应用到它自身，比如：

$\begin{align*} \omega \ a &= a \ a \\\\ \omega \ I &= I \ I = I \end{align*}$

现在，我们试着对 $\omega$ 应用它自己：

$loop := \omega \ \omega$

让我们看一下它做了些什么。直观上，可以看到这是将 $\omega$ 应用于它自身。而对于 $\omega$ ，它实际上也是这样做的——对于 $x$ ，将其应用于自身。

让我们考虑一下真正去运行它，或者说，展开：

$\begin{align*} loop &= \omega \ \omega \\\\ &= (\lambda \ x. x \ x) \ \omega \\\\ &= \omega \ \omega = loop \\\\ \end{align*}$

结果又回到了起点，这意味着：我们已经创造出了“循环”——即使是最基本的——下一步我们考虑“递归”。

我们考虑一个算子 $rec$ ，他只需要做到如下一点：

$rec \ f = f \ (rec \ f)$

或者，也就是：

$rec \ f = f \ (f \ (f \ (f \ (\dots))))$

这是一个最基本的递归函数，也是可以得到的最基本的递归函数，任何其他的递归函数均可以通过它来得到。所以，如果我们可以在Lambda演算中实现它，我们理论上就可以实现任意其他的递归函数——并且让它们实际做点什么。

Y-Combinator

在数学函数中我们定义不动点为 $x$ ，它满足： $f(x) = x$

类似的，在Lambda演算中，如果 $x$ 与 $F(x)$ 是 $\beta$ 等价的，那么 $x$ 称为 $F$ 的不动点。

$\beta$ 等价的本质上是函数调用——其实你已经使用了很多很多次了，比如 $I \ I$ 就与 $I$ 是 $\beta$ 等价的。

回过头来看 $rec$ 算子的定义——如果将 $rec \ f$ 视为一项，我们想要找到的：

$rec \ f = f \ (rec \ f)$

就是 $f$ 的不动点——因此，我们称 $rec$ 为不动点算子(Fixed-Point combinator)，它可以作用于任意的 $f$ ，并使得 $rec \ f$ 是其不动点。

借助之前关于循环的思想，可以试着自己构造一个不动点算子，我们看一下最为著名的一个，Y-Combinator：

$Y := \lambda f. (\lambda x. f(x \ x))(\lambda x. f(x \ x))$

它是由美国的一个叫做Haskell Curry的数学家发明的，并且用他的名字命名了一种函数式编程语言：Haskell。

至此，利用Lambda演算进行递归的基础便告一段落。简而言之，我们的思想是利用规约——或者说函数调用的过程，在其中复制自身，来达到的递归操作。

不妨用一个简单的阶乘函数举例：

def fact(n):
    return 1 if n == 1 else n * fact(n - 1)

定义：

$\begin{align*} base &= \lambda f. \ \lambda n. \ (IsZero \ n) \ 1 \ (mult \ n \ (f \ (pred \ n))) \\\\ fact &= Y \ base = base \ (Y \ base) = base \ (base \ (base \ (\dots))) \end{align*}$

我们尝试计算一下，为了便于识别，我将每一步最顶级 $base$ 中的 $f$ 所对应的参数标为红色：

$\begin{align*} fact \ 3 &= base \ {\color{red}(base \ (base \ (base \ (\dots))))} \ 3\\\\ &= mult \ 3 \ (base \ {\color{red}(base \ (base \ (\dots)))} \ 2) \\\\ &= mult \ 3 \ (mult \ 2 \ (base \ {\color{red}(base \ (\dots))} \ 1)) \\\\ &= mult \ 3 \ (mult \ 2 \ (mult \ 1 \ (base \ {\color{red}(\dots)} \ 0 ))) \\\\ &= mult \ 3 \ (mult \ 2 \ (mult \ 1 \ 1)) \\\\ &= 6 \end{align*}$

Prefect!

而除了Y-Combinator之外，还有一些不动点组合子：

$\begin{align*} X &:= \lambda f. \ (\lambda x. \ x \ x)(\lambda x. \ f \ (x \ x)) \\\\ \Theta &:= (\lambda x \ y. \ y \ (x \ x \ y))\ (\lambda x \ y. \ y \ (x \ x \ y)) \end{align*}$

另外，其实你可以利用JS以很类似的方式去编写一个阶乘：

var Y = (f) => ((x) => x(x))((y) => f((x) => y(y)(x)));
var fac = Y((f) => (n) => (n > 1 ? n * f(n - 1) : 1));

fac(6);
720;

小插曲

在Reference.5的评论区我看到了如下的内容：

‘if you want to learn more about the y combinator you can look online’
look online
find this video

这是学到精髓了（确信。

未完待续…