バックナンバー

Arrow化pipeはFRPの夢を見るか？

本記事も引き続き、Arrow記法対応のpipe系(ないしはIteratee系)自作ライブラリmachinecellの紹介です。

machinecell: Arrow based stream transducers

今回はインパクト重視のデモとして、小さなGUIプログラムを披露します。

その前にイントロとして、なぜIteratee系のライブラリをArrow化したか、というモチベーションの部分について、前回の記事より少し突っ込んで触れてみようと思います。

イントロ：Arrow化のモチベーション

Iteratee系ライブラリとは、データを読み、書き、副作用を実行する小さな部品を「あたかもUnixのパイプのごとく」連ねて、一連の処理を行う事ができる「機能」を提供するものでした。

ArrowとはCategoryの拡張で、「あたかもパイプのごとく」処理を連ねる「文法」を提供できるものです。

片やパイプっぽい機能、又一方はパイプっぽい文法。この二つを合わせて使う事ができれば、最強のパイプが誕生するのでは？
……と安直に考えてしまう人間は、別に私だけではないようです。

Haskell for all: pipes-3.2: ListT, Codensity, ArrowChoice, and performance

Ever since I first released pipes, I've received numerous questions about whether or not pipes can be made an instance of Arrow. While you can't make Arrow work, you CAN make proxies implement ArrowChoice, although I don't provide an actual instance because there are two such instances (one for downstream and one for upstream) and the requisite newtypes would be very cumbersome.

という風に、「Arrowに出来ないの？」という質問自体はたくさんあったようなのですが、Gonzalez氏は「pipesはアローにはならない」と言っているようです。（ArrowChoiceなら出来るよ、と言うのが引用記事の趣旨ですが、ArrowとArrowChoiceはHaskellでの定義において特に包含関係がないので、ArrowChoiceだけあってもArrow記法は使えないのです）

このコメントが出たのが2013年3月。
そして同氏の同年10月、11月の投稿がこちら。

どうもArrow化を諦めている訳ではなく、随時研究中の模様。一番目の記事からリンクされているgithubに、試験的実装も既に存在しています。(machinecellを作り始めたのが2013年の5月なので、当時はまだ無かったんですってば！)
そしてGonzalez氏以外にもアロー化の模索はされているっぽい。

Part 4: Category and Arrow

なので、もしかしたら他のライブラリで、この記事のようなコードが書ける日が来るかもしれません。

ともあれ、Arrow化のモチベーション自体はそれほど特別な物ではないという事がお分かり頂けたでしょうか。問題は結果。今ここに、machinecellという一つの実装がある訳ですが、果たして思惑通り、それは「最強のパイプ」たりえているのでしょうか。
では、その威力が感じられるexampleを見ていきましょう。

Iteratee系でGUIプログラミング？

世に溢れるGUIプログラミングは、大抵はイベントへの応答をプログラミングする事に帰着します。

そうだ、これこそイベントストリームだ。Iterateeを使って書いてやろう！

と考える酔狂は、多分世の中にあんまりいません（全くいないとは言い切れない）。

Iteratee系のライブラリは基本的に文字通りのパイプライン処理、処理を直列つなぎにする事に特化しているので、「たまに来るイベントに反応する」みたいなコードは書き辛いし、書いてもあまりメリットがないのです。
一方で、処理を縦横繋ぎ放題のArrow記法なら、ひょっとしてその辺りが上手く扱えるかもしれません。

machinecellによる実装

machinecellのGUIライブラリへのバインディングは、実は現時点でソースツリー中にこっそり含まれています。
それを使って書いたのが、以下のexampleになります。

example/wx/hello.hs

実行すると、こんなウィンドウが表示されます。

ではコードを見ていきます。

コード中、Wxでqualifiedされているのは、WxHaskellライブラリのモジュールメンバです。Pがmachinecell本体、そしてWxPが、expample/wx/lib以下で定義されるWxHandlerモジュールのメンバを表します。

まずは以下の部分に注目。

data MyForm a b c = MyForm { 
      myFormF :: Wx.Frame a,
      myFormBtnDlg :: Wx.Button b,
      myFormBtnQuit :: Wx.Button c
}

{- ... -}

setup = 
  do
    f <- Wx.frame [Wx.text := "Hello!"]
    btnDialog <- Wx.button f [Wx.text := "Show Dialog"]
    btnQuit <- Wx.button f [Wx.text := "Quit"]
    Wx.set f [Wx.layout := Wx.column 5 
                    [Wx.widget btnDialog, Wx.widget btnQuit]]

    return $ MyForm f btnDialog btnQuit

ここだけ見ると、完全にWxHaskellのコードです。こちらの一番上のサンプルと比べても、呼んでいる関数のレパートリーはほとんど同じです。

machinecellが使われているのは、この部分になります。

machine = proc world ->
  do
    initMsg <- WxP.onInit -< world
    form <- P.anytime (arrIO0 setup) -< initMsg

    (returnA -< form) `P.passRecent` \(MyForm f btnDlg btnQuit) ->
      do    
        dialogMsg <- WxP.on0 Wx.command -< (world, btnDlg)
        P.anytime (arrIO (\f -> Wx.infoDialog f "Hello" "Hello")) 
                -< f <$ dialogMsg

        quitMsg <- WxP.on0 Wx.command -< (world, btnQuit)
        P.anytime (arrIO Wx.close) -< f <$ quitMsg

GUIプログラミングの経験がある方なら何となく、このコードがイベントハンドラであるという事がお察しできるのではないかと思います。

前回の記事にもこっそり入っていたanytime関数を使って、WxHaskellのIOアクションを呼び出しています。anytime関数は取り立てて特別なものではない単なるユーティリティで、概念的には、前回紹介したawaitやyieldを使ってこんな風に書けます。

anytime 処理 = repeatedlyT 何か $
  do
    x <- await
    y <- lift $ 処理
    yield y

つまり、「上流がyieldするのを待って、処理を実行し、戻り値をそのままyieldする、以下繰り返し」というアローです。

anytimeの引数に多用されている<$演算子はData.Functorで定義されているもので、定義は x <$ fy = fmap (const x) fy です。いくつか動作例を挙げてみます。

"foo" <$ [0, 1] → ["foo", "foo"]
"bar" <$ Nothing → Nothing

意味的には、「Functorの中身を上書きする」と解釈すれば良さそうです。anytimeの入出力は、何らかのFunctorになるようです。後の型表示でもちょくちょく出てくるEvent型がそれですが、Maybe型に近い解釈で「値が上流から来ている時もあるし、来ていない時もある」みたいに考えればよろしいでしょうか。

この辺を踏まえた上でmachine関数を見ると、「worldとかWxP.on〜といったブラックボックスから、イベントが伝わって来た時だけ、anytime関数でアクションを実行する」という形でイベントハンドリングを行っている事が分かります。

worldを根として、ストリームをウネウネと分岐させるため、Arrow記法にかなり頼っています、これは普通のpipe系ライブラリでやると非常に面倒な事です。先ほど引用したHaskell: Splitting pipes (broadcast) without using spawnという記事も、まさにそういう話題について扱っていて、最終的には「Arrowを使おう」という話になっています。

イベントの値を覚える

一点、machine関数の中で面白い動きをしているのがpassRecentです。
passRecentは上記コード中では、ちょっと変な文法で呼ばれていますね。実はArrow記法ではArrowを引数とする関数のうち、特定の条件を満たすものを「ユーザー定義の制御構文」として使用する事ができるのです。詳しくはこちらの記事の下の方を参照して下さい。

という訳で、passRecentは単なる関数で、型は以下の通りです。

passRecent ::
    (ArrowApply a, Occasional c) =>
    ProcessA a e (Event b) ->
    ProcessA a (e, b) c ->
    ProcessA a e c

passRecentの機能は、「第一引数のアローが出力したイベントの値を覚えておいて、そのうち最新のものを第二引数のアローに渡す」事です。上記の例では、初期化時(onInit)に一度しか呼ばれないsetup関数の戻り値を、その後もアプリケーションが終了するまで参照し続ける為に使われています。

一般的なIteratee系ライブラリでは、「複数の部品で状態を共有する」というのがなかなか難しいです。データと一緒に流して各自で保持するか、またはStateTを使うか、といった所でしょうか。なので、こう書けるのもArrow記法を導入したメリットであると言えます。

passRecentと同じ働きをするアローとして、以下のものもあります。

hold ::
    ArrowApply a =>
    b -> ProcessA a (Event b) b

どちらかといえば、界隈で一般的なのはこちらの表式で、多くのFRPライブラリで同名の関数を見る事ができます。
passRecentはholdを使って以下のように実装されています。

passRecent af ag = proc e ->
  do
    evx <- af -< e
    mvx <- hold Nothing -< Just <$> evx
    case mvx of
      Just x -> ag -< (e, x)
      _ -> returnA -< noEvent

Nothingに関する部分をハンドリングするのが面倒でなければ、直接holdで書いても問題ないでしょう。

WxHandlerの実装

という訳で、大半はブラックボックスの中でした。おわり。
ではあんまりなので、WxHandlerの中のソースも見てみる事にしましょう。興味のない方は飛ばして頂いてOKです。

WxHandlerのソースは、僅か154行という短さです。

example/wx/lib/WxHandler.hs

World型の内容

World型の定義は以下の通り。

type MainState a = P.ProcessA a
                    (P.Event (EventID, Any)) (P.Event ())

data EventEnv a = EventEnv {
      envGetIDPool :: Wx.Var EventID,
      envGetState :: Wx.Var (MainState a),
      envGetRun :: forall b c. a b c -> b -> IO c
    }

data World a = World {
      worldGetEnv :: EventEnv a,
      worldGetEvent :: P.Event (EventID, Any)
}

内訳はこんな感じ。

EventEnvとして2つのVar (※Var型は、WxHaskellで再定義されたIORef型)と、作業用に必要な関数
現在処理中のイベントID(後述)と、イベントの引数

コールバック

コールバックとしてWxHaskellのコアから呼んでもらう関数は、以下の通り。

handleProc env eid arg =
  do
    stH <- Wx.varGet $ envGetState env
    (_, stH') <- envGetRun env (P.stepRun stH) (eid, arg)
    envGetState env `Wx.varSet` stH'

処理の中枢はstepRun関数です。

stepRun :: 
    (ArrowApply a, ArrowIO a) =>
    Process a (Event b) (Event c) ->
    a b (ExecInfo [c], ProcessA a (Event b) (Event c)

前回の記事ではrunで引数のリストを渡して、終了まで一気にプロセスを走らせていましたが、stepRun関数はステップ実行を行います。一つだけ値を入力して、戻り値＋αの情報と、ワンステップ進んだ状態のプロセスを返す訳です。
最新の状態のプロセスは逐次、先述のWorld中のIORefに保存しています。machine関数から見て、あたかもストリーミングのように連続してGUIイベントが流れてきていたカラクリは、こういう事なのでした。

listenの正体

ここまでを踏まえた上で、on〜関数の本体であるlisten関数の定義を見ていきましょう。

listenID = proc (World _ etp, myID) ->
  do
     ret <- P.filter (arr fst) -< go myID <$> etp
     returnA -< snd <$> ret

  where
    go myID (curID, ea) = (curID == myID, ea)

listen reg getter = proc (world@(World env etp), ia) ->
  do
    initMsg <- P.edge -< ia
    evId <- P.anytime (arrIO newID) -< env <$ initMsg

    (returnA -< evId) `P.passRecent` \myID ->
      do
        P.anytime reg -< (handleProc env myID, ia) <$ initMsg

        ea <- listenID -< (world, myID)
        P.anytime getter -< ea

listen関数を順に見ていきます。
edgeはholdの反対で、「入力値が変化した時（起動直後含む）にイベントを発生させる」という効果を持ちます。

edge::
    (ArrowApply a, Eq b) =>
    ProcessA a b (Event b)

イベントフックの対象となるWxWidgetのオブジェクトiaが入力されると、まずは新しいイベントIDを取得(newID)。実処理としてはIORefに最新のIDを入れておいて、取得の度にインクリメントしているだけです。
イベントIDは先ほどのpassRecentを使って、ローカル変数myIDとして捕まえておきます。

その後、myIDを引数としてreg(registerの意)を呼び出してハンドラを登録します。regの定義は、例えばon関数ならばこんな感じ。

on signal = listen (arrIO2 regIO) (arr getter)
  where
    regIO handler w = 
        Wx.set w [Wx.on signal := (handler . unsafeCoerce)]
    getter = arr unsafeCoerce

handler引数にはhandleProcに、Worldから取ったenvと先ほど登録したmyIDをbindしたものを渡していますが、regでそれをWxWidgetのコールバックとして登録しています。このハンドラが実際に呼び出される時、worldの中にmyIDが入ってくる事になります。

そしてlistenID内のfilterに到達します。filterもUtils.hsで定義されるアローですが、大体の用途は名前で分かると思うので、説明は割愛します。
この時点では、worldには何か古い別のイベントIDが入っているので、イベントはフィルターされて、これより後には伝播しません。

初回の処理はここまでで終わりですが、注意すべきはこのルーチン、初回だけでなく何度も呼び出されるという事です。
二回目以降はどうなるかというと、edgeの処理が誘発しないため、myIDとworldのIDをfilterで比較する処理だけが走る事になります。
もうお分かりでしょうか。regで登録したhandleProcがstepRunを走らせた場合のみ、このfilterが条件を満たして、イベントが下流に伝わる訳です。

……と、やや突っ込んだ話になってしまいましたが、これがGUIイベントをmachinecellのイベントストリームに変換する処理の全貌でした。

Arrow化とともにFRPから輸入したhold、edgeの活躍が光っていました。

もう一つのexample:石取りゲーム

最初の簡単な例に加えて、WxHandlerを使用したexampleをもう一つ用意しています。
「石取りゲーム」という、アルゴリズム界隈では比較的有名な例を、GUIで実装しました。
ルール（及び必勝戦略）は、検索すれば引っかかると思います。

example/wx/stone/Main.hs

詳細の解説は割愛しますが、最初の例では使わなかったこんな機能が使われています。

イベントを上流側に伝達するfeedback。例ではfeedbackした値をholdで捕まえる事で、書き換え可能な変数のように使っている
その変数の変化をedgeで検出、GUIに逐次反映させる
普通ならGUIイベント応答のためにぶつ切りになる逐次的処理を、コルーチンモナドを使って一本道で記述する

特に後ろの二つは、GUIを書いた事がある方にとっては、かなり有難味の理解できる機能ではないでしょうか。

おわりに

「Arrow化pipeはFRPの夢を見るか？」と題していますが、GUIの実装を見る限りでは

pipe系譲りのコルーチンと、自由なIO呼び出し
FRP譲りのネットワーク構築力と、holdやedgeといった状態制御

と、両パラダイムの「良い所取り」に成功したと感じています。

HaskellにおけるGUI処理の一つの形として、こういうのはいかがでしょうか、という話でした。

Arrow化pipeはFRPの夢を見るか？(GUI編)