Admittedly something small.

ミーリマシンで遊ぼう

2017年1月21日 ( 8年前に投稿 )

RxJS Rx purescript redux

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

# ミーリ・マシンの定義

何か抽象的なものを学ぶときは、最初に定義をさらっと眺めておくといいです。もちろん定義を眺めたからといってすぐに理解できるわけがないのですが、ぼんやりと手掛かりが得られることもよくあります。[ウィキペディア](https://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%BC%E3%83%AA%E3%83%BB%E3%83%9E%E3%82%B7%E3%83%B3)から拝借：

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

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


(´・ω・｀)？

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

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

* [purescript-contrib/purescript-machines](https://github.com/purescript-contrib/purescript-machines)

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

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

```haskell
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`の組ですから、こんな感じになると思います。

```haskell
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](https://github.com/paf31/24-days-of-purescript-2014/blob/master/8.markdown) 

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

```haskell
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`で作ることができます。シグネチャはそれぞれこんな感じです。

```haskell
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`を用意して、次のように連結してみます。

```haskell
machine = source readLine >>> sink log
```

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

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

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



# ディレイ

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

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

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

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

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

```
> Hi

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

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

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


# プーリング

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

```haskell 
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`へと翻訳するマシンも作りました。

```haskell
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`コマンドを送ります。マシンを組み立てます。

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

では実行してみます。

```
> だめだ

> まだ吐くな

> こらえるんだ

> ｵｴｰｯ!

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

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




# 外部から入力する

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

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

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

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

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





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

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

```haskell
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`もあります。

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

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

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

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

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

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

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

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

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

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

マシンの間に挟むと

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

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

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

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

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

```haskell
machine5 = random >>> sink logShow
```

```haskell
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
...
```

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

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

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

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

```haskell
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`で囲まないといけません。

```haskell
machine = loopRec (executeOOP >>> sink log)
```

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

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


# ミーリマシンの圏

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

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

実行してみます。

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

```

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

```haskell
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](https://github.com/slamdata/purescript-halogen-vdom/blob/master/GUIDE.md)っていうライブラリはVDomを入力して`Node`を吐くミーリ・マシンになっているよ、とガイドに書いてあります。こんな応用もあるんですね。

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

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

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

ミーリ・マシンは：

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


# 参考文献

* [ミーリ・マシン - Wikipedia](https://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%BC%E3%83%AA%E3%83%BB%E3%83%9E%E3%82%B7%E3%83%B3)
* [24-days-of-purescript-2014 8. purescript-machines](https://github.com/paf31/24-days-of-purescript-2014/blob/master/8.markdown) 
* [purescript-contrib/purescript-machines](https://github.com/purescript-contrib/purescript-machines)


 

（この記事は同じ筆者が Qiita に投稿した記事の複製です。オリジナル記事)