하스켈

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 참조를 간단한 경우에 대한 해결책을 찾을 경우에도), 이미 대부분의 사용 사례를 다룰 것입니다.

모든 안내를 환영합니다!

아래는 간단한 언어의 모형입니다.

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) 뒤에 명시적인 공유 해제 패스를 설정하는 것이 좋습니다.