GHCの末尾再帰最適化をCore上で確認してみる
まず簡単に再帰関数(factorialとした)を、
で記述した。
fac1 0 = 1 fac1 n = n * fac1 (n-1) fac2 n = fac' 1 n fac' acc 0 = acc fac' acc n = fac' (acc*n) (n - 1) main = do print $ fac1 35 print $ fac2 35
まあこれはいいだろう。
そうしてSTGに渡す直前のCoreを見てみる(-ddump-prep)
ghc -O1 -ddump-prep -ddump-simpl-stats main.hs > dump1
OK.そうすると以下の用な関数が見える。main_fac1はfac1に、main_fac'はfac'にそれぞれ対応している。
... snip ... Rec { Main.main_fac1 [Occ=LoopBreaker] :: GHC.Integer.Type.Integer -> GHC.Integer.Type.Integer [GblId, Arity=1, Str=DmdType <S,U>, Unf=OtherCon []] Main.main_fac1 = \ (ds_s3Xx :: GHC.Integer.Type.Integer) -> case GHC.Integer.Type.eqInteger# ds_s3Xx lvl_r3Xw of wild_s3Xy { __DEFAULT -> case GHC.Prim.tagToEnum# @ GHC.Types.Bool wild_s3Xy of _ [Occ=Dead] { GHC.Types.False -> case GHC.Integer.Type.minusInteger ds_s3Xx Main.main5 of sat_s3XA { __DEFAULT -> case Main.main_fac1 sat_s3XA of sat_s3XB { __DEFAULT -> GHC.Integer.Type.timesInteger ds_s3Xx sat_s3XB } }; GHC.Types.True -> Main.main5 } } end Rec } Rec { Main.main_fac' [Occ=LoopBreaker] :: GHC.Integer.Type.Integer -> GHC.Integer.Type.Integer -> GHC.Integer.Type.Integer [GblId, Arity=2, Str=DmdType <S,1*U><S,U>, Unf=OtherCon []] Main.main_fac' = \ (acc_s3XC [Occ=Once*] :: GHC.Integer.Type.Integer) (ds_s3XD :: GHC.Integer.Type.Integer) -> case GHC.Integer.Type.eqInteger# ds_s3XD lvl_r3Xw of wild_s3XE { __DEFAULT -> case GHC.Prim.tagToEnum# @ GHC.Types.Bool wild_s3XE of _ [Occ=Dead] { GHC.Types.False -> case GHC.Integer.Type.minusInteger ds_s3XD Main.main5 of sat_s3XH { __DEFAULT -> case GHC.Integer.Type.timesInteger acc_s3XC ds_s3XD of sat_s3XG { __DEFAULT -> Main.main_fac' sat_s3XG sat_s3XH } }; GHC.Types.True -> acc_s3XC } } end Rec } ... snip ...
さらにそれぞれの再帰部のみを抜粋する。
まずはfac1:
case Main.main_fac1 sat_s3XA of sat_s3XB { __DEFAULT -> GHC.Integer.Type.timesInteger ds_s3Xx sat_s3XB }
次にfac':
case GHC.Integer.Type.timesInteger acc_s3XC ds_s3XD of sat_s3XG { __DEFAULT -> Main.main_fac' sat_s3XG sat_s3XH }
お分かりだろうか。分からんよね。
以下に日本語でGHCの内部についてまとまっている素敵文章がある。
Core言語の操作的解釈を抜粋する。caseと関数適用についてだ。
- case式はネストした評価に対応する。「case e of _ {...}」を実行する際は、戻りアドレスをスタックにプッシュした上でeの評価を開始する。評価が終わって、プッシュしておいたアドレスに制御が戻ると、戻り値を調べて分岐する。eが単純なプリミティブ演算の場合は、呼び出しを経ずにインラインで直接それを実行する。
- 関数適用はジャンプ(末尾呼び出し)に対応する。「f v1 v2 ...」を実行するには、単にfのentry codeに飛ぶ。このとき適当な呼び出し規約に従って引数とf自身を渡す。
caseの評価はスタックを消費するらしい。関数適用は単なるジャンプらしい。
それをふまえ、もう一度再帰部を見てみる。
fac1:
case Main.main_fac1 sat_s3XA of sat_s3XB { __DEFAULT -> GHC.Integer.Type.timesInteger ds_s3Xx sat_s3XB }
case式の内部でmain_fac1を再帰呼び出ししていることが分かる。つまりこいつはスタックを消費する。
次にfac':
case GHC.Integer.Type.timesInteger acc_s3XC ds_s3XD of sat_s3XG { __DEFAULT -> Main.main_fac' sat_s3XG sat_s3XH }
最後に関数適用がされているだけ。つまりこいつはスタックを消費しない。単なるジャンプだ。
ということで末尾呼び出しがスタックを消費しない、単なるジャンプになっていることをCore上で確認する方法を確認した。
注意点としては、-ddump-prepではなく、-ddump-simplを用いて吐いたCoreを確認しても、この再帰部の構造は確認出来なかったことだ。
あとCmmは現状読めなかった。STGからCmmはstraight forwardだと書いてあったため、確認してみたが確かにまあ単純な構造になってはいそうだった、慣れれば読めるかもしれない。それならSTG読むけど。