にわかにReduxミーリ・マシン説が浮上したので、ミーリ・マシンが実用上どのように役立つのかを調べるため、ミーリ・マシンについてもう少し詳しくお勉強することにしました。

ミーリ・マシンの定義

何か抽象的なものを学ぶときは、最初に定義をさらっと眺めておくといいです。もちろん定義を眺めたからといってすぐに理解できるわけがないのですが、ぼんやりと手掛かりが得られることもよくあります。ウィキペディアから拝借：

定義：ミーリ・マシンとは、 $\rm (S, Σ, Λ, T, G, s)$ をいう。ここで、

• 状態の有限集合 $\rm S$
• 入力文字列の有限集合 $\rm Σ$
• 出力文字列の有限集合 $\rm Λ$
• 遷移関数 $\rm T : S × Σ → S$
• 出力関数 $\rm G : S × Σ → Λ$
• 開始状態 $\rm s ∈ S$

(´・ω・｀)？

よくわかりませんが、何か入力したら内部で何か状態が変わって何かが出力されるモノ、ということのようです。手続きの抽象化というところでしょうか。普通のプログラミング言語では手続きが作用や内部的な状態を持つのは当たり前のことなので、わざわざこんな堅苦しく述べるようなことでもない気がします。

数学的な定義はおいておいて、今回使うライブラリのほうでもミーリ・マシンの定義も確認しておきます。まあどうせすぐにはピンとこないんですけどね。言語はPureScriptを使っていますが、別に他の言語でも簡単に同じことができるはずです。

• purescript-contrib/purescript-machines

newtype MealyT f s a = MealyT (s -> f (Step f s a))

このミーリ・マシンMealyTは、ただひとつの関数s -> f (Step f s a)で表現されています。あれ？状態を表現する型変数がありませんね。また、出力関数も見当たりません。ミーリ・マシンは内部に状態を持っているはずですし、出力関数もあるはずなのですが、なぜか入力関数らしきものしかありません。謎です。MealyTにはStep f s aという型も含まれるので、簡単に確認しておきます。

data Step f s a = Emit a (MealyT f s a) | Halt

Emit a mは文字通り出力を示すんでしょうが、ここでまたMealyT f s aが再帰的に出てきます。ややこしくて頭がどうにかなりそうです。しかもHalt？　字面から察すればミーリ・マシンの実行を停止できる操作のようですが、そんなことはウィキペディアの定義には書かれていませんでしたし、何か実用上の都合なのでしょう。もしHaltの操作がないとしたら、Step f s aは単にsとMealyT f s aの組ですから、こんな感じになると思います。

newtype MealyT f s a = MealyT (s -> f (Tuple a (MealyT f s a)))

気持ち的にはクライスリ射newtype Kleisli f s a = Kleisli (s -> f a)に近い気がしますが、出力だけじゃなくて状態も陽に触れるみたいな感じなんでしょうか。たしかに、単なるKleisli f s aではタイムトラベリングとかはできない気もします。この時点では謎が多いですが、まあどうせ考えてもわかりはしませんので、あとは実践あるのみです。

とりあえずライブラリを動かそう

なんかよくわかんないライブラリを動かすときは、もちろんまずサンプルコードをコピペです。しかし、このライブラリ、サンプルコードやテストすらついていません。そこで、以下のドキュメントを参照しました。これがこのライブラリについて解説しているほとんんど唯一のテキストだと思います。

• 24-days-of-purescript-2014 8. purescript-machines

PureScriptは昨日今日出来たばかりの言語なので、バージョンアップしまくりで当たり前のようにコンパイルが通りません。手直ししたものがこちら：

main = runMealy machine
  where
    machine = take 100 (loop (pure "Merry Christmas!")) >>> sink log

pure "Merry Christmas!"が文字列"Merry Christmas!"を出力するミーリ・マシンで、それにloop関数を適用すると、無限に"Merry Christmas!"と出力を繰り返すミーリ・マシンになります。それからtake 100を適用すると、その無限の出力のうち先頭100個だけを取り出して出力しから終了するミーリ・マシンになります。無限のデータからtakeでその一部を取り出すとか、なんだか遅延リストみたいですね。

また、sink関数は任意の作用をミーリ・マシンに変換することができ、sink logは文字列の入力を受け取って標準出力するミーリ・マシンになります。シンクってお台所に付いているあのシンクです。データをだーっと流しこむイメージです。そして、ミーリ・マシンどうしは>>>で合成できるということです。このため、マシン全体としては、"Merry Christmas!"を100回出力するミーリ・マシンになるようです。ミーリ・マシンを実際に実行するには、runMealy関数に与えればＯｋです。実行してみます。

Merry Christmas!
Merry Christmas!
Merry Christmas!
Merry Christmas!
Merry Christmas!
Merry Christmas!
Merry Christmas!
Merry Christmas!
Merry Christmas!
Merry Christmas!
Merry Christmas!
Merry Christmas!
Merry Christmas!
...

どわっ！　やかましいわ！　クリスマスは家族と静かに祝う行事なんやぞ！　恋人といちゃつくイベントちゃうんやぞ！　年末くらいもう少し静かに過ごせんのか！

ソースとシンク

とりあえず、ミーリ・マシンを作って>>>で接続すればそれっぽく動くことがわかりました。さて、さっきはsinkでデータをドバっと流しこむシンクを作りましたが、それに対応するものとして、データがドバっと流れ出してくる『ソース』もあり、ソースはsourceで作ることができます。シグネチャはそれぞれこんな感じです。

source :: forall f s. (Monad f) => f s -> Source f s

sink :: forall f a. (Monad f) => (a -> f Unit) -> Sink f a

Source f sはsがドバドバ噴き出してくるマシンで、Sink f aはaがドバっと流れこんで消費していくマシンです。なるほど、適当な作用f sを与えればソースになるわけですね。そんなわけで、標準入力の作用readLineを用意して、次のように連結してみます。

machine = source readLine >>> sink log

標準入力から入力したら、それをそのまま標準出力に注ぎ込む感じです。実行してみます。

> 42
42
> foo
foo
> akane
akane
> aoi
aoi
>

おお！　入力をそのまま出力するエコーなプログラムが完成しました。ctrl+cで止めない限りずっと続きます。

ディレイ

次は、入力を一回分遅らせてから出力するdelayマシンを作ってみることにします。このマシンは前回の入力を状態として持つのがポイントですが、ミーリ・マシンに状態を持たせるにはどうすればいいんでしょうか。ちょっと頭を捻って、次のように書けることがわかりました。関数からミーリ・マシンをつくるmealy関数を使います。

delay :: forall s m. s -> (Applicative m) => MealyT m s s
delay v = mealy \s -> pure (Emit v (delay s))

ややこしいですが、前回の状態をクロージャに持ってそれを参照しているわけです。まあ細かいことは気にしない！　さっきのエコーマシンの真ん中にdelayを挟みんでみます。

machine = source readLine >>> delay mempty >>> sink log

それから実行してみます。

> Hi

> あれ？
Hi
> 声が
あれ？
> 遅れて
声が
> 聞こえて
遅れて
> くるよ？
聞こえて
>

最初の入力では空文字列が出力されますが、それ以降は直前ではなく、更にひとつまえの入力が出力されます。ミーリ・マシンがその前の入力をしっかり覚えていてくれているわけですね！　状態を扱うことができて、なんかいよいよマシンっぽくなってきました。

Rxのイベントストリームとかシグナルにも似てますね。でも、ミーリマシンは一般には非同期的であるとも限らず、同期的かもしれませんし、まったく純粋かもしれません。また、常に一個の入力と一個の出力が対応しており、ひとつの入力に対して複数の出力があることはないです。実入りがあると出力するからミーリ・マシンと呼ばれているわけですね。なるほどなあ。

プーリング

今度は入力をプーリングする機構を作ってみます。入力があってもそれをすぐには吐き出さずに代わりにひとまず空文字を出力し、特定の入力があったときにぞれまでの入力を一気にドバーッと放出するという振る舞いです。

data Command s = Add s | Flush

pool :: forall s m. Monoid s => s -> (Applicative m) => MealyT m (Command s) s
pool v = mealy \cmd -> pure case cmd of
    Add s -> Emit mempty (pool (v <> s))
    Flush -> Emit v (pool mempty)

こんな感じ。Add sを送り続けると、それを状態として蓄積していきますが、そのときは空っぽの値memptyを出力します。でもFlushを送るとそれまで溜めたモノをドバーっと一気に放出します。これだけだとコマンドラインから指示できないので、コマンドラインの入力をこのCommandへと翻訳するマシンも作りました。

interplet :: forall m. (Monad m) => MealyT m String (Command String)
interplet = mealy case _ of
    "flush" -> pure (Emit Flush interplet)
    s -> pure (Emit (Add s) interplet)

このinterpletマシンは、通常の文字列はAdd sコマンドに変換して送りますが、"flush"という文字列が来たときだけFlushコマンドを送ります。マシンを組み立てます。

machine = source readLine >>> interplet >>> pool mempty >>> sink log

では実行してみます。

> だめだ

> まだ吐くな

> こらえるんだ

> ｵｴｰｯ!

> flush
だめだまだ吐くなこらえるんだｵｴｰｯ!
>

いよいよRxっぽいですね。こんな感じで、入力を送るたびに内部状態を変化させ、同時に記号を出力するということが、ミーリ・マシンではできるようです。

外部から入力する

今まではsourceでソースのマシンを作って入力を発生させていましたが、次はマシンの外部から入力をしてみます。といってもstepMealy関数を適用するだけです。たとえば、入力を大文字にするマシンupperを作って、

upper :: forall m. (Monad m) => MealyT m String String
upper = mealy \s -> pure (Emit (toUpper s) upper)

あとはstepMealyで値を投げ込みます。ただし、結果はStep f s aで返ってきますから、Emitした場合とHaltで停止した場合について分岐をします。

step <- stepMealy "Hello" upper
case step of
    Emit o m' -> log o
    Halt -> pure unit

実行すると、HELLOが出力されます。値を投げ入れてミーリ・マシンを外部から駆動するという感じで、これはなんだかRedux-Sagaっぽいですね。putでReduxに値を投げ入れるように、stepMealyを使うというという違いだけです。でも、結果のマシンm'が明示的に出てくるのがちょっと違いますか。

ほかにもいろいろやってみます

配列の値を次々流しこむfromArrayもあります。

machine = fromArray [0, 1, 2, 4, 5, 6, 7] >>> sink logShow

実行すると

0
1
2
4
5
6
7

Rxのrangeっぽいですね。

take nが先頭n個だけを取り出すマシンですが、先頭のn個を捨てるdropもあります。

machine = drop 3 (fromArray [0, 1, 2, 4, 5, 6, 7]) >>> sink logShow

zipWithでふたつのミーリ・マシンからひとつづつ取り出して処理したり

machine = zipWith Tuple (fromArray ["春香", "ゆず", "コトネ"]) (fromArray ["優", "楓", "しずく"]) >>> sink logShow

(Tuple "春香" "優")
(Tuple "ゆず" "楓")
(Tuple "コトネ" "しずく")

interleaveで交互に出したりもできます。

machine = interleave (fromArray ["春香", "ゆず", "コトネ"]) (fromArray ["優", "楓", "しずく"]) >>> sink log

春香
優
ゆず
楓
コトネ
しずく

Rxが好きな人はこの辺りでほぼイキかけるんじゃないでしょうか。すみません。

入力されたらnミリ秒待ってから出力するwaitマシーンも作ってみました。

wait :: forall a eff. Int -> MealyT (Aff (Effects eff)) a a

マシンの間に挟むと

machine = source readLine >>> wait 500 >>> sink log

> そんなことは
そんなことは
> ナン　ノブ　マイ　ビジネス
ナン　ノブ　マイ　ビジネス
> （夜に影を探すようなもの）
（夜に影を探すようなもの）
> です
です
>

字面ではわかりませんが、動かすと入力してから出力するまでにちょっともたつく感じになります。

あとは、乱数をドバドバ放出し続けるマシンとか

random :: forall eff m. (MonadEff (random :: RANDOM | eff) m) => MealyT m Unit Number
random = mealy \_ -> do
    r <- liftEff Random.random
    pure (Emit r random)

machine5 = random >>> sink logShow

0.8077749259343008
0.843892567634853
0.24019024441745174
0.3026528383375737
0.02644466353948971
0.5897859494813793
0.8602703304837029
0.7307064885220147
0.706604323773312
0.8734853221998418
0.8062628648977004
0.3400836400233571
0.16986491173524798
0.5245064121019869
...

オブジェクト指向絶許マシーンとか

executeOOP :: forall m. MealyT m Unit String
executeOOP = loop (pure "オブジェクト指向はｼｮｹｰですよｼｮｹｰ！")

オブジェクト指向はｼｮｹｰですよｼｮｹｰ！
オブジェクト指向はｼｮｹｰですよｼｮｹｰ！
オブジェクト指向はｼｮｹｰですよｼｮｹｰ！
オブジェクト指向はｼｮｹｰですよｼｮｹｰ！
オブジェクト指向はｼｮｹｰですよｼｮｹｰ！
...

でもこれ『ループ』を続けるとスタックオーバーフローします。ぜんぜんループじゃないですね。なるほど、これでは今の装備では殺しきれん。そんなわけで、MonadRecというスタックセーフなループを提供する型クラスを使ってみました。

loopRec :: forall f s a b. (MonadRec f) => MealyT f s a -> MealyT f s b
loopRec m0 = do
    mealy \s -> do
        tailRecM (\m -> do
            stepMealy s m >>= case _ of
                Halt -> pure (Loop m0)
                Emit s' m' -> pure (Loop m')
        ) m0
    loopRec m0

この関数loopRecで作られたマシーンは、一度Haltで停止しても最初のマシーンm0を使って復活させて動き続けます。でも元のloopとはちょっと使い方が異なっていて、ループしたい全体をloopRecで囲まないといけません。

machine = loopRec (executeOOP >>> sink log)

一般性がなくて、なんか違う感じがします。何かうまい方法はあるんでしょうか。まだ思いつきません。

そういえば、Rxにはなんであんなに関数がたくさんあるのかとみんな思っているでしょうが、Rxを作ってる人の気持がだんだんわかってきました。要するになんでもできるので、あれもできそう！これもできそう！って思いつく端から作っていくと、機能がモリモリ増えていってしまうんです。たぶんRxを作っている人も、それRxでできるよってやり続けてあんな巨大になっちゃったんだと思います。そりゃあRxで『も』できますが、そんなに色々あっても覚えきれないし使われないんですけどね。それはRxでもできますが、それをRxでやるべきかどうかはまた別の話です。早すぎる抽象化というやつで、ミーリ・マシンも普遍的すぎてどこまでミーリ・マシンでやるべきなのかよくわからない感じです。

ミーリマシンの圏

ところで脱線しますが、ミーリ・マシンは圏でもあるようです。『関数型プログラミング』の話でたまに出てくる『圏論』の『圏』です。『ミーリ・マシンが圏をなす』というのは難しいことを言っているわけではなくて、ミーリ・マシンは>>>演算子で合成できるし、入力をそのまま出力する素通りマシンidも使えると、ということを言っているだけです。試しにidミーリ・マシンを使ってみましょう。

machine = source readLine >>> id >>> sink log

実行してみます。

> そんなことは
そんなことは
> ナン　ノブ　マイ　ビジネス

おや。idは入力を左から右に素通りさせるだけですが、それは１回だけで、２回めに通そうとするとそこでHaltで停止してしまうというマシンのようです。これ、ちょっとだけ予想外の振る舞いでした。実装も確かにそうなっています。

instance categoryMealy :: (Monad f) => Category (MealyT f) where
  id = pureMealy $ \t -> Emit t halt

そういえば、pure "Merry Christmas!"は"Merry Christmas!"を一度出力して停止するミーリ・マシンでしたし、それをloopすることで無限に叫び続けるミーリ・マシンになってました。なんかいちいち停止しなければいけない理由があるんです？このへんがまだよくわかりません。

プログラミングにおける代表的な圏といえば関数の圏で、関数は合成できるし、引数をそのまま返す『恒等関数』が存在します。ミーリ・マシンが提供する手続きも、同じように合成と恒等射という構造を持つということですね。こんなところにも圏がひょっこり出てきてちょっとおもしろいなと思いました。

まとめ

まだ他にもいろいろできますが、というか何でもできると思っていいでしょうが、なんかトラベリングデバッガとかホットリロードみたいな具体的な機能として使ってみないと、まだそこまで便利な抽象だという感じではないです。そこまで考えて気付いたんですが、このライブラリの実装では、マシンの状態を取得して永続化する一般的な方法がありません。そのため、タイムトラベリングはともかく、ホットリローディングの実装には使えないと思います。だめじゃん！

今回使ったpurescript-machinesではありませんが、purescript-halogen-vdomっていうライブラリはVDomを入力してNodeを吐くミーリ・マシンになっているよ、とガイドに書いてあります。こんな応用もあるんですね。

ミーリ・マシンは入力があって状態が変化して出力するというだけのものですから、プログラムとしては当たり前のことをしているだけっていう感じもします。その一方で、いろんなものをミーリ・マシンで表現してそれを合成するというのは新たなプログラミングスタイルの一種なのかもしれません。Rxのスタイルをリアクティブプログラミングなどと格好いい名前で呼ぶなら、ミーリ・マシンを合成するこのスタイルも何か格好いい名前があってもいいかもしれませんね。ミーリ・マシン自体はただの関数一個で表現できますし、他の言語でもミーリ・マシンを抽象化するのは簡単だと思うので、トライしてみたら面白んじゃないでしょうか。

今回書いたまとまっていないコード：

• https://gist.github.com/aratama/5130e2ecf540d0ea6e4ce29e4b223f01

ミーリ・マシンは：

• ただの手続きっぽい
• が、合成可能なので
• 遅延リストっぽいところもあり
• Rxのイベントストリームっぽいところもあり
• Redux/Redux-Sagaっぽいところもあり
• 要するに変化する内部状態と入力と出力を持った手続きなのでとても普遍的な構造っぽい
• 普遍的すぎて逆にどう使ったらいいかわかんないです
• Rxの気持ちがわかる

参考文献

• ミーリ・マシン - Wikipedia
• 24-days-of-purescript-2014 8. purescript-machines
• purescript-contrib/purescript-machines