什么是 haskell 核聚变?

hc2pp10m  于 12个月前  发布在  其他
关注(0)|答案(2)|浏览(187)

我不时地在Haskell文档中注意到以下内容:(例如在Data.Text中):
进行融合
什么是“融合”以及如何使用它?

8wtpewkr

8wtpewkr1#

一般来说,融合是指转换,其目的是摆脱中间数据结构。你 * 融合 * 函数调用,导致浪费内存分配到更有效的东西。这实际上是IMO Haskell纯最大的应用之一。你几乎不需要做任何事情来获得它,它通过GHC编译器免费提供。

Haskell是纯的

因为Haskell是纯的,所以我们得到了一个叫做referential transparency的东西,(来自链接),意味着“表达式在任何上下文中总是计算出相同的结果“1.这意味着我可以在不改变程序实际输出内容的情况下进行非常通用的程序级操作。例如,即使不知道xyzw我一直都知道

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

字符串
将评估为相同的东西,

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


而第二种方法实际上将涉及较少的存储器分配(因为x ++ y需要重新分配输出列表的整个前缀)。

重写规则

事实上,我们可以做很多这样的优化,而且,因为Haskell是纯的,我们基本上可以移动整个表达式(替换xyzw为实际列表或上面例子中计算为列表的表达式)。
此外,事实证明,你可以为高阶函数(Theorems for free!)提出很多等价。例如,

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


无论fgxs是什么(两边在语义上相等)。然而,虽然这个等式的两边产生相同的价值输出,但左手边的效率总是更差:它最终为一个中间列表map g xs分配了空间,这个中间列表立即被丢弃。我们想告诉编译器,每当它遇到类似map f (map g xs)的东西时,用map (f . g) xs替换它。对于GHC,这是通过重写规则:

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


fgxs可以与任何表达式匹配,而不仅仅是变量(所以像map (+1) (map (*2) ([1,2] ++ [3,4]))这样的东西被转换为map ((+1) . (*2)) ([1,2] ++ [3,4])。(There doesn't appear to be a good way to search for rewrite rules,所以我编译了一个list)。This paper解释了GHC重写规则的动机和工作原理。

原来GHC是这样优化map的?

实际上,不完全是。上面的东西是short-cut fusion。这个名字有点暗示了缺点:它不能很好地扩展,调试起来很烦人。你最终不得不为相同的公共函数的所有安排编写大量的ad-hoc规则。然后,你希望重复应用重写规则会很好地简化你的表达式。
事实证明,在某些情况下,通过组织重写规则,我们可以做得更好,这样我们就可以构建一些中间范式,然后拥有针对该中间范式的规则。这样,我们开始获得重写规则的“热”路径。
这些系统中最先进的可能是靶向共诱导序列的stream fusion(基本上是像列表一样的惰性序列)。(这实际上是vector包的实现方式)。例如,在vector中,您的代码首先转换为涉及Stream s和Bundle s的中间形式,优化成这个形式,然后再转换成向量。
还有... Data.Text
Data.Text使用流融合来最小化发生的内存分配次数。(我认为这对严格变体尤其重要).如果你查看源代码,你会看到函数“subject to fusion”实际上大部分操作Stream s(它们的一般形式是unstream . (stuff manipulating stream) . stream),并且有一堆RULES杂注用于转换Stream s。最后,这些功能的任何组合都被认为是融合的,从而仅需要发生一次分配。

那么,我需要为我的日常编码学习什么呢?

要想知道你的代码什么时候会被融合,唯一真实的方法就是对重写规则有一个很好的理解,并理解GHC是如何工作的。也就是说,有一件事你应该做的:尽可能使用非递归的高阶函数,因为这些函数可以(至少现在是这样,但总的来说会更容易)被融合。

并发症

由于Haskell中的融合是通过重复应用重写规则来实现的,因此只要让自己相信每个重写规则的正确性,就足以知道整个“融合”程序与原始程序做的事情相同。除了与程序终止相关的边缘情况。例如,有人可能会认为,

reverse (reverse xs) = xs


然而,这显然不是真的,因为head $ reverse (reverse [1..])不会终止,而head [1..]会终止。
1只有在这些上下文中表达式保持相同的类型时,这才是真的。

xxb16uws

xxb16uws2#

TL;DR:

Fusion是中间数据结构,就像内联是函数一样。

这是一种由编译器完成的优化技术。编译器可能需要一些(有时是手写的)转换规则的支持,以便使更多的东西融合,而不仅仅是显而易见的东西。
在许多命令式语言中,只有函数/子例程可以内联。在Haskell中可以做得更多:内联函数可能会产生这样有趣的情况:

case (if a==b then Just 42 else Nothing) of
    Just x -> print x
    Nothing -> return ()

字符串
现在的结果将归功于Fusion:

if a==b then print 42 else return ()


为了更频繁地使用这种优化,可能需要存在一些transformation rules,比如i.e.

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


.所以fg可以在这里融合。然后我们说,map f . map g中的map fmap g也融合了,而且不仅是以创建列表并使用它的明显方式,而且更深:在fg之间。
另请参见https://wiki.haskell.org/GHC_optimisations#Fusion

相关问题