GHCの正格性解析を利用する

 seq関数などを利用して正格評価するよう指定したプログラムで最適化の問題が生じる原因は,GHCの単純化器の段階ですでに評価戦略が決定してしまう点にあります。そこで,GHCの正格性解析を利用すれば,評価戦略の決定を遅らせることができます。seq関数などを使って正格評価するプログラムを直接記述するのではなく,正格性解析を利用して,最終的なコンパイル結果で正格評価が行われるようにするのです。

 単純化器で正格性解析を実行している段階では,正格性解析の結果は直接はGHCコアに反映されずに,あくまでメタ情報としてGHCコアの中に保持されます(参考リンク1参考リンク2)。

 正格性解析の結果はCorePrepで適用されます。遅延評価を行うプログラムが,正格性解析によって最終的に正格評価を行うプログラムになれば,GHCの最適化機能は妨げられません。

 例を見てみましょう。GHCの正格性解析を使って,main関数内部で呼び出されるsum関数が正格評価されるようにコンパイルします。

 ちなみに,ここでは『Haskell 98』の言語仕様で提示されているfoldl関数の定義ではなく,GHCのソースコードで使われているfoldl関数の定義を使用しています。理由は後述します。

import Prelude hiding (foldl, sum)

main = print $ sum [0..1000000]

sum              :: (Num a) => [a] -> a
sum              =  foldl (+) 0

foldl        :: (a -> b -> a) -> a -> [b] -> a
foldl f z0 xs0 = lgo z0 xs0
             where
                lgo z []     =  z
                lgo z (x:xs) = lgo (f z x) xs

 正格性解析の結果を見るには,最適化オプション-O<n>を使ってコンパイルします。GHCの正格性解析は,最適化オプションを使用しなければ有効にならないからです。加えて,正格性解析は他の最適化と連携して実行されるので,単純に正格性解析だけを有効にするよりも,-O<n>オプションを付けるほうが適切な結果を得られます(参考リンク)。

$ ghc Lazy2.hs -fforce-recomp -O2 -ddump-simpl
[1 of 1] Compiling Main             ( Lazy2.hs, Lazy2.o )

==================== Tidy Core ====================
Rec {
Main.main_lgo [Occ=LoopBreaker]
  :: GHC.Integer.Type.Integer
     -> [GHC.Integer.Type.Integer]
     -> GHC.Integer.Type.Integer
[GblId, Arity=2, Caf=NoCafRefs, Str=DmdType SS]
Main.main_lgo =
  \ (z_abQ :: GHC.Integer.Type.Integer)
    (ds_dq5 :: [GHC.Integer.Type.Integer]) ->
    case ds_dq5 of _ {
      [] -> z_abQ;
      : x_abS xs_abT ->
        Main.main_lgo (GHC.Integer.plusInteger z_abQ x_abS) xs_abT
    }
end Rec }

Main.main7 :: GHC.Integer.Type.Integer
[GblId,
 Caf=NoCafRefs,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=0, Value=True,
         ConLike=True, Cheap=True, Expandable=True,
         Guidance=IF_ARGS [] 1 2}]
Main.main7 = GHC.Integer.Type.S# 0

~ 略 ~

Main.main3 :: GHC.Integer.Type.Integer
[GblId,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=0, Value=False,
         ConLike=False, Cheap=False, Expandable=False,
         Guidance=IF_ARGS [] 3 0}]
Main.main3 = Main.main_lgo Main.main7 Main.main4

~ 略 ~

 GHCコアには,sum関数の最適化により生成されたmain_lgo関数とmain7変数が出力されています。main_lgo関数の型と定義の間には,関数に対するメタ情報「[GblId, Arity=2, Caf=NoCafRefs, Str=DmdType SS]」が埋めこまれています。「Str=DmdType SS」の部分が正格性解析の結果です(参考リンク)。

 正格性の情報は,関数の引数ごとに付与されます。正格だと判断された引数は「S」,非正格だと判断された引数は「L」です。「Str=DmdType SS」は,main_lgo関数の二つの引数が正格であり,遅延評価から正格評価に変更しても意味が変わらないため正格評価されるべきであることを示しています(参考リンク1参考リンク2)。

 CorePrepでは,正格性解析の結果を利用して「GHC.Integer.plusInteger z_abQ x_abS」がcase式を使った変数束縛になります。すなわち正格評価されます。

$ ghc Lazy2.hs -fforce-recomp -O2 -ddump-prep
[1 of 1] Compiling Main             ( Lazy2.hs, Lazy2.o )

==================== CorePrep ====================
Rec {
Main.main_lgo [Occ=LoopBreaker]
  :: GHC.Integer.Type.Integer
     -> [GHC.Integer.Type.Integer]
     -> GHC.Integer.Type.Integer
[GblId, Arity=2, Caf=NoCafRefs, Str=DmdType SS, Unf=OtherCon []]
Main.main_lgo =
  \ (z_sR7 :: GHC.Integer.Type.Integer)
    (ds_sR5 :: [GHC.Integer.Type.Integer]) ->
    case ds_sR5 of _ {
      [] -> z_sR7;
      : x_sRa xs_sRc ->
        case GHC.Integer.plusInteger z_sR7 x_sRa of sat_sRg { __DEFAULT ->
        Main.main_lgo sat_sRg xs_sRc
        }
    }
end Rec }

~ 略 ~

  最終的に生成されるプログラムでは正格評価が行われるので,領域漏れの問題は生じません。

$ ./Lazy2
500000500000

 ただし,正格性解析も万能ではありません。まず,最適化オプションを使うかどうかで正格性解析の結果が変わってきます。インライン化や書き換え規則の適用などの最適化が行われれば,正格性解析の対象となるコードの構造が変わるからです。このため,GHCiによる対話的なプログラム開発には利用できません。また,正格性解析を利用しても,必ず正格評価が行われるようコンパイルされるとは限りません。

 先の節で述べたように,遅延評価するよう定義されたプログラムをやみくもに正格評価に書き換えると,プログラムの意味そのものが変わり,「何も問題のなかったプログラムで例外が発生するようになったり,遅延評価では終了する計算が終了しなくなったりしてしまう」といった問題が発生する危険性があります。

 この問題を避けるために,GHCの最適化機能では,正格性解析器を使って「関数内のそれぞれの変数に対し,正格になる値を関数が束縛しているかどうか」を判断し,「正格になる値を束縛する変数」だけを正格評価を行うように書き換えるという保守的な方針を採用しています。もともと正格なプログラムに対して正格評価を行うように変更しても意味は変わないからです。

 しかし,保守的である必要がない場合もあります。例えば値が⊥にならないことがテストによって保証されており,関数を非正格から正格に書き換えても問題ないことがわかっているかもしれません。あるいは関数が例外処理の中で利用されているため,関数を適用する値が⊥であっても,例外処理によって適切に処理される場合もあります。こうした場合でも,正格性解析器では単純に関数が値に対して正格であるかどうかだけを判断し,その結果を使って正格評価への書き換えが行われます。

 また,GHCの正格性解析はプログラムのコンパイル時にコード片に対して行われます。このため正格性解析の精度にはおのずと限界があります。プログラマには正格であることがわかっているプログラムであっても,正格性解析では正格だと判断できないかもしれません。

 したがって,正格性解析を最大限に生かすには,正格性解析器がプログラムを正格だと判断しやすいようにプログラムを書き換える必要があります。

 例えば「Haskell 98」のfoldl関数の定義を使った場合,「f z x」を正格評価するようにはコンパイルされません。このため先のfoldl関数の例では,GHCのソースコードでのfoldl関数の定義を使いました。

import Prelude hiding (foldl, sum)

main = print $ sum [0..1000000]

sum              :: (Num a) => [a] -> a
sum              =  foldl (+) 0

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

 Haskell98の定義では,lgoという内部関数を経由せずに,再帰を直接行う形でfoldl関数を定義しています。第38回で説明したように,GHCはインライン化のループが発生するのを避けるために再帰関数をインライン化しません。foldl関数の定義がインライン化されなければ,正格評価は行われません。

$ ghc Lazy2.hs -fforce-recomp -O2 -ddump-simpl
[1 of 1] Compiling Main             ( Lazy2.hs, Lazy2.o )

==================== Tidy Core ====================
Rec {
Main.foldl [Occ=LoopBreaker]
  :: forall a_abE b_abF.
     (a_abE -> b_abF -> a_abE) -> a_abE -> [b_abF] -> a_abE
[GblId, Arity=3, Caf=NoCafRefs, Str=DmdType LLS]
Main.foldl =
  \ (@ a_akP)
    (@ b_akQ)
    (f_abH :: a_akP -> b_akQ -> a_akP)
    (z_abI :: a_akP)
    (ds_dqj :: [b_akQ]) ->
    case ds_dqj of _ {
      [] -> z_abI;
      : x_abL xs_abM ->
        Main.foldl @ a_akP @ b_akQ f_abH (f_abH z_abI x_abL) xs_abM
    }
end Rec }

Main.main7 :: GHC.Integer.Type.Integer
[GblId,
 Caf=NoCafRefs,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=0, Value=True,
         ConLike=True, Cheap=True, Expandable=True,
         Guidance=IF_ARGS [] 1 2}]
Main.main7 = GHC.Integer.Type.S# 0

~ 略 ~

Main.main3 :: GHC.Integer.Type.Integer
[GblId,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=0, Value=False,
         ConLike=False, Cheap=False, Expandable=False,
         Guidance=IF_ARGS [] 4 0}]
Main.main3 =
  Main.foldl
    @ GHC.Integer.Type.Integer
    @ GHC.Integer.Type.Integer
    GHC.Integer.plusInteger
    Main.main7
    Main.main4

~ 略 ~

 foldl関数がインライン化されないため,Integer型での+演算子の実体であるplusIntegerの正格性を「sum関数内部で使用されるfoldl関数の正格性」の判断材料として使うことはできません。このため「引数f_s113と引数z_s110に対してfoldlは非正格であり,引数ds_s10Yに対してfoldlは正格である」というLLSの判断がそのまま使われます。

 foldl関数は引数z_s110に対して非正格なので,「f z x」に相当する「f_s113 z_s110 x_s114」はlet式を使った遅延評価の変数束縛としてコンパイルされます。

$ ghc Lazy2.hs -fforce-recomp -O2 -ddump-prep
[1 of 1] Compiling Main             ( Lazy2.hs, Lazy2.o )

==================== CorePrep ====================
Rec {
Main.foldl [Occ=LoopBreaker]
  :: forall a_abt b_abu.
     (a_abt -> b_abu -> a_abt) -> a_abt -> [b_abu] -> a_abt
[GblId, Arity=3, Caf=NoCafRefs, Str=DmdType LLS, Unf=OtherCon []]
Main.foldl =
  \ (@ a_akE)
    (@ b_akF)
    (f_s113 :: a_akE -> b_akF -> a_akE)
    (z_s110 :: a_akE)
    (ds_s10Y :: [b_akF]) ->
    case ds_s10Y of _ {
      [] -> z_s110;
      : x_s114 xs_s116 ->
        let {
          sat_s11a :: a_akE
          [LclId]
          sat_s11a = f_s113 z_s110 x_s114 } in
        Main.foldl @ a_akE @ b_akF f_s113 sat_s11a xs_s116
    }
end Rec }

~ 略 ~

 このように,プログラムの書き方によって,正格評価できる場合とできない場合があります。期待通り正格評価されない場合には,seq関数などを使って正格評価するようプログラムを書き換える前に,正格性解析の結果やGHCコアの出力などを見て,どこに問題があるかを探ってみてください。正格性解析ではどうしても正格評価すべきだと判断できない場合にのみ,seq関数などを使ってプログラムを書き換えるようにしましょう。