Haskell 中的融合是什么? [英] What is fusion in Haskell?

问题描述

我时不时地注意到 Haskell 文档中的以下内容:(例如在 Data.Text):

Every now and again I have been noticing the following in Haskell documentation: (for example in Data.Text):

需要融合

什么是fusion以及如何使用它?

What is fusion and how do I use it?

推荐答案

通常，融合是指旨在摆脱中间数据结构的转换.您融合 导致浪费内存分配的函数调用更有效.这实际上是 IMO 最大的 Haskell 应用之一.而且您几乎不需要做任何事情来获得它，它通过 GHC 编译器免费提供.

In general, fusion refers to transformations whose purpose is to get rid of intermediate data structures. You fuse function calls that result in wasteful memory allocations into something more efficient. This is actually IMO one of the biggest applications of Haskell being pure. And you pretty much don't need to do anything to get it, it comes for free through the GHC compiler.

因为 Haskell 是纯粹的，我们得到了一个叫做引用透明度的东西，它(来自链接)，表示表达式在任何上下文中的计算结果始终相同"¹.这意味着我可以在不改变程序实际输出内容的情况下进行非常通用的程序级操作.例如，即使不知道 x、y、z 和 w 是什么，我也总是知道

Because Haskell is pure, we get this thing called referential transparency, which (from the link), means that "expression always evaluates to the same result in any context"¹. That means that I can do very general program level manipulations without changing what the program will actually output. For example, even without knowing what x, y, z and w are I always know that

 ((x ++ y) ++ z) ++ w

将评估为与

 x ++ (y ++ (z ++ w))

然而，第二个在实践中将涉及较少的内存分配(因为 x ++ y 需要重新分配输出列表的整个前缀).

yet the second one will in practice involve less memory allocations (since x ++ y requires reallocating whole prefix of the output list).

事实上，我们可以做很多这种优化，而且，因为 Haskell 是纯粹的，我们基本上可以只移动整个表达式(替换 x, y、z 或 w 用于实际列表或计算为上述示例中的列表的表达式不会改变任何内容).这变成了一个非常机械的过程.

In fact, there are a whole lot of this sort of optimization we can do, and, because Haskell is pure, we can basically just move whole expressions around (replacing x, y, z, or w for actual lists or expressions that evaluate to lists in the example above changes nothing). This becomes a pretty mechanical process.

此外，事实证明你可以为高阶函数想出很多等价物(免费定理！).例如，

Furthermore, it turns out that you can come up with a lot of equivalences for higher order functions (Theorems for free!). For example,

map f (map g xs) = map (f . g) xs

不管f、g和xs是什么(两者在语义上是相等的).然而，虽然这个等式的两侧产生相同的值输出，但左侧的效率总是更差:它最终为中间列表 map g xs 分配空间，该列表立即被丢弃.我们想告诉编译器，当它遇到类似 map f (map g xs) 的时候，用 map (f . g) xs 替换它.而且，对于 GHC，这是通过 重写规则:

no matter what f, g, and xs are (the two sides are semantically equal). Yet while the two sides of this equation produce the same value output, the left hand side is always worse in efficiency: it ends up allocating space for an intermediate list map g xs, that is immediately thrown away. We'd like to tell the compiler to, whenever it encounters something like map f (map g xs), replace it with map (f . g) xs. And, for GHC, that is through rewrite rules:

{-# RULES     "map/map"    forall f g xs.  map f (map g xs) = map (f.g) xs #-}

f、g 和 xs 可以匹配任何表达式，而不仅仅是变量(比如 map (+1) (map (*2) ([1,2] ++ [3,4])) 转化为 map ((+1) . (*2)) ([1,2] ++ [3,4]).(似乎没有搜索重写规则的好方法，所以我编译了一个列表.这篇论文解释了动机以及 GHC 重写规则的工作原理.

The f, g, and xs can be matched against any expressions, not just variables (so something like map (+1) (map (*2) ([1,2] ++ [3,4])) gets transformed into map ((+1) . (*2)) ([1,2] ++ [3,4]). (There doesn't appear to be a good way to search for rewrite rules, so I compiled a list). This paper explains the motivation and workings of GHC rewrite rules.

实际上，不完全是.上面的内容是short-cut fusion.这个名字暗示了一个缺点:它不能很好地扩展并且调试起来很烦人.您最终不得不为相同通用功能的所有安排编写大量的临时规则.那么，你希望重复应用重写规则能够很好地简化你的表达式.

Actually, not quite. The thing above is short-cut fusion. The name sort of implies the drawback: it doesn't scale too well and is annoying to debug. You end up having to write a ton of ad-hoc rules for all arrangements of the same common functions. Then, you hope that repeated application of rewrite rules will simplify your expressions nicely.

事实证明，在某些情况下，我们可以通过组织重写规则来做得更好，这样我们就可以建立一些中间范式，然后针对该中间形式制定规则.这样，我们开始获得重写规则的热"路径.

It turns out that we can do even better in some cases by organizing our re-write rules so that we build up some intermediate normal form and then have rules targeting that intermediate form. This way, we start getting "hot" paths of rewrite rules.

这些系统中最先进的可能是流融合 针对共归纳序列(基本上是像列表这样的惰性序列).查看这篇论文和这篇论文(实际上vector 包已实现).例如，在 vector 中，您的代码首先被转换为包含 Streams 和 Bundles 的中间形式，然后以该形式进行优化，然后被转换回向量.

Probably the most advanced of these systems is stream fusion targeting coinductive sequences (basically lazy sequences like lists). Check out this thesis and this paper (which is actually pretty much how the vector package is implemented). For example, in vector, your code gets first transformed into an intermediate form involving Streams and Bundles, is optimized in that form, then gets transformed back into vectors.

Data.Text 使用流融合来最小化发生的内存分配次数(我认为这对于严格的变体尤其重要).如果您查看源，你会看到函数受融合"实际上操纵 Streams 大部分(它们的一般形式是 unstream . (stuff manipulating stream) . stream)，然后在那里是一堆用于转换 Stream 的 RULES 编译指示.最后，这些函数的任何组合都应该融合在一起，以便只需要进行一次分配.

Data.Text uses stream fusion to minimize the number of memory allocations that occur (I think this is especially important for the strict variant). If you check out the source, you'll see that the functions "subject to fusion" actually manipulate Streams for the most part (they are of the general form unstream . (stuff manipulating stream) . stream) and there are a bunch of RULES pragmas for transforming Streams. In the end, any combination of these functions is supposed to get fused so that only one allocation needs to occur.

了解您的代码何时进行融合的唯一真正方法是充分了解所涉及的重写规则并充分了解 GHC 的工作原理.也就是说，您应该做一件事:尽可能使用非递归高阶函数，因为这些可以(至少现在，但通常会更)容易融合.

The only real way to know when your code is subject to fusion is to have a good understanding of the rewrite rules involved and understand well how GHC works. That said, there is one thing that you should do: try to use non-recursive higher order functions when possible, since these can be (at least for now, but in general will always be more) easily fused.

因为 Haskell 中的融合是通过重复应用重写规则而发生的，所以只要让自己相信每个重写规则的正确性，就可以知道整个融合"程序与原始程序所做的事情相同.除了有与程序终止有关的边缘情况.例如，人们可能认为

Because fusion in Haskell occurs through repeated application of rewrite rules, it suffices to convince yourself of each rewrite rule's correctness to know that the whole "fused" program does the same thing as your original program does. Except there are edge cases relating to programs terminating. For example, one might think that

 reverse (reverse xs) = xs

但这显然不是真的，因为 head $ reverse (reverse [1..]) 不会终止，而 head [1..] 会终止.来自 Haskell Wiki 的更多信息.

yet that is clearly not true, since head $ reverse (reverse [1..]) will not terminate yet head [1..] will. More information from the Haskell Wiki.

¹ 这实际上是正确的，前提是在这些上下文中表达式保持相同的类型.

¹ This is actually true only provided that in these contexts the expression maintains the same type.

这篇关于Haskell 中的融合是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！