PR

書き換え規則のタイミングを制御

 "fold/build"規則を使った融合変換には,インライン化のタイミング以外にもう一つ問題があります。「buildやfoldrを使って定義したリストを扱う関数は,foldrやbuildを使わずに再帰で直接定義した関数に比べ効率が劣る場合がある」という問題です。こうした関数では,リストを扱う演算の組み合わせが優良生産者と優良消費者の組み合わせになっている場合には,"fold/build"規則で融合変換が行われるため,効率化が期待できます。しかし,優良生産者と優良消費者の組み合わせになっていないときには,"build/foldr"規則が適用されないため,foldrやbuildで定義したことによる性能の低下が問題になります。

 例を見てみましょう。

module Rewrite where
import Data.List

test = nub . map (+1) . map (+2)

 nubはリストから重複する要素を取り除く関数です。Data.Listモジュールで定義されています(参考リンク)。

Prelude Data.List> :i nub
nub :: (Eq a) => [a] -> [a]     -- Defined in Data.List
Prelude Data.List> nub [1..5]
[1,2,3,4,5]
Prelude Data.List> nub [1,1,1]
[1]
Prelude Data.List> nub [1,7,5,3,3,6,5]
[1,7,5,3,6]

 前回説明したようにmapは優良生産者であり優良消費者でもあるので,"fold/build"規則を使って「map (+1)」と「map (+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) 
  #-}

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

{-# INLINE (.) #-}
-- Make sure it has TWO args only on the left, so that it inlines
-- when applied to two functions, even if there is no final argument
(.)    :: (b -> c) -> (a -> b) -> a -> c
(.) f g = \x -> f (g x)

    map (+1) . map (+2)
==> { 「.」のインライン化 }
    \xs -> map (+1) (map (+2) xs)
==> { "map"規則の適用 }
    \xs -> map (+1)
             (build (\c n -> foldr (mapFB c (+2)) n xs)
==> { "map"規則の適用 }
    \xs -> build (\c' n' ->
             foldr (mapFB c' (+1)) n'
                   (build (\c n -> foldr (mapFB c (+2)) n xs)
==> { "fold/build"規則の適用 }
    \xs -> build (\c' n' ->
             (\c n -> foldr (mapFB c (+2)) n)
                            (mapFB c' (+1)) n' xs)
==> { β-簡約 }
    \xs -> build (\c' n' ->
             (foldr (mapFB (mapFB c' (+1)) (+2)) n') xs)
==> { "mapFB"規則の適用 }
    \xs -> build (\c' n' ->
             (foldr (mapFB  c' ((+1) . (+2))) n') xs)

 このように「map (+1) . map (+2)」を「\xs -> build (\c' n' -> (foldr (mapFB c' ((+1) . (+2))) n') xs)」に融合変換できます。しかし,nubは優良消費者ではありません。このため「nub」と「\xs -> build (\c' n' -> (foldr (mapFB c' ((+1) . (+2))) n') xs)」を"fold/build"規則等を使って融合変換することはできません。この結果,「\xs -> build (\c' n' -> (foldr (mapFB c' ((+1) . (+2))) n') xs)」のbuildとfoldrは,そのままインライン化されることになります。

    \xs -> build (\c' n' ->
             (foldr (mapFB  c' ((+1) . (+2))) n') xs)
==> { build関数のインライン化 }
    \xs -> foldr (mapFB  (:) ((+1) . (+2))) []) xs
==> { foldr関数のインライン化 }
    \xs -> go xs
         where
            go []     = []
            go (y:ys) = y `(mapFB  (:) ((+1) . (+2)))` go ys
==> { mapFB関数のインライン化 }
    \xs -> go xs
         where
            go []     = []
            go (y:ys) = ((+1) . (+2)) y : go ys

 段階制御により,フェーズ1でbuildがインライン化され,フェーズ0でfoldrとmapFBがインライン化されます。この結果,「xs -> go xs」という式が作成されます。

 「xs -> go xs」という式は,mapを使って定義された元の式「map ((+1) . (+2))」よりも効率が悪くなります。なぜなら,「\xs -> go xs」という式はコードの肥大化を起こす可能性があるからです。

 コードの肥大化は,「\xs -> go xs」を含む式のインライン化によって引き起こされます。goは再帰的な関数であるためインライン化されませんが,「\xs -> go xs」という式には再帰は存在しないので,このコードを含む式はインライン化されます。このインライン化が行われる際,「\xs -> go xs」が使用しているgo関数もローカル関数として定義がコピーされます。この結果,融合変換可能ではないmap関数と同じ数だけgoの定義のコピーが作られ,コードのサイズが膨れ上がる可能性があります。この問題を回避するには「\xs -> build (\c' n' -> (foldr (mapFB c' ((+1) . (+2))) n') xs)」という式を,mapを使って定義した元の式に戻し,goの定義のコピーを防がなくてはなりません。