Simplifier

至って普通のGHCだけど、Core Simplifierが面白い。
Playing by the Rules: Rewriting as a practical optimisation technique in GHC
どうでもいいけど、実装系の話はPeyton Jonesの独断場だな

{-# OPTIONS -fglasgow-exts #-}
{-# RULES "map/map" forall f g xs. map f (map g xs) = map (f . g) xs #-}
test::[Integer]
test = map (+2) (map (+1) [1,2,3,4,5])
main = return test

とかやって、-ddump-simplを見ると(STGでもいいですが)、

lit_r1Co :: GHC.Num.Integer
[GlobalId]
[NoCafRefs]
lit_r1Co = GHC.Num.S# 5

lit1_r1Cq :: GHC.Num.Integer
[GlobalId]
[NoCafRefs]
lit1_r1Cq = GHC.Num.S# 4

lit2_r1Cs :: GHC.Num.Integer
[GlobalId]
[NoCafRefs]
lit2_r1Cs = GHC.Num.S# 3

lit3_r1Cu :: GHC.Num.Integer
[GlobalId]
[NoCafRefs]
lit3_r1Cu = GHC.Num.S# 1

lit4_r1Cw :: GHC.Num.Integer
[GlobalId]
[NoCafRefs]
lit4_r1Cw = GHC.Num.S# 2

test1_r1Cy :: [GHC.Num.Integer]
[GlobalId]
[]
test1_r1Cy = GHC.Base.map
               @ GHC.Num.Integer
               @ GHC.Num.Integer
               (GHC.Base..
                  @ GHC.Num.Integer
                  @ GHC.Num.Integer
                  @ GHC.Num.Integer
                  (\ (ds_d1BR :: GHC.Num.Integer) ->
                     case GHC.Num.Integer GHC.Num.$fNumInteger
                     of tpl_B1 { GHC.Num.:DNum tpl1_B2 tpl2_B3 tpl3_B4 tpl4_B5 tpl5_B6 tpl6_B7 tpl7_B8 tpl8_B9 tpl9_Ba ->
                     tpl3_B4 ds_d1BR lit4_r1Cw
                     })
                  (\ (ds_d1BV :: GHC.Num.Integer) ->
                     case GHC.Num.Integer GHC.Num.$fNumInteger
                     of tpl_B1 { GHC.Num.:DNum tpl1_B2 tpl2_B3 tpl3_B4 tpl4_B5 tpl5_B6 tpl6_B7 tpl7_B8 tpl8_B9 tpl9_Ba ->
                     tpl3_B4 ds_d1BV lit3_r1Cu
                     }))
               (GHC.Base.:
                  @ GHC.Num.Integer
                  lit3_r1Cu
                  (GHC.Base.:
                     @ GHC.Num.Integer
                     lit4_r1Cw
                     (GHC.Base.:
                        @ GHC.Num.Integer
                        lit2_r1Cs
                        (GHC.Base.:
                           @ GHC.Num.Integer
                           lit1_r1Cq
                           (GHC.Base.: @ GHC.Num.Integer lit_r1Co (GHC.Base.[] @ GHC.Num.Integer))))))

となって、test1_r1Cyの部分が、map ( (+2).(+1) ) [1,2,3,4,5]をコンパイルした結果と同じになる。すんげーと思ったけど、

map (+2) $ map (+1) [1,2,3,4,5]

だと、この最適化は効かないとか、結構バカっぽい。$も一応関数なので、そこらへんで書換え不能になるみたいで。

仕方ないので、

{-# OPTIONS -fglasgow-exts #-}
{-# RULES "map/map" forall f g xs. map f (map g xs) = map (f . g) xs #-}
{-# RULES "$-expand" forall f x . f $ x = f x #-}

test::[Integer]
test = map (+2) $ map (+1) [1,2,3,4,5]
main = return test

とかルールを追加すればいいような。一応GHCライブラリソース見ると、あちこちにRULESがちりばめられてるけど、これって使われてんのかな。だとすると、$を使うと、かかるはずの最適化がされなかったりするってこと?まあ、自分で上のルール追加しとけばいいわけですが。というか、$使うと、普通に一個関数呼び出しが増えるのか。なんてバカなんだorz(バカなのは私の方でしたorz最適化オプション付ければよいと教えていただきました)それと、合流性とかは多分ないと思うので、ルールの適用順序に依存して結果が変わるのはどうなの、それ。別にいいんじゃね？とか、そんなこんな

あと、嘘ルールを書くと、間違った結果を返すことになる諸刃の剣。

{-# OPTIONS -fglasgow-exts #-}
{-# RULES "map/map" forall f g xs. map f (map g xs) = map f xs #-}
test::[Integer]
test = map (+2) ( map (+1)  [1,2,3,4,5])
main = print $  test

とか。このへん解決するには、究極的には、プログラマがルールの証明を書いて、証明パスしたルールだけ使うという方向にするしかないかな。-fext-coreで吐かれるコードは、simplifyされる前なので、普通にmapが2回適用されている。

今はまだ随分原始的だけど、このへん突き詰めれば、より効率的なアルゴリズムを自動導出できたりするのかもしれない
http://www.dcs.gla.ac.uk/jfp/online/jfpvol9-3/Gibbon/radix.lhs
というか、ある意味それがFPの見果てぬ夢とか、そんな感じかもしれない。

　　　　　　　　 ,. -‐'''''""¨¨¨ヽ
　　　　 　 　 (.＿＿_,,,... -ｧァﾌ|　　　　　　　　　　あ…ありのまま 今　起こった事を話すぜ！
　 　 　 　 　 |i i|　 　 }!　}} /／|
　　　　 　 　 |l､{　 　j}　/,,ｨ//｜　　　　　　　『おれはバブルソートを書いていたと
　　　　　　　 i|:!ヾ､_ﾉ／ u {:}//ﾍ　　　　　　　　思ったらいつのまにかクイックソートになっていた』
　　　　　　　 |ﾘ u' }　 ,ﾉ　_,!V,ﾊ |
　　 　 　 ／´fト､_{ﾙ{,ィ'ｅﾗ　, ﾀ人　　　　　　　　な…　何を言ってるのか　わからねーと思うが
　　　　 /' 　 ヾ|宀| {´,)⌒`/ |<ヽﾄiゝ　　　　　　　　おれも何をされたのかわからなかった…
　　　　,ﾞ　 ／ )ヽ iLﾚ 　u' |　| ヾｌﾄﾊ〉
　　 　 |／_／　 ﾊ !ニ⊇　'／:} 　V:::::ヽ　　　　　　　　頭がどうにかなりそうだった…
　　　 /／ 二二二7'T'' ／u'　__ /:::::::/｀ヽ
　　　/'´r　-―一ｧ‐ﾞＴ´　'"´ ／::::／-‐ 　＼　　　　インライン展開だとか定数畳み込みだとか
　　 / // 　 广¨´ 　/'　　 ／:::::／´￣｀ヽ ⌒ヽ　　　　そんなチャチなもんじゃあ　断じてねえ
　　ﾉ ' /　 ノ:::::`ー-､___／:::::／/ 　 　 　 ヽ　　}
_／｀丶　/::::::::::::::::::::::::::￣`ー-{:::...　　　 　　　ｲ　 もっと強力な最適化の片鱗を味わったぜ…

結論：「Coreダンプ」とか「STGダンプ」を張ると読みづらい