在Scala中解释Y组合子的实现？

Question

这是Scala中Y组合子的实现方式：

scala> def Y[T](func: (T => T) => (T => T)): (T => T) = func(Y(func))(_:T)
Y: [T](func: (T => T) => (T => T))T => T

scala> def fact = Y {
     |           f: (Int => Int) =>
     |             n: Int =>
     |               if(n <= 0) 1
     |               else n * f(n - 1)}
fact: Int => Int

scala> println(fact(5))
120

问题1：步骤是如何得出结果为120的？由于Y(func)被定义为func(Y(func))，Y应该变得越来越多，那么Y到底去哪了，在执行过程中如何得出120？

问题2：以下两行代码有什么区别？

def Y[T](func: (T => T) => (T => T)): (T => T) = func(Y(func))(_:T)

并且

def Y[T](func: (T => T) => (T => T)): (T => T) = func(Y(func))

在Scala REPL中，它们是相同类型的，但第二个无法打印出结果120？

scala> def Y[T](func: (T => T) => (T => T)): (T => T) = func(Y(func))
Y: [T](func: (T => T) => (T => T))T => T

scala> def fact = Y {
     |           f: (Int => Int) =>
     |             n: Int =>
     |               if(n <= 0) 1
     |               else n * f(n - 1)}
fact: Int => Int

scala> println(fact(5))
java.lang.StackOverflowError
  at .Y(<console>:11)
  at .Y(<console>:11)
  at .Y(<console>:11)
  at .Y(<console>:11)
  at .Y(<console>:11)

- liango

Answer 1

首先，需要注意的是这不是一个Y-组合器，因为该函数的lambda版本使用了自由变量Y。尽管如此，这仍然是正确的Y表达式，只是不是组合器。

接下来，我们将计算阶乘的部分放入一个单独的函数中。我们可以称之为comp：

def comp(f: Int => Int) =
  (n: Int) => {
    if (n <= 0) 1
    else n * f(n - 1)
  }

阶乘函数现在可以这样构建：

def fact = Y(comp)

问题1：

Y被定义为func(Y(func)). 我们调用fact(5)，实际上是调用Y(comp)(5)，而Y(comp)会被求值为comp(Y(comp))。这是关键点：我们在此停止，因为comp接受一个函数并且只有在需要的时候才对其进行求值。所以，运行时将comp(Y(comp))看作comp(???)，因为Y(comp)部分是一个函数，只有在（如果）需要时才会被求值。

你了解Scala中的按值调用和按名调用参数吗？如果你将参数声明为someFunction(x: Int)，它将在someFunction被调用时立即求值。但是如果你将其声明为someFunction(x: => Int)，那么x将不会立即求值，而是在使用它的时候求值。第二个调用是“按名调用”，它基本上将x定义为“一个不带参数并返回Int的函数”。因此，如果你传入5，实际上是传递一个返回5的函数。这样我们就实现了函数参数的惰性求值，因为函数在使用时才被求值。

因此，comp中的参数f是一个函数，因此只有在需要时才会评估它，这是在else分支中。这就是为什么整个过程能够工作- Y可以创建一个无限的func(func(func(func(…))))链，但该链是惰性的。每个新链接仅在需要时计算。

因此，当您调用fact（5）时，它将通过主体运行到else分支，并且仅在那一点上f将被评估。不是之前。由于您的Y将comp（）作为参数f传递，因此我们将再次进入comp（）。在comp（）的递归调用中，我们将计算4的阶乘。然后我们再次进入comp函数的else分支，从而有效地进入另一层递归（计算3的阶乘）。请注意，在每个函数调用中，您的Y将comp作为参数提供给comp，但仅在else分支中进行评估。一旦我们到达计算0的阶乘的级别，if分支将被触发，我们将停止进一步向下深入。

Q2：

这个

func(Y(func))(_:T)

是这个的语法糖

x => func(Y(func))(x)

这意味着我们将整个内容包装成了一个函数。这样做并没有损失任何东西，只有收益。

我们获得了什么？好吧，这就是前面问题的答案所使用的技巧；通过这种方式，我们实现了func(Y(func))只在需要时才被评估，因为它被包装在一个函数中。这样我们就避免了无限循环。将（单参数）函数f扩展为函数x => f(x)称为eta扩展（您可以在这里阅读更多相关内容）。

下面是另一个简单的eta扩展示例：假设我们有一个方法getSquare()，它返回一个简单的square()函数（即，计算一个数的平方的函数）。我们可以返回一个接受x并返回square(x)的函数，而不是直接返回square(x)：

def square(x: Int) = x * x
val getSquare: Int => Int = square
val getSquare2: Int => Int = (x: Int) => square(x)

println(square(5)) // 25
println(getSquare(5)) // 25
println(getSquare2(5)) // 25

希望这能帮到你。

- slouc

---

这个答案完全是错误的，不幸的是。因为Y(comp)部分是一个函数，只有在需要时才会被评估。→ 这不是函数的工作方式。Y(comp)会立即被评估，并且它会评估为一个闭包（因为使用了(_)进行了η-展开），然后等待被调用。 - Clément

你提到了“在Scala中了解过按值调用和按名调用参数吗？”，但是在这个例子中根本没有按名调用参数。 - Clément

这样我们就实现了函数参数的惰性求值，因为函数在使用的时候才会被计算。再次强调，这不是函数的工作方式。试一下这个例子：def makeAFunction(): Int => Int = { println("Hi!"); x => x } def comp(f: Int => Int): Unit = () println(comp(makeAFunction())) → comp忽略了传入的函数参数，但它仍然被求值了。 - Clément

我尝试在另一个答案中逐步展示发生的情况。 - Clément

我们正在讨论完全相同的事情，两个答案都是一样的。唯一的区别是我做了两个简化：1.说函数不会立即求值，而实际上它们会被 eta 扩展成闭包，就像你说的那样。2.使用按名调用作为解释函数发生的另一种方式（将类型 => A 视为 () => A，这与 eta 扩展有关）。回想起来，我同意我不应该提到按名调用和按值调用，因为这可能会引起困惑，特别是因为我们在提供的代码中没有使用它。 - slouc

Answer 2

补充接受答案：

首先需要注意的是，这不是一个Y组合子，因为lambda函数版本使用了自由变量Y。虽然它是正确的Y表达式，但并不是一个组合子。

组合子不允许显式递归；它必须是一个没有自由变量的lambda表达式，这意味着它不能在定义中引用自己的名称。在lambda演算中，不可能在一个函数体内引用函数的定义。递归只能通过将函数作为参数传递来实现。

基于此，我从Rosetta Code复制了下面的实现，使用了一些类型技巧来实现无需显式递归的Y组合子。请参见此处

  def Y[A, B](f: (A => B) => (A => B)): A => B = {
    case class W(wf: W => A => B) {
      def get: A => B =
        wf(this)
    }
    val g: W => A => B = w => a => f(w.get)(a)

    g(W(g))
  }

希望这有助于理解。

- Gagandeep Kalra

---

我现在才看到这个额外的回答 - 真棒！ - slouc

Answer 3

很遗憾，接受的答案完全错误。函数参数并没有什么神奇之处；特别是，默认情况下它们不是按名称或惰性求值的。让我们来看一下你的代码，稍作修改以提高可读性：

def Y[T](F: (T => T) => (T => T)): (T => T) =
  t => F(Y(F))(t)

def F(f: Int => Int)(n: Int) =
  if (n <= 0) then 1 else n * f(n - 1)

val fact = Y(F)

问题1：120的结果是如何一步一步得出的？

让我们手动运行它！以下每一行都是简化步骤的结果，每个注释描述了该步骤使用的简化方法。

fact(5)
// { Apply `fact` }
Y(F)(5)
// { Apply `Y` }
(t => F(Y(F))(t))(5)
// { Apply the anonymous function }
F(Y(F))(5) // Here we learned that `F(Y(F))(5)` is the same as `fact(5)`
// { Reduce the first argument of F: Apply `Y` }
F(t => F(Y(F))(t))(5)
// { Apply `F` }
if (5 <= 0) then 1 else 5 * (t => F(Y(F))(t))(4)
// { Simplify the if }
5 * (t => F(Y(F))(t))(4)
// { Reduce the arguments of `*`: Apply the anonymous function }
5 * F(Y(F))(4)
// { Notice the repeated pattern }
5 * fact(4)
// { ... }

重要的是要理解这里的关键是，在调用`F`之前，`F(Y(F))`只会被简化一次：由于匿名函数，`Y(F)`变成了`t => F(Y(F))(t)`，无法进一步简化，然后调用`F`，进行阶乘计算的一步。

Q2. `t => F(Y(F))(t)`和`F(Y(F))`之间有什么区别？

第一个使用了延迟计算的匿名函数（"thunk"）。在`t => F(Y(F))(t)`中，内部的`Y(F)`不会被求值，直到传递给函数的`t`值。而在`F(Y(F))`中，立即构建了无限嵌套的函数调用。让我们看看使用这个新定义对`fact(5)`会发生什么。

fact(5)
// { Apply `fact` }
Y(F)(5)
// { Apply `Y` }
F(Y(F))(5)
// { Reduce the first argument of F: Apply `Y` }
F(F(Y(F)))(5)
// { Reduce the first argument of F: Apply `Y` }
F(F(F(Y(F))))(5)
// { Reduce the first argument of F: Apply `Y` }
F(F(F(F(Y(F)))))(5)
// { Reduce the first argument of F: Apply `Y` }
F(F(F(F(F(Y(F))))))(5)
// { ... }

看到问题了吗？使用匿名函数可以防止构建这个无限调用堆栈。

- Clément

Answer 4

我不知道答案，但会尝试猜测。由于您有 def Y[T](f: ...) = f(...)，编译器可以尝试用简单的 f 替换 Y(f)。这将创建一个无限序列的 f(f(f(...)))。部分应用 f 会创建一个新对象，这样的替换变得不可能。

- Victor Moroz