PR

GHCコアで見る遅延評価と正格評価の違い

 正格評価では最適化の問題が起こる可能性もあります。この問題を考えるために,遅延評価を行うプログラムと,seq関数などを利用して正格評価するよう指定したプログラムが,それぞれどのようにコンパイルされるかを見てみましょう。

 GHC 7.0.3では,プログラムを最適化する際に「seq関数などを使用してプログラムに付加した正格性の情報」を保持しているわけではありません。GHCの中間形式であるGHCコア(コア言語)では,let式やcase式を使って値の評価方法を表現します(参考リンク1参考リンク2参考リンク3)。

let
遅延評価される値に対する変数束縛
letrec
遅延評価される値に対する変数束縛(変数を再帰的に評価)
case
正格評価される値に対する変数束縛

 GHCコアで関数やラムダ式の適用による暗黙の変数束縛が行われている場合には,遅延評価と正格評価のいずれが行われるかはまだ決まっていません。のちの正格性解析などの結果を利用し,暗黙の変数束縛から陽にlet式やcase式を使った変数束縛へと書き換えるタイミングで決定します。

 ためしにfoldl関数とfoldl'関数をコンパイルした結果を比べてみましょう。foldl関数を-ddump-simplオプション付きでコンパイルすると,以下のようなGHCコアが出力されます。このオプションで出力されるのは,第38回で紹介したGHCの「単純化器」で最適化されたGHCコアです。

module Laxy2 where
import Prelude hiding (foldl)

foldl            :: (a -> b -> a) -> a -> [b] -> a
foldl f z []     =  z
foldl f z (x:xs) =  foldl f (f z x) xs

$ ghc Lazy2.hs -c -ddump-simpl

==================== Tidy Core ====================
Rec {
Laxy2.foldl [Occ=LoopBreaker]
  :: forall a_abp b_abq.
     (a_abp -> b_abq -> a_abp) -> a_abp -> [b_abq] -> a_abp
[GblId, Arity=3, Caf=NoCafRefs]
Laxy2.foldl =
  \ (@ a_abJ)
    (@ b_abK)
    (f_abr :: a_abJ -> b_abK -> a_abJ)
    (z_abs :: a_abJ)
    (ds_dbN :: [b_abK]) ->
    case ds_dbN of _ {
      [] -> z_abs;
      : x_abv xs_abw ->
        Laxy2.foldl @ a_abJ @ b_abK f_abr (f_abr z_abs x_abv) xs_abw
    }
end Rec }

 foldlでの「f z x」に相当する「f_abr z_abs x_abv」は,暗黙の変数束縛を伴う関数呼び出しになっています。つまり,「f z x」が遅延評価されるのか正格評価されるのかは,これだけではわかりません。それを確認するには,「f z x」の結果を陽に変数に割り当てるような,より先の段階の情報を出力する必要があります。

 GHCでは,プログラムをGHCコアに変換した後,GHCコアよりも低水準のSTGという中間形式に変換します。STGは「Spineless Tagless G-machine」と呼ばれる抽象機械の上で実行できるように定義された言語です。STGでは暗黙の変数束縛は行われず,関数を呼び出して処理を行った結果は必ず変数に保存ます。

 GHCでは,プログラムをSTGに変換する前の準備段階として「関数呼び出しの結果を変数に割り当てる」といった正規化を行います。この準備を行うのが「CorePrep」です(参考リンク)。CorePrepでの処理の結果を出力させれば,「f_abr z_abs x_abv」がどう評価されるかを,STGではなくGHCコアの形式で確認できます。CorePrepでの処理の結果は,-ddump-prepオプションで出力します(参考リンク)。

$ ghc Lazy2.hs -c -ddump-prep

==================== CorePrep ====================
Rec {
Laxy2.foldl [Occ=LoopBreaker]
  :: forall a_abp b_abq.
     (a_abp -> b_abq -> a_abp) -> a_abp -> [b_abq] -> a_abp
[GblId, Arity=3, Caf=NoCafRefs, Unf=OtherCon []]
Laxy2.foldl =
  \ (@ a_abJ)
    (@ b_abK)
    (f_sbY :: a_abJ -> b_abK -> a_abJ)
    (z_sbV :: a_abJ)
    (ds_sbT :: [b_abK]) ->
    case ds_sbT of _ {
      [] -> z_sbV;
      : x_sbZ xs_sc1 ->
        let {
          sat_sc3 :: a_abJ
          [LclId]
          sat_sc3 = f_sbY z_sbV x_sbZ } in
        Laxy2.foldl @ a_abJ @ b_abK f_sbY sat_sc3 xs_sc1
    }
end Rec }

 foldlの「f z x」に相当する「f_sbY z_sbV x_sbZ」の結果は,let式を使って変数sat_sc3に束縛されています。つまり「f z x」は遅延評価されます。これはfoldlの定義で期待した通りの振る舞いです。

 次に,foldl'関数をコンパイルした結果を見てみましょう。

module Laxy2 where
import Prelude hiding (foldl)

foldl'           :: (a -> b -> a) -> a -> [b] -> a
foldl' f a []     = a
foldl' f a (x:xs) = let a' = f a x in a' `seq` foldl' f a' xs

$ ghc Lazy2.hs -c -ddump-simpl

==================== Tidy Core ====================
Rec {
Laxy2.foldl' [Occ=LoopBreaker]
  :: forall a_abp b_abq.
     (a_abp -> b_abq -> a_abp) -> a_abp -> [b_abq] -> a_abp
[GblId, Arity=3, Caf=NoCafRefs]
Laxy2.foldl' =
  \ (@ a_abK)
    (@ b_abL)
    (f_abr :: a_abK -> b_abL -> a_abK)
    (a_abs :: a_abK)
    (ds_dbP :: [b_abL]) ->
    case ds_dbP of _ {
      [] -> a_abs;
      : x_abv xs_abw ->
        case f_abr a_abs x_abv of a'_abH { __DEFAULT ->
        Laxy2.foldl' @ a_abK @ b_abL f_abr a'_abH xs_abw
        }
    }
end Rec }

$ ghc Lazy2.hs -c -ddump-prep

==================== CorePrep ====================
Rec {
Laxy2.foldl' [Occ=LoopBreaker]
  :: forall a_abp b_abq.
     (a_abp -> b_abq -> a_abp) -> a_abp -> [b_abq] -> a_abp
[GblId, Arity=3, Caf=NoCafRefs, Unf=OtherCon []]
Laxy2.foldl' =
  \ (@ a_abK)
    (@ b_abL)
    (f_sc1 :: a_abK -> b_abL -> a_abK)
    (a_sbX :: a_abK)
    (ds_sbV :: [b_abL]) ->
    case ds_sbV of _ {
      [] -> a_sbX;
      : x_sc0 xs_sc4 ->
        case f_sc1 a_sbX x_sc0 of a'_sc3 { __DEFAULT ->
        Laxy2.foldl' @ a_abK @ b_abL f_sc1 a'_sc3 xs_sc4
        }
    }
end Rec }

 foldl'での「let a' = f a x in a'」をコンパイルした結果は,-ddump-simplでも-ddump-prepでも「case f_sc1 a_sbX x_sc0 of a'_sc3」というcase式を使った変数束縛になります。つまり「f z x」は正格評価されます。これはfoldl'の定義で期待した通りの振る舞いです。

 これらのコンパイル結果の違いは,通常は気にする必要はありません。しかし,書き換え規則を使ってプログラムを効率化する場合には問題になります。第38回で説明したように,書き換え規則を使ったプログラムの最適化は,GHCの単純化器で行われます。

 例えば,seq関数などを使って正格評価するように書かれたプログラムは,GHCの単純化器の段階ですでにcase式を使った変数束縛に変換されています。その結果,書き換え規則を適用できなくなります。

 このように,正格評価を利用すると書き換え規則などのGHCの最適化機能が働かなくなることがあります(参考リンク1参考リンク2)。