GHC能否真的不内联地图，scanl，foldr等？ [英] Can GHC really never inline map, scanl, foldr, etc.?

问题描述

我注意到 GHC手册说对于自我递归函数，循环断路器只能是函数本身，所以一个INLINE编译指示总是被忽略。

这不是说每个应用程序都有通用的递归函数像 map ， zip ， scan * ， fold * ， sum 等无法内联？

当您使用它们时，您可以随时重写所有这些功能，添加适当的严格标签，或者采用像流融合这样的花式技术 here 。

然而，这并不是所有这些都会显着限制我们编写代码的能力同时又快又优雅？

解决方案

的确，GHC目前不能内联递归函数。但是：

• GHC仍然会专门用于递归函数。例如，给定
  
  

    fac ::（等式a，数字a）=> a  - > a 
   fac 0 = 1 
   fac n = n * fac（n-1）
   
   f :: Int  - > Int 
  fx = 1 + fac x 
    

  GHC会发现 fac 用于类型 Int - > Int 并为该类型生成 fac 的专用版本，该类型使用快速整数算术。

  
  
  

  这种专业化在模块中自动发生（例如，如果在同一模块中定义 fac 和 f ）。对于跨模块专业化（例如，如果在不同模块中定义了 f 和 fac ），具有 INLINABLE pragma 的专门功能：
  
  

    { - ＃INLINABLE fac＃ - } 
   fac ::（等式a，数字a）=> a  - > a 
   ... 
    




• 有一些手动转换可以使函数不递归。功耗最低的技术是静态参数转换，它适用于递归函数的参数在递归调用时不会改变（例如许多高阶函数，如 map ， filter ， fold * ）。这个转变转变为

$ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ xs


  转换为

    map f xs0 = go xs0 
   where 
   go [] = [] 
   go（x：xs）= fx：go xs 
   
   g :: [Int]  - > [Int] 
  g xs = map（2 *）xs 
    
  将会有 map 内联并成为 
   
   
    g [] = [] 
  g（x： xs）= 2 * x：g xs 
    
  此转换已应用于Prelude函数，如 foldr 和 foldl 。
   




• 使许多函数不是递归的，并且比静态参数变换更强大。列入内容列表的主要方法是快捷方式融合。基本的方法是尽可能多地编写使用 foldr 和/或 build 的非递归函数;那么所有的递归都被捕获在 foldr 中，并且有特殊的RULES用于处理 foldr 。

  
  
  

  利用这种融合原则上很简单：避免手动递归，更喜欢库函数，比如 foldr ， map ， filter 以及此列表。特别是，以这种风格编写代码会产生同时又快又优雅的代码。

现在的库如 text 和 vector a>在幕后使用流融合。唐·斯图尔特写了一对博客文章（ 1 ， 2 ）在现在已过时的图书馆中展示了这一行动 uvector ，但是相同的原则适用于文本和矢量。



与捷径融合一样，利用流文本和向量中的流融合原则上很简单：避免手动递归，更喜欢已被标记为易融合的库函数。 致力于改善GHC以支持递归函数的内联。这属于超级编译的标题，最近的工作似乎已经被引导通过 Max Bolingbroke 和 Neil Mitchell 。

I've noticed the GHC manual says "for a self-recursive function, the loop breaker can only be the function itself, so an INLINE pragma is always ignored."

Doesn't this say every application of common recursive functional constructs like map, zip, scan*, fold*, sum, etc. cannot be inlined?

You could always rewrite all these function when you employ them, adding appropriate strictness tags, or maybe employ fancy techniques like the "stream fusion" recommended here.

Yet, doesn't all this dramatically constrain our ability to write code that's simultaneously fast and elegant?

解决方案

Indeed, GHC cannot at present inline recursive functions. However:

• GHC will still specialise recursive functions. For instance, given

  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 will spot that fac is used at type Int -> Int and generate a specialised version of fac for that type, which uses fast integer arithmetic.

  This specialisation happens automatically within a module (e.g. if fac and f are defined in the same module). For cross-module specialisation (e.g. if f and fac are defined in different modules), mark the to-be-specialised function with an INLINABLE pragma:

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

• There are manual transformations which make functions nonrecursive. The lowest-power technique is the static argument transformation, which applies to recursive functions with arguments which don't change on recursive calls (eg many higher-order functions such as map, filter, fold*). This transformation turns

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

  into

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

  so that a call such as

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

  will have map inlined and become

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

  This transformation has been applied to Prelude functions such as foldr and foldl.

• Fusion techniques are also make many functions nonrecursive, and are more powerful than the static argument transformation. The main approach for lists, which is built into the Prelude, is shortcut fusion. The basic approach is to write as many functions as possible as non-recursive functions which use foldr and/or build; then all the recursion is captured in foldr, and there are special RULES for dealing with foldr.

  Taking advantage of this fusion is in principle easy: avoid manual recursion, preferring library functions such as foldr, map, filter, and any functions in this list. In particular, writing code in this style produces code which is "simultaneously fast and elegant".

• Modern libraries such as text and vector use stream fusion behind the scenes. Don Stewart wrote a pair of blog posts (1, 2) demonstrating this in action in the now obsolete library uvector, but the same principles apply to text and vector.

  As with shortcut fusion, taking advantage of stream fusion in text and vector is in principle easy: avoid manual recursion, preferring library functions which have been marked as "subject to fusion".

• There is ongoing work on improving GHC to support inlining of recursive functions. This falls under the general heading of supercompilation, and recent work on this seems to have been led by Max Bolingbroke and Neil Mitchell.

这篇关于GHC能否真的不内联地图，scanl，foldr等？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！