val it: α → α = fun

alohakun が次のようなことを書いていたのが面白かったので、今日ちょっと帰宅途中につらつら考えたんだけど、twitterでつぶやくには長すぎるのでちょっと書いてみることにします。

malloc() って副作用あるの ? もちろん内部的にはあるだろうけど、外部的な振る舞いだけを見ると、有効なメモリリージョンの先頭アドレスが返ってくるだけだから、観測できないと思うんだけど。 (http://twitter.com/alohakun/status/5433639881)

Haskell で乱数作るときってどうやって参照透明にしてるんだ ? 乱数を直接作る関数は無くて、シードを元に、乱数の無限リストを作るとかなのかな。ならば、確保可能アドレスの無限リストを作れば、副作用の無い参照透明な malloc() は作れるな。 (http://twitter.com/alohakun/status/5434352613)

free や gc が入ってくると破綻するけど。 (http://twitter.com/alohakun/status/5434378848)

話がややこしくなりそうなので free や gc は考えないとするとこれは何が問題なのかということを考えたいと思います。すると問題になるのは、実はむしろ値の永続性にあるのではないかと思いました。

純粋に参照透明であるということは、次のような意味を持ちます。まず、無限リストのようなものを想定した場合、残りのメモリが現在どれくらいかという情報を保持していないといけません。これを「メモリ状態」と呼ぶことにし、仮に変数 m で代替しましょう。すると、 malloc はメモリ状態とサイズ s を受け取り、そのサイズのメモリ領域 a を返す関数ということになります。また、 a を割り当てた残りのメモリ状態 m’ も返さないといけません。

(a, m') = malloc s m

これはちょうど、リスト l の先頭から n 個の要素を取り出す splitAt 関数と似ています。

(x, rest) = splitAt n l

良さそうですよね。

複数のメモリ領域を確保したいとします。

let (a, m') = malloc s m
    (b, m'') = malloc s m'
in ...

これは問題ありません。でもこう書くことも許されます。

let (a, m') = malloc s m
    (b, m'') = malloc s m
in ...

この場合どうなるでしょうか？　どちらのmallocも引数はmとsで同じです。したがってaとb、m’とm”は同じものが返されなければなりません。これは非常に都合が悪い。簡単にヤバイことが起こりそうな気がします。

話はそれだけではありません。これはつまり、ある状態のメモリ状態mをずっと持っておくことができるということです。だったら、すごい時間がたってからそのmで再びmallocを読んだならば、まさにそのmと全く同じメモリ状態にmallocしようとしたものを返さないといけません。ようするに任意の時点でのシステムのスナップショットが必要なので、これは現実的に不可能でしょう。

Cleanという言語ではこれらの問題を「一意性型」という考え方で解決します。一意性型の値がプログラム中の複数の場所から参照されることがないことは保証されています。ようするに、同じ引数でmallocを二度呼ぶことはないし、一度どこかでとっておいたメモリ状態変数mは一度しかmallocに渡すことができません。上で挙げたような問題は、メモリ状態mが一意性があるとすれば発生しませんよね。

ではHaskellでこの問題をどう考えればいいでしょうか。ひとまず、引数となるメモリ状態を分離しましょう。ようするに malloc s とだけ書いて、この\m -> (a, m')という関数を考えるわけです。bのためのmallocも同じくmalloc sで、これも\m -> (b, m')な関数です。これだけでは何のかわりもありませんが、次に、こんなメモリ状態を受け取る関数同士を合成する関数合成を考えます。c f g = \m -> let (a, m') = f m in let (b, m'') = g m' in ((a, b), m'')。つまりc (malloc s) (malloc s)は、あるメモリ状態を受け取り、サイズsの領域ふたつを割り当ててその結果のメモリ状態を返します。こんなふうに「メモリ状態を受け取ってなんかの処理をして、その結果の値と処理後のメモリ状態を返す関数」だけがあるとして、そのメモリ状態に対する(cのような)正しい計算を行う関数合成だけを使っていれば、とりあえず問題は起こりません。

ただ、こんな関数合成は見た目がごちゃごちゃしていて汚い。ところが、このような関数合成を行ってくれる便利なライブラリがあります。それはモナドといいます。ここでは、上の関数合成cにあたる処理は「束縛」>>=と呼ばれています。あとはだいたい一緒です。これにモナドの糖衣構文を使えば、

do a <- malloc s
   b <- malloc s

と書くだけで「あるメモリ状態を受け取って、サイズsのメモリ領域aとbを割り当て、そのあとのメモリ状態を返す関数」が出来上がります。

もちろん、実際にこれを実行するにはどこかでメモリ状態を引数として与えないといけませんから、途中で問題が起こる危険性がないとしても問題を先送りしているだけですよね。もしプログラムのどこからか「現在のメモリ状態」を変数として保持できてしまうと、上で書いたように「すごい昔のメモリ状態からもう一度mallocする」ということが可能になってしまうので。そこでひとつの取り決めをします。つまり、プログラム中にmainという名前の関数があると、その関数にシステムがプログラム開始時のメモリ状態を与えてその結果の値を計算する。すると、計算途中のメモリ状態mをHaskellプログラムからアクセスする手段はなく、初期メモリ状態はどこからともなく降ってくるので、問題が解決します。

これがIOモナドと呼ばれるものの正体です。

実際にはIOモナドが扱うのはメモリの状態だけではないですが、概ねこんなふうに考えることができるのではないかと思います。Haskellに副作用が「ない」といっているのはそういうことです。

たとえば、ファイルの読み込みをHaskellではhGetContents hと書きます(hはファイルハンドル)。こういうのは「ファイルハンドルを引数として与えてファイルの中身を返す関数」だと考えがちですが、実はそうではないのです。「ファイルハンドルを引数として与えると、「その時点のコンピュータの状態を引数として受けとればその時点でのファイルの中身と、ファイルを読んだ後のコンピュータの状態とを返す関数」を返す関数」なわけです。

というわけで参照透明なmallocの例としてForein.Marshal.Allocをご覧ください。