CPS変換もいいけど融合変換もね - ぼくのぬまち出張版

要約すると，元々

fb :: Int -> Either Int String
fb n = case n `gcd` 15 of
         15 -> Right "FizzBuzz"
         5  -> Right "Buzz"
         3  -> Right "Fizz"
         _  -> Left n

fizzbuzz1 :: Int -> String
fizzbuzz1 n = either show id (fb n)

みたいなコードだったのを，

fbCPS :: (Int -> t) -> (String -> t) -> Int -> t
fbCPS left right n = case n `gcd` 15 of
                       15 -> right "FizzBuzz"
                       5  -> right "Buzz"
                       3  -> right "Fizz"
                       _  -> left n

fizzbuzz2 :: Int -> String
fizzbuzz2 n = fbCPS show id n

みたいにCPS変換しておいて使えば，

条件分岐の結果を一旦代数的データに押し込み、それに対してさらに条件分岐を行おうとしているのだ……

と問題視していたデータの構成及びパターンマッチが

計算の結果を代数的データ型を介さずに受け渡しできる

ことになって無くなってくれるのでイイねぇという話．

たしかに高速化にCPS変換が効果的なのは正しい．けど，fizzbuzz1とfizzbuzz2を見比べたときにちょっとアレ？って思うところ無いだろうか．というのは，CPS変換前ではfbという部品を作りeitherという別の部品と組み合わせて全体の処理fizzbuzz1を構成していたのが，CPS変換後のものを使ったfizzbuzz2では妙に強く結合してしまったナァという印象を受ける．まぁ，元のfbと同じものはfbCPS Left Rightだからそれでいいっちゃいい．でも，Haskellは関数適用と型システムによる強くて硬いcomposabilityに裏打ちされたmodularityがウリのひとつではなかったか．それともイザ速いプログラムを書くにあたっては仕方のないことなのだろうか？

いや我々にごはんを食べさせてくれているHaskellさんはさすがにそんなことはないはずなのだ．要は代数的データ型に対し，それを消費するeitherやfoldrみたいなものと，代数的データ型の生成が自動的に打ち消されてくれればいい．ぱよえーん

たとえば次のような関数buildEを考えよう．要RankNTypes

buildE :: (forall x . (a -> x) -> (b -> x) -> x) -> Either a b
buildE g = g Left Right

buildEは，Leftに対応する変換であるa to xの関数と，Rightに対応する変換であるb to xの関数を受けてxになる関数gを受け，Either a bとなる関数である．まぁ，型をそのまま読むとそう書いてある．このbuildEを使うと，とりあえず適切なgさえ与えてあげれば，fbのような関数はなんとなく書けそうな気分になる．

さて，Either a bを生成するこの関数buildEと，Either a bを消費する関数eitherを組み合わせると，

either l r (buildE g) = g l r

という等価な式がなりたってeitherとbuildEが消える．という最適化ができる．この等式の右辺を構成する要素g,l,rの型にはEither a bは一切出現しないので右辺の処理ではEither a bの値は作られない．この最適化規則はghcではRULESプラグマとして次のようにコンパイラに教えてあげることができる．

{-# RULES "either/buildE" forall l r (g :: forall x . (a -> x) -> (b -> x) -> x) . either l r (buildE g) = g l r #-}

こうしておくと，buildEで書かれたEither a bを生じる関数は，eitherされると最適化によりEither a bの生成・パターンマッチなどが勝手に消えたコードになってくれるはずだ．

あとは実際にbuildEでfbを書き直す．

fbBuildE :: Int -> Either Int String
fbBuildE n = buildE g where
    g l r = case n `gcd` 15 of
              15 -> r "FizzBuzz"
              5  -> r "Buzz"
              3  -> r "Fizz"
              _  -> l n

この関数fbBuildEはfbと同じ型と同じ結果を持ち，CPS変換済みのコードをbuildEを介して内部に隠し持ったような形になっている．これをfizzbuzz1と同様にeitherと組み合わせ，

fizzbuzz3 :: Int -> String
fizzbuzz3 n = either show id (fbBuildE n)

とすると，fizzbuzz1と部品化の度合いは同じままで済んでおりコードの見た目は変わらない．それでいて，先程の変換規則に合致するので中間的なEither Int Stringは作らないよう最適化される．

Eitherみたいに構造が小さい代数的データ型に対してはあまり強い効果は持たないが，リストのように再帰的に大きくなる代数的データ型に対してはとても強い効果を発揮する．実際，同じようなことをするリスト用の変換規則"fold/build"などはGHC.Baseに入っている．

と，ここまで書いたけど，実際にはこれで完全に最適化がキモチよく決まるかというとghcの他の最適化機構やらイロイロなアレやコレやによって，案外そういうわけでもなかったりすることもある．加えて，正しさがよくわかってない規則であるならRULESプラグマをウカツに書くのはとてもよろしくない結果をもたらす．本当に間違った規則を書くこともできるし，変換が停止しない規則を書くこともできる．変換に関わる関数の正格性などによって正しい/正しくないが変わってしまうということもある．いまのところ，確実に何かしたい場合はCPS変換を手で書くのもアリなのだろう．CPS変換する目的自体もいろいろあるだろうし．

ただ，果たして本当にCPS変換はニンゲンがやるようなサギョウなのかというのはコードいっぱい書く前に一考する必要がある．効率化全般に言えることだけど全体からみて本当にソレがボトルネックなのかとかは最初は案外わかんない．CPS変換も人手で正しく変換してあげる必要はあるわけだし，CPS変換によって本当に変換前と意味が変わってないかはそんなにスンナリとわからないんじゃないかな．

折角Haskell使ってるんだからコンパイラとか頭いい研究者達に任せられる分はガンガン任せて，私としてはあんまり難しいこと考えずに楽したい．というかメンドクサイのであんまりやりたくない．