防止Haskell中某些子树的可观察共享
我有一个EDSL，它提供了数组的列表式组合器（ map ， zipWith等）。
一些组合器需要某些输入才能随机访问。 例如， Gather的数据数组在另一个指定的索引处从数据数组中挑选元素：
Gather (Manifest [10,11,12]) (Manifest [2,0,0,1,2]) = [12,10,10,11,12]
该语言使用data-reify通用包来恢复共享。 问题是有时同一个子树包含需要提供随机访问的节点和可以顺序计算的节点。 让他们共享会破坏随后的评估者。
例如，在下面的树中，我希望[1,2,3]保持共享，但Manifests将它们包装为恢复图中的不同节点：
[1, 2, 3]
/
Manifest Manifest
| |
| Map (+1)
/
Gather
一个更复杂的例子可能包括许多共享节点，所有这些节点应该变得不同（即使Map (+1) (Manifest [1,2,3])可以共享。
[1, 2, 3]
/
Manifest Manifest
| |
Map (+1) Map (+1)
| /|
Map (*2) / |
/ |
Gather |
|
ZipWith (+)
即使我找到了一个简单案例的解决方案（直接Gather引用Manifest ），它已经涵盖了大部分用例。
任何指针都欢迎！
下面是一个简单的语言模型。
module NoSharing where
data AST = Manifest [Int]
| Map (Int -> Int) AST
| ZipWith (Int -> Int -> Int) AST AST
| Gather AST -- ^ Data
AST -- ^ Indices
complex = ZipWith (+) gathered indexes
where
gathered = Gather (Map (*2) indexes) indexes
indexes = Map (+1) $ Manifest [1,2,3]
simple = Gather dat indexes
where
dat = Manifest [1,2,3]
indexes = Map (+1) dat
一种方法是在调用data-reify通知之前手动消除共享。 例如，该函数应该有希望取消共享顶层Manifest构造函数，但保留其参数共享：
rebuildManifest :: AST -> AST
rebuildManifest (Manifest xs) = Manifest xs
rebuildManifest t = t
现在取消共享任何Manifest下Gather ，你可以做同样的事情递归，同时注意在适当的时候重新使用原来的
rebuildAllManifestsUnderGather :: AST -> (AST, Bool)
rebuildAllManifestsUnderGather t@(Map f t') =
let (newt', reuse) = rebuildAllManifestsUnderGather t'
in if reuse then (t, True) else (Map f newt', False)
rebuildAllManifestsUnderGather t@(ZipWith f t1 t2) =
let (newt1, reuse1) = rebuildAllManifestsUnderGather t1
(newt2, reuse2) = rebuildAllManifestsUnderGather t2
in if reuse1 && reuse2 then (t, True) else (ZipWith f newt1 newt2, False)
rebuildAllManifestsUnderGather t@(Gather t1 t2) =
let (newt1, reuse1) = rebuildManifest $ rebuildAllManifestsUnderGather t1
(newt2, reuse2) = rebuildManifest $ rebuildAllManifestsUnderGather t2
in if reuse1 && reuse2 then (t, True) else (Gather newt1 newt2, False)
where rebuildManifest (Manifest xs, _) = (Manifest xs, False)
rebuildManifest (t, reuse) = (t, reuse)
rebuildAllManifestsUnderGather t@(Manifest xs) = (t, True)
但是， 需要注意的是 ：可观察分享并不能保证，并且可能在两个方向都不可靠。 GHC优化器可以合法地“重新分享”上述取消共享Manifest的尝试。 我不知道它在实践中会做什么。
而且这个解决方案相当复杂，所以考虑到易碎性，在调用data-reify reify之后，最好有一个明确的不共享通道。
上一篇: Preventing observable sharing for certain subtrees in Haskell