7.21. 書き換え規則

プログラマは、ソースプログラムの一部として(プラグマで)書き換え規則を指定することができる。 以下に例を示す。

{-# RULES
"map/map"    forall f g xs.  map f (map g xs) = map (f.g) xs
  #-}

どの規則が発動したかを見るには-ddump-simpl-statsというデバッグフラグを使えばよい。もっと情報が必要な場合は、-ddump-rule-firingsによって、個々の規則発動を見ることができるし、-ddump-rule-rewritesなら、書き換えの前と後でコードがどんな風であったかを見ることができる。

7.21.1. 構文

構文の観点からは、以下がいえる。

  • 一つのRULESプラグマには零個以上の規則を書ける。規則の間はセミコロンで区切る。(このセミコロンはレイアウト規則によって生成されたものでもよい)

  • プラグマ内ではレイアウト規則が適用される。現在、新しいインデントの水準が設定されることはない。そのため、一つのRULESプラグマに複数の規則を書いて、レイアウトを使ってそれを区切りたい場合、外側の定義と同じ位置で開始するように配置しなければならない。

    {-# RULES
"map/map"    forall f g xs.  map f (map g xs) = map (f.g) xs
"map/append" forall f xs ys. map f (xs ++ ys) = map f xs ++ map f ys
  #-}

    さらに、閉じ括弧#-}は開き括弧{-#よりも右で始まっているようにするべきである。

  • 全ての規則には名前があり、二重引用符で囲って示される。名前自体には全く意味はない。規則が何回発動したかを報告する際に用いられるだけである。

  • 規則名の直後に段階番号(7.20.6.5. 段階制御を見よ)を書くこともできる。次のように。

    {-# RULES
      "map/map" [2]  forall f g xs. map f (map g xs) = map (f.g) xs
  #-}

    ここでの「[2]」は、この規則が段階2以降(段階2を含む)で有効になることを意味している。逆の記法である「[~2]」を使うこともでき、規則が段階2まで有効(段階2自体は含まない)という意味である。

    規則は特殊な段階制御記法"[~]"に対応している。これは、規則が有効になることが決してないことを意味する。この機能はプラグイン(9.3. コンパイラプラグインを見よ)用である。これによって、GHCには実行されないものの、パース、型検査などされ、プラグインによって利用可能になるような規則を定義することが可能になる。

  • 規則中で言及される変数は、スコープにある(mapのように)か、forallで束縛される(f、g、xsのように)かのどちらかでなければならない。forallで束縛された変数はパターン変数と呼ばれる。パターン変数は、型のforallの場合と同じく、空白で区切る。

  • パターン変数には型シグネチャをつけても良い。パターン変数の型が多相的なら、その変数には型シグネチャが必須である。例えば、以下はfoldr/build規則である。

    "fold/build"  forall k z (g::forall b. (a->b->b) -> b -> b) .
              foldr k z (build g) = g k z

    gの型は多相的なので、型シグネチャを与える必要がある。

  • 規則の左辺は、最上位の変数を任意の式に適用したものでなければならない。例えば、以下のものは正しくない。

    "wrong1"   forall e1 e2.  case True of { True -> e1; False -> e2 } = e1
"wrong2"   forall f.      f True = True

    "wrong1"では、左辺が適用でない。"wrong2"では、左辺の先頭がパターン変数である。

  • 規則は、それが言及する変数(のどれか)と同じモジュールにある必要はない。もちろん、それらはスコープになければならないが。

  • 規則は全て暗黙にモジュールからエクスポートされ、したがって規則を定義したモジュールを直接または間接にインポートしたモジュールの全てで有効である。(つまり、AがBをインポートしていて、BがCをインポートしている場合、AをコンパイルするときにCの規則が有効である)この状況はインスタンス宣言の場合と非常に良く似ている。

  • RULEの内部において、「forall」は他のフラグ設定の如何にかかわらずキーワードとして扱われる。さらに、RULE内部では、言語拡張-XScopedTypeVariablesが自動的に有効になる。7.13.8. 字句的スコープを持つ型変数 を見よ。

  • 他のプラグマと同様、RULEプラグマは常にスコープの誤りを検査され、型検査される。型検査というのは、規則の左辺と右辺が型検査され、さらに同じ型でなければならないということである。しかし、規則が有効になるのは-fenable-rewrite-rulesフラグが有効な時だけである(7.21.2. 意味論を見よ)。

7.21.2. 意味論

意味論の観点からは以下のことが言える。

  • 規則は-fenable-rewrite-rulesフラグによって有効になる(つまり、最適化に使われる)。このフラグは-Oによって有効になり、(いつも通り)-fno-enable-rewrite-rulesで解除できる。(注意: 一方、-Oなしで-fenable-rewrite-rulesを有効にしても期待通りにはならないかもしれない。なぜなら-OなしではGHCはインタフェースファイル中の全ての最適化情報を無視するからである。-fignore-interface-pragmas、4.10.2. -f*: プラットフォーム非依存のフラグを見よ。)-fenable-rewrite-rulesは最適化フラグであって、パースや型検査には効果を及ぼさないことに注意。

  • 規則は左から右への書き換えの規則だとみなされる。規則の左辺の置換例であるような式が見付かると、その式は右辺(に適切な置換を施したもの)に置き換えられる。「置換例」というのは、左辺に、パターン変数について置換を施すことで、その式と等しくすることができる、という意味である。

  • 規則の左辺と右辺が同じ意味かどうかについては、GHCは一切検証を試みない。これは一般的には決定不能であるし、興味深い場合について実行不可能である。これについて、責任は完全にプログラマにある。

  • GHCは規則が合流性や停止性を持つことを確かめようとはしない。例。

    "loop"        forall x y.  f x y = f y x

    この規則はコンパイラを無限ループさせる。

  • 一つの呼び出しに複数の規則が適合する場合は、恣意的に一つが選ばれる。

  • 現在、GHCでは、規則の左辺を式と照合するに当たって、非常に単純で構文的な照合アルゴリズムが使われている。左辺と式を、α変換を法として構文的に等しくするような置換を探すのである。パターン(規則)は必要ならη展開されるが、式はされない。(式をη展開すると遅延性にかかわるバグにつながる)。また、β変換(高階照合と呼ばれる)は行わない。

    照合はGHCの中間言語で行われる。この言語には型抽象と型適用があるので、規則は型が合うときのみ適合する。下の7.21.5. 特殊化 を見よ。

  • GHCは、最適化過程において、常に規則を適用しようとする。例として以下のものを考えてみよう。

    let s = map f
    t = map g
in
s (t xs)

    式s (t xs)は規則"map/map"に適合しないが、GHCはsとtを置換するので、結果として適合する式ができる。sやtが(a)二度以上使われていて、かつ(b)大きかったり簡約項だったりする、場合は、これらは置換されないので、規則が発動することもない。

7.21.3. 書き換え規則と、INLINE/NOINLINEおよびCONLIKEプラグマとの間の相互作用

通常のインライン化は規則による書き換えと同時に起きる。これによって予期せぬ結果につながることがある。次の(人為的な)例を考えよ。

f x = x
g y = f y
h z = g True

{-# RULES "f" f True = False #-}

fの右辺は小さいので、gへとインライン化され、次のような結果になる。

g y = y

次にgがhへとインライン化されるが、fのRULEが発動する機会はない。GHCが逆にまずgをhへとインライン化していたら、fのRULEが発動する機会はより大きかっただろう。

振る舞いを予測可能にするには、fにNOINLINEプラグマかINLINE[phase]プラグマを使って、RULEに発動の機会があるうちにインライン化されることがないようにすれば良い。

GHCは、仕事を複製することに関して非常に慎重である。例として次を考えよ。

f k z xs = let xs = build g
           in ...(foldr k z xs)...sum xs...
{-# RULES "foldr/build" forall k z g. foldr k z (build g) = g k z #-}

xsが二回使われているので、GHCはfold/build規則を発動しない。これは正しい動作である。なぜなら、xsを計算するのに大量の作業が必要かもしれず、規則が発動したらその作業が複製されるからである。

しかし、場合によっては、この方針では慎重すぎることがある。例え簡約基を複製することになっても、規則に発動してもらいたい場合である。これが良案だということをGHCが見つけ出す方法はないので、そのことを宣言するためのCONLIKEプラグマを提供している。次のようにする。

{-# INLINE CONLIKE [1] f #-}
f x = blah

CONLIKEは、INLINEまたはNOINLINEプラグマに対する修飾子である。fを一つの引数(一般には、'='記号の左側にある引数の数)に適用することが十分低コストで、複製によって規則が発動するならば複製できる、ということを示す。(「CONLIKE」という名前は"constructor-like"の短縮形である。構築子(constructor)は確実にこの性質を持つので) CONLIKEプラグマはINLINE/NOINLINEの修飾子であるが、これは次のような事情による。すなわち、規則が発動する前にfがインライン化されてしまわないことがはっきりしているのでない限り、fを規則の左辺と照合するのは実際上意味がないからである。

7.21.4. リストの融合変換

RULES機構は、良く使われるリスト関数についての融合変換(伐採)を実装するのに使われている。「優良生産者」の構築した中間リストを「優良消費者」が消費する場合、このリストは完全に排除されるはずである。

以下のものが優良生産者である。

  • リスト内包表記

  • IntおよびIntegerおよびCharについての列挙(例えば['a'..'z'])。

  • 明示的なリスト(例: [True, False])

  • cons構築子(例: 3:4:[])

  • ++

  • map

  • take, filter

  • iterate, repeat

  • zip, zipWith

以下は優良消費者である。

  • リスト内包表記

  • array (第二引数について)

  • ++ (第一引数について)

  • foldr

  • map

  • take, filter

  • concat

  • unzip, unzip2, unzip3, unzip4

  • zip, zipWith (ただし引数一つについてのみ。両方が優良生産者の場合、zipは片方のみと融合する)

  • partition

  • head

  • and, or, any, all

  • sequence_

  • msum

よって、例えば以下のものは中間リストを生成しないはずである。

array (1,10) [(i,i*i) | i <- map (+ 1) [0..9]]

この一覧を拡張することはいつでもできる。良く使うPrelude関数でここに含まれていないものがあったら教えてほしい。

自分で優良生産者や優良消費者を書きたいときは、上の関数のPreludeでの定義を見てどうするか知ると良い。

7.21.5. 特殊化

書き換え規則を使って、GHCの昔の版で使えた、ある機能と同等のことを行える。例として、以下のものを考えよ。

genericLookup :: Ord a => Table a b   -> a   -> b
intLookup     ::          Table Int b -> Int -> b

ここで、intLookupは、キーがIntの時に非常に高速に動作するgenericLookupの実装である。genericLookupが型Table Int b -> Int -> bで呼ばれたときは代わりにintLookupを使うようにさせたいと思うかもしれない。次のように書くことが可能だった。

{-# SPECIALIZE genericLookup :: Table Int b -> Int -> b = intLookup #-}

この機能はもはやGHCにはないが、書き換え規則を使って同等のことができる。

{-# RULES "genericLookup/Int" genericLookup = intLookup #-}

この少々奇妙な規則は、genericLookupをintLookupに、型が適合するときはいつでも置き換えるように指示するものである。さらに、SPECIALIZEプラグマの場合と違って、この規則はgenericLookupと同じモジュールにある必要がない。(SPECIALIZEプラグマの場合は、特殊化するのに元の定義が必要である)

intLookupがちゃんとgenericLookupの特別な場合として振る舞うようにするのはあなたの責任である！！！

RULESを使った特殊化が高い効果をあげる例を一つ挙げる。

toDouble :: Real a => a -> Double
toDouble = fromRational . toRational

{-# RULES "toDouble/Int" toDouble = i2d #-}
i2d (I# i) = D# (int2Double# i) -- Glasgowのprim-opを直接使う

i2d関数は、事実上、機械語命令一個である。これに比べると、Rationalを経由した通常の変換は、非常識なまでに効率が悪い。

7.21.6. 書き換え規則の中で何が起こるか制御する

  • このモジュールで定義された規則を見るには、-ddump-rulesを使う。これには特殊化過程で生成されたものも含むが、他モジュールからインポートされたものは除外される。

  • どの規則が発動したかを知るには-ddump-simpl-statsを使う。-dppr-debugも加えればより詳細な出力が得られる。

  • -ddump-rule-firingsや-ddump-rule-rewritesを使うと、どの規則が発動したかを極めて詳細に見ることができる。-dppr-debugを加えるとさらに詳細な一覧が得られる。

  • 例えば、GHC/Base.lhsのbuildの定義は以下の様になっている。

    build   :: forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
{-# INLINE build #-}
build g = g (:) []

    INLINEが使われていることに注意。これのおかげで、PrelBaseをコンパイルするときに(:)がインライン化されることがなく、結果としてインポート元のモジュールが(:)を「見る」ことができ、これを規則の左辺に適合させることができる。INLINEがあると、そのINLINEなものの右辺にインライン化が発生することが抑制される。私はこの気遣いを後悔している。

  • 融合変換を行い、融合が起こらなかった場合でも効率的なプログラムになるような規則の書き方についてはlibraries/base/GHC/Base.lhsにあるmapの規則を見よ。GHC/List.lhsにも規則がある。

7.21.7. COREプラグマ

外部コア形式は「Note」注釈をサポートしている。COREプラグマを使うと、どういう注釈を入れるかをHaskellコード中で指定することができる。構文的には、core注釈は式に付属し、Haskellの文字列リテラルを引数として取る。以下の関数定義が例である。

f x = ({-# CORE "foo" #-} show) ({-# CORE "bar" #-} x)

意味上は、これは以下のものに等しい。

g x = show x

しかし、(-fext-coreで)外部coreが生成されるとき、式showとxにNoteが付加される。fのcoreでの宣言は以下である。

f :: %forall a . GHCziShow.ZCTShow a ->
                 a -> GHCziBase.ZMZN GHCziBase.Char =
  \ @ a (zddShow::GHCziShow.ZCTShow a) (eta::a) ->
      (%note "foo"
       %case zddShow %of (tpl::GHCziShow.ZCTShow a)
         {GHCziShow.ZCDShow
          (tpl1::GHCziBase.Int ->
                 a ->
                 GHCziBase.ZMZN GHCziBase.Char -> GHCziBase.ZMZN GHCziBase.Char)
          (tpl2::a -> GHCziBase.ZMZN GHCziBase.Char)
          (tpl3::GHCziBase.ZMZN a ->
                 GHCziBase.ZMZN GHCziBase.Char -> GHCziBase.ZMZN GHCziBase.Char) ->
            tpl2})
      (%note "bar"
       eta);

ここで、関数show(これは展開されてShow辞書についてのcase式になっている)に%noteが付属していることが分かる。eta(xという名前だったもの)も同様である。