GHC真的不会内联地图,扫描,折叠等吗？

Question

我注意到GHC手册说"对于自递归函数,环路断路器只能是函数本身,因此INLINE编译指示总是被忽略."

这难道不是说像普通的递归功能结构的每一个应用程序map,zip,scan*,fold*,sum,等不能被内联？

您可以随时重写所有这些功能,添加适当的严格标签,或者使用像这里推荐的"流融合"这样的花哨技术.

然而,这并不是所有这些都极大地限制了我们编写同时快速和优雅的代码的能力吗？

Answer 1

实际上,GHC目前无法实现内联递归函数.然而:

• GHC仍然会专门提供递归函数.例如,给定

  fac :: (Eq a, Num a) => a -> a
  fac 0 = 1
  fac n = n * fac (n-1)
  
  f :: Int -> Int
  f x = 1 + fac x
  

  GHC将发现fac在类型中使用Int -> Int并生成该类型的专用版本,fac该版本使用快速整数运算.

  这种专业化发生内的模块自动地(例如,如果fac与f同一模块中定义).为跨模块专业化(例如,如果f和fac在不同的模块中定义)中,标记与待专门功能的可以内联的pragma:

  {-# INLINABLE fac #-}
  fac :: (Eq a, Num a) => a -> a
  ...
  

• 有手动转换使函数非递归.最低功耗技术是静态的参数变换,它适用于递归函数与不递归调用(如许多高阶功能,如更改参数map,filter,fold*).这种转变开始了

  map f []     = []
  map f (x:xs) = f x : map f xs
  

  成

  map f xs0 = go xs0
    where
      go []     = []
      go (x:xs) = f x : go xs
  

  这样的电话如

   g :: [Int] -> [Int]
   g xs = map (2*) xs
  

  将map内联并成为

   g [] = []
   g (x:xs) = 2*x : g xs
  

  此转换已应用于诸如foldr和之类的Prelude函数foldl.

• 融合技术也使许多函数非递归,并且比静态参数转换更强大.列表的主要方法是Prelude中的快捷融合.基本方法是尽可能多地编写函数作为使用foldr和/或的非递归函数build; 然后捕获所有的递归foldr,并有特殊的规则来处理foldr.

  以这种融合的优势是在原则很简单:避免了人工递归,宁愿库函数,例如foldr,map,filter,和任何函数此列表.特别是,以这种方式编写代码会产生"同时快速和优雅"的代码.

• 文本和矢量等现代图书馆在幕后使用流融合.唐·斯图尔特写道:一对博客文章(的1,2)在现在已经过时的库演示这个动作uvector,但同样的原则也适用于文本和矢量.

  与快捷方式融合一样,利用文本和向量中的流融合原则上很容易:避免手动递归,更喜欢被标记为"融合"的库函数.

• 目前正在努力改进GHC以支持递归函数的内联.这属于超级编译的总标题,最近的工作似乎是由Max Bolingbroke和Neil Mitchell领导的.

Answer 2

简而言之,不像你想象的那么频繁.原因是在实现库时使用了诸如流融合之类的"花哨技术",并且库用户不需要担心它们.

考虑Data.List.map.基础包定义map为

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

这map是自我递归的,因此GHC不会内联它.

但是,base还定义了以下重写规则:

{-# RULES
"map"       [~1] forall f xs.   map f xs                = build (\c n -> foldr (mapFB c f) n xs)
"mapList"   [1]  forall f.      foldr (mapFB (:) f) []  = map f
"mapFB"     forall c f g.       mapFB (mapFB c f) g     = mapFB c (f.g) 
  #-}

这取代了mapvia foldr/build fusion的使用,然后,如果函数无法融合,则将其替换为原始函数map.因为融合是自动发生的,所以它不依赖于用户意识到它.

作为一切有效的证明,您可以检查GHC为特定输入生成的内容.对于这个功能:

proc1 = sum . take 10 . map (+1) . map (*2)

eval1 = proc1 [1..5]
eval2 = proc1 [1..]

当使用-O2编译时,GHC将所有内容融合proc1到一个递归形式中(如核心输出中所示-ddump-simpl).

当然,这些技术可以实现的目标是有限的.例如,简单的平均函数mean xs = sum xs / length xs可以很容易地手动转换成单个折叠,并且存在可以自动执行此操作的框架,但是目前还没有已知的方法可以在标准函数和融合框架之间自动转换.因此,在这种情况下,用户确实需要了解编译器生成的代码的限制.

因此,在许多情况下,编译器已经足够先进,可以创建快速而优雅的代码.知道何时会这样做,以及何时编译器可能会崩溃,恕我直言是学习如何编写高效Haskell代码的很大一部分.