プログラムの処理は，いつも効率的であるとは限りません。非効率的な処理があれば，別の効率的な処理に置き換える必要があります。プログラムのアルゴリズムやデータ構造に問題がない場合には，こうした最適化は通常は処理系が行います。
しかし，処理系に実装されている最適化機能は完璧ではありません。プログラマが最適化を行ったほうがいい場合もあります。GHCには，プログラマが最適化の方法を処理系に指示するための「書き換え規則（Rewrite Rules）」という機能があります（参考リンク1，参考リンク2）。
今回は，書き換え規則の基本的な使い方と，GHCに付属するライブラリで使われている最適化テクニックの一部を紹介します。
RULES指示文に書き換え規則を記述
書き換え規則は，「RULES指示文」をソースコードに埋め込むことで利用します。例を見てみましょう。
前回，IntとWordとの間の型変換に，fromIntegralという関数を使いました。この関数は，以下のように定義されています（参考リンク）。
-- | general coercion from integral types fromIntegral :: (Integral a, Num b) => a -> b fromIntegral = fromInteger . toInteger
toIntegerはIntegralクラスのインスタンスである型からInteger型に変換する関数です。一方，fromIntegerはInteger型からNumクラスのインスタンスである型に変換する関数です。
Prelude> :t toInteger toInteger :: (Integral a) => a -> Integer Prelude> :t fromInteger fromInteger :: (Num a) => Integer -> a
fromIntegralの定義から，fromIntegralによる型変換は「Integer型に変換した後，目的の型に変換する」という2段階の処理になっていることがわかります。しかし，Integer型を介する変換は非効率です。fromIntegralの効率を向上させるには，Integer型を介する処理とInteger型の中間データを除去する必要があります。しかし，fromIntegral関数は型クラスのメソッドではありません。このため，Integer型を介する処理を使わないような効率的なfromIntegralの定義を，型クラスのインスタンスによって与えることはできません。
そこでGHCにおける実際のfromIntegralの定義は，RULES指示文によって効率的な式に書き換えられています（参考リンク1，参考リンク2）。
{-# RULES
"fromIntegral/Int->Int" fromIntegral = id :: Int -> Int
#-}"formIntegral/Int->Int"は，RULES指示文を使って定義する書き換え規則の名前です。この規則名に続いて記述されている「fromIntegral = id :: Int -> Int」という等式が書き換え規則です。"fromIntegral/Int->Int"という書き換え規則では，左辺の式「fromIntegral」を右辺の式「id :: Int -> Int」に書き換えます。Int型からInt型に変換する場合には，同じ型同士なので，型変換を行う必要はありません。そこで，こうした場合にはfromIntegral関数を何も行わないid関数に書き換える規則を定義しているのです。このように，書き換える対象の式を左辺，書き換えた結果の式を右辺に記述することで，書き換え規則を定義します。
GHCのfromIntegralでは，Int型同士の変換だけでなく，他の型変換も書き換え規則によって効率的な関数として定義されています。
{-# RULES
"fromIntegral/Word8->Int32" fromIntegral = \(W8# x#) -> I32# (word2Int# x#)
"fromIntegral/Word16->Int32" fromIntegral = \(W16# x#) -> I32# (word2Int# x#)
"fromIntegral/Int8->Int32" fromIntegral = \(I8# x#) -> I32# x#
"fromIntegral/Int16->Int32" fromIntegral = \(I16# x#) -> I32# x#
"fromIntegral/Int32->Int32" fromIntegral = id :: Int32 -> Int32
"fromIntegral/a->Int32" fromIntegral = \x -> case fromIntegral x of I# x# -> I32# (narrow32Int# x#)
"fromIntegral/Int32->a" fromIntegral = \(I32# x#) -> fromIntegral (I# x#)
#-}このように，RULES指示文の内部には複数の書き換え規則を列挙できます。複数の規則を列挙する場合には，"fromIntegral/Word8->Int32"などの個々の規則名を，インデントをせずに行頭から書く必要があります。これは現在のGHCが抱える実装上の制限です。規則を行頭から書かないとパース・エラーになります。書き換え規則を使う際には，規則が1個の場合でも常に行頭から記述するクセを付けておきましょう。
fromIntegralの各規則は，Integer型を介さない効率的な実装を，変換する型ごとに提供しています。例えば，"fromIntegral/a->Int32"規則は，「Integralクラスのインスタンスである型からInt32型への変換」になっています。同様に，"fromIntegral/Int32->a"規則は，「Int32型からNumクラスのインスタンスである型への変換」になっています。
型ごとに最適な定義を与えていることから，第34回のコラムで紹介したSPECIALIZE指示文を思い出すかもしれません。しかし，最新のGHC 6.12.1のSPECIALIZEでは，型ごとに特化した関数の定義を自分で用意することはできないようになっています。型に特化した関数は，すべて処理系が生成します。一方，書き換え規則では，型に特化した関数の生成を処理系に任せることはできません。このように，現在のGHCでは，書き換え規則とSPECIALIZEは明確に機能が分けられています（参考リンク）。
では，実際に書き換え規則が使われる様子を見てみましょう。
module Rewrite where import Data.Int val :: Int val = fromIntegral (5::Int) val' :: Int32 val' = fromIntegral (5::Int) val'' :: Int val'' = fromIntegral (5::Int32) val''' :: Int32 val''' = fromIntegral (5::Int32)
RULESに記述された書き換え規則は，「-fenable-rewrite-rules」オプション，または最適化オプションである「-O」を使用することで有効になります（参考リンク1，参考リンク2）。val*に対して書き換え規則が使われたかどうかを確認するには，「-ddump-simpl-stats」オプションを使うとよいでしょう（参考リンク）。このオプションを指定すると，コア言語を最適化するために行われたプログラム変換の統計情報が表示されます。
$ ghc -O -c Rewrite.hs -ddump-simpl-stats
==================== FloatOut stats: ====================
0 Lets floated to top level; 0 Lets floated elsewhere; from 0 Lambda groups
==================== FloatOut stats: ====================
0 Lets floated to top level; 0 Lets floated elsewhere; from 0 Lambda groups
==================== Grand total simplifier statistics ====================
Total ticks: 106
40 PreInlineUnconditionally
12 PostInlineUnconditionally
10 UnfoldingDone
7 RuleFired
3 fromIntegral/Int->Int
1 fromIntegral/Int32->Int32
1 fromIntegral/Int32->a
1 fromIntegral/a->Int32
1 narrow32Int#
31 BetaReduction
6 KnownBranch
9 SimplifierDone
出力結果の中の「Grand total simplifier statistics」にあるRuleFiredの項目を見てください。fromIntegralの型ごとに定義された書き換え規則が，それぞれ1回以上利用されていることがわかります。Int型からInt32型への変換は"fromIntegral/a->Int32"規則，Int32型からInt型への変換は"fromIntegral/Int32->a"規則で行われます。val*では，RULES指示文による書き換え規則で定義した型変換しか行っていないので，すべてのコードがRULESによって効率の良いコードに変換されているのです。
この例では「どの式に対してどの規則が使われたか」をすぐに把握できます。しかし，実際のプログラムでは「どの式に対してどの規則が使われたか」がそれほど明確ではないことがあります。そこで「-ddump-rule-firings」オプションを使うことで，書き換え規則によりプログラムが最適化される様子を出力させることができます。
$ ghc -O2 -c Rewrite.hs -ddump-rule-firings
～ 略 ～
SimplBind [main:Rewrite.val{v r3} [lidx]]
Rule fired
Rule: fromIntegral/Int->Int
Before: base:GHC.Real.fromIntegral{v r2t} [gid] (TYPE ghc-prim:GHC.Types.Int{(w) tc 3J})
(TYPE ghc-prim:GHC.Types.Int{(w) tc 3J})
base:GHC.Real.$fIntegralInt{v rdp} [gid]
$dNum{v avE} [lid]
(ghc-prim:GHC.Types.I#{(w) v 6d} [gid[DataCon]]
5)
After: (\ ($dNum{v aAc} [lid] [ALWAYS Dead Nothing] :: <pred>base:GHC.Num.Num{tc 2b}
ghc-prim:GHC.Types.Int{(w) tc 3J})
($dIntegral{v aAd} [lid] [ALWAYS Dead Nothing] :: <pred>base:GHC.Real.Integral{tc 27}
ghc-prim:GHC.Types.Int{(w) tc 3J}) ->
base:GHC.Base.id{v rx} [gid] @ ghc-prim:GHC.Types.Int{(w) tc 3J})
$dNum{v avE} [lid] base:GHC.Real.$fIntegralInt{v rdp} [gid]
Cont: Stop[BoringCtxt]
～ 略 ～valが"fromIntegral/Int->Int"規則を使って書き換えられたことと，その結果，どのように式が変換されたかが表示されています。この出力を見れば「どの式に対してどの規則が使われたか」が一目でわかります。
ただし，「-ddump-rule-firings」オプションによる出力結果で使われているコードは，第34回のコラムで触れたコア言語（GHCコア）とは異なり，モジュール名が「base:」や「ghc-prim:」のようなパッケージ名で修飾されています。Rewriteモジュールを修飾している「main」は，Mainモジュールなどが属しているmainパッケージを示しています。GHCのオプションなどでモジュールの属するパッケージを明示的に指定しなければ，そのモジュールはmainパッケージに属することになります。上の例では，Rewriteモジュールが属するパッケージを指定していないので，mainパッケージに属するRewriteモジュールが使われています（参考リンク）。
