Prevenire la condivisione osservabile per alcuni sottostrutture in Haskell

Question

Ho un EDSL che offre combinatori lista simile per gli array (map, zipWith, ecc ..)

Alcuni combinatori richiedono determinati ingressi di essere ad accesso casuale. Per esempio. la matrice di dati di Gather raccogliere gli elementi dell'array dati a indici specificati dall'altra:

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

Il linguaggio fa uso di data-reify pacchetto per il recupero condivisione. Il problema è che a volte la stessa sottostruttura contiene entrambi i nodi che devono fornire accesso casuale e quelli che possono essere calcolati in sequenza. Averli condivisi interrompe il valutatore successivo.

Ad esempio nell'albero sotto desidero per [1,2,3] continuare a essere condivisi, ma la Manifests avvolgendoli essere diversi nodi nel grafico recuperato:

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

Un esempio più complesso può comprendere un numero di nodi condivisi tutto ciò dovrebbe diventare distinti (anche se Map (+1) (Manifest [1,2,3]) potrebbe essere condivisi.

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

anche se trovo una soluzione per il caso semplice (Gather riferimenti Manifest direttamente), coprirà già la maggior parte dei casi d'uso.

Qualsiasi suggerimento è benvenuto!

Di seguito è riportato un semplice mock-up della lingua.

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

Un modo si potrebbe fare questo è quello di eliminare manualmente la condivisione prima di chiamare data-reify. Ad esempio, questa funzione dovrebbe auspicabilmente annullare la condivisione di un costruttore di livello superiore Manifest, ma lasciare il suo argomento condiviso:

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

Ora annullare la condivisione di qualsiasi Manifest sotto un Gather, si potrebbe fare la stessa cosa in modo ricorsivo, avendo cura di riutilizzare il originale quando appropriato

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) 

Tuttavia, essere avvertiti: condivisione osservabili non sono garantite e potrebbe essere inaffidabile in entrambe le direzioni. L'ottimizzatore di GHC potrebbe legalmente "ricondividere" i tentativi di annullare la condivisione di Manifest sopra. Non so cosa potrebbe fare nella pratica.

Anche questa soluzione è abbastanza complessa, quindi data la fragilità, potrebbe essere meglio avere un pass unsharing esplicito dopo chiamare data-reify.