GHC中函数参数的嵌入

Question

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

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中，我看到了以下定义：

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)在这里内联。我想知道是哪个优化过程生成了这个代码，它是如何工作的？

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

我还研究了似乎相关的静态论点转换；例如，GHC的消息来源这样说通行证：

可以看作是从循环中移除不变量：递归中不更改的递归函数的参数调用从递归中删除，递归是在本地完成的并且只通过有效改变的论点。

但是，我尝试使用-fno-static-argument-transformation -fno-specialise禁用这两个过程，发现无论如何仍会发生这种转换。

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

---

完整的测试程序

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

Answer 1

优化称为"呼叫模式专业化"；(又称SpecConstr(这专门化了函数，根据它们应用于哪些参数；Haskell程序的调用模式专业化；西蒙·佩顿·琼斯著。GHC中当前的实现与论文中描述的不同，有两个高度相关的方面：

1. SpecConstr可以应用于同一模块中的任何调用，而不仅仅是单个定义中的递归调用
2. SpecConstr可以作为参数应用于函数，而不仅仅是构造函数。然而，这对lambdas来说是行不通的，除非它们是因为完全的懒惰而漂出来的

以下是在没有进行此优化的情况下使用-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年的"流融合。从列表到流再到什么都没有"论文以来(，人们一直希望这种优化可以优化流融合。然而，据我所知，没有人能够使其正常可靠地工作(见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函数，它是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传递之后的核心(它还内联了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不适用于lambdas。这种漂浮需要完全的懒惰。