PR

fold/buildを使った融合変換

 書き換え規則が真に威力を発揮するのは,リストなどのデータ構造に対する処理を効率的なものに書き換える場合です。

 Haskellでは,データ構造に対する定型の処理を抽象化した関数が各データ構造に対して提供されています。具体的には,FunctorクラスのmapメソッドやFoldableクラスのfoldrメソッドなどです。これらの関数を使った処理をブロックのように組み合わせることで,多くの処理を実現できます。特にリストには豊富な関数が提供されているため,このような手法が多用されます。

 しかし,処理効率という面では,抽象度の高さが災いすることもあります。処理同士の組み合わせを素朴に記述すると,効率が悪い処理になってしまう可能性があるのです。

 Haskellでは,こうした非効率性を遅延評価によって部分的に解決しています。最終的な結果を求めるのに必要ない計算は,遅延評価によって実行が省略されるため,無駄な計算を削減できます。ただし,遅延評価で解決するのは,あくまで問題の一部です。必要な計算にかかわる非効率性は,遅延評価では解決できません。

 必要な計算同士の間にある非効率性は,「計算と計算をつなぐために一時的に使用される中間データ」という形で現れます。例えば「map f . map g」のようにmap関数を使用する処理同士を組み合わせた場合,二つのmapの間にはリストという「中間データ構造(Intermediate Data Structures)」が作成されます。同様に「filter p . filter q」のような場合でも,二つのfilterの間に中間データ構造のリストが作成されます。

 こうした非効率性を解消するには,中間データ構造を必要としないようにプログラムを書き換える必要があります。例えば,「map f . map g」で生じる中間データ構造を除去するには「map (f . g)」と書き換えます。同様に,「filter p . filter q」を「filter (\x -> q x && p x)」と書き換えれば,中間データ構造を除去できます。

 このような「複数回の関数適用によって行われる処理を一度の関数適用に変更する書き換え」を「融合変換(fusion transformation)」と呼びます。「関数融合(function fusion)」や単にfusionと呼ぶこともあります(参考リンク1参考リンク2参考リンク3)。処理と処理の間に挟まる中間データ構造を木に例えて「森林伐採法(deforestation)」とも呼びます(参考リンク)。

 理想を言えば,処理系がすべての融合変換を自動的に行うべきでしょう。しかし,残念ながら融合変換の理論はまだ発展途上であり,処理系が完璧な融合変換を提供するには至っていません(参考リンク)。そこで,Haskellによるプログラミングでは,融合変換を行うための書き換え規則をプログラマが定義するケースがよくあります。

 では,書き換え規則を使って融合変換を行ってみましょう。

module Rewrite where

fg = map (+1) . map (+2)
pq = filter (> 5) . filter (< 10)

{-# RULES
"map/map"        forall f g xs.  map f (map g xs) = map (f . g) xs
"filter/filter"  forall p q xs.  filter p (filter q xs) = filter (\x -> q x && p x) xs
  #-}

 "map/map"規則により「map f . map g」は「map (f .g)」に変換されます。同様に,"filter/filter"規則により「filter p . filter q」は「filter (\x -> q x && p x)」に変換されます。

$ ghc -O2 -c Rewrite.hs -ddump-simpl-stats
~ 略 ~
6 RuleFired
    1 filter
    1 filter/filter
    1 filterList
    1 map
    1 map/map
    1 mapList
~ 略 ~

 このように融合変換を行うための書き換え規則を定義することで,処理系に融合変換を行わせることができます。

 しかし,この方法には重大な欠陥があります。「map f . map g」や「filter p . filter q」といった処理ごとにアドホックに融合変換を定義していくと,利用可能なすべての処理の組み合わせに対して融合変換を定義しなければなりません。この結果,融合変換すべき処理の「組み合わせ爆発(combinatorial explosion)」が生じてしまいます。

 この問題を解決するには,アドホックな定義を避け,様々な処理を抽象化した基本構造に対してのみ融合変換を定義する必要があります。これを解決するのが「fold/build」という名前の手法です(参考リンク)。

 リストを扱う関数には,iterateやrepeatのようにリストを作り出す「生産者(producer)」の役割を持つ関数と,foldrのようにリストを使用して処理を行う「消費者(consumer)」の役割を持つ関数があります。生産者の役割を持つ関数を融合変換可能にするには,GHC.Extsモジュールのbuild関数を使って定義します。こうして定義した融合変換可能な生産者を「優良生産者(good producer)」と呼びます。同様に,消費者の役割を持つ関数を融合変換可能にするには,foldr関数を使って定義します。融合変換可能な消費者を「優良消費者(good consumer)」と呼びます。

build   :: forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
{-# INLINE [1] build #-}
        -- The INLINE is important, even though build is tiny,
        -- because it prevents [] getting inlined in the version that
        -- appears in the interface file.  If [] *is* inlined, it
        -- won't match with [] appearing in rules in an importing module.
        --
        -- The "1" says to inline in phase 1
build g = g (:) []

 buildのINLINE指示文の中にある「[1]」は,インライン化や書き換え規則などの適用のタイミングを制御する「段階制御(Phase Control,段階管理)」という機能です。段階制御は,実際にプログラムを効率化する際には重要ですが,「build/foldr」という手法そのものには直接関係ないので,今回は無視してかまいません(参考リンク)。

 buildの引数であるgは,型構成子「:」とリストの末尾にくる型構成子「[ ]」を引数にしてリストを作成する関数です。したがって,リストを作成する関数を,build関数を使うように書き換えるには,リストを作成する関数を,buildに渡すことが可能な「型構成子の : と[ ]を引数にしてリストを作成する関数」に変更し,その関数をbuildに渡す形にします。

 個々の関数を見ていきましょう。GHCのiterateやrepeatは,コンパイル時に書き換え規則によってbuildに使う形に書き換えられます(参考リンク)。

iterate :: (a -> a) -> a -> [a]
iterate f x =  x : iterate f (f x)
iterateFB :: (a -> b -> b) -> (a -> a) -> a -> b
iterateFB c f x = x `c` iterateFB c f (f x)

{-# RULES
"iterate"    [~1] forall f x.   iterate f x = build (\c _n -> iterateFB c f x)
"iterateFB"  [1]                iterateFB (:) = iterate
 #-}

-- | 'repeat' @x@ is an infinite list, with @x@ the value of every element.
repeat :: a -> [a]
{-# INLINE [0] repeat #-}
-- The pragma just gives the rules more chance to fire
repeat x = xs where xs = x : xs
{-# INLINE [0] repeatFB #-}     -- ditto
repeatFB :: (a -> b -> b) -> a -> b
repeatFB c x = xs where xs = x `c` xs

{-# RULES
"repeat"    [~1] forall x. repeat x = build (\c _n -> repeatFB c x)
"repeatFB"  [1]  repeatFB (:)       = repeat
 #-}

 さて,第34回で,Data.FoldableモジュールのtoList関数が,実際には最適化のために少し複雑な定義になっていたのを覚えているでしょうか。実は,融合変換が可能になるようにbuild関数を使って定義されていたのです。

-- | List of elements of a structure.
toList :: Foldable t => t a -> [a]
#ifdef __GLASGOW_HASKELL__
toList t = build (\ c n -> foldr c n t)
#else
toList = foldr (:) []
#endif

 GHCでは,concatMapはもともとfoldrを使って定義されているので,融合変換が可能な優良消費者としてそのまま利用できます(参考リンク)。

concatMap               :: (a -> [b]) -> [a] -> [b]
concatMap f             =  foldr ((++) . f) []

 mapやfilterのような「リストを取ってリストを返す関数」は,生産者と消費者の両方の側面を持っています。したがって,リストを取ってリストを返す関数は,buildとfoldrを組み合わせて定義する必要があります。mapやfilterのコンパイル時には,buildとfoldrを使うように書き換え規則によって定義が変更されます(参考リンク1参考リンク2)。

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs
-- Note eta expanded
mapFB ::  (elt -> lst -> lst) -> (a -> elt) -> a -> lst -> lst
{-# INLINE [0] mapFB #-}
mapFB c f x ys = c (f x) ys
-- The rules for map work like this.
-- 
-- Up to (but not including) phase 1, we use the "map" rule to
-- rewrite all saturated applications of map with its build/fold 
-- form, hoping for fusion to happen.
-- In phase 1 and 0, we switch off that rule, inline build, and
-- switch on the "mapList" rule, which rewrites the foldr/mapFB
-- thing back into plain map.  
--
-- It's important that these two rules aren't both active at once 
-- (along with build's unfolding) else we'd get an infinite loop 
-- in the rules.  Hence the activation control below.
--
-- The "mapFB" rule optimises compositions of map.
--
-- This same pattern is followed by many other functions: 
-- e.g. append, filter, iterate, repeat, etc.
{-# RULES
"map"       [~1] forall f xs.   map f xs                = build (\c n -> foldr (mapFB c f) n xs)
"mapList"   [1]  forall f.      foldr (mapFB (:) f) []  = map f
"mapFB"     forall c f g.       mapFB (mapFB c f) g     = mapFB c (f.g) 
  #-}

filter :: (a -> Bool) -> [a] -> [a]
filter _pred []    = []
filter pred (x:xs)
  | pred x         = x : filter pred xs
  | otherwise      = filter pred xs
{-# NOINLINE [0] filterFB #-}
filterFB :: (a -> b -> b) -> (a -> Bool) -> a -> b -> b
filterFB c p x r | p x       = x `c` r
                 | otherwise = r
{-# RULES
"filter"     [~1] forall p xs.  filter p xs = build (\c n -> foldr (filterFB c p) n xs)
"filterList" [1]  forall p.     foldr (filterFB (:) p) [] = filter p
"filterFB"        forall c p q. filterFB (filterFB c p) q = filterFB c (\x -> q x && p x)
 #-}

 では,中間データ構造を除去する規則を実際に見てみましょう。

 「map f . map g」に対して"map"規則を適用した場合や「filter p . filter q」に対して"filter"規則を適用した場合を思い出してください。中間データ構造は「buildを使ってリストを作成し,foldrを使ってリストを使用する間の個所」で生まれます。したがって,中間データ構造を除去するには,この個所を書き換える規則を用意すればよいことになります。

{-# RULES
"fold/build"    forall k z (g::forall b. (a->b->b) -> b -> b) . 
                foldr k z (build g) = g k z
~ 略 ~
 #-}

 fold/buildという手法名は,この"fold/build"規則に由来します。

 buildはランク2多相性を持つ型なので,書き換え規則を適用するにはパターン変数gに対する型宣言が必要であることに注意してください。書き換え規則では,パターン変数を多相型として扱うには必ず型注釈を付ける必要があるためです。型注釈を付けないと,パターン変数gの多相性が保証されないため,型エラーになります。

module Rewrite where
import GHC.Exts

{-# RULES
"fold/build"    forall k z g . 
                foldr k z (build g) = g k z
 #-}

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

Rewrite.hs:6:27:
    Inferred type is less polymorphic than expected
      Quantified type variable `b' is mentioned in the environment:
        g :: (a -> b -> b) -> b -> b (bound at Rewrite.hs:5:27)
    In the first argument of `build', namely `g'
    In the third argument of `foldr', namely `(build g)'
    In the expression: foldr k z (build g)

 この制限は,変数が必ず何らかの型に確定する通常の型であれば気にする必要はありませんが,ランク2以上の多相性を持つ型を扱う場合には重要です。

 話を戻しましょう。"fold/build"規則では,「buildを使ってリストを作成し,foldrを使ってリストを使用する処理」を「buildとfoldrを使わない処理」に変換します。"fold/build"規則により,「型構成子である : と[ ]を引数にしてリストを作成する関数」であるgに対し,: の代わりに「リストの各要素に対して適用するための関数であるk」,[ ]の代わりに「foldr関数の初期値であるz」が渡されることになります。この結果,gとkは中間データ構造を介さずに処理を行うことが可能になるのです。

 "fold/build"規則は,「buildを使ってリストを作成する優良生産者」と「foldrを使ってリストを使用する優良消費者」を組み合わせて定義された任意の式に適用できます。つまり,リストに対する様々な処理をbuildとfoldrで再定義し,"fold/build"規則で融合変換することで,"map/map"規則や"filter/filter"規則のようにアドホックな融合変換ではなく,様々なリスト処理で利用できる汎用的な融合変換を実現できるのです(参考リンク)。