haskell - 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是递归的，所以它不能直接内联。但是，在生成的核心中，我看到了以下定义:

Rec {
-- RHS size: {terms: 16, types: 11, coercions: 0, joins: 0/0}
Main.main_$smapMyList [Occ=LoopBreaker] :: MyList Int -> MyList Int
[GblId, Arity=1, Str=<S,1*U>, Unf=OtherCon []]
Main.main_$smapMyList
  = \ (sc_s2Rb :: MyList Int) ->
      case sc_s2Rb of {
        Nil -> Main.Nil @Int;
        Cons a_aBe rest_aBf ->
          Main.Cons
            @Int
            (case a_aBe of { GHC.Types.I# x_a24u ->
             GHC.Types.I# (GHC.Prim.*# x_a24u 2#)
             })
            (Main.main_$smapMyList rest_aBf)
      }
end Rec }

特别是， smapMyList不再将函数作为参数， (* 2)在这里内联。我想知道哪个优化 channel 正在生成此代码，以及它是如何工作的？
我找到了 this related issue ，这似乎是在寻求一种使用 SPECIALIZE 杂注来保证这种行为的方法，这让我相信特化通行证正在这样做。但是，在阅读有关 GHC 特化的文档时，似乎是专门针对类型类字典，而不是函数参数(在我的示例中没有类型类)。
我还看了 static argument transformation这似乎相关；例如 GHC source关于通行证是这样说的:

May be seen as removing invariants from loops:Arguments of recursive functions that do not change in recursivecalls are removed from the recursion, which is done locallyand only passes the arguments which effectively change.

但是，我尝试使用 -fno-static-argument-transformation -fno-specialise 禁用这两个 channel 。并发现这种转变仍然会发生。
我提出这个问题的动机是我正在用另一种语言( Koka)实现这种转换，所以我想了解其他语言是如何做到的。

Complete test program
Generated core (禁用特化和静态参数转换后)

Answer 1

优化称为“调用模式特化”(又名 SpecConstr)，它根据函数应用于哪些参数来专门化函数。优化在论文 "Call-pattern specialisation for Haskell programs" by Simon Peyton Jones 中进行了描述。 . GHC 中的当前实现与该论文中描述的内容在两个高度相关的方面有所不同:

SpecConstr 可以应用于同一模块中的任何调用，而不仅仅是单个定义中的递归调用。

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

我认为这种优化有点令人失望，因为它只适用于同一模块内的使用。此外，很长一段时间(从 "Stream Fusion. From Lists to Streams to Nothing at All" paper from 2007 开始)人们一直希望这种优化可以优化流融合。但是，据我了解，没有人能够使其正常可靠地工作(参见 this GHC issue)。所以现在我们还是用劣质的 foldr/build基地融合。
我在 this GHC issue 中开始讨论改善现状的可能性。 .我认为 future 最有希望的工作是改进静态参数转换优化。见 this comment by 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 mapMyList 的一个版本的函数专门用于 lvl参数，即 *2功能。
请注意，尚未使用此专门功能，这是使用新创建的重写规则完成的，该规则随后在 Simplifier 运行时触发。如果您使用标志 -ddump-rule-rewrites你可以看到他们在行动:

Rule fired
    Rule: SC:mapMyList0
    Module: (Main)
    Before: mapMyList TyArg Int TyArg Int ValArg lvl ValArg rest
    After:  (\ sc -> $smapMyList sc) rest
    Cont:   Stop[BoringCtxt] MyList Int
Rule fired
    Rule: SC:mapMyList0
    Module: (Main)
    Before: mapMyList
              TyArg Int TyArg Int ValArg lvl ValArg fromList (eftInt 1# 5#)
    After:  (\ sc -> $smapMyList sc) (fromList (eftInt 1# 5#))
    Cont:   StrictArg toList
            Select nodup wild
            Stop[RhsCtxt] String

这是随后的 Simplifier pass 之后的核心(它还内联了 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。这种 float 需要完全的懒惰。