防止Haskell中某些子树的可观察共享

Question

我有一个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

Answer 1

您可以执行此操作的一种方法是在致电之前手动消除共享data-reify。例如，这个函数应该希望取消共享顶级Manifest构造函数，但保留其参数共享：

rebuildManifest :: AST -> AST
rebuildManifest (Manifest xs) = Manifest xs
rebuildManifest t = t

现在要取消共享Manifesta 下的任何内容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。