haskell - 防止 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

现在要取消共享 Gather 下的任何 Manifest，您可以递归地执行相同的操作，并注意在适当的时候重用原始文件

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 之后进行显式取消共享传递。