하스켈 : GHC에서 최적화 할 예정입니까?

Question

GHC는 id = (\(a, b) -> (a, b)).(\(a, b) -> (a, b))을 id = \(a, b) -> (a, b)으로 단순화 할 수 있습니까?

더 복잡한 사건에 대해 무엇 :

id (Just x) = Just x 
id Nothing = Nothing 

map f (Just x) = Just (f x) 
map _ Nothing = Nothing 

GHC는 map에 id . map을 단순화 할 것인가?

나는 일반 베타 감소를 사용하려고 시도했지만,이 용어는 불쾌한 패턴 매칭 때문에 환원 할 수없는 것처럼 보입니다.

따라서 GHC의 최적화 기법이 어떻게 처리되는지 궁금합니다.

Answer 1

ghc에 대한 질문은 -ddump-simpl으로 실행할 수 있습니다. 이렇게하면 ghc가 프로그램을 컴파일하는 "핵심"코드를 덤프하게됩니다. 코어는 컴파일러에서 하스켈 코드에 대한 이유와 그 코드를 기계어 코드로 변환하는 컴파일러 부분 간의 중간 언어입니다.

-O2 -ddump-simpl으로 다음을 컴파일하면 놀라운 결과를 얻었습니다.

tupid1 :: (a, b) -> (a, b) 
tupid1 = (\(a, b) -> (a, b)) 

tupid2 :: (a, b) -> (a, b) 
tupid2 = (\(a, b) -> (a, b)) . (\(a, b) -> (a, b)) 

tupid1에 대한 결과 코어는 새로운 특수화 된 아이덴티티 기능을 만든다.

-- RHS size: {terms: 4, types: 7, coercions: 0} 
tupid1 :: forall a_aqo b_aqp. (a_aqo, b_aqp) -> (a_aqo, b_aqp) 
[GblId, 
Arity=1, 
Caf=NoCafRefs, 
Str=DmdType <S,1*U(U,U)>m, 
Unf=Unf{Src=InlineStable, TopLvl=True, Value=True, ConLike=True, 
     WorkFree=True, Expandable=True, 
     Guidance=ALWAYS_IF(arity=1,unsat_ok=True,boring_ok=True) 
     Tmpl= \ (@ a_ayd) 
       (@ b_aye) 
       (ds_dIl [Occ=Once] :: (a_ayd, b_aye)) -> 
       ds_dIl}] 
tupid1 = \ (@ a_ayd) (@ b_aye) (ds_dIl :: (a_ayd, b_aye)) -> ds_dIl 

코어에서 함수에 대한 다형 유형 인수는 명시 적 인수로 표시됩니다. tupid1은 a_ayd 및 b_aye이라는 형식 인수 중 두 가지 형식 변수 인 a 및 b을 서명에 사용합니다. 또한이 두 유형의 튜플 형식 (ds_dIl :: (a_ayd, b_aye))을 갖는 용어 ds_dIl을 사용하며 수정되지 않은 상태로 반환합니다. tupid1로 단순화 GHC

-- RHS size: {terms: 1, types: 0, coercions: 0} 
tupid2 :: forall a_aqm b_aqn. (a_aqm, b_aqn) -> (a_aqm, b_aqn) 
[GblId, 
Arity=1, 
Caf=NoCafRefs, 
Str=DmdType <S,1*U(U,U)>m, 
Unf=Unf{Src=InlineStable, TopLvl=True, Value=True, ConLike=True, 
     WorkFree=True, Expandable=True, 
     Guidance=ALWAYS_IF(arity=1,unsat_ok=True,boring_ok=True) 
     Tmpl= \ (@ a_axZ) (@ b_ay0) (x_aIw [Occ=Once] :: (a_axZ, b_ay0)) -> 
       x_aIw}] 
tupid2 = tupid1 

놀라운 결과가 tupid2입니다 ...

...! 그것이 내 연역이나 발견 능력을 뛰어 넘는 것은 아닙니다.

Maybe

maybeid :: Maybe a -> Maybe a 
maybeid (Just x) = Just x 
maybeid Nothing = Nothing 

의 신원 예는 어떠한 패턴 Maybe위한 map의 핵심이 질문에 대한 흥미없는

-- RHS size: {terms: 3, types: 4, coercions: 0} 
maybeid :: forall a_aqn. Maybe a_aqn -> Maybe a_aqn 
[GblId, 
Arity=1, 
Caf=NoCafRefs, 
Str=DmdType <S,1*U>, 
Unf=Unf{Src=InlineStable, TopLvl=True, Value=True, ConLike=True, 
     WorkFree=True, Expandable=True, 
     Guidance=ALWAYS_IF(arity=1,unsat_ok=True,boring_ok=True) 
     Tmpl= \ (@ a_aqI) (ds_dIq [Occ=Once] :: Maybe a_aqI) -> ds_dIq}] 
maybeid = \ (@ a_aqI) (ds_dIq :: Maybe a_aqI) -> ds_dIq 

일치하지 갖는 항등 함수로 단순화

---

이 maybeid

maybeidmap :: (a -> b) -> Maybe a -> Maybe b 
maybeidmap f = maybeid . maybemap f 

GHC로 구성 않다면

는 그러나 maybemap

-- RHS size: {terms: 1, types: 0, coercions: 0} 
maybeidmap 
    :: forall a_aqp b_aqq. 
    (a_aqp -> b_aqq) -> Maybe a_aqp -> Maybe b_aqq 
[GblId, 
Arity=2, 
Caf=NoCafRefs, 
Str=DmdType <L,1*C1(U)><S,1*U>, 
Unf=Unf{Src=InlineStable, TopLvl=True, Value=True, ConLike=True, 
     WorkFree=True, Expandable=True, 
     Guidance=ALWAYS_IF(arity=0,unsat_ok=True,boring_ok=True) 
     Tmpl= maybemap}] 
maybeidmap = maybemap 

로 단순화 그리고 id는 f로 구성되어있는 경우 같은 일을한다.

maybemapid :: (a -> b) -> Maybe a -> Maybe b 
maybemapid f = maybemap (id . f) 

식별 기능을 갖는 조성물을 제거하고, 전체 기능 maybemap

-- RHS size: {terms: 1, types: 0, coercions: 0} 
maybemapid 
    :: forall a_aqq b_aqr. 
    (a_aqq -> b_aqr) -> Maybe a_aqq -> Maybe b_aqr 
[GblId, 
Arity=2, 
Caf=NoCafRefs, 
Str=DmdType <L,1*C1(U)><S,1*U>, 
Unf=Unf{Src=InlineStable, TopLvl=True, Value=True, ConLike=True, 
     WorkFree=True, Expandable=True, 
     Guidance=ALWAYS_IF(arity=2,unsat_ok=True,boring_ok=False) 
     Tmpl= \ (@ a_ar2) 
       (@ b_ar3) 
       (f_aqL [Occ=Once!] :: a_ar2 -> b_ar3) 
       (eta_B1 [Occ=Once!] :: Maybe a_ar2) -> 
       case eta_B1 of _ [Occ=Dead] { 
        Nothing -> GHC.Base.Nothing @ b_ar3; 
        Just x_aqJ [Occ=Once] -> GHC.Base.Just @ b_ar3 (f_aqL x_aqJ) 
       }}] 
maybemapid = maybemap 

로 단순화되고