このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

圏論番外:同期/非同期の結合

「はじめての圏論」を書きはじめたので、愚痴みたいな話も書きやすくなったね。背景とか予備知識とかがより多くの人に共有されれば、「何をワケワカンナイ繰り言をいってんだ?」と思う人が少し減って、「なるほど、それは確かに問題だな」とか「こうすれば解決可能だ」とか(あるいは、「やっぱりワケワカンナイ」とか)考える人が少し増える可能性もある。

で、愚痴みたいな話を書くわけだ。


A, Bなどがプロセス(自律的/継続的な処理実行単位)だとして、Aの出力の型がY、Bの入力の型もYのとき、Aの出力をBの入力に繋げれば、AとBをあわせたものを新しいプロセスとみなせますね。この合成プロセスをA;Bと書くのだけど、「;」を使うココロは圏論的な結合ね。このへんの事情は、「はじめての圏論」の「第5歩:変換キューの圏」「第6歩:有限変換キューと半圏」を読んでもらえれば納得がいくことだと思います。

それで、AとBが離れていたり(例えば、Aが東京にいて、Bはブエノスアイレスで動いている)、AとBの性能差があったり(例えば、Aが携帯電話内のアプリケーションで、Bがスーパーコンピュータ上の計算エンジン)すると、AとBの結合は非同期のほうがいいかも知れません。仮に非同期な結合を「;;」とでも書いて、「;;」を圏論的にうまく定式化できるでしょうか。

非同期結合「;;」を基本とする圏を定義はできるだろうけど、僕は、圏論的結合は同期結合を出発点にしたほうがいいと思いますね。つまり、Aが何か(データとかメッセージとか)を出力すると同時にそれはBの入力となる、と。それじゃ、非同期の結合はどうやって表現するか?

非同期性はプロセスの性質/機能性と考える。つまり、「AとBを非同期に結合する」とは、あいだに遅れ(時間のズレ)を実現するプロセスMが入ってA;M;Bのように3プロセスを結合するわけ。つまり、適当なMを使って、A;;B を A;M;B として定義する。

何人かの人が指摘していることなのだけど、実際の作業をしているプロセスと通信媒体/通信チャネルは、実は区別つかない。それは、圏TransQの説明で出した無変換キューのようなものを考えれば明らかでしょう;無変換キュー(変換するキューでも)は、処理機構とも通信媒体とも考えられる。通信(転送、媒介)は処理の一種だとも言えるわけ。

Mは(何の変換もしない)無限キューだとしよう。次の図を見ながら考えて欲しいのだけど、Mを通信媒体だとみなす。AがMのメソッドpostを呼ぶ(パケット送出に例えられる)と同時に、M内のメソッドpost本体が実行される。つまり、AとMの結合は同期している。が、この時点ではMのバッファにデータが溜まるだけで、Bには何の影響もない。Bが気が向いたときにMのgetを呼び出してデータを拾い出すことで、Aからの通信データ(パケット)を受け取ることになる。



結合法則 (A;M);B = A;(M;B) は、通信媒体Mを、送信プロセスAの一部と思っても受信プロセスBの一部と思っても系全体の振る舞いは同じだ、と読める。Mの“動作”を変えれば、例えば「ロストはしないが順序は保証しない通信媒体」を表現したりもできる。「たまにロストする通信媒体」の「たまに」を正確に表現しようとすると、確率的遷移系とかを持ち出すんだろうが、僕はよくわからん。

「メソッド呼び出し一元論」という記事で、「(基本概念としては)同期呼び出しだけあればいいだろう」と書いた気分はこんなところです。