不动点组合子Y-Combinator

发表于 |

不管怎样，可以把 lambda 当做一个匿名函数来看待，那么这个匿名函数如何在递归调用的时候引用自己呢？Haskell B. Curry给出了Y不动点组合子(Y Combinator，当然不是那个著名的公司啦)可以解决这个问题。在本文中：

  1. 基于 Haskell 如何在匿名函数中调用自己
    1. 在其他语言中，如何解决 Lazy Evaluation 的问题
    2. 自定义的 fix 中，如何避免递归调用 fix
  2. 基于 Python 的 Demo
    1. Python 如何在匿名函数中调用自己
    2. Python 中的 Y Combinator
    3. Z Combinator
  3. 基于 C++ 的 Demo
  4. 为什么通过找不动点可以解决自我调用的问题
    1. 什么是不动点
    2. 不动点和本问题的联系
  5. 简单的 lambda 演算
  6. 证明 Y-Combinator 的性质 Y f = f (Y f)
    讨论 Y-Combinator 的类型

基于 Haskell 的 demo

1
2
fix f = f (fix f)
fact = fix $ \ f n -> if (n == 0) then 1 else n * f (n - 1)

这里的 fact 的签名依然是 fact :: (Eq p, Num p) => p -> p。

fix 函数和递归

fix 定义如下

1
fix f = let {x = f x} in x

可以直接import

1
:m Control.Monad.Fix

可以直接用它来实现不动点组合子

1
fix (\self n -> if n == 0 then 1 else n * self (n-1)) 5

对于一个发散函数，它的不动点是 _|_。

1
2
Prelude> (2+) undefined
*** Exception: Prelude.undefined

注意到，对于有的函数，例如 (*3)，是存在不动点0的，但是 fix (*3) 仍然发散。这是因为 fix 找的是 least-defined 的不动点。

可以用 fix 函数来解方程

1
2
fix (\next guess tol val -> if abs(guess^2-val) < tol then guess else
                     next ((guess + val / guess) / 2.0) tol val) 2.0 0.0001 25.0

这有两个问题

  1. 只能 lazy evaluation
  2. fix 的定义是递归的
    如下所示，我们的 Y 函数满足 fix 的要求，但是它定义中出现了 Y 自己，而这在一些语言中是不被允许的

如何解决 lazy evaluation 问题

通过η-变换。
为了防止下面代码中的 Y f 被 eager 计算

1
2
3
4
5
6
7
8
9
10
11
12
(define Y
  (lambda (f)
    (f (Y f))))

(define F
  (lambda (f)
    (lambda (n) 
      (cond
        ((eq? n 0) 1)
        (else (* n (f (- n 1))))))))
 
(define fact (Y F))

我们对 Y f 做η-变换。这里注意到 Y f 是 Int -> Int

1
2
3
(define Y
  (lambda (f)
    (f (lambda (x) ((Y f) x)) )))

但这个定义中，同样无法避免递归调用 Y

如何解决递归调用Y

通过引入 Curry 的 Y-Combinator 的定义，即

1
Y = λf.(λx.f (x x)) (λx.f (x x))

基于C++的demo

基于Python的Demo

Python 中的 lambda 用起来还是很爽的，不过坑也有很多，比如说这个early binding和late binding的问题，或者 lambda 中只能有一个语句(实际上是表达式)。

考虑计算阶乘函数，Python 可以很容易写出下面的代码：

1
factor = lambda x: 1 if x <= 1 else x * factor(x - 1)

注意到在 lambda 中存在对自己的引用 factor。不过对于某些其他的语言，例如C#或者 Rust，则不存在这样的机制。于是我们希望有一个类似 this 指针的东西，能够在 lambda 函数体中用来表示自己。

简易做法

想一想，核心是如何在函数内部引用自己。一个简单的方案是把自己作为参数传进来

1
fac = lambda self, x: 1 if x <= 1 else x * self(self, x - 1)

可以按照下面的方式调用

1
fac(fac, 3)

可以编译的原因是：

  1. 最先开始被当做参数传进来的 fac 实际上是有定义的
  2. Python 可以自己推导类型
    考虑 C++，如果一个函数 fac 接受自己作为参数，它的类型是什么呢？不如假设内部 fac 的类型是 F，则外部 fac 的类型是 (F,int) -> ()，如果再套一层就是 F((F,int) -> (), int) -> ()。

太丑了

解决方案

太丑了，能不能去掉self这个参数呢？

1
fact = lambda x: fac(fac, x)

这样就OK了。我们还可以用柯里化把这个 fac 提出来

1
2
3
fac = (lambda self: lambda x: 1 if x <= 1 else x * self(self)(x - 1))
fact = fac(fac)
fact(10) # 3628800

fac(fac) 结构引起了我们的兴趣：

  1. 为啥一个函数会接受自己作为参数？
    稍后可以看到，目的是为了在函数体里面干掉 f，实现递归。
  2. 为什么这个函数是递归的？
    因为 fac 本身是递归的了，但我们直接用的话需要传两个参数，很麻烦。

下面来解释这个做法。

原理1：实现递归

这里 f 是一个很典型的递归函数，调用 f 会产生对 f 的无限递归。

1
2
3
def f():
    print("in f")
    return f()

可以通过返回一个 lambda 来实现 lazy evaluation。如果按照 f()()()() 进行调用，每一次调用会打印一行。

1
2
3
def f():
    print("in f")
    return lambda: f()

原理2：在函数体内干掉f

我们对下面的代码调用 f(f)，会打印一次。调用 f(f)() 会打印两次。这个函数和上面实现的效果是一样的，但是函数体里面没有 f 了

1
2
3
def f(g):
    print("in f")
    return lambda: g(g)

总结

现在实现递归分为两步：

  1. 递归函数主体 fac
    定义如下，其中 F 是函数的具体实现，在这里面引用 self 就等于引用 fac 自己。

    1
    fac = lambda self: F

  2. 封装fac

    1
    fact = fac(fac)

但是现在还有缺憾，就是得一开始 fac(self) 一下，另外我们多一个 fac(fac) 这种让人感觉很奇怪的封装。

Y-Combinator 的实现

Eager 版本

1
2
3
4
def Y(F):
    f_gen = lambda self: F(self(self))
    # will eager evaluated
    return f_gen(f_gen)

Lazy 版本

1
2
3
gen2_lazy = (lambda g:
  ( lambda self: g(self(self)) )
  ( lambda self: g(self(self)) ))

通过Z-不动点来美化

首先，可以提出来一个gen

1
2
gen = lambda f: f(f)
fact = gen(lambda self: lambda x: 1 if x <= 1 else x * self(self)(x - 1))

然后研究去掉 fac(fac)，也就是我们需要一个函数gen2，满足

1
fact = gen2(lambda self: lambda x: 1 if x <= 1 else x * self(x - 1))

这个 gen2 就是

1
gen2 = lambda g: gen(lambda self: g(lambda y: self(self)(y)))

理解的最好方式是自己带入算一算。
首先用 beta 做代换，得到

1
2
fact = (lambda g: gen(lambda self: g(lambda y: self(self)(y)))) (g)
     = gen(lambda self: g(lambda y: self(self)(y)))

此时不能像下面一样 beta 代换把 gen 也消掉，这样是结束不了这个代换的。而是把 g 进行代换

1
fact = gen(lambda self: (lambda self: lambda x: 1 if x <= 1 else x * self(x - 1)) (lambda y: self(self)(y)))

下面，把 (lambda y: self(self)(y)) 代换，这样可以去掉一个 lambda self

1
fact = gen(lambda self: (lambda x: 1 if x <= 1 else x * (lambda y: self(self)(y))(x - 1))  )

再把 x - 1 带入，发现得到了和开始一样的，带有 self(self) 的式子

1
fact = gen(lambda self: (lambda x: 1 if x <= 1 else x * self(self)(x - 1)) )

其实这就是 Z-Combinator

1
2
3
gen2 = (lambda g:
  ( lambda self: g(lambda y: self(self)(y)) )
  ( lambda self: g(lambda y: self(self)(y)) ))

通过引入不动点解决问题

不动点的数学定义

如果 f(x) = x 那么 x 是 f 的不动点，即不动点指那些被函数仍然映射到自身的点。当然并不是所有函数都有不动点，因为上面给出的方程不一定有解。

容易发现不动点和我们的问题之间有关联。比如设 g 是一个函数，那么 f(g) 的结果是 g，发现还是一个函数。

进一步地，有 g(f(g)) = f(g)。可是这个式子是如何和“自己调用自己”扯上关系的呢？

从不动点的视角回顾Demo

继续来看阶乘这个例子

1
fac = lambda self: 1 if x <= 1 else x * self(x - 1)

我们将 fac 柯里化，得到 F。这里的 F 看做是接受参数 self，并且返回一个用来计算阶乘的函数。

1
F = lambda self: lambda x: 1 if x <= 1 else x * self(x - 1)

从最里面函数的角度：self就是自己(即lambda x:...)，但是从外面被传进来的。
从最外面的角度：F是已知的，因为它是被定义出来的。，先需要传一个 self 进去，但我们又不知道 self 是啥。
如何知道 self 是什么呢？注意到 F(self) 实际上就是 lambda x:...，即 self。所以，实际上F和self构成下面的方程：

1
F(self) = self

因此这个 self 函数实际上就是 F 的不动点。借助于 Y 不动点组合子，可以求得不动点。因为它满足下面的特性：对于任意的函数F，存在Y F是F的不动点。也就是如下所示

1
F (Y F) = (Y F)

也就是说，在需要访问 self 的时候，Y F 便是了。这样也同时甩掉了 F 的两参数的包袱，因为：

  1. 在使用时，可以直接令 self(10) 这样调用
  2. 但在定义时，又能获取到参数 self

lambda演算简介

为了能够将上面的数学思路推广到lambda中，首先需要简单了解lambda演算(Lambda Calculus)。lambda演算是图灵完备的，邱奇利用lambda演算证伪了可判定性问题。

形式化定义

lambda演算文法非常简单，只由下面三个lambda term组成

  1. 引用标识符(Variable)
    $a$

  2. 定义函数(Abstraction)
    $(\lambda x. M)$，括号可省略。
    此时变量$x$被绑定到了这个lambda表达式，而这个绑定的作用域便以括号为界。

  3. 应用函数(Application)
    $(M \, N)$
    在lambda演算中函数作用是左结合的，即 $s\,t\,x$ 实际上是 $(s\,t)x$。
    例如 $\omega$ 组合子 $\lambda x.x\,x$，它可以被看做 $(\lambda x.x) (x)$，而不是$\lambda x.(x\,x)$。

括号

lambda演算中的括号在无歧义的情况下是可以省略的。因此式子$(\lambda x.x \, x)(\lambda y.y)$可以写成$\lambda(x.x\,x) \lambda y.\,y$。
式子$\lambda x.((\lambda x.x)x)$和式子$(\lambda x.(\lambda x.x))x$并不能作为同一个lambda term。其中第一个式子中外面的lambda是返回的一个值，而第二个式子中外面的lambda是返回的一个lambda。

绑定

一个合法的 lambda 函数不应当出现自由变量。如 $\lambda x.(x\,y)$ 中，$x$ 是被绑定的，但是 $y$ 没有被绑定到在表达式中的任何一个 $\lambda$ 上。

lambda演算规则

首先定义$E[V:=W]$，这表示一个表达式$E$，这个表达式中的所有$V$的自由出现都替换成$W$。

α-转换(Alpha equivalence)

这个变换的意义是被绑定变量的名称是不重要的，所以我们可以用任何的其他名字来替换，其定义为$\lambda V.E = \lambda W.E[V:=W]$。
当然，前提是首先要是被绑定的，我们看前面的一个例子$\lambda x.x\,x$，它相当于$(\lambda x.x) (x)$。这里面有两个$x$，但这两个变量却不是一个变量，因为只有前一个变量被绑定到了$\lambda$上，而后一个是自由变量

β-归约(Beta reduction)

这个类似于C等语言中的传参，或者数学里面的代入。其定义是 $\lambda x.t$ 能够归约成 $t[x:=s]$，这个 beta reduce 过程表示为 $(\lambda x.t)s \rightarrow t[x:=s]$。在这时，相当于我们将 $x$ 的值赋为了 $s$。这个过程必须要确保 $E’$ 再替换后仍然是自由的。

绑定与自由

例如 $\lambda z.(\lambda x . x + z)(x + 2)$，和我们在 α-转换中看到的例子一样，$(\lambda x . x + z)$ 中出现的 $x$ 是绑定的，但是 $x + 2$ 中的却是自由的，因此不能直接把这个自由的 $x$ 代入到绑定的 $x$ 里面去。
如对于任意的“自变量” $s$，有 $(\lambda x.x)s \rightarrow x[x:=s] = s$，因此该函数是个恒等函数。又如 $(\lambda x.y)s \rightarrow y[x:=s] = y$，这说明 $\lambda x.y$ 是个常量函数。

通常形式

beta可归约式(redex)具有以下的形式$((\lambda x.A(x))t)$。例如$(\lambda x.x\,x)(\lambda y.z) \leftarrow (\lambda y.z)(\lambda y.z)$
对于无类型的lambda演算来说，这个规约过程还可能是无法终止的。考虑下面的$\Omega$算子$\Omega = (\lambda x.x\,x)(\lambda x.x\,x)$

$$
\begin{equation}\begin{split}
& (\lambda x.x\,x)(\lambda x.x\,x) \\
\rightarrow & (x\,x)[x:=\lambda x.x\,x] \\
= & (x[x:=\lambda x.x\,x])(x[x:=\lambda x.x\,x]) \\
= & (\lambda x.x\,x)(\lambda x.x\,x)
\end{split}\end{equation}
$$

η-变换(Eta conversion)

η-变换体现了外延性(extensionality)的思想，即两个数学对象是相等的，如果没有区分它们的检验。对于lambda中的函数来说，如果两个函数对于任意的输入都能产生相同的行为（即返回相同的结果），那么可以认为这两个函数是相等的。
η-变换的一个用途是$\lambda x.f\,x$和$f$是等价的（注意它们不一定性能相同，详见Haskel里有关where的一个例子），只要$x$不是$f$中的自由出现。

Y Combinator的实现

Curry 的 Y Combinator 定义为
$$
Y = \lambda f . (\lambda x. f(x \, x)) (\lambda x. f(x \, x))
$$

我们在前面介绍了 Python 的 Lazy 和 Eager 的实现。

证明 Y Combinator 的性质

下面证明这样的$Y$满足
$$
(Y g) = g (Y g)
$$
首先根据 beta 归约，将函数 $g$ 带入
$$
Y g = (\lambda x . g (x \, x)) (\lambda x . g (x \, x))
$$
下面使用 alpha 法则来修改一下绑定的变量名字，以便后面的带入，有
$$
Y g = (\lambda y . g (y \, y)) (\lambda x . g (x \, x))
$$
下面将所有的 $y$ 替换成 $(\lambda x . g (x \, x))$，也就是将左边的 lambda 应用在右边，这同样是根据 beta 法则
$$
Y g = g ((\lambda x . g (x \, x)) (\lambda x . g (x \, x)))
$$
而后面的又是一个 $Y g$，于是得证。

Y Combinator的类型

下面进一步探究一下为什么这样的构造能得到一个递归。y 接受一个函数，返回这个函数的不动点，因此类型应该是这样的。

1
y :: (a -> a) -> a

把\x -> f (x x)作为一个整体 g，那么 y 的工作就是将 g 作为唯一参数来调用自己，这有点像我们证明停机问题的时候的操作。

1
y = \f -> g g

查看这个 g，它接受一个可调用的 x作为参数，并且做 f (x x) 这样的调用。首先令 x x 的类型是 a，即

1
x x :: a

则有

1
x :: b -> a

其中 a，b 为未知类型。在另一方面，我们还能推导出

1
b :: b -> a

这因为作为函数来考虑 x，它接受一个 b 类型的 x 作为参数，而根据前面的式子 x 又具有类型 b -> a，所以可以得出 b 的类型是 b -> a。因此这个类型是递归类型。

递归类型

List 就可以看做一种递归类型。

1
data List a = Nil | Cons a (List a)

在函数式语言例如 Haskell/OCaml 中，递归是不能以 type synonyms 的形式来实现的，例如下面这些使用**type**的语句是不合法的。我们可以简单地想象在 C++ 里面的 typedef 关键字定义的“类型”，在实际上他们并不是真正的类型，而是 alias 构成的语法糖。如果使用这样的定义，那么在编译时就会因为简单的替换而导致死循环的发生

1
2
type Bad = (Int, Bad)
type Evil = Bool -> Evil

解决之道就是按照下面的方式去新建一个ADT(Algebraic data type)

1
2
data Good = Pair Int Good
data Fine = Fun (Bool->Fine)

Reference

  1. https://lptk.github.io/programming/2019/10/15/simple-essence-y-combinator.html
    根据这篇文章，增加了Demo，使得通俗易懂
  2. https://zhuanlan.zhihu.com/p/34526779
    讲述不动点相关知识
  3. https://en.m.wikibooks.org/wiki/Haskell/Fix_and_recursion
    Haskell中的Fix函数和递归
  4. https://yongweiwu.wordpress.com/2014/12/14/y-combinator-and-cplusplus/
    YC的C++实现