하스켈에서 AST의 보편적 인 주석이 있습니까?

Question

나는 Haskell에 작성된 Elm 컴파일러를 둘러 보았다.

나는 그것을위한 몇 가지 최적화를 구현하기 시작하고 싶습니다,이 부분 등의 AST를 순회하며 꼬리 전화와 같은 특정 노드에 "주석"을 추가 포함

내가 사용할 수 있습니다 알고 SYB 또는 uniplate를 사용하여 순회를 수행하지만, 유형을 처리 할 수있는 상용구없는 방법이 있는지 궁금합니다.

data AnnotatedExpr = PlusExpr Expr Expr [Annotation] ... 

data AnnotatedDef = TypeAlias String [String] Type [Annotation] ... 

이것은 : 나는 상용구를 작성한다면

data Expr = PlusExpr Expr Expr ... 

data Def = TypeAlias String [String] Type ... 

, 나는이 같은 새로운 유형을 만들어 주겠다고 : 그래서

, 우리는 우리의 AST에 대한 대수 종류의 무리가 있다고 가정 쓸만한 많은 표식, 그리고 이것을 피하는 것이 좋은 습관처럼 보입니다.

나는 이런 식으로 뭔가를 작성할 수

Data AnnotationTree = Leaf [Annotation] 
    | Internal [AnnotationTree] [Annotation] 

그럼 난 그냥 AST에 주석 트리 실행 평행이있을 것이다. 그러나이 나무들이 같은 구조를 가질 것이라는 보장은 없으므로 유형 안전을 잃습니다.

그렇다면 정형을 피할 수 있지만 형식이 안전한 방식으로 트리에 주석을 달아주는 세련된/권장 솔루션이 있습니까? 각 노드를 동등한 노드로 바꾸고 나중에 컴파일 할 때 사용되는 주석 목록을 바꾸려면?

Answer 1

을하지만, 스켈 레탈 트리의 대부분을 변경하지 않고도 주석에 자유롭게 레이어 할 수 있습니다.

data Hutton x -- non-recursive functor type 
    = Int Int | Plus x x 
    deriving Functor 

newtype Tie f = Tie (f (Tie f)) 

data Annotate f a = Annotate { annotation :: a, layer :: (f (Annotate f a)) } 

type Unannotated = Tie  Hutton 
type Annotated a = Annotate Hutton a 

이 스타일

은 더 나은 구성하기 때문에 당신이 Hutton -algebras로 계산의 대부분을 쓸 수있을 때 훨씬 더 쉽습니다. 또한 좋은 무엇

interp :: Hutton Int -> Int 
interp (Int i) = i 
interp (Plus a b) = a + b 

runUnannotated :: Functor f => (f x -> x) -> Tie f -> x 
runUnannotated phi (Tie f) = phi (fmap (runUnannotated phi) f)  

runAnnotated :: Functor f => (f x -> x) -> Annotate f a -> x 
runAnnotated phi (Annotate _ f) = phi (fmap (runAnnotated phi) f) 

하면 (예 : 중간급 깊이 eDSL 같이) 하스켈 수준에서 라이브 바인딩의 일부 금액을시키는 괜찮다면 다음 Free Hutton 모나드가 건축하는 AST와 Cofree Hutton 위해 중대하다이다 comonad는 본질적으로 무엇입니까 Annotated입니다.

아래에서 위로 주석을 작성하는 방법은 다음과 같습니다.

annotate :: Functor f => (f b -> b) -> Tie f -> Annotate f b 
annotate phi = runUnannotated $ \x -> Annotate (phi (fmap annotation x)) x 

memoize :: Unannotated -> Annotated Int 
memoize = annotate interp 

같은 적절한 Show 및 Num 인스턴스와

λ> memoize (2 + (2 + 2)) 
Annotate 6 (Plus (Annotate 2 (Int 2)) (Annotate 4 (Plus (Annotate 2 (Int 2)) (Annotate 2 (Int 2))))) 

그리고 여기 당신이 달성하는 방법에 대한 설명은 here를 참조 그들에게

strip :: Annotated a -> Unannotated 
strip = runAnnotated Tie 

---

을 제거 할 수있는 방법하다고 이 종류의 AST는 상호 ​​반복적으로 작동합니다. e ADTs, 아래 Gallais의 코멘트에 의해 보증 됨.

Answer 2

이 질문은 소스 위치의 특정 주석에 대해 이야기하는 past one과 매우 유사합니다. 내가 가장 우아한 찾을 솔루션은 주석이 포함 된 생성자를 제공하기 위해 Expr 및 Def를 다시 정의하는 것입니다, 당신은 당신의 데이터 유형에 재귀를 떠나 당신이 사방에 여분의 생성자를 겪고 결국 열면

data Expr = PlusExpr Expr Expr 
      | AnnotatedExpr Annotation Expr 
      ... 

Answer 3

데이터 형식을 주석으로 변환하는 템플릿 하스켈 매크로를 작성할 수도 있습니다.

Answer 4

주석에 특성 문법을 사용할 수도 있습니다. 여러 가지 특수 효과가 필요한 경우 문법 접근 방식이 더 잘 확장됩니다. Hackage에는 AG 라이브러리와 전처리 기가 거의없고, 하나는 UHC/EHC 하스켈 컴파일러를 빌드하는 데 사용되는 uuagc입니다.