函数式编程

目录

#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

这是学到精髓了(确信。


未完待续…

Reference

  1. Functional programming - Wikipedia
  2. Lambda calculus - Wikipedia
  3. $\lambda$演算 - 函数式语言的起源 - 知乎
  4. 神奇的$\lambda$演算 - 简书
  5. Essentials: Functional Programming’s Y Combinator - Computerphile
  6. Fixed-point combinator - Wikipedia