あどけない話

インターネットに関する技術的な話など

GHC は再帰を末尾再帰に最適化するか?

GHC に -ddump-simpl オプションを渡すと、Core 形式(中間表現の関数型言語)を出力するというので、Performance/Accumulating parameterのコードに対して Core を出力しみた。

len

末尾再帰でない len のコードはこう。

len :: [a] -> Int
len [] = 0
len (x:xs) = len xs + 1

これに対して、Core を出力させるとこう。明らかに末尾再帰には直されてない。

len_rfB =
  \ (@ a_afQ) (ds_dyA :: [a_afQ]) ->
    case ds_dyA of wild_B1 {
      [] -> GHC.Types.I# 0;
      : x_afH xs_afJ ->
        GHC.Num.+
          @ GHC.Types.Int
          GHC.Num.$f6
          (len_rfB @ a_afQ xs_afJ)
          (GHC.Types.I# 1)
    }

GHC に -O2 を渡して、Core を出力させるとこう。末尾再帰に直っているような気がする。

Main.$wlen =
  \ (@ a_afu) (w_sIa :: [a_afu]) ->
    case w_sIa of wild_B1 {
      [] -> 0;
      : x_afw xs_afy ->
        case Main.$wlen @ a_afu xs_afy of ww_sId { __DEFAULT ->
        GHC.Prim.+# ww_sId 1
        }
    }

追記:case of の部分で $wlen を先に呼び、後で + しているので、末尾再帰にはなってないそうです。(shelarcy さんより)

len'

ついでに末尾再帰の len' に対してもやってみる。

len' :: [a] -> Int -> Int
len' [] acc = acc
len' (x:xs) acc = len' xs (1 + acc)

GHC に -O2 を渡さないとこうなる。

len'_rfF =
  \ (@ a_afY) (ds_dyR :: [a_afY]) (acc_afL :: GHC.Types.Int) ->
    case ds_dyR of wild_B1 {
      [] -> acc_afL;
      : x_afN xs_afP ->
        len'_rfF
          @ a_afY
          xs_afP
          (GHC.Num.+ @ GHC.Types.Int GHC.Num.$f6 (GHC.Types.I# 1) acc_afL)

GHC に -O2 を渡すとこうなる。

Main.$wlen' =
  \ (@ a_afH) (w_sIw :: [a_afH]) (ww_sIz :: GHC.Prim.Int#) ->
    case w_sIw of wild_B1 {
      [] -> ww_sIz;
      : x_afN xs_afP -> Main.$wlen' @ a_afH xs_afP (GHC.Prim.+# 1 ww_sIz)
    }

コメント&議論を求む!