STはState Transformerとは言うけれど

Haskell ST Monad

少し前に巷ではやったSTのことを勉強してみました。原典のLazy Functional State Threadsをかじってみました。

僕はStateモナドはなんとなく自分でかけるくらいまで理解していたのですが、STは使ったこともないし、いったい何物なんだかぜんぜん知りませんでした。

Stateモナドは要するに関数なわけで
State s a = State \s -> (a, s)

ということはStateモナド系のKleisli関数がバインドされる図は乱暴な見方をすればこうゆう絵柄になるわけです。

runState (\s -> (a, s') >>= \a s -> (b, s') >>= \b s -> (c, s'))

何をスケッチしてるんだかよくわからなくなっちゃうんですがここではそれぞれのKleisli関数をそのシグネチャだけで書いています。それぞれのKleisli関数は（Kleisli関数なので）パラメタ１つとステートをもらってステートと何かほかの値のTupleを返すようになっているので、基本的には違うステートや何か値を下流のKleisli関数に流すことができますね。でもやっていることは単に関数をつなげているだけなので、まるっきり純粋関数型です。でも、見方によったら変数の値が変わっているような気もしなくもない…

モナドでTransformerというとMaybeTとかListTみたいなモナド同士を合成するタイプクラスを思いつきますよね…だから僕も最初はSTは単純にStateのTransformerなのかと思ってたんですが、これが違うことはちゃんとSTのシグネチャをほかのMonadTransformerと比較するとはっきりしてきます。おまけにStateTもControl.Monad.Stateモジュール内に定義されています…

newtype MaybeT m a
newtype StateT s m a
newtype State s a
data ST s a

こうやって見るとMonadTransformerであるStateTはSTよりも型パラメタが一個多いですよね。そして、STとStateはシグネチャ的には同じです。このことから、STがMonadTransformerではないことがはっきりしますね。
しかしながら混乱するのは原典のほうを当たってみるとSTをたびたびState Transformerという呼び方をしているわけです。これだと「あー、これはきっとState Monad Transformerのことを言ってるに違いない」と思っちゃう人がいてもおかしくないですよね…しかしながらこの論文の日付は１９９３年、論文の中でもモナドのバインドすら出てきません。そんなことから推察するに、この論文が書かれたころにはまだMonad Transformerのほうが生まれてすらいなかったんじゃないかと…

前説が長くなっちゃったんですが、論文で説明されているSTの考え方は大体こんな感じです…

あるステートを孤立した「スレッド」の中に閉じ込めてしまうと、そのスレッド内でどんなことがおきていてもスレッドの外側からは何も変化しているようには見えない。僕たちが知っているStateモナドの保有している状態をこういったスレッドの中に閉じ込めてしまうと安全に刻々と変化する状態をうまく表現できる。

見たいな事が書いてあって、さらに理論的な安全性の検証みたいなことが書いてあります。

そして何より何も知らなかった僕にとって衝撃的だったのは

newtype IO a = ST RealWorld a

と言うことです。つまり、IOはSTで実装されている。といっても、今のGHCの中身が実際どうなってるのかは知らないですが…

以前からIOについて漠然と思っていたことのひとつに、副作用のあるものはみんなIOといっても、アドレス0x10000000にある１バイトの値はアドレス0x20000000にある１バイトの値とは独立に変化すると考えるのが自然なはずなのに、メモリを書き換える操作がIOモナドであるためにこの２つの操作の実行順序がdeterministicに決定されているようにしかコードがかけないのはなんだかおかしいんじゃないか…（ちょっと突っ込みどころ満載かもしれませんが、まぁ、漠然と思っていることということで…）なんて思っていたんですが、こういったモデルをSTモナドは割りと正確に表現しているような気がしますね…

論文を読むとrunSTの定義：
runST :: (forall s. ST s a) -> a
に出てくる forallがそのSTモナドが保持している状態がほかから見えないことを証明することに役立っているようなことが書いてありましたが、そこのところは、まだちょっとわかんない感じです…

きょうはこのへんで。
ではでは。