Verhindern beobachtbaren Freigabe für bestimmte Teilbäume in Haskell

Question

Ich habe eine EDSL die Liste artige combinators für Arrays bietet (map, zipWith, etc ..)

Einige combinators erfordern bestimmte Eingaben Direktzugriff sein. Z.B. das Datenfeld von Gather die Elemente von Datenarray an den Indizes von der anderen angegebenen Picking: macht

Gather (Manifest [10,11,12]) (Manifest [2,0,0,1,2]) = [12,10,10,11,12] 

Die Sprache für die Rückgewinnung Sharing Verwendung von data-reify Paket. Das Problem besteht darin, dass manchmal der gleiche Teilbaum sowohl Knoten enthält, die einen wahlfreien Zugriff ermöglichen, als auch solche, die sequentiell berechnet werden können. Wenn sie geteilt werden, bricht der nachfolgende Evaluator.

Zum Beispiel im Baum unter ich für [1,2,3] möchte geteilt halten werden, aber die Manifests Umwickeln sie verschiedene Knoten in der wiedergewonnenen Graph zu sein:

 [1, 2, 3] 
    /  \ 
Manifest Manifest 
    |  | 
    |  Map (+1) 
    \ /
    Gather 

Ein komplexeres Beispiel eine Reihe umfassen kann gemeinsame Knoten von denen alle sollten verschieden sein (obwohl Map (+1) (Manifest [1,2,3]) geteilt werden könnte.

 [1, 2, 3] 
    /  \ 
Manifest Manifest 
    |  | 
Map (+1) Map (+1) 
    |  /| 
Map (*2)/| 
    \ /| 
    Gather | 
     \ | 
     ZipWith (+) 

auch wenn ich eine Lösung für den einfachen Fall (Gather Referenzenfindendirekt), deckt es bereits die meisten Anwendungsfälle ab.

Alle Zeiger sind willkommen!

Unten ist ein einfaches Modell der Sprache.

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

Eine Möglichkeit, dies tun könnte, ist, um manuell die gemeinsame Nutzung zu beseitigen, bevor Sie data-reify nennen. Zum Beispiel sollte diese Funktion unshare hoffentlich ein Top-Level-Manifest Konstruktor, aber ihr Argument verlassen geteilt:

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

Jetzt jede Manifest unter einem Gather auf Freigabe rückgängig, könnten Sie die gleiche Sache rekursiv tun, kümmert sich die wiederzuverwenden Original, wenn entsprechende

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) 

jedoch gewarnt werden: beobachtbarer Sharing ist nicht garantiert und kann in beide Richtungen unzuverlässig sein. Der GHC-Optimierer könnte die oben genannten Versuche zur Freigabe von Manifest ganz legal "erneut teilen". Ich weiß nicht, was es in der Praxis tun würde.

Auch diese Lösung ist ziemlich komplex. Angesichts der Zerbrechlichkeit könnte es besser sein, einen expliziten Freigabepass nach zu haben, der data-reify aufruft.