𝚲

用类型看透 Y Combinator

当 f(x) = x ，称此时的 x 为函数 f 的固定点（Fixed Point）。如果 x 是一个函数呢？

Fixed Point Combinator

“不就是 Y Combinator 嘛， 我知道” 1。

嗯，介绍它的文章确实不少，但容易看懂的应该不多。这次，我另辟蹊径，尝试从类型的视角来剖析 Y Combinator ，看能否让人豁然开朗。

回顾一下 Y Combinator 的无类型 Lambda 演算表达式，如下（此后不再有更多公式）：

Y Combinator

不卖关子，直接上翻译后的 Scala 代码：

type F[A] = A => A
trait X[A] extends (X[A] => F[A])

def Y[A](f: F[A] => F[A]): F[A] = 
  val g: X[A] = x => a => f(x(x))(a)
  g(g)

秒懂的朋友，可略过后文了，若感兴趣验证一下代码的请参阅脚注 2。留下的朋友，请继续跟我来。

破除阅读障碍

看不懂 Y Combinator 的原因，大概率是因为看不懂（无类型的） Lambda 演算语法。为方便后文理解，以下语法翻译小抄请记牢：

那么，Y Combinator 若翻译成 Javascript 就是 3：

const Y = f => (x => f(x(x)))(x => f(x(x)))

自应用函数 4

Y 是什么类型，很难判断。不妨从 f 和 x 这两个相对简单的函数入手先。假定，f 的类型为 F，参数和返回值类型不详，暂且用 Any 表示：

scala> type F = Any => Any
// defined alias type F = Any => Any

x 的类型 X 就有点让人挠头了，它 自己 依赖 自身 作为参数。硬着头皮可以这么声明：

scala> type X = X => Any
-- [E140] Cyclic Error: ------------
1 |type X = X => Any
  |     ^
  |illegal cyclic type reference: 
  |  alias X => Any of type X refers
  |  back to the type itself
1 error found

意思是这么个意思，可惜编译器不接受这样的类型别名（alias）声明。编译器可接受的等价形式是这样的：

scala> trait X extends (X => Any)
// defined trait X

由此，我们可以尝试将 Y Combinator 翻译成 Scala，来看看 Y 的类型：

scala> def Y(f: F) = 
     |   val g: X = x => f(x(x)) 
     |   g(g)
     | 
def Y(f: F): Any

其中的 g 相当于给后面 X 的表达式起了个别名，这样代码看着更简洁。最后一行，编译器已经推断出 Y 的完整类型表达了。

注意，根据 f(x(x))，可知 x 的返回值是要作为 f 的参数的，这二者的类型必然是 一致 的。显然，Any 是不足以采信的。因此，我需要将这个类型参数化，以做到严谨的表达。

scala> type F[A] = A => A
     | trait X[A] extends (X[A] => A)
     | 
     | def Y[A](f: F[A]) = 
     |   val g: X[A] = x => f(x(x)) 
     |   g(g)
     | 
// defined alias type F[A] = A => A
// defined trait X
def Y[A](f: F[A]): A

至此，是不是有点感觉了？Y Combinator 的奥义在于，对「自应用函数」类型 X 的自应用。这样做的价值，从编程的角度来看，就是实现了递归（循环）。

没想通的话，我们就以阶乘函数为例验证一下：

scala> def fact: Int => Int = 
     |   case 1 => 1
     |   case n => n * fact(n - 1)
     | 
def fact: Int => Int

scala> fact(4)
val res1: Int = 24

将其改写为对 Y 的应用：

val fact = Y[Int => Int]: f =>
  case 1 => 1
  case n => n * f(n - 1)

二者区别在于，前者是直接引用自身，后者的参数是自身的代理。

I’m my own granddad…

The Bartender, Predestination (2014) 5

不幸的是，这么改写编译器是扛不住的：

scala> val fact = Y[Int => Int]: f =>
     |   case 1 => 1
     |   case n => n * f(n - 1)
     | 
java.lang.StackOverflowError
  ...

惰性求值

为什么会栈溢出呢？这个问题确实不好解释，不如从解决方案中，我们去逆向理解。

scala> class Lazy[A](f: () => A):
     |   def eval: A = f()
     | 
// defined class Lazy

首先，需要引入 Lazy 来模拟 惰性求值 6。其次，对应地调整 F X Y ：

scala> type F[A] = Lazy[A] => A
     | trait X[A] extends (X[A] => Lazy[A])
     | 
     | def Y[A](f: F[A]) = 
     |   val g: X[A] = x => Lazy:
     |     () => f(x(x))
     |   g(g)
     | 
// defined alias type F[A] = Lazy[A] => A
// defined trait X
def Y[A](f: F[A]): Lazy[A]

最后，调整改写的 fact，回车！

scala> val fact = Y[Int => Int]: f => 
     |   case 1 => 1
     |   case n => n * f.eval(n - 1)
     | 
val fact: Lazy[Int => Int] = Lazy@1c23e369  

scala> fact.eval(4)
val res2: Int = 24

从结果来看，栈溢出是没有了。其中的细节就在 g ：

// stack overflow
val g: X[A] = x => f(x(x))

// ok
val g: X[A] = x => Lazy:
  () => f(x(x))

主流编程语言几乎都是 严格求值 的，这意味着 x(x) 会在 自应用 中无限循环直到栈溢出。而 Lazy 类型的引入，就让 自应用 可按需（延迟）调用。这个按需，就体现在 f.eval(n - 1)。

眼尖的你，可能已经发现了，这一步步剖析得到的代码和最初给出的答案不一样啊。嗯，是不一样，但效果是一样的，不信就自己去试试吧。

写在最后

由此可见，Y Combinator 的实质是，在 向未来借一个「代理」 啊。

不懂，没关系。墙裂推荐这部电影，看过之后再来体会 Y Combinator，必定更生动。

图片来自

  1. https://en.wikipedia.org/wiki/Fixed-point_combinator↩︎

  2. https://scastie.scala-lang.org/zhongl/inj6N2dpQ6eSB5xSAKwVlQ/28↩︎

  3. https://juejin.cn/post/7043748080109223944#heading-16↩︎

  4. 出自我的个人命名，可能不严谨，懂我意思就行。↩︎

  5. https://www.imdb.com/title/tt2397535/quotes/?item=qt4296558&ref_=ext_shr_lnk↩︎

  6. https://en.wikipedia.org/wiki/Lazy_evaluation#Simulating_laziness_in_eager_languages↩︎

  7. https://www.imdb.com/title/tt2397535/mediaviewer/rm2485654785/?ref_=tt_ov_i↩︎