haskell - 类型类函数调用的 GHC 代码生成

Question

在 Haskell 中要定义类型类的实例，您需要提供类型类所需的函数字典。即要定义的实例Bounded，您需要为minBound和提供定义maxBound。

出于这个问题的目的，让我们将此字典称为vtbl类型类实例。让我知道这是否是一个糟糕的类比。

我的问题集中在当我调用类型类函数时，我可以从 GHC 中获得什么样的代码生成。在这种情况下，我看到了三种可能性：

用于查找实现功能的 vtbl 查找在运行时已关闭
vtbl 查找在编译时完成，并在生成的代码中发出对实现函数的直接调用
vtbl 查找在编译时完成，实现函数在调用站点内联

我想了解这些情况何时发生 - 或者是否还有其他可能性。

此外，类型类是否在单独编译的模块中定义而不是“主”编译单元的一部分是否重要？

在可运行的程序中，Haskell 似乎知道程序中所有函数和表达式的类型。因此，当我调用类型类函数时，编译器应该知道 vtbl 是什么以及确切调用哪个实现函数。我希望编译器至少生成对实现函数的直接调用。这是真的？

（我在这里说“可运行程序”是为了将其与编译您不运行的模块区分开来。）

score 20 · Accepted Answer

与所有好的问题一样，答案是“视情况而定”。经验法则是任何类型类多态代码都有运行时成本。然而，库作者在使用 GHC 的重写规则消除这种成本方面具有很大的灵活性，特别是有一个{-# SPECIALIZE #-}编译指示可以自动创建多态函数的单态版本，并在可以推断出多态函数用于单态函数时使用它们。类型。（我认为这样做的代价是库和可执行文件的大小。）

-ddump-simpl您可以使用 ghc 的标志回答任何特定代码段的问题。例如，这是一个简短的 Haskell 文件：

vDouble :: Double
vDouble = 3
vInt = length [2..5]
main = print (vDouble + realToFrac vInt)

如果没有优化，您可以看到 GHC 在运行时进行字典查找：

Main.main :: GHC.Types.IO ()
[GblId]
Main.main =
  System.IO.print
    @ GHC.Types.Double
    GHC.Float.$fShowDouble
    (GHC.Num.+
       @ GHC.Types.Double
       GHC.Float.$fNumDouble
       (GHC.Types.D# 3.0)
       (GHC.Real.realToFrac
          @ GHC.Types.Int
          @ GHC.Types.Double
          GHC.Real.$fRealInt
          GHC.Float.$fFractionalDouble
          (GHC.List.length
             @ GHC.Integer.Type.Integer
             (GHC.Enum.enumFromTo
                @ GHC.Integer.Type.Integer
                GHC.Enum.$fEnumInteger
                (__integer 2)
                (__integer 5)))))

...相关位是realToFrac @Int @Double. 另一方面-O2，您可以看到它静态地进行字典查找并内联实现，结果是一次调用int2Double#：

Main.main2 =
  case GHC.List.$wlen @ GHC.Integer.Type.Integer Main.main3 0
  of ww_a1Oq { __DEFAULT ->
  GHC.Float.$w$sshowSignedFloat
    GHC.Float.$fShowDouble_$sshowFloat
    GHC.Show.shows26
    (GHC.Prim.+## 3.0 (GHC.Prim.int2Double# ww_a1Oq))
    (GHC.Types.[] @ GHC.Types.Char)
  }

库作者也可以选择将多态函数重写为对单态函数的调用，而不是内联单态函数的实现；这意味着您提出的所有可能性（以及更多）都是可能的。

score 11 · Accepted Answer

如果编译器可以在编译时“告诉”您正在使用的实际类型，那么方法查找会在编译时发生。否则它会在运行时发生。如果查找发生在编译时，方法代码可能会被内联，具体取决于方法的大小。（这也适用于常规函数：如果编译器知道您正在调用哪个函数，如果该函数“足够小”，它将内联它。）

例如，考虑(sum [1 .. 10]) :: Integer。在这里，编译器静态知道该列表是一个 take 列表Integer，因此它可以内联+函数 for Integer。另一方面，如果你做类似的事情

foo :: Num x => [x] -> x
foo xs = sum xs - head x

然后，当您调用时sum，编译器不知道您使用的是什么类型。（这取决于赋予的类型foo），因此它不能进行任何编译时查找。

另一方面，使用{-# SPECIALIZE #-}pragma，您可以执行类似的操作

{-# SPECIALIZE foo:: [Int] -> Int #-}

这样做是告诉编译器编译foo输入是Int值列表的特殊版本。这显然意味着对于该版本，编译器可以在编译时进行所有方法查找（并且几乎可以肯定将它们全部内联）。现在有两个版本foo- 一个适用于任何类型并进行运行时类型查找，另一个仅适用于Int，但 [可能] 快得多。

当你调用foo函数时，编译器必须决定调用哪个版本。如果编译器可以在编译时“告诉”您想要该Int版本，它就会这样做。如果它不能“告诉”你将使用什么类型，它将使用较慢的任何类型版本。

请注意，您可以对单个函数进行多个专业化。例如，你可以做

{-# SPECIALIZE foo :: [Int] -> Int #-}
{-# SPECIALIZE foo :: [Double] -> Double #-}
{-# SPECIALIZE foo :: [Complex Double] -> Complex Double #-}

现在，只要编译器知道您正在使用其中一种类型，它就会使用为该类型硬编码的版本。但是如果编译器不能告诉你使用的是什么类型，它就永远不会使用专门的版本，而且总是使用多态版本。（例如，这可能意味着您需要专门化调用的函数foo。）

如果您浏览编译器的核心输出，您可能可以准确地弄清楚它在任何特定情况下做了什么。不过，您可能会发疯似的发疯……

score 9 · Accepted Answer

正如其他答案所描述的，任何这些都可能发生在不同的情况下。对于任何特定的函数调用，唯一确定的方法是查看生成的内核。也就是说，在某些情况下，您可以很好地了解会发生什么。

在单态类型上使用类型类方法。

当在编译时类型完全已知的情况下调用类型类方法时，GHC 将在编译时执行查找。例如

isFive :: Int -> Bool
isFive i = i == 5

这里编译器知道它需要Ints Eq 字典，所以它发出代码来静态调用函数。该调用是否被内联取决于 GHC 通常的内联规则，以及INLINE编译指示是否适用于类方法定义。

暴露多态函数

如果多态函数从已编译的模块中公开，则基本情况是需要在运行时执行查找。

module Foo (isFiveP) where

isFiveP :: (Eq a, Num a) => a -> Bool
isFiveP i = i == 5

GHC 实际所做的是将其转换为形式的函数（或多或少）

isFiveP_ eqDict numDict i = (eq_op eqDict) i (fromIntegral_fn numDict 5)

所以函数查找需要在运行时执行。

无论如何，这是基本情况。实际发生的是 GHC 在跨模块内联方面可能非常激进。 isFiveP足够小，可以内联到调用站点。如果可以在调用站点确定类型，则字典查找将全部在编译时执行。即使多态函数没有在调用站点直接内联，由于 GHC 的常用函数转换，字典查找仍可能在编译时执行，如果代码曾经到达函数（带有类字典参数）可以的形式应用于静态已知的字典。

haskell - 类型类函数调用的 GHC 代码生成

3 回答 3

Related

Reference