はじめに

machinecell: Arrow based stream transducers

この記事は、先日公開したmachinecellライブラリの紹介記事です。
machinecellは、一言で言うと「いわゆるpipe系のライブラリに、Arrow計算の機能を足したもの」となります。
さすがに予備知識なしでは厳しいので、一つずつ見ていく事にしましょう。

Statefulな部品を組み合わせるpipe

参考

Pipeモナドの紹介

pipe系とは、HaskellでIOを扱う方法の一つです。あたかもパイプのように、読み込み→加工→出力と、上流から下流へデータを流しながら処理していきます。pipe系に分類されるライブラリには、現行のものでpipes, conduit, machinesがあります。pipe系より広い括りでiteratee系というものもありまして、いずれにせよHaskellの弱点であるIOを上手いこと処理するためのライブラリです。

とりあえず、machinesとmachincellによるサンプルプログラムを見てみましょう。
(完全なコードはこちら)

machines版

1-intro.hs

askMc = Mc.construct $
  do
    lift $ putStrLn "情報を入力して下さい"
    forever $
      do
        lbl <- Mc.await
        lift $ putStr (lbl ++ ": ")

        ct <- lift $ getLine

        Mc.yield (lbl, ct)

registerMc =
  do
    r <- Mc.runT $ askMc <~ Mc.source ["Zip code", "Address", "Name"]
    print r

machinecell版

1-intro.hs

askP = P.constructT P.kleisli0 $
  do
    lift $ putStrLn "情報を入力して下さい"
    forever $
      do
        lbl <- P.await
        lift $ putStr (lbl ++ ": ")

        ct <- lift $ getLine

        P.yield (lbl, ct)

registerP =
  do
    r <- runKleisli (P.run askP) ["Zip code", "Address", "Name"]
    print r

ほとんど間違い探しのレベルですね。真似して作ったので仕方ない。machinecell側にだけkleisliという見慣れない名前が見えますが、これは型合わせだと思って無視して頂いてOKです。

上のコードは、ちょっと変則的ですが、pipe系の汎用性をデモするために「データの中間加工時に副作用を起こす処理」を実装してみました。

yieldは、pythonでお馴染みのyieldです。呼ぶとそこでdo文の処理が中断し、下流に処理が移ります。一種のコルーチンですね。さらに、pipeというのはiteratorであると同時にiterateeでもあるので、上流から処理を受け取るためのawaitもあります。

MonadTransの特徴を活かしてliftで副作用が使えたり、do文なのでローカル変数が使えたりと自由度は高いです。このように状態を持つ部品を簡単に定義できるのが、pipe系のメリットです。

Monadより一般的なArrow

pipe系ライブラリは前節のように個々の要素を定義した後、それらを繋ぎ合せて全体の処理を構成します。
繋ぎ合わせのツールはライブラリによって、独自の演算子を使ってみたり、Categoryの演算を使ってみたり、その両方が提供されていたりします。

一方で、machinecellはこの部分にArrow演算を使います。

Arrowというのは、包含関係で言うとCategoryとMonadの中間にある型です。Haskellの歴史の中では比較的新しい概念のようです。
数学的な意味を置いておくと、Monadというのは「do記法を使うために必要なインターフェイス」と捉える事ができます。
同様に、ここでArrowを「Arrow記法を使用するためのインターフェイス」と考えてみましょう。

Arrow記法は、GHCでArrows拡張を有効にすると使用できます。
単なる(->)もArrowなので、まずは普通の関数をArrow記法で書いたものを見てみましょう。

foo = proc x -> 
  do
    y <- returnA -< x + 1
    returnA -< y + 1
-- foo 1 `shouldBe` 3

Arrow記法に絶対必須なものはprocです。その他doや-<、そして今回は扱いませんがif、caseやバナナ括弧といったものが適宜出てきます。

proc x -> ... は、ラムダ式の\x -> ... と似たようなものですが、仮引数は必ず1個になります。Monadならば、コマンドにあたるものはm aでもa->m bでもa->b->m cでも良かったのですが、Arrow記法のコマンドに相当するArrow型は必ず1引数です（複数引数が必要ならタプルを使う）。-<を含む文はArrowの「実行」に当たり、左辺にArrowを表す式、右辺にその引数というフォーマットで書く事になっています。

Monadのdo構文との重要な違いとして、-<の左辺には、そこまでの計算結果を使用する事ができません。たとえばMonadのdoでは、do { result <- some_func; result }というように戻り値のアクションをそのまま実行することが出来ますが、Arrowの場合は文法的にこれと同じものを作る事ができません。これはMonadとArrowが許している演算の違いによるものです。若干の不便さは裏を返せば、Monadとしての演算をフルにサポートできないような型でも、Arrowにならば出来る可能性があるというメリットでもあります。その一方で、結合しかできないCategoryと比べれば、Arrowの演算は遥かに強力です。

machinecellによるArrow記法のプログラムは、次のような形になります。

1-intro.hs

-- Print with label.
pWL :: Show a => String -> a -> IO ()
pWL l x = putStrLn $ l ++ show x

doProcess = P.repeatedly $
  do
    x <- P.await
    P.yield (x+1)
    P.yield (x+2)

body = proc evx ->
  do
    P.anytime (P.kleisli $ pWL "input ") -< evx
    evy <- doProcess -< evx
    P.anytime (P.kleisli $ pWL "output ") -< evy
    returnA -< evy

main =
  do
    result <- runKleisli (P.run body) [1, 10, 100]
    pWL "final result " result

実行結果はこんな感じです。

input 1
output 2
output 3
input 10
output 11
output 12
input 100
output 101
output 102
final result [2,3,11,12,101,102]

一番目の例は純粋な例でしたが、Monadと比較されている事から分かる通り、一般にArrowは副作用を持つ事ができます。doの中に並べてコマンドを記述するという事は、すなわちその二つの処理を逐次実行する事を意味します。
実行結果を見ると、doProcessが1入力に対し2回の出力を行うのを反映して、input1行につきoutputが2行出力されています。この挙動は、ListTモナドとよく似ています（多分。使った事ないけど）。

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

参考

関数リアクティブプログラミングの実践

iteratee系と並んで、関数型におけるIOの有望株と目されている要素技術として、FRP(Functional Reactive Programming)があります。FRPとは、値同士の関係をネットワークとしてプログラムしておき(Excelでセル参照と関数を使ってゴリゴリやるイメージ)、時間経過によって値が変化することでプログラムが駆動するというパラダイムになります。

このように時間の関数として変化する値をビヘイビアと呼びますが、その一方でFRPにはもう一種類、不定期に発生してはネットワークを流れていく、イベントという種類の信号も存在します。最初に挙げた資料によると、iterateeは一階のFRPをイベントのみに制限したもの、と見做す事ができるそうです。
machinecellも同様にある種のFRPであるといえるのですが、Arrow化されているという特徴から、さらなる類似性が見えてきます。
FRPの中にはそのものまさに、ネットワークをArrowで表現するAFRPという流派が存在するのです。

例えば、FRPには動的にネットワークを組み換えるswitchとよばれる関数があります。
AFRPライブラリの例であるYampaのswitch関数は、以下のようなシグネチャを持っています。

switch :: SF a (b, Event t) -> (t -> SF a b) -> SF a b

引用元

実はmachinecellでも、Yampaと全く同じシグネチャのswitchが提供されています。

src/Control/Arrow/Machine/Utils.hs

switch ::
    ArrowApply a =>
    ProcessA a b (c, Event t) ->
    (t -> ProcessA a b c) ->
    ProcessA a b c

Event型はYampaとmachinecellにそれぞれ定義されており、ほんの少しだけ定義が違います。実はmachinecellのEvent型は、今までの例でもたくさん使用されています。ちゃんと型を書くとEventだらけになるのですが、Eventを受け取っては渡しているだけなので陽に見えないんですね。

さて、これによって動的にネットワークを組み換えるmachinecellコードの例として、ソースツリー中のテストコードから少し引っ張ってみます。

test/spec.hs

    describe "switch" $
      do
        it "switches once" $
          do
            let
                before = proc evx ->
                  do
                    ch <- P.filter (arr $ (\x -> x `mod` 2 == 0)) -< evx
                    returnA -< (NoEvent, ch)

                after t = proc evx -> returnA -< (t*) <$> evx

                l = [1,3,4,1,3,2]

                -- 最初に偶数が与えられるまでは、入力を無視(NoEvent)し、
                -- それ以降は最初に与えられた偶数 * 入力値を返す
                ret = run (switch before after) l

                -- dが付くと次回からの切り替えとなる
                retD = run (dSwitch before after) l

            ret `shouldBe` [16, 4, 12, 8]
            retD `shouldBe` [4, 12, 8]

上の例はあまりネットワークという感じがしませんが、もちろんswitchで合成された結果もArrowなので、これをさらにアロー記法の中に入れたりできます。

この他にも、先ほど「イベントのみ」と銘打っておきながら実はaccumやholdを使用して疑似的にビヘイビアを扱う事ができたり、ArrowLoopインスタンスを使って輪になった回路を扱う事ができたりと、色々とわけのわからない事が可能です。

どうでしょう。夢が広がってこないでしょうか。

おわりに

そんな訳でpipe系、Arrow、FRPと、関数型界隈でも比較的ホットな部分を、上手い事つまみ食いできて楽しかったです。今回、いろんな説明をかなり意図的にスルーしたので、興味のある所は適宜検索してみる事をお勧めします。