在Haskell中共享数据

Question

我想了解Haskell中的内存共享机制是如何工作的。实际上，计算斐波那契数列项的函数的一种编程方式是：

fibo' n = f n
  where 
    f 0 = 1
    f 1 = 1
    f n = fibs !! (n-1) + fibs !! (n-2)
    fibs = [f x | x <- [0..]]

这假设有一个改进，即fibs列表不会被多次评估，而是在调用之间共享，但我不确定这个假设或它的工作原理。

- Ftyupl

Answer 1

作为第一次近似，您可以使用变量作用域来预测将共享什么。

所有使用 fibs 的地方都在同一个作用域内，因此该名称的每个出现都解析为内存中的同一对象。这意味着每次在一个顶级 fibo' 调用内调用 f 时，都有一个单独的 fibs 列表。它在 f 调用之间共享。

然而，fibs 定义在一个 where 作用域中，附加到函数方程式 fibo' n =。这意味着作用域位于 fibo' 的每个调用内部（在某个特定的 n 上）；where 子句中定义的所有名称每次调用 fibo' 时都指向内存中的不同对象。（这就像任何主流编程语言中工作的局部变量 - 在函数内部定义）

您在这里拥有的是一个函数，它将使用预先计算的斐波那契数列列表来节省在一个顶级调用内的重新计算，但然后会放弃它并从头开始处理下一个顶级调用。

这可能正是你想要的，所以从本质上讲并没有错。如果fibs在顶层应用程序之外的范围内定义，那么它将在所有调用之间共享，但这也意味着它将永久占用内存以便下一次调用时可用。由于Haskell中的对象在评估得更深时可以在内存中扩展，这可能被视为内存泄漏。而每次顶层调用后丢弃它意味着多个调用会重复一些工作，但你只使用了加速每次调用所需的内存（而不是你曾经进行的最大调用所需的内存），而且仅在运行时使用。因此，“更好”的方式取决于你的程序对这个函数的其他操作，而不是这个函数本身。

请注意，您的where子句中没有任何一个定义实际使用了fibo'的参数，而fibo'本身并没有真正“做任何事情”；它只是立即将调用转发到f。因此，将代码放在类似这样的where中的唯一“有趣”效果就是创建了一个作用域，在该作用域中可以在顶层调用内部但在内部f调用之外定义fibs。（我认为访问控制效果不是有趣的）。如果您不想要这样，并且确实希望在调用之间共享fibs，那么只需像这样定义您的代码即可：

fibo'' 0 = 1
fibo'' 1 = 1
fibo'' n = fibs !! (n-1) + fibs !! (n-2)

fibs = [fibo'' x | x <- [0..]]

现在，fibs只是全局范围内的一个单一对象，并且将在所有调用之间共享（但也会占用所有调用的内存）。

如果您关心访问控制（如果fibs在局部范围内定义，则其他任何内容都无法访问它，但如果在全局范围内定义，则可以访问），您可以这样做：

fibo''' = f
  where 
    f 0 = 1
    f 1 = 1
    f n = fibs !! (n-1) + fibs !! (n-2)
    fibs = [f x | x <- [0..]]

这里的fibs（和f）是在本地作用域中定义的。但是附加了where的方程式只是fibo''' = f。这个本地作用域仍然处于顶层调用的“外部”，因为该作用域在fibo'''接收其参数之前被“进入”。而原始的fibo'将where附加到已经将参数n引入作用域的方程式上，因此where作用域在每次进行顶层调用之后才被“进入”。

---

现在，我开始这篇文章时说了“作为第一个近似值”。编译器允许重新组织您的代码以尝试优化它。例如，它可以理论上注意到fibs不依赖于参数n，因此将其移动到顶层调用之外，使您的fibo'的行为类似于fibo'''。或者（再次理论上）它可以决定内联fibs，这将删除所有共享并使您的fibo'的行为类似于一个天真的递归斐波那契计算器。

然而，在实践中，它极不可能做任何一件事情。它“允许”进行任何不改变代码最终结果的转换，但GHC开发人员实际放入编译器的转换旨在使您的代码更好。因此，他们非常努力地不增加或减少共享，以导致大型内存泄漏或减速。

因此，尽管编译和优化后的代码通常与您实际编写的代码非常不同，但在假设“如果您给某物命名，在相同作用域内使用该名称的所有内容将被共享”的情况下，理解您的代码是相当安全的。 您只需要注意确切进入本地作用域的时间，以便知道什么被视为“在相同的作用域内”。

- Ben

Answer 2

在 GHC 中，初步估计，只有当它是同一变量时，在内存中的值才相同。给一个东西命名就能创造分享的可能性。

这个规则有以下例外：

• 如果 GHC 决定内联一个定义，它会在每个内联的地方都复制一份。通常情况下这不是问题，因为只有“简单”的东西才会被内联。只有当你的值使用 unsafePerformIO 与实际上不是纯的东西，并且你指望共享以便该值在整个程序执行期间保持一致时，这才真正成为你需要担心的事情。这里的典型解决方案是用 NOINLINE pragma 标记那些不安全定义的东西。
• 如果 GHC 进行公共子表达式消除，那么可以在没有显式命名的情况下引入表达式的共享。只有当应用该转换的启发式方法出现错误时，这才会有所影响，而且长期以来它们一直非常好。我想这对于像 criterion 这样想要重复计算相同表达式的库来说是个问题。我查看了它的源代码，以找出它如何处理它，似乎是通过将评估移动到 GHC 不知道具体类型的上下文中来解决的，这足以防止 CSE 发生。
• 完全惰性变换有时会将堆分配浮动到 lambda 外部，如果堆分配不依赖于 lambda 的参数。这个可能会是一个巨大的痛苦。实际上它将应用于你的代码。既不是 f 也不是 fibs 依赖于 fibo' 的参数。如果 GHC 决定应用完全惰性变换，你的代码可能会被转换为：

它将转换当前的表单，这相当于：

fibo' = \n' -> let f 0 = 1
                   f 1 = 1
                   f n = fibs !! (n-1) + fibs !! (n-2)
                   fibs = [f x | x <- [0..]]
               in f n'

针对以下代码，使用 let 将其浮动到 lambda 之外：

fibo' = let f 0 = 1
            f 1 = 1
            f n = fibs !! (n-1) + fibs !! (n-2)
            fibs = [f x | x <- [0..]]
        in \n' -> f n'

这里的作用域很重要。将let浮动到顶部后，f和fibs的定义在多次调用fibo'时是共享的，而不是为每个调用重新分配。在这种情况下，这可能会引入过多的共享，因为使用大参数一次调用fibs将导致保留那么多计算列表，无论程序的其余部分需要多少。通常我认为完全惰性转换是一个错误的功能，并通过编译器选项禁用它。如果我想要共享，我会手动浮动分配。

- Carl