为什么GHC让fix函数变得如此困惑？

Question

我查看了 GHC 源代码，发现 fix 的定义如下：

fix :: (a -> a) -> a
fix f = let x = f x in x

在这个例子中，fix 被使用如下所示：

fix (\f x -> let x' = x+1 in x:f x')

这基本上产生了一个由一递增到无限的数字序列。为此，fix必须将其接收到的函数柯里化回该函数作为其第一个参数。我不清楚上面列出的fix定义如何实现这一点。

这个定义是我理解fix如何工作的方法：

fix :: (a -> a) -> a
fix f = f (fix f)

现在我有两个问题：

1. x 如何成为第一个定义中的 fix x 的意思？
2. 使用第一个定义有什么优势吗？

- Vanson Samuel

Answer 1

通过应用等式推理，很容易看出这个定义的工作原理。

fix :: (a -> a) -> a
fix f = let x = f x in x

fix f = f (f (f (f ...)))是当我们尝试评估fix f时，x将会评估为什么值呢？它被定义为f x，所以fix f = f x。但这里的x是什么？它和之前一样是f x。因此，你得到了一个无限的f应用链：fix f = f (f (f (f ...)))。通过这种方式推理，现在将(\f x -> let x' = x+1 in x:f x')替换为f，你会得到：

fix (\f x -> let x' = x+1 in x:f x')
    = (\f x -> let x' = x+1 in x:f x') (f ...)
    = (\x -> let x' = x+1 in x:((f ...) x'))
    = (\x -> x:((f ...) x + 1))
    = (\x -> x:((\x -> let x' = x+1 in x:(f ...) x') x + 1))
    = (\x -> x:((\x -> x:(f ...) x + 1) x + 1))
    = (\x -> x:(x + 1):((f ...) x + 1))
    = ...

编辑：关于你的第二个问题，@is7s在评论中指出，第一个定义更好，因为它更有效率。

要了解原因，让我们来看看 fix1 (:1) !! 10^8 的核心：

a_r1Ko :: Type.Integer    
a_r1Ko = __integer 1

main_x :: [Type.Integer]   
main_x =
  : @ Type.Integer a_r1Ko main_x

main3 :: Type.Integer
main3 =
  !!_sub @ Type.Integer main_x 100000000

你可以看到，在这些转换之后，fix1 (1:) 本质上变成了 main_x = 1 : main_x。注意该定义是如何自我引用的 - 这就是“tying the knot”的意思。这种自我引用在运行时表示为简单的指针间接引用：

现在让我们来看看 fix2 (1:) !! 100000000:

main6 :: Type.Integer
main6 = __integer 1

main5
  :: [Type.Integer] -> [Type.Integer]
main5 = : @ Type.Integer main6

main4 :: [Type.Integer]
main4 = fix2 @ [Type.Integer] main5

main3 :: Type.Integer
main3 =
  !!_sub @ Type.Integer main4 100000000

这里实际上保留了fix2应用程序：

结果是第二个程序需要为列表的每个元素进行分配（但由于列表立即被消耗，因此程序仍然在常量空间内运行）：

$ ./Test2 +RTS -s
   2,400,047,200 bytes allocated in the heap
         133,012 bytes copied during GC
          27,040 bytes maximum residency (1 sample(s))
          17,688 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)
 [...]

将其与第一个程序的行为进行比较：

$ ./Test1 +RTS -s          
          47,168 bytes allocated in the heap
           1,756 bytes copied during GC
          42,632 bytes maximum residency (1 sample(s))
          18,808 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)
[...]

- Mikhail Glushenkov

---

第一个定义更有效，因为它打了结。例如，比较fix1(1:) !! 1000000和fix2(1:) !! 1000000。 - is7s

@is7s 我认为使用 -O2 选项，GHC 能够使第二个定义和第一个一样快。在我的机器上，两个测试程序都能瞬间完成。不过，在 GHCi 中，第二个定义会稍微慢一些。 - Mikhail Glushenkov

不，使用“-O2”选项仍然可以使第一个定义更快。您可以尝试使用更大的数字，例如“100000000”。在我的计算机上，速度大约快了5倍。 - is7s

Answer 2

第一定义中，x如何变成表示修复 x？

fix f = let x = f x in x

Haskell中的let绑定是递归的

首先，需要意识到Haskell允许递归的let绑定。在一些其他编程语言中所谓的“let”被称为“letrec”。这在函数定义中感觉相当正常。例如：

ghci> let fac n = if n == 0 then 1 else n * fac (n - 1) in fac 5
120

然而，对于值的定义来说，这可能看起来相当奇怪。尽管如此，由于Haskell的非严格性，值可以进行递归定义。

ghci> take 5 (let ones = 1 : ones in ones)
[1,1,1,1,1]

请参考Haskell入门教程第3.3和3.4节，了解更多有关Haskell的惰性计算的详细信息。

在GHC中，一个尚未求值的表达式被包装在一个“thunk”中：一种执行计算的承诺。只有在必须时才会评估thunk。假设我们想要fix someFunction。根据fix的定义，这是一个thunk。

let x = someFunction x in x

现在，GHC看到的是类似于这样的东西。

let x = MAKE A THUNK in x

因此，它会为您愉快地创建一个惰性计算并继续执行，直到您要求知道 x 实际上是什么。

示例评估

该惰性计算的表达式恰好是指向自身的。让我们以使用 fix 的 ones 示例进行重写。

ghci> take 5 (let ones recur = 1 : recur in fix ones)
[1,1,1,1,1]

那么这个thunk会是什么样子呢？ 为了更清晰地展示，我们可以将“ones”作为匿名函数“\recur -> 1 : recur”内联。

take 5 (fix (\recur -> 1 : recur))

-- expand definition of fix
take 5 (let x = (\recur -> 1 : recur) x in x)

那么，x是什么呢？虽然我们不太确定x是什么，但我们仍然可以进行函数应用：

take 5 (let x = 1 : x in x)

嘿，看这里，我们回到了之前的定义。

take 5 (let ones = 1 : ones in ones)

如果你认为你理解了那个的工作原理，那么你就能很好地理解fix的工作原理。

---

使用第一个定义是否有任何优势？

是的。问题在于即使进行了优化，第二个版本也可能会导致空间泄漏。请参见GHC trac ticket #5205，关于forever定义的类似问题。这就是为什么我提到thunks：因为let x = f x in x只分配了一个thunk：即x thunk。

- Dan Burton

Answer 3

区别在于分享和复制。¹

fix1 f = x where x = f x    -- more visually apparent way to write the same thing

fix2 f = f (fix2 f)

如果我们把定义代入自身，两者都会被减少为相同的无限应用链 f(f(f(f(...))))。但是第一个定义使用了显式命名，在Haskell（以及大多数其他语言）中，通过能够命名事物来实现共享：一个名称更或多或少保证指向一个“实体”（这里是x）。第二个定义不保证任何共享-调用fix2 f的结果被替换到表达式中，因此也可能被替换为值。

但是理论上，某个编译器也可以聪明地在第二种情况下使用共享。

相关问题是“Y组合子”。在没有命名结构（因此没有自我-引用）的未类型化λ演算中，Y组合子通过安排复制定义来模拟自我引用，因此引用复制品变得可能。但在使用环境模型允许在语言中使用命名实体的实现中，直接按名称引用就变得可能了。

要看到两个定义之间更加激烈的差异，请比较

fibs1 = fix1 ( (0:) . (1:) . g ) where g (a:t@(b:_)) = (a+b):g t
fibs2 = fix2 ( (0:) . (1:) . g ) where g (a:t@(b:_)) = (a+b):g t

另请参见：

• 在Scheme中如何使用lambda创建递归函数？
• “小计算机科学家”中的Y组合器讨论
• 可以使用fold创建无限列表吗？

（特别是尝试解决上面链接中最后两个定义的问题）。

---

¹ 根据定义，对于您的示例 fix (\g x -> let x2 = x + 1 in x：g x2)，我们得到：

fix1 (\g x -> let x2 = x+1 in x : g x2)
 = fix1 (\g x -> x : g (x+1))
 = fix1 f where {f = \g x -> x : g (x+1)}
 = fix1 f where {f g x = x : g (x+1)}
 = x      where {x = f x ; f g x = x : g (x+1)}
 = g      where {g = f g ; f g x = x : g (x+1)}   -- both g in {g = f g} are the same g
 = g      where {g = \x -> x : g (x+1)}           -- and so, here as well
 = g      where {g x = x : g (x+1)}

因此，实际上创建了一个适当的递归定义来定义g。（在上面的代码中，我们使用....x.... where {x = ...}来表示let {x = ...} in ....x....，以增加可读性。）

但第二次推导过程中进行了一个关键的区分，即用一个值而不是名称进行替换。

fix2 (\g x -> x : g (x+1))
 = fix2 f             where {f g x = x : g (x+1)}
 = f (fix2 f)         where {f g x = x : g (x+1)}
 = (\x-> x : g (x+1)) where {g = fix2 f ; f g x = x : g (x+1)}
 = h                  where {h   x = x : g (x+1) ; g = fix2 f   ; f g x = x : g (x+1)}

因此，实际的调用将进行如下，例如：

take 3 $ fix2 (\g x -> x : g (x+1)) 10
 = take 3 (h 10)      where {h   x = x : g (x+1) ; g = fix2 f   ; f g x = x : g (x+1)}
 = take 3 (x:g (x+1)) where {x = 10 ;              g = fix2 f   ; f g x = x : g (x+1)}
 = x:take 2 (g x2)    where {x2 = x+1 ; x = 10 ;   g = fix2 f   ; f g x = x : g (x+1)}
 = x:take 2 (g x2)    where {x2 = x+1 ; x = 10 ; g = f (fix2 f) ; f g x = x : g (x+1)}
 = x:take 2 (x2 : g2 (x2+1))   where {             g2 = fix2 f  ;
                             x2 = x+1 ; x = 10 ;                  f g x = x : g (x+1)}
 = ......

我们可以看到，这里建立了一个新的绑定（用于g2），而不是像在fix1定义中一样重复使用先前的绑定（用于g）。

- Will Ness

Answer 4

我有一个可能有点简化的解释，来自内联优化。如果我们有：

fix :: (a -> a) -> a
fix f = f (fix f)

那么fix是一个递归函数，这意味着它不能在使用它的地方内联（如果给定，将会忽略INLINE编译指令）。

然而

fix' f = let x = f x in x

这不是一个递归函数——它从未调用自身。只有内部的x是递归的。因此，在调用时

fix' (\r x -> let x' = x+1 in x:r x')

编译器可以将其内联到代码中。

(\f -> (let y = f y in y)) (\r x -> let x' = x+1 in x:r x')

然后继续简化它，例如。

let y = (\r x -> let x' = x+1 in x:r x') y in y 
let y = (\  x -> let x' = x+1 in x:y x')   in y 

如果使用标准的递归表示法而不是 fix 来定义函数，这就等效于：

    y       x =  let x' = x+1 in x:y x'   

- Petr