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と関数適用についてだ。

  1. case式はネストした評価に対応する。「case e of _ {...}」を実行する際は、戻りアドレスをスタックにプッシュした上でeの評価を開始する。評価が終わって、プッシュしておいたアドレスに制御が戻ると、戻り値を調べて分岐する。eが単純なプリミティブ演算の場合は、呼び出しを経ずにインラインで直接それを実行する。
  2. 関数適用はジャンプ(末尾呼び出し)に対応する。「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読むけど。