reuse/memoization 个全局多态 (class) 值 Haskell

Question

我关心多态性 "global" class 值 是否以及何时为 shared/memoized，尤其是跨模块边界。我已阅读 this and this，但它们似乎并不能完全反映我的情况，而且我看到的行为与人们对答案的预期有所不同。

考虑一个 class 公开一个计算成本很高的值：

{-# LANGUAGE FlexibleInstances, UndecidableInstances #-}

module A

import Debug.Trace

class Costly a where
  costly :: a

instance Num i => Costly i where
  -- an expensive (but non-recursive) computation
  costly = trace "costly!" $ (repeat 1) !! 10000000

foo :: Int
foo = costly + 1

costlyInt :: Int
costlyInt = costly

还有一个单独的模块：

module B
import A

bar :: Int
bar = costly + 2

main = do
  print foo
  print bar
  print costlyInt
  print costlyInt

运行 main 产生两个单独的 costly 评估（如跟踪所示）：一个用于 foo，一个用于 bar。我知道 costlyInt 只是 returns 来自 foo 的（评估的）costly，因为如果我从 main 中删除 print foo 那么第一个 costlyInt 变得昂贵。（我也可以通过将 foo 的类型泛化为 Num a => a，无论如何使 costlyInt 执行单独的评估。）

我想我知道为什么会发生这种行为：Costly 的实例实际上是一个接受 Num 字典并生成 Costly 字典的函数。因此，当编译 bar 并解析对 costly 的引用时，ghc 会生成一个新的 Costly 字典，其中包含一个昂贵的 thunk。问题 1：我对此是否正确？

有几种方法可以只对 costly 进行一次评估，包括：

将所有内容放在一个模块中。
删除 Num i 实例约束并只定义一个 Costly Int 实例。

不幸的是，这些解决方案的类似物在我的程序中不可行——我有几个模块以其多态形式使用 class 值，并且只有在顶级源文件中才是具体类型终于用上了

还有不减少评价次数的变化，例如：

在实例中的 costly 定义上使用 INLINE、INLINABLE 或 NOINLINE。（我没想到这会奏效，但是嘿，值得一试。）
在实例定义中使用 SPECIALIZE instance Costly Int pragma。

后者令我感到惊讶——我原以为它在本质上等同于所做的第二项。也就是说，我认为它会生成一个特殊的 Costly Int 字典，所有 foo、bar 和 costlyInt 都将共享该字典。我的问题 2：我在这里错过了什么？

我的最后一个问题：是否有任何相对简单和万无一失的方法来获得我想要的东西，即，跨模块共享对特定具体类型 costly 的所有引用？据我目前所见，我怀疑答案是否定的，但我仍然抱有希望。

Answer 1

在 GHC 中控制共享很棘手。 GHC 做了很多会影响共享的优化（例如内联、浮动等）。

在这种情况下，要回答为什么SPECIALIZE pragma没有达到预期效果的问题，让我们看一下B模块的核心，特别是bar函数：

Rec {
bar_xs
bar_xs = : x1_r3lO bar_xs
end Rec }

bar1 = $w!! bar_xs 10000000
--     ^^^ this repeats the computation. bar_xs is just repeat 1

bar =
  case trace $fCostlyi2 bar1 of _ { I# x_aDm -> I# (+# x_aDm 2) }
  --         ^^^ this is just the "costly!" string

这没有达到我们想要的效果。 GHC 没有重用 costly，而是决定直接内联 costly 函数。

所以我们必须防止 GHC 内联代价高昂，否则计算将被重复。我们该怎么做？您可能认为添加 {-# NOINLINE costly #-} 编译指示就足够了，但不幸的是，没有内联的专业化似乎不能很好地协同工作：

A.hs:13:3: Warning:
    Ignoring useless SPECIALISE pragma for NOINLINE function: ‘$ccostly’

但是有一个技巧可以说服GHC做我们想做的事情：我们可以这样写costly：

instance Num i => Costly i where
  -- an expensive (but non-recursive) computation
  costly = memo where
    memo :: i
    memo = trace "costly!" $ (repeat 1) !! 10000000
    {-# NOINLINE memo #-}
  {-# SPECIALIZE instance Costly Int #-}
-- (this might require -XScopedTypeVariables)

这允许我们专门化 costly，同时避免我们计算的内联。

reuse/memoization 个全局多态 (class) 值 Haskell

reuse/memoization of global polymorphic (class) values in Haskell

haskell

polymorphism

memoization