PR

書き換え規則を使う際の注意点

 実際に書き換え規則を使う場合,いくつか注意しなければならない点があります。

 fromIntegral関数に対して型ごとに定義を与えられる点から推測できると思いますが,書き換え規則の内部でも型検査が行われます。

module Rewrite where

add1 :: Int -> Int
add1 x = 1 + x

add2 :: Double -> Double
add2 x = 2 + x

{-# RULES
"add1/add1"  forall x.  add1 (add1 x) = add2 x
  #-}

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

Rewrite.hs:10:45:
    Couldn't match expected type `Double' against inferred type `Int'
    In the first argument of `add2', namely `x'
    In the expression: add2 x
    When checking the transformation rule "add1/add1"

 書き換え規則の内部で型検査が行われた結果,add1とadd2では引数として取るxに対して要求する型が異なるため,型エラーになっています。このように,型検査で正当だと認められないプログラムの書き換えはできないので注意してください。同様に,プログラムの中の式と書き換え規則で定義された式の型が一致しない場合には,その規則でプログラムの式が書き換えられることはありません。

 型検査を利用して不当な書き換えを防ぐという制限は,書き換え規則を使って書き換えた後のプログラムが正しいことを保証するためのものです。もし書き換え規則に対して型検査が行われなければ,どんなプログラムに書き換えることも可能になってしまうため,Haskellの安全性が壊れてしまいます。このことから,書き換え規則に対して型の制限を与えているのは正当なことだと理解できると思います。

 "add1/add1"規則の中でforall量化子を使っていることにも注意してください。書き換え規則の内部で使用するローカルな変数が欲しい場合には,forall量化子を陽に使用して変数を束縛する必要があります。書き換え規則の内部でforall量化子を使って束縛した変数を「パターン変数(pattern variables)」と呼びます。書き換え規則の中でパターン変数以外の変数を使おうとした場合には,書き換え規則はモジュール内で利用できる同名の変数を探索します。その結果,エラーになったり,意図とは異なる動作になってしまったりします。

module Rewrite where

add1 :: Int -> Int
add1 x = 1 + x

add2 :: Int -> Int
add2 x = 2 + x

{-# RULES
"add1/add1"  add1 (add1 x) = add2 x
  #-}

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

Rewrite.hs:10:24: Not in scope: `x'

Rewrite.hs:10:34: Not in scope: `x'

 なお,パターン変数として束縛できるのは,関数の引数として利用されている変数に限られます。「任意の型を持つすべての関数」を書き換える規則を書こうとしてもエラーになります。

module Rewrite where

{-# RULES
"wrongForallF"  forall f (x::Int).  f x = x
  #-}

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

Rewrite.hs:4:4:
    Rule wrongForallF:
        Illegal expression: f
        in left-hand side: f x
    LHS must be of form (f e1 .. en) where f is not forall'd

 wrongForallFでは,左辺の式「f x」の関数fを書き換え規則のローカル変数として扱おうとしているため,そのような式は書けないという旨のエラー・メッセージが表示されています。

 このエラー・メッセージからさらにわかることがあります。それは,書き換え規則の左辺には,fromIntegralのような変数か,「f e1 .. en」のような関数適用しか書けないということです。if文やcase式といった「変数でも関数適用でもない式」を左辺に書いた場合にも,同様のエラー・メッセージが表示されます。

module Rewrite where

{-# RULES
"wrongExpression"  forall e1 e2. if True then e1 else e2 = e1
  #-}

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

Rewrite.hs:4:0:
    Rule wrongExpression:
        Illegal expression: if True then e1 else e2
        in left-hand side: if True then e1 else e2
    LHS must be of form (f e1 .. en) where f is not forall'd

 さらに重要な注意点があります。書き換え規則では「記述した書き換え規則(またはそれらの組み合わせ)が,常にコンパイルを終了させるかどうかは保証されない」という点です。単体の書き換え規則,あるいは複数の書き換え規則の組み合わせが,コンパイル時に無限ループを生じさせてしまう可能性があります。

 例を見てみましょう。以下のloop規則のような「引数の順番を入れ替えるだけの規則」を記述した場合,loop関数の内部で使われているadd関数に対して何度も同じ規則が適用されます。

module Rewrite where

add :: Int -> Int -> Int
add x y = x + y

loop = add 1 2

{-# RULES
"loop"        forall x y.  add x y = add y x
  #-}

 この結果,「書き換え規則による式の書き換えの無限ループ」が生じてしまい,強制終了させるまでコンパイルが延々と続くことになります。

$ ghc -O2 -c Rewrite.hs -ddump-simpl-stats
(応答なし)

 書き換え規則を書く場合には,無限ループが生じるような規則にならないよう注意してください。

 最後の注意点は,「書き換え規則は既存のコードを別のコードに書き換えるものである」という事実を忘れないことです。新たな書き換え規則を提供する場合には,最適化前のコードと書き換え規則を適用した後のコードの両方をテストする必要があります。