(TODO)Concurrent Haskell
1. Introduction
遅延評価と非同期性の統合
便利なabstraction
意味論
について紹介する。
この論文んでは複数のプロセサを利用することでプログラムの性能を向上させることをconcurrencyとは呼ばない。
IOを含む非同期処理を意味的に明確に使っていくか、にフォーカスしたい。
2. The basic ideas
プロセスとプロセス生成の仕組み
プロセス間で協調するアトミックな状態
これらがConcurrent Haskellの主な内容だが、ここでまずはI/Oに関するモナディックなアプローチを見てみたい。
2.1. A review of monadic I/0
非正格な言語では遅延評価によりI/Oの副作用がいつ発生するかその式がいつ評価されるかに依存する。
これはI/O操作を状態の変換として扱うことで解決できる。
code:haskell
type IO a = World -> (a, World)
(確かにstateモナドの実装は実質関数なのでこれと似たような定義になる IO a = State World a みたいな)
この定義の実装はIOを直ちに実行して変更された World を返却する。
我々はこの IO をアクションと呼ぶ。
このようなIOのモナドを使った計算は手続き的なIOの計算と同様に、実行の順序が保証されることを処理系に要求する。
IOと同様に変更可能な状態へのアクションも提供できる。
code:haskell
newMutVar :: MutVar a
readMutVar :: MutVar a -> IO a
writeMutVar :: MutVar a
MutVarは状態の保存場所への参照だと考える。
こうしたアクションは果たしてどのように実際に適用されるのか。
原則として、プログラムはただ世界の状態を受け取って新しい世界の状態を返すただの状態変換子だと考えることができる。
実際には、この副作用が段階的に実行されるべきで、プログラムの終了間際にすべてが同時に発生していいわけではない。
非同期処理の世界ではこの副作用が問題となってくる。
2.2. Processes
Concurrent Haskellでは新しいプリミティブとして
code:haskell
forkIO :: IO () -> IO ()
を提供する。これは非同期プロセスを開始させる。
IO () という副作用のあるアクションを受け取りfolkした方のアクションとfolkされた方のアクションはinterleavingしながら実行される。
特記事項
forkIO時にプロセスの同期が必要
プロセスで評価されてthunkからvalueになったものを別のプロセスが使う場合など
２つのプロセスが共有状態を安全に変更するための仕組みが必要
forkIOは親プロセスから子プロセスを生成する非対称な関数である。2つの子プロセスを生成して待ち合わせる対称な関数にしていないのは、それがAPIとして不便になるから。
forkされたプロセスはUnixのように名前をもつわけではない。したがってそのプロセスの終了を待ったり中止させたりすることが難しい。 MVarを使うことで待ち合わせはできるが、中止させるのは新たな困難を招く
2.3. Syncronisatoin and communication
forkIO以外の機構が必要な理由。
外界のリソースに対して排他的なアクセス
N:Mのプロセス間のデータを非決定的にmergeする方法が必要 (サーバがNクライアントの入力を受け取る場合など)
ストリーム処理関数がN入力M出力する場合の問題。ストリームスタイルのIOはめんどかったのでMonadによるIOが人気になった。いまさらそれを復活させるのは矛盾している。あくまでもMonadic IO的にやりたい。
解法
データフロー記述言語IdのI構造とM構造をMVarと組み合わせる。
MVarはこんな感じ。
MutVar の同期バージョン
receiveとsendを持つチャネルとみなせる (これはまさしくgoやclojureのcore.asyncだな)
MVar () はON/OFFをもつセマフォとみなせる
MVar はMLにおける ref
3. A standard abstraction: buffering
MVarによるメモリセルの実装を例示してみよう。
3.1. A buffer variable
通常ProducerとConsumerの連絡にMVarを使う場合、ConsumerがMVarからデータを取り出す前に、Producerが新しいデータでMVarを上書きしてしまう可能性がある。
これを解決するために2つ目のMVarを使ってConsumerからのAckを表現する。これをCVar (Channel variable) と呼称する。
このCVarは2つのMVarのペアで作られている。1つはデータのキャリアーMVar a、もう1つはConsumerからのAckを受け取るMVar ()となる。ProducerはAckを表すMVar ()から()が取り出せた場合だけ、次のステップとしてデータaをキャリアーに送信できる。ConsumerはMVar aからaを取り出せた場合だけ、次のステップとして()をAckに送信する。
3.2. A buffered channel
CVarは長さ1のバッファを持っていたので次は無制限の長さを持つバッファを考える。
type Channel aとして表す。このチャンネルは複数のプロセスから安全に読み書きされることが条件となる。
これがチャンネルの全容。
code:haskell
type Channel a = (MVar (Stream a), MVar (Stream a))
type Stream a = MVar (Item a)
type Item a = Item a (Stream a)
片方向の連結リストのようになっているが間にMVarが入って参照のあるなしを表現している。
putChanやgetChanを見ているとそれが表現されており面白い。
この構造を複製するdupChanを定義すればマルチキャストのChannelを作ることができる。
ここ難しいなあ, step by stepでみないとわからん
あ、書く側のMVarは維持して読む側のMVarを新しく付け替えているのか
ここあとで自分でコード書いて確認すること
3.3. Skip channel
最後の例として