GHC 中函数参数的内联

Question

我试图找到 GHC 中发生的某种内联的来源，其中作为参数传递给另一个函数的函数是内联的。例如，我可能会编写如下定义（使用我自己的 List 类型以避免重写规则）：

data MyList a = Nil | Cons a (MyList a)
  deriving (Show)

mapMyList :: (a -> b) -> MyList a -> MyList b
mapMyList f Nil = Nil
mapMyList f (Cons a rest) = Cons (f a) $ mapMyList f rest

随后拨打电话

fromList :: [a] -> MyList a
fromList = ...

main = do
  print $ mapMyList (*2) $ fromList [1..5]

mapMyList是递归的，所以它不能直接内联。但是，在生成的 Core 中，我看到以下定义：

fromList :: [a] -> MyList a
fromList = ...

main = do
  print $ mapMyList (*2) $ fromList [1..5]

特别是，smapMyList不再将函数作为参数，并且(* 2)这里内联了 。我想知道哪个优化过程正在生成此代码，以及它是如何工作的？

我发现了这个相关的问题，它似乎要求一种使用 SPECIALIZE pragma 来保证这种行为的方法，这让我相信专业化过程正在这样做。然而，当阅读有关 GHC 专门化的文档时，它似乎是专门化类型类字典，而不是函数参数（我的示例中没有类型类）。

我还研究了似乎相关的静态参数转换；例如，GHC 消息来源是这样描述通行证的：

可能被视为从循环中删除不变量：在递归调用中不更改的递归函数的参数将从递归中删除，递归是在本地完成的，并且仅传递有效更改的参数。

然而，我尝试禁用这两个通道-fno-static-argument-transformation -fno-specialise，发现这种转换仍然会发生。

我问这个问题的动机是我正在用另一种语言（Koka）实现这种转换，所以我想了解其他语言是如何做到的。

---

完整的测试程序

生成的核心（禁用专业化和静态参数转换后）

Answer 1

这种优化称为“调用模式专门化”（又名 SpecConstr），它根据应用的参数来专门化函数。Simon Peyton Jones 的论文“Haskell 程序的调用模式专门化”中描述了该优化。GHC 当前的实现与该论文中描述的不同，有两个高度相关的方面：

1. SpecConstr 可以应用于同一模块中的任何调用，而不仅仅是单个定义中的递归调用。
2. SpecConstr 可以应用于函数作为参数，而不仅仅是构造函数。然而，它对 lambda 不起作用，除非它们因完全惰性而被浮出。

-fno-spec-constr以下是在未进行此优化的情况下使用、 和 标志生成的核心的相关部分-dsuppress-all -dsuppress-uniques -dno-typeable-binds：

Rec {
mapMyList
  = \ @ a @ b f ds ->
      case ds of {
        Nil -> Nil;
        Cons a1 rest -> Cons (f a1) (mapMyList f rest)
      }
end Rec }

Rec {
main_go
  = \ x ->
      Cons
        (I# x)
        (case x of wild {
           __DEFAULT -> main_go (+# wild 1#);
           5# -> Nil
         })
end Rec }

main3 = \ ds -> case ds of { I# x -> I# (*# x 2#) }

main2
  = $fShowMyList_$cshowsPrec
      $fShowInt $fShowMyList1 (mapMyList main3 (main_go 1#))

main1 = main2 []

main = hPutStr' stdout main1 True

我认为这种优化有点令人失望，因为它仅适用于同一模块内的使用。而且，很长一段时间（自2007 年《Stream Fusion. From Lists to Streams to Nothing at All》论文）以来，人们一直希望这种优化能够优化流融合。然而，据我了解，没有人能够使其正常可靠地用于此目的（请参阅此 GHC 问题）。所以现在我们在基地仍然使用劣质foldr/build融合。

我开始讨论改善GHC 问题现状的可能性。我认为未来最有前途的工作是改进静态参数变换优化。请参阅Sebastian Graf 的评论。

我做了更多调试，特别是我使用了该-dverbose-core2core选项并检查了结果。正如我所期望的，优化是由于 SpecConstr 优化而发生的。这是 SpecConstr 之前的核心（在 Simplifier 通道之后）：

Rec {
mapMyList
  = \ @ a @ b f ds ->
      case ds of {
        Nil -> Nil;
        Cons a rest -> Cons (f a) (mapMyList f rest)
      }
end Rec }

lvl = \ ds -> case ds of { I# x -> I# (*# x 2#) }

main
  = case toList (mapMyList lvl (fromList (eftInt 1# 5#))) of {
      ...

这是 SpecConstr 之后的核心：

Rec {
$smapMyList
  = \ sc ->
      case sc of {
        Nil -> Nil;
        Cons a rest -> Cons (lvl a) (mapMyList lvl rest)
      }

mapMyList
  = \ @ a @ b f ds ->
      case ds of {
        Nil -> Nil;
        Cons a rest -> Cons (f a) (mapMyList f rest)
      }
end Rec }

lvl = \ ds -> case ds of { I# x -> I# (*# x 2#) }

main
  = case toList (mapMyList lvl (fromList (eftInt 1# 5#))) of {
      ...

因此，您可以看到 SpecConstr 创建了该函数，该函数是专门针对参数（即函数）$smapMyList的版本。mapMyListlvl*2

请注意，此专用函数尚未使用，这是使用新创建的重写规则完成的，该规则随后在简化器运行时触发。如果您使用该标志，-ddump-rule-rewrites您可以看到它们的实际效果：

Rec {
mapMyList
  = \ @ a @ b f ds ->
      case ds of {
        Nil -> Nil;
        Cons a1 rest -> Cons (f a1) (mapMyList f rest)
      }
end Rec }

Rec {
main_go
  = \ x ->
      Cons
        (I# x)
        (case x of wild {
           __DEFAULT -> main_go (+# wild 1#);
           5# -> Nil
         })
end Rec }

main3 = \ ds -> case ds of { I# x -> I# (*# x 2#) }

main2
  = $fShowMyList_$cshowsPrec
      $fShowInt $fShowMyList1 (mapMyList main3 (main_go 1#))

main1 = main2 []

main = hPutStr' stdout main1 True

这是后续 Simplifier 传递之后的核心（它也已内联lvl）：

Rec {
$smapMyList
  = \ sc ->
      case sc of {
        Nil -> Nil;
        Cons a rest ->
          Cons (case a of { I# x -> I# (*# x 2#) }) ($smapMyList rest)
      }
end Rec }

main
  = case toList ($smapMyList (fromList (eftInt 1# 5#))) of {
      ...

这也表明了为什么完全惰性对于这种优化也是必要的：该lvl函数需要浮出，因为 SpecConstr 不适用于 lambda。这种飘浮需要充分的懒惰。