Arrowの心
昨日の続きです。記法がよいとかMonadみたいに副作用が扱えるとか言ったメリットをはるかに越えたArrowの素晴らしさについて紹介します。
reverse.reverse == id か?
自分が最初にArrowってすごいと気づいた問題がこれです。大学で同級生と話している時に気づきました。大して役に立つ例では無いですが、Arrowの新しい側面が見えてくる例です。
標準入力に対してreverse,reverse,headを順に実行して結果を出力するコードは以下のようになります。後の比較の為に敢えてArrowで書いています。
import Control.Arrow main :: IO () main = getContents >>= print. (reverse >>> reverse >>> head)
リストを２回ひっくり返したら元に戻るだけなので、そのheadをとるという計算は一瞬で終わってもらいたいものです。
しかし、そのようにはならず実際に内部でreverseの計算が行われます。試しに大きいファイル(5Mほどのghc6のソースを使ってみました)で実行速度を計算してみました。
% ghc test.hs -o test % time ./test < ghc6_6.6.1.orig.tar.gz '\US' ./test < ghc6_6.6.1.orig.tar.gz 1.82s user 0.18s system 100% cpu 1.994 total
(注) : これは決してghcの最適化が足りないとかではなく、正当な処理内容です。もしreverse.reverse == idになるとしたら無限リストについてもreverseが定義できてしまうことになるのでおかしくなってしまいますので。
しかしこれから敢えて、reverse.reverse == idになるような計算を実現してみたいと思います。
計算を静的に表現する
Arrowクラスに属するデータは「計算」を表現します。(数学的な話はわかりません。あくまでイメージ)
なのでストリームファンクションの様に、内部に関数を格納するようなArrowを定義して使うことが多いです。
newtype SF a b = SF {runSF ::[a]->[b]} -- リスト操作を行うArrowの定義
実行時にはこのArrowから関数を取り出してつなげていきます。
ここで考え方を変えてみます。「Arrowの中身を取り出して実行」ではなく「Arrowから計算を作り出して実行」と考えてみます。計算を作り出す元になるものは別に関数でなくても良いでしょう。計算を作り出す時に必要な材料が揃っていれば静的なデータであっても構いません
ReverseとIdを静的に定義
以上をふまえてReverseとIdを静的に表現するOpというArrowを定義してみます。
data Op a b where Reverse :: Op [a] [a] Id :: Op a a Pure :: (a -> b) -> Op a b
何て事はありません。ReverseとIdはただのラベルで、中身はなにもありません。
Op a bは入力の型がaで出力の型がbであるArrowを表します。Reverseはリスト[a]を入力としてとり、同じ型のリスト[a]を出力するというように読みます。
Pureはその他の１入力１出力の関数を表します。データとして(a->b)型の関数を格納しています。
これは後でpureという関数を定義する時に使います。pureの別名はarrですが、pureと書く方が静的でなく純粋に関数そのものというイメージが湧いて私は好みです。
これらから実際の計算を作り出すrunOpを定義します。非常に簡単です。
runOp :: Op a b -> (a -> b) runOp Reverse = reverse runOp Id = id runOp (Pure f) = f
ReverseやIdという静的なデータから関数が作り出せるということの意味が分かるかと思います。
簡単な応用なら内部に数値を格納して(+n)する関数を作り出すとかいくらでも考えられます。とにかく計算を作り出す材料としてArrowをとらえればいいのです。
Pureは中に格納してた関数を取り出すだけです。
Arrowの演算子を定義
Arrowの３演算子であるpure(arr), first, >>>を定義します。firstはとりあえず今は使いません。
instance Arrow Op where pure = Pure first = error "使いません" op >>> Id = op Id >>> op = op Reverse >>> Reverse = Id op1 >>> op2 = Pure (runOp op1 >>> runOp op2)
pureはいいとして、重要なのが(>>>)の実装です。(>>>)は二つの計算を合成して一つの計算にするものですが、今は計算が静的に定義されているので、実行前に何をするのかが分かります。Reverse >>> ReverseだったらIdに作り変えちゃいましょう。
一番最後の行の定義は、すべてを受け入れる汎用定義です。
実行してみましょう。
runOpを使えば関数になるんだからこんな感じで書けます。headは普通の関数なのでpureでArrow化しておきます。
main :: IO () main = getContents >>= print.runOp (Reverse >>> Reverse >>> pure head)
最初のコードと見比べてみるとrunOpとpure以外はほとんど同じです。ここでArrowの記法の良さが生きてきます。Reverseは内部的にはタダの数値ですが、あたかも関数であるかのように読めます。
Arrowのハマりどころ
実は上のコードはうまくいきません。やっぱり最初のコードと同じくらいの時間がかかります。
% time ./test2 < ghc6_6.6.1.orig.tar.gz ~ '\US' ./test2 < ghc6_6.6.1.orig.tar.gz 1.68s user 0.25s system 90% cpu 2.132 total
原因は(>>>)演算子の結合性です。(>>>)は右結合性なので上のコードは先に
Reverse >>> pure head
の合成が行われます。この結果はPure (head.reverse)になってしまうので、Reverse >>> Reverseの合成規則が効かなくなっています。
解決策としては括弧を付けるなどがあります。もう一つの解決方法として以下のように書く方法もあります。
main = getContents >>= print.runOp (pure head <<< Reverse <<< Reverse)
なんと(<<<)も右結合性なので、(a <<< bと b >>> aは違う!!) Reverse >>> Reverseが先に計算されます。
% time ./test3 < ghc6_6.6.1.orig.tar.gz ~ '\US' ./test3 < ghc6_6.6.1.orig.tar.gz 0.00s user 0.00s system 90% cpu 0.004 total
期待どおり、めちゃくちゃ早くなりました。Haskellは必要な計算しか行わないので、ファイルから1バイト読んだ時点で終了しているはずです。
Arrow則
上のやり方は一時的な解決策にしかなりません。実はMonadと同様にArrowにもArrow則という規則があります。以下に示しますが、これらの規則を満たすならば上記のような問題は発生しません。
正しい解決方法はこのArrow則を満たす様に定義を修正することです。
1. (a >>> b) >>> c = a >>> (b >>> c) 2. arr (g.f) = arr f >>> arr g 3. arr id >>> a = a = a >>> arr id 4. first a >>> arr pi1 = arr pi1 >>> a 5. first a >>> arr (id X f) = arr (id X f) >>> first a 6. first a >>> arr alpha = arr alpha >>> first (first a) 7. first (arr f) = arr (f X id) 8. first (a >>> b) = first a >>> first b
pi1はタプルの第１要素を取り出すだけのもの、alphaはタプルを組み替える関数、Xは直積(?)のつもりです。
pi1 (x, y) = x alpha (x, (y, z)) = ((x, y), z) f1 X f2 = \(x, y) -> (f1 x, f2 y)
詳しくはhttp://www.cs.ru.nl/~heunen/publications/2006/arrows/arrows.pdfを参照してください。
Monad則はたったの3つだったのにいきなり8つになって非常にややこしいですが、行き当たりばったりに書いていくよりも「これさえ満たせばよいのだ」という明確なルールの元で書いた方がかなりすっきりします。(規模の大きいArrowを作ろうとしたときにこれを見ながら書くと本当に助かります。現在それをものすごく実感しているところです。数学って素晴らしい)
先ほどのOpの定義を見直します。とりあえずfirstについてのルール4,5,6,7,8は無視します。
Arrowの等価性の定義
そもそも、２つのArrowが等しいとはどういうことであるかということを考えないといけません。例えば関数のArrowやKleisli Arrowの場合は、同じ入力に対して同じ出力が必ず出てくるならば等価であるということになっています。
(注) : つまりArrowのデータ構造がまったく同じにならなくてはいけないということではありません。
今考えているOpではReverse >>> Reverse = Idの簡約が完全に行われている事を条件として加えましょう。つまり
A == B <-> A, B内にReverse >>> Reverseの並びがあったらIdに置き換えられている。かつ、runOp AとrunOp Bが等価
とすれば良さそうですが、もうちょっと条件をきつくします。それは
Reverse >>> Id >>> Reverse
のようにReverseとReverseの間にIdが挟まっているようなパターンも簡約しなければいけないことにします。
このArrowの等価性をどう定義するかはArrowを自分で作るときに最も大事な点です。
結合則
1のルール(結合則)が最も重要ですので、これから考えていきます。というかこれについてしかここでは書きません。
実は簡単そうに見えてものすごく難しい問題です。いろいろ調べてみたのですが明確な解が見つからなかったので自分が考えた方法を書きます。
まず、(>>>)の定義からrunOpを使う最後の定義をなくします。(... (Reverse >>> Pure f))の簡約をrunOpでやってしまったら、Reverseが簡約できる可能性を無視してしまう事になるからです。この様な場合は簡約を保留する必要があります。
式を木構造として解釈する
括弧でくくられた数式は木構造として表現できます。例えば以下の4つの式を考えます。
p1 >>> p2 >>> (p3 >>> p4) >>> p5 p1 >>> (p2 >>> p3 >>> p4) >>> p5 p5 <<< p4 <<< p3 <<< p2 <<< p1 p1 >>> p2 >>> p3 >>> p4 >>> p5
これを2分木で表すことにすると(右結合とします)
(p1, (p2, ((p3, p4), p5))) (p1, ((p2, (p3, p4)), p5)) ((((p1, p2), p3), p4), p5) (p1, (p2, (p3, (p4, p5))))
という感じになります。簡約できない部分はこの木構造のまま保持することにします。
そこで、新しくNodeというデータを定義します。
data Op a b where Reverse :: Op [a] [a] Id :: Op a a Pure :: (a -> b) -> Op a b Node :: (Op a b) -> (Op b c) -> (Op a c)
Node型は2つの他のOp型を内部に持っています。左の木の出力が右の木の入力になるわけなので、2つのOp型の入出力が同じ型変数(b)で表されています。
Arrowの演算子の定義はこんな感じになるでしょう。その場で簡約できるものはすぐにしてしまい、できないものはとりあえずNodeの中にいれておきます。
Id >>> p = p p >>> Id = p Reverse >>> Reverse = Id Pure f1 >>> Pure f2 = Pure (f2.f1) op1 >>> op2 = Node op1 op2
runOpは次のような感じになります
runOp (Node p1 p2) = runOp p2.runOp p1
木構造を表示できるようにshow関数を定義してみましょう。
instance Show (Op a b) where show Reverse = "Reverse" show Id = "Id" show (Pure _) = "Pure" show (Node p1 p2) = "("++show p1++", "++show p2++")"
こんな感じで表示されます。
> (arr sort >>> Reverse >>> ((Reverse >>> arr id) >>> ((Reverse >>> arr nub >>> arr reverse) >>> arr tail >>> Reverse) >>> Reverse)) (Pure, (Reverse, ((Reverse, Pure), (((Reverse, Pure), (Pure, Reverse)), Reverse))))
Reverseの簡約
保留にしたReverseの簡約をするアルゴリズムを考えます。
まず、ついている括弧はすべて無意味なものなので、全部はずし右結合にしてしまいます。
-- (p1 >>> p2) >>> p3を p1 >>> (p2 >>> p3)にする Node p1 p2 >>> p3 = p1>>>(p2>>>p3)
実行例
> (arr sort >>> Reverse >>> ((Reverse >>> arr id) >>> ((Reverse >>> arr nub >>> arr reverse) >>> arr tail >>> Reverse) >>> Reverse)) (Pure, (Reverse, (Reverse, (Pure, (Reverse, Pure)))))
これで(p1 >>> (p2 >>> p3))のパターンについての簡約だけ考えればよくなります。右から順番に合成されていきますのでp3の部分は十分に簡約されていると仮定してしまってよくなります。
ここまでくれば非常にシンプルです。Reverseの連続とPureの連続を簡約しましょう。Idの簡約はすでにある規則によって行われます。
Reverse >>> Node Reverse p = p p1@(Pure _) >>> Node p2@(Pure _) p3 = Node (p1>>>p2) p3
以上をまとめると以下のようになります。
Id >>> p = p p >>> Id = p Reverse >>> Reverse = Id Pure f1 >>> Pure f2 = Pure (f2.f1) Reverse >>> Node Reverse p = p p1@(Pure _) >>> Node p2@(Pure _) p3 = Node (p1>>>p2) p3 Node p1 p2 >>> p3 = p1>>>(p2>>>p3) op1 >>> op2 = Node op1 op2
実行例
> (arr sort >>> Reverse >>> ((Reverse >>> arr id) >>> ((Reverse >>> arr nub >>> arr reverse) >>> arr tail >>> Reverse) >>> Reverse)) (Pure, (Reverse, Pure))
期待どおりの結果になりました。
では最初にダメだったコードを試してみます。
main :: IO () main = getContents >>= print.runOp (Reverse >>> Reverse >>> pure head)
% time ./test4 < ghc6_6.6.1.orig.tar.gz ~ '\US' ./test4 < ghc6_6.6.1.orig.tar.gz 0.00s user 0.00s system 6% cpu 0.063 total
うまくいきました。もっと複雑な計算を記述していっても必ずReverse >>> ReverseはIdとして計算されます。
まとめ
ここまで書いてきた例は実用性の無い入門的なものです。
しかし、Arrowを利用して計算前に計算そのものについての計算を行えるということがよく分かっていただけたのではないかと思います。これはMonadでは基本的に実現できないことです。
計算を実行する前に計算をするというオーバーヘッドがかかりますが
(計算を合成するのに要する時間) + (計算を実行するのに要する時間) < (最適化をかけない状態での計算に要する時間)
であればトータルの時間は短くなります。性能のよいコンパイラであればReverse >>> Reverse = Idなどの定数計算はコンパイル時にやってくれるかもしれません。(これはちゃんと調べてません。)
また、Arrow則についてですが、Monad則に比較して重要性が非常に高いと思います。(重要性というか、Monadの場合は基本的に合成されるのはa -> m b型の関数なので、あまり意識しなくても自然にMonad則が成立していました。)
さまざまな実験をしてみた結果、やはり一度右結合に直してしまうのが最もシンプルに書け、効率もよいのではないかと思っています。(多くの場合 p1 >>> p2 >>> p3 のように書くので最初から右結合になっています)
このあたりの方法論については、まだまだ整理されていないところだと思います。もっといいやり方があるんじゃないかと思っています。
ArrowはHaskellにニュージャンルの人を呼び寄せるキラーモジュールになるのではないかと感じています。C++のテンプレート好きな人とかはものすごくはまってしまうんではないでしょうか。また、計算そのものをパズルのように考えていけるので純粋におもしろいということもあります。
こういった手法が有効である領域は結構多いのではないかと考えています。例えばArrowの論文では頻繁にパーサコンビネータが紹介されます。http://www.cs.chalmers.se/~rjmh/Papers/arrows.pdf
現在ちょうどHaskellでコンパイラを書いていることもあって、私もこの手法を応用してパーサコンビネータライブラリを製作しています。私は論文にあるものと違って、非決定的な(バックトラックありの)パーサに取り組んでいます。決定的パーサだと文法について十分に考えないと正しく動きませんが、非決定的なパーサなら文法について特によく考えず書いても必ずパースできます。
そしてArrowを生かす為の基本的なアイデアは、特定のパーサ同士が組み合わされたときはもっと効率的なパーサに置き換えてしまおうというものです。
コードは近日中に公開する予定です。アイデアについて詳しくはそのときに書きたいと思います。
(現在8割程度終了し、実験段階です。まだArrow則の問題をクリアしていません。また計算を合成する為のオーバーヘッドの方が結構大きいのでこれは失敗作になる可能性が大きいです(汗))
[訂正]
上の定義では簡約できないと分かっているところまで木のまま残すという無駄をしていました。正式な全コードは以下のようになります。
import Control.Arrow data Op a b where Reverse :: Op [a] [a] Id :: Op a a Pure :: (a -> b) -> Op a b Node :: (Op a b) -> (Op b c) -> (Op a c) runOp :: Op a b -> (a -> b) runOP Id = id runOp Reverse = reverse runOp (Pure f) = f runOp (Node p1 p2) = runOp p2.runOp p1 instance Arrow Op where pure = Pure first = error "not implemented" Id >>> p = p p >>> Id = p Reverse >>> Reverse = Id Pure f1 >>> Pure f2 = Pure (f2.f1) Node p1 p2 >>> p3 = p1>>>(p2>>>p3) Reverse >>> Node Reverse p = p p1@(Pure _) >>> Node p2@(Pure _) p3 = Node (p1>>>p2) p3 p1 >>> Node p2 p3 = Node p1 (Pure $ runOp p3.runOp p2) <- これを追加 op1 >>> op2 = Node op1 op2 instance Show (Op a b) where show Reverse = "Reverse" show Id = "Id" show (Pure _) = "Pure" show (Node p1 p2) = "("++show p1++", "++show p2++")" main :: IO () main = getContents >>= print.runOp (Reverse >>> Reverse >>> pure head)
[追記]
Arrowではないですが同じ事をするのに、こんなやりかたもあるようです。
{-# RULES "reverse/reverse" forall x. reverse (reverse x) = id x #-} main :: IO () main = do cs <- getContents print $ head $ reverse $ reverse cs
これもおもしろい機能ですね。
[追記2]
RULESでghcのソースコードを探索してみたらこんなん見つかりました。Control/Arrow.hsより。
{-# RULES "compose/arr" forall f g . arr f >>> arr g = arr (f >>> g) "first/arr" forall f . first (arr f) = arr (first f) "second/arr" forall f . second (arr f) = arr (second f) "product/arr" forall f g . arr f *** arr g = arr (f *** g) "fanout/arr" forall f g . arr f &&& arr g = arr (f &&& g) "compose/first" forall f g . first f >>> first g = first (f >>> g) "compose/second" forall f g . second f >>> second g = second (f >>> g) #-}
Arrow則にあるものがたくさん含まれてます。これはimportした側でも適用されるのでしょうか？未確認です。
このコンパイラによる書き換え規則を積極的に使っていくのもありかもしれません。Arrow本体のコードで使っているくらいなので問題ないでしょう。というか、その為のArrow則ですね。(ちなみに、Control以下にはMonadとかのコードもありますが、ArrowでしかRULESは使われていませんでした)
ちょっと危険な香りのするハックですが...いろんな意味で。
