uehaj's blog

Grな日々 - GroovyとかGrailsとかElmとかRustとかHaskellとかReactとかFregeとかJavaとか -

HaskellにおけるIOモナドとSTモナドの関係

haskell

HaskellにおけるIOモナド(IO a型)とSTモナド(ST s a型)について整理してみました。

IOの定義から知るST

IOモナドの考え方についての原論文に相当する「Lazy Functional State Threads」においては、IOの定義は

newtype IO a = ST RealWorld a

のようにST型を直接使用して定義されるものとして説明されています。ただ、「IO inside」によれば、GHCのライブラリ実装においてIO aの定義は

newtype IO a = IO (State# RealWorld -> (# State# RealWorld, a #))

だそうで直接STを使ってはいません。後者のは正格タプル非ボックス化タプルを使ってます(知らん!)。

まあ、Haskell仕様ではIO aと関数仕様が定義されているだけで=の右側は実装依存というわけなのでしょう。

IOモナドとSTモナドとの機能的関係

直接的な利用関係があるかどうかはともかく、記事「第7回 入出力と遅延評価の間を取り持つIOモナド - ITpro」からすると

STモナドは、「状態」を参照型などのより効率の良い仕組みで利用できるようにするため、IOモナドと同じ技術を使って実装されています

とのことです。

まず、IOモナドの機能を整理しよう

上記を踏まえて私の理解した限りでは、まずIOモナドには以下(1),(2)の2つの役割りがあります。

  • (1) 副作用コードを分離する
    • (1-1)純粋コードから副作用コードを呼べなくする。
      • 静的型チェックおよびランタイムがmainを経由してからしかIOアクションを起動できないことによって
    • (1-2)更新状態を外に持ち出せなくする。
      • 静的型(多相型)チェックでコンパイル時に保証(ランクN多相によって)。ただし、IOでは(1-1)があるので(1-2)は試みることもできず、IO利用者からは(1-1)と一体的に認識される役割りである。
  • (2) 副作用を有するコードの実行順序を保証する
    • 副作用は以下の二種類に分けて考えることができるが、実行順序の保証はいずれに対しても必須。
      • (2-1)外部から観測可能なもの→入出力
      • (2-2)外部から観測不能なもの→変数更新(IORef,newIORef,...)

    • おさらいでした。

    そして、STモナドは?

    STモナドは、機能的に前述の青字の(1-2)と(2-2)を得るものです。つまり、入出力を行なわず、変数更新(STRef,newSTRef..)だけを行なう用途に使用できます。STモナドには、入出力を行なえない、という制限がありますが、実行順序は保証されるので変数更新はでき、さらに有用なことに(1-1),(2-1)が無いので純粋関数からも呼べるという利点が得られます。

    もうちょっと詳しく言うと、

    • 「変数更新」のみを実行するコードは、そのコードがもはやコードの見た目としても実質としても状態更新バリバリの命令型(=評価順序が結果に影響を与える)であったとしても、呼び出し側から見たときの参照透過性さえ保てれば、純粋コードから呼んでも大丈夫だ問題ない(呼ぶ側のコードは純粋なので、呼ばれるかどうか、呼ばれる順序などはわからないが、一旦呼ばれたならその呼ばれるコード内なら順序が保たれる)。なぜなら、プログラムの外部から見て検知不能だからである。プログラムの最適化と同じである。ばれなきゃイカサマじゃないんだぜby承太郎である。
      • ここで言う「変数更新」は、Stateモナドによる「状態から異なる新規状態を作り、次々と置き換えていくことで「状態の更新」をエミュレーションする」ということとは違い、特定アドレスのバイト値の書き換えが発生するような、真のメモリ更新の意味。ここで問おうとしているのは、アルゴリズムの特性によって「実際のメモリ書き換えでのみ、期待される高い実行効率が達成できるようなアルゴリズム」が実際にあり、それを直接的に記述・実装するような用途に使える、ということ。
    • しかし「入出力(=プログラム外とのインタラクション)」を行うコードは、たとえそれが「呼び出し側から見て参照透過(引数のみによって返り値が定まる)」としても、純粋コードから呼ばれるわけにはいかない。純粋コード自身が遅延評価によって、呼ばれるかよばれないか、あるいは呼び出し順序について保証がないからで、その状況下では外部から見ておかしなこと(起きて欲しい副作用が起きない・順序が変、など)が検出でき都合が悪いからである*1。だから純粋コードのような恐ろしいものから呼ばれないようにIOで守り、mainにつらなる「見えないバトン*2」の唯一の連鎖(the chain)に繋げる必要がある。
    • IOは、入出力も変数更新も両方行なうことができる。しかし、入出力を行なわず、変数更新だけを行うコードをIOにするのは、純粋コードから呼べなくなるので嫌である。STモナドは、その目的のためにある。STモナドは入出力はできないが変数更新は行うことができる(ただし更新中の状態を外に持ち出せないように工夫がしてある)。そして、純粋コードからも(IOからも)任意に呼び出すことができる。

    表にすると

    入出力 起動方法 純粋関数から 変数更新 順序の保証 相互に呼べるか
    STモナド できない runST 呼べる できる ある IOを呼べない(純粋関数と同様)
    IOモナド できる mainで起動 呼べない できる ある ST,State含め純粋関数を呼べる
    Stateモナド できない runState 呼べる できない ある IOを呼べない(純粋関数と同様)

    まとめ

    • STモナドはIOモナドへの接続性を意図的に除去したIOモナドのようなものである。
    • STモナドはメモリ更新の可否が重要なアルゴリズムを命令型で効率良く実装できる(ただし入出力を行わず、参照透過である場合に限る)
    • STモナドは純粋コードからも純粋コードであるかのように呼べる。

    *1:時系列に沿った因果律に支配された哀れな人間はそういう状態をバグと呼ぶかもしれない。

    *2:バトンはIO Insideの表現。実行順序を保証するためにうけわたしていく状態値を意味する。