GHC：对于具有固定值的呼叫，是否有一致的备忘录规则？

Question

为了理解和利用GHC自动记忆，我碰壁了：当纯函数以诸如的固定值调用时fib 42，它们有时又快又慢。如果fib 42通过数学简单地或隐式地调用它们，则它们会有所不同(\x -> fib (x - 1)) 43。这些案件似乎没有押韵或理由，因此我将向他们提出这些案件的目的是询问行为背后的逻辑是什么。

考虑一个慢速的斐波那契实现，这使备忘录有效时显而易见：

slow_fib :: Int -> Integer
slow_fib n = if n < 2 then 1 else (slow_fib (n - 1)) + (slow_fib (n - 2))

我测试了三个基本问题，以查看GHC（8.2.2版）是否可以使用固定参数来记录调用：

1. 可以slow_fib访问以前的顶级通话slow_fib吗？
2. 是否为以后的非平凡（例如数学）顶级表达式记忆了以前的结果？
3. 是否为以后相同的顶级表达式记忆了以前的结果？

答案似乎是：

1. 没有
2. 没有
3. 是[??]

最后一种情况有效的事实令我感到困惑：例如，如果我可以重印结果，那么我应该希望能够添加它们。这是显示此代码的代码：

main = do
  -- 1. all three of these are slow, even though `slow_fib 37` is 
  -- just the sum of the other two results. Definitely no memoization.
  putStrLn $ show $ slow_fib 35
  putStrLn $ show $ slow_fib 36
  putStrLn $ show $ slow_fib 37

  -- 2. also slow, definitely no memoization as well.
  putStrLn $ show $ (slow_fib 35) + (slow_fib 36) + (slow_fib 37)
  putStrLn $ show $ (slow_fib 35) + 1

  -- 3. all three of these are instant. Huh?
  putStrLn $ show $ slow_fib 35
  putStrLn $ show $ slow_fib 36
  putStrLn $ show $ slow_fib 37

---

然而，奇怪的是，当结果嵌入到递归函数中时，对结果进行数学运算是有效的：此fibonacci变体始于Fib（40）：

let fib_plus_40 n = if n <= 0
  then slow_fib 40
  else (fib_plus_40 (n - 1)) + (fib_plus_40 (n - 2))

显示如下：

main = do
  -- slow as expected
  putStrLn $ show $ fib_plus_40 0

  -- instant. Why?!
  putStrLn $ show $ fib_plus_40 1

我找不到这方面的任何理由在GHC memoization的任何解释，这通常连累明确的变量（例如这里，在这里，并在这里）。这就是为什么我期望fib_plus_40无法记忆。

Answer 1

为了详细说明，以防 @amalloy 的答案不清楚，问题是你在这里混淆了两件事——隐式记忆化行为（人们在谈论 Haskell 的“自动记忆化”时的意思，尽管它不是真正的记忆化！），它直接由基于 thunk 的惰性求值和编译器优化技术（基本上是公共子表达式消除的一种形式）产生。前者或多或少是可以预见的；后者是编译器的突发奇想。

Recall that real memoization is a property of the implementation of a function: the function "remembers" results calculated for certain combinations of arguments, and may reuse those results instead of recalculating them from scratch when called multiple times with the same arguments. When GHC generates code for functions, it does not automatically generate code to perform this kind of memoization.

Instead, the GHC code generates to implement function application is unusual. Instead of actually applying the function to arguments to generate the final result as a value, a "result" is immediately constructed in the form of a thunk, which you can view as a suspended function call or a "promise" to deliver a value at a later time.

When, at some future point, the actual value is needed, the thunk is forced (which actually causes the original function call to take place), and the thunk is updated with the value. If that same value is needed again later, the value is already available, so the thunk doesn't need to be forced a second time. This is the "automatic memoization". Note that it takes place at the "result" level rather than the "function" level -- the result of a function application remembers its value; a function does not remember the results it previously produced.

Now, normally the concept of the result of a function application remembering its value would be ridiculous. In strict languages, we don't worry that after x = sqrt(10), reusing x will cause multiple sqrt calls because x hasn't "memoized" its own value. That is, in strict languages, all function application results are "automatically memoized" in the same sense they are in Haskell.

The difference is lazy evaluation, which allows us to write something like:

stuff = map expensiveComputation [1..10000]

which returns a thunk immediately without performing any expensive computations. Afterwards:

f n = stuff !! n

magically creates a memoized function, not because GHC generates code in the implementation of f to somehow memoize the call f 1000, but because f 1000 forces (a bunch of list constructor thunks and then) a single expensiveComputation whose return value is "memoized" as the value at index 1000 in the list stuff -- it was a thunk, but after being forced, it remembers its own value, just like any value in a strict language would.

So, given your definition of slow_fib, none of your examples are actually making use of Haskell's automatic memoization, in the usual sense people mean. Any speedups you're seeing are the result of various compiler optimizations that are (or aren't) recognizing common subexpressions or inlining / unwrapping short loops.

To write a memoized fib, you need to do it as explicitly as you would in a strict language, by creating a data structure to hold the memoized values, though lazy evaluation and mutually recursive definitions can sometimes make it seem like it's "automatic":

import qualified Data.Vector as V
import Data.Vector (Vector,(!))

fibv :: Vector Integer
fibv = V.generate 1000000 getfib
  where getfib 0 = 1
        getfib 1 = 1
        getfib i = fibv ! (i-1) + fibv ! (i-2)

fib :: Int -> Integer
fib n = fibv ! n

Answer 2

在座的各位在年底链接例子利用同样的技术：不是实现功能f直接，他们首先推出其内容的列表中的所有呼叫f能否被作出。该列表仅被懒惰地计算一次；然后使用该列表中的简单查找作为面向用户功能的实现。因此，他们不依赖GHC的任何缓存。

您的问题有所不同：您希望调用某些函数会自动为您缓存，并且通常不会发生。真正的问题是为什么您的任何结果都很快。我不确定，但我认为这与GHC可能会自行决定在多个使用地点之间共享的恒定适用表格（CAF）有关。

CAF最相关的功能是“常量”部分：GHC只会为这样的表达式引入这样的缓存：该表达式的值在程序的整个运行过程中都是恒定的，而不仅仅是在特定范围内。因此，您可以确定f x <> f x不会重复使用结果f x（至少不是由于CAF折叠；也许GHC可以找到其他借口来记住某些功能，但通常不会）。

程序中不是 CAF 的两件事是的实现slow_fib和的递归情况fib_plus_40。GHC绝对不能对这些表达式的结果进行任何缓存。的基本情况fib_plus_40是CAF，以及中的所有表达式和子表达式main。因此，GHC可以选择缓存/共享任何这些子表达式，而不必随意共享它们。也许它认为slow_fib 40保存起来“显然”很简单，但是不确定是否应该共享其中的slow_fib 35表达式main。同时，听起来它确实决定putStrLn $ show $ slow_fib 35出于任何原因共享IO操作。对您我来说，这似乎是一个奇怪的选择，但我们不是编译器。

这里的道理是，您完全不能依靠它：如果要确保只计算一次值，则需要将其保存在某个变量中，然后引用该变量而不是重新计算它。

为了确认这一点，我接受了luqui的建议，并查看了-ddump-simpl输出。以下是一些片段，显示了显式缓存：

-- RHS size: {terms: 2, types: 0, coercions: 0}
lvl1_r4ER :: Integer
[GblId, Str=DmdType]
lvl1_r4ER = $wslow_fib_r4EP 40#

Rec {
-- RHS size: {terms: 21, types: 4, coercions: 0}
Main.main_fib_plus_40 [Occ=LoopBreaker] :: Integer -> Integer
[GblId, Arity=1, Str=DmdType <S,U>]
Main.main_fib_plus_40 =
  \ (n_a1DF :: Integer) ->
    case integer-gmp-1.0.0.1:GHC.Integer.Type.leInteger#
           n_a1DF Main.main7
    of wild_a2aQ { __DEFAULT ->
    case GHC.Prim.tagToEnum# @ Bool wild_a2aQ of _ [Occ=Dead] {
      False ->
        integer-gmp-1.0.0.1:GHC.Integer.Type.plusInteger
          (Main.main_fib_plus_40
             (integer-gmp-1.0.0.1:GHC.Integer.Type.minusInteger
                n_a1DF Main.main4))
          (Main.main_fib_plus_40
             (integer-gmp-1.0.0.1:GHC.Integer.Type.minusInteger
                n_a1DF lvl_r4EQ));
      True -> lvl1_r4ER
    }
    }
end Rec }

这并不能告诉我们GHC 为什么选择引入此缓存-请记住，它可以做它想做的事情。但是它确实确认了这种机制，它引入了一个变量来保存重复的计算。我无法向您展示main包含较小数字的较长时间的核心，因为在进行编译时，我会得到更多的共享：第2节中的表达式也为我缓存。