前回で説明した書き換え規則は，プログラムの実行を効率化するのに有用です。しかし，書き換え規則が意図どおりに動かなかったり，書き換え規則を使用することで思わぬ結果が生じたりすることもあります。

　今回は，そうした問題を解決するのに役立つ「段階制御」という機能を取り上げます。

三つのステップでインライン化

　GHCでは，書き換え規則の適用とインライン化を「単純化器（simplifier）」と呼ばれる部分で並行して行います。インライン化とは，式の中の「関数や変数の呼び出し」を「関数や変数の定義」に置き換えるようなプログラム変換のことです。インライン化によって関数や変数の呼び出しが消えることで，プログラムをより効率的に動作させることが可能になります。

　まず，インライン化がどのように行われるかを説明しましょう。

　GHCでのインライン化は，三つのステップで行われます。「展開（unfolding）」，「不要コードの除去（dead code elimination，無用コードの除去）」，「β-簡約（beta-reduction）」です。β-簡約は「β-変換（beta-conversion）」ともいいます。

　まず，関数や変数の定義を，関数や変数を利用している部分に展開します。このステップが狭義のインライン化です。「インライン展開」と呼ぶこともあります。

    let f = \x -> x + 1 in f 2
==> { インライン展開 }
    let f = \x -> x + 1 in (\x -> x + 1) 2

　関数や変数をインラインに展開した結果，関数や変数の定義が必要なくなることがあります。この場合，不要になった関数や変数の定義を除去します。これが不要コードの除去です（参考リンク）。

    let f = \x -> x + 1 in (\x -> x + 1) 2
==> { 不要コードの除去 }
    (\x -> x + 1) 2

　関数をインラインに展開した結果，「(\x -> x + 1) 2」のような「関数を値に適用する式」ができることがあります。この場合，関数の中の変数を値で置き換えます。これがβ-簡約です（参考リンク）。

    (\x -> x + 1) 2
==> { β-簡約 }
    2 + 1

　実は，前回の説明で「-ddump-simpl-stats」オプションを使って出力させた統計情報には，こうしたインライン化に対する情報が含まれていました。

$ ghc -O -c Rewrite.hs -ddump-simpl-stats

〜 略 〜
==================== Grand total simplifier statistics ====================
Total ticks:     106

40 PreInlineUnconditionally
12 PostInlineUnconditionally
10 UnfoldingDone
〜 略 〜
31 BetaReduction
〜 略 〜
9 SimplifierDone

　インライン化の結果「2+1」のような定数のみを使った式がプログラム中に現れる場合には，その定数を使ってコンパイル時に式の評価を行うことがあります。このような処理を「定数畳み込み（constant folding）」と呼びます（参考リンク）。

    2 + 1
==> { 定数畳み込み }
    3

　インライン化の例をもう一つ見てみましょう。前回取り上げたbuild関数を使う場合です。build関数にはINLINE指示文が付いています。

build   :: forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
{-# INLINE [1] build #-}
        -- The INLINE is important, even though build is tiny,
        -- because it prevents [] getting inlined in the version that
        -- appears in the interface file.  If [] *is* inlined, it
        -- won't match with [] appearing in rules in an importing module.
        --
        -- The "1" says to inline in phase 1
build g = g (:) []

　「build (\c n -> foldr (mapFB c f) n xs)」という式は，以下のようにインライン化されます。

    build (\c n -> foldr (mapFB c f) n xs)
==> { インライン展開 }
    (\c n -> foldr (mapFB c f) n xs) (:) []
==> { β-簡約 }
    foldr (mapFB (:) f) [] xs

　INLINE指示文の有無が，インライン化が行われるかどうかを決定しているのではないことに注意してください。先の「let f = \x -> x + 1 in (\x -> x + 1) 2」のような式があれば，INLINE指示文が付いていなくても処理系はインライン化を行います。GHCでは，関数や変数の規模があまり大きくなければ，INLINE指示文を付けていなくても勝手にインライン化を行うのです。インライン化したくない関数には，必ずNOINLINE指示文を付ける必要があります。

　逆に，INLINE指示文を付けていてもインライン化が行われないこともあります。関数や変数をインライン化することで明らかな不利益がある場合です。

　例えば，関数や変数の定義が大きく，しかもその関数や変数が2回以上使われている場合，処理系が生成するバイナリのサイズがインライン化により肥大化する可能性があります。この問題は，プログラマが巨大な関数や変数の定義を書かないよう心がけるだけでは防げません。関数や変数の定義自体がインライン化によって大きく膨れ上がることがあるからです。こうした場合には，下手にインライン化するよりも，関数を呼び出すほうが実行時のコストが低くなります。

　インライン化が不利益になるもう一つの状況は，関数や変数が再帰的な構造を持つ場合です。関数や変数が再帰的に定義されていると，関数や変数をインライン化するときに元の式が出現します。この結果，インライン化が繰り返され，ループが生じてしまいます。

　例としてmap関数について考えてみましょう。

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

　map関数は再帰的な関数なので，map関数をインライン化しようとすると，インライン化の過程でmap関数が出てきます。

map _ []     = []
map f (x:xs) = f x : map f xs
==> { case 式に変換
    （正確には，コア言語に変換するときに実行） }
map f xs'
  = case xs' of
         []   -> []
         x:xs -> f x : map f xs
==> { インライン化 }
map f xs'
  = case xs' of
         []   -> []
         x:xs -> f x : case xs of
                            []   -> []
                            y:ys -> f y : map f ys
==> ... 

　この結果，インライン化のループが発生してしまいます。

　このように再帰関数のインライン化はループを生じさせてしまうので，GHCでは再期関数をインライン化しません。INLINE指示文が再帰的な関数に対して宣言されている場合，GHCはINLINE指示文を無視することでループの発生を防ぎます。

　さて，処理系が勝手にインライン化を行うのなら，INLINE指示文の意義はどこにあるのでしょうか？

　INLINE指示文の意義の一つは，プログラマが処理系に対して「この関数をインライン化したい」という意図を示すところにあります。現行のGHC 6.12.1では，INLINE指示文を使用しているかどうかで，関数をインライン化すべきかどうかの判断の重み付けを変えています。INLINE指示文を付けている関数のほうがインライン化されやすくなるのです（参考リンク）。

　このあたりについて詳しく知りたい方は，GHCのインライン化の仕組みについて書かれた論文「Secrets of the Glasgow Haskell Compiler inliner」やGHCのソースコードのコメントを読んでください。「Secrets of the Glasgow Haskell Compiler inliner」には，今回説明を省略したインライン化の詳細な戦略が書いてあります。また，GHCのソースコードのコメントには，「Secrets of the Glasgow Haskell Compiler inliner」の執筆後，新たに追加・変更された最新のインライン化戦略が記述されています。

　INLINE指示文を使うもう一つの意義は，今回のテーマである段階制御を利用できるということです。段階制御により，INLINE指示文を使わない場合に比べて，コードを柔軟に効率化できるようになります。