遅延評価とはなにか、そしてモナドの話

# TL;DR

- 関数は呼び出されるまで評価されない、というのは当然の性質だ。
- 正格評価を行う言語でも、クロージャーがあれば遅延評価の挙動を模倣できる。
- 遅延評価という言葉の意味を拡大して使うのは危険なのではないか。
- 様々な計算効果を持つプログラムは、クライスリ圏の射と見なせる。
- クライスリ圏を作るためのものがモナドだ。
- 計算効果を自由に組み合わせられるHaskellは「究極の手続き型言語」だ。
- モナドは（普通の意味では）遅延評価ではない。

# 事の発端

[「純粋関数型」 ＆「副作用」というトリッキーワードについて想うこと『裸の王様』](http://qiita.com/kenokabe/items/0dfe134428665d66d757)を読みました。

>> じっと時を待ちます。この実装では、アクションとはこういう引数がなくて実行の時を今か今かと待ち構えている関数のことです。
>> でもまだその時ではありません。put に渡す文字列が来るまでじっと待ちます。雌伏のときです。
>> しかしあくまで結びつけるだけで、何もしません。ひたすら時を待ちます。
>> このアクションを起動します。時が来た！結び付けられたアクションが順番に起動し始めます。

> これはどこからどう読んでも、遅延評価のことであり、

と、最後に「時が来た」時に「アクションが順番に起動し始める」ことを、遅延評価と呼んでいます。

モナドは、遅延評価なのでしょうか？ 考えてみます。

# 評価戦略

「アクションを結びつけ、時が来たら順番に起動する」機構は、関数を使って実現しています。「関数は呼び出すまで評価されることがない」というのは、**遅延評価でない正格評価の言語についても当然成り立っている性質**です。

問題なのは、「関数の評価がいつ行われるのか?」ではなく、「関数の引数として渡される_値_の評価がいつ行われるのか?」ということで、その部分の差異が評価戦略の差となります。

関数の呼出しより前に引数の値を評価し、その値を関数に渡すことを_値呼び_と呼び、これはJavaScriptやOCamlなどの言語が採用している戦略です。一方、関数の呼出し時には評価を行わず、関数から引数が使われた時に、使われる度に評価を行う場合、これは_名前呼び_になります。初めて使われた時だけ評価し、その後は評価済みの値を用いるのであれば、それは_必要呼び_です。

遅延評価とは、名前呼びあるいは必要呼びを行う評価戦略のことを言います。英語だと、lazy evaluationと区別して名前呼びはdelayed evaluationと呼び分けることがあるようです。([遅延評価ってなんなのさ - ぐるぐる～](http://bleis-tift.hatenablog.com/entry/20120303/1330785641))

値呼びを行う言語であっても、値を直接渡さずに、値を返すような関数を渡すようにしておけば、関数呼出し時ではなく、値を使いたいときに評価させることは可能です。私は以前、そのような手法についての記事を書きました。

[CoffeeScriptで遅延評価（もどき）を実装しよう](http://mandel59.hateblo.jp/entry/2013/02/10/161445) 

これは先に述べたように、「関数は呼び出すまで評価されることがない」という、値呼びを行う言語でも成り立っている性質を用いて、名前呼びや必要呼びの挙動を真似ているのです。そのため、この記事では「もどき」という表現を使いました。

# 「遅延評価」の用例の混乱

Schemeは`delay`と`force`という評価を遅延させるためのプリミティブがあり、これがDelayed evaluationであると説明する文章があります。

[21.1.  Delayed evaluation in Scheme](http://people.cs.aau.dk/~normark/prog3-03/html/notes/eval-order_themes-delay-stream-section.html#eval-order_delay-force_title_1)
[9.3 Delayed Evaluation](http://download.plt-scheme.org/doc/html/reference/Delayed_Evaluation.html)

`(delay e)`で式`e`の評価を遅延させることを指定し、`(force p)`で_プロミス promise_`p`の評価を強制しています。これは遅延評価でしょうか? 先ほどの“遅延評価もどき”も、`(-> e)`で式`e`の評価を遅延させ、`p()`でプロミス（単なる関数ですけど）の評価を行うというのと、同じような形をしています。`e`という式を関数の引数にしているのではなく、`(delay e)`という式を評価したプロミスを関数に渡しているわけです。こういうプロミスを使った遅延評価は（遅延評価を、名前呼びや必要呼びのエイリアスだと考えている人にとっては気持ち悪い呼び方でしょうけれども）「値呼び、だけど遅延評価」と呼べるかもしれません。

しかし、“遅延評価もどき”に留まらず、遅延評価の性質を用いて実装された_遅延データ構造_のことも遅延評価と呼ぶような用法も多く、混乱が起きているという現状があります。<small>（遅延データ構造という用語を他人が使っているのを私は見たことがないのですが、検索したところ、lazy data-structuresという語の用例は一応あるようです。ここでは、プロミスや_サンク thunk_を含んだデータ構造ぐらいの意味だと思って下さい。）</small>

[遅延評価いうなキャンペーンとかどうか - ぐるぐる～](http://bleis-tift.hatenablog.com/entry/20130102/1357062031)

遅延データ構造も遅延評価と呼んでしまってよいのでしょうか? （プロミスも最も単純な形の遅延データ構造とも考えられますね。）これまで遅延評価と呼ぶのは、元の意味からのずれが大きく、かなり厳しいように思います。

このように、遅延評価の意味合いは広がっていってしまう可能性があります。言葉を使う前に、いちいち自分の言う「遅延評価」とはこういう意味なんだぞ、と言っておかないと危ないと思います。

# モナドって何?

[モナド (プログラミング)](http://ja.wikipedia.org/wiki/%E3%83%A2%E3%83%8A%E3%83%89_%28%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%29)を読んで下さい。読まないでいいように肝心の部分だけ引っ張ってくると、**プログラムは集合写像ではない**。では、プログラムとはなにか? それは**クライスリ圏 Kleisli category の射**である。そのように考えれば、副作用、例外処理、非決定計算などの_計算効果 computational effects_ がうまく説明できる。そういう主張がなされたということです。

今まで、「プログラムは関数だ」と思ってプログラムを書いてきましたよね。違うんです。クライスリ圏の射だって言うんです。C言語にもJavaScriptにもありますよね、関数。今度から、C言語の・JavaScriptのクライスリ圏の射って呼んでくださいね。（もちろん冗談ですけど。）聞きなれないけど、今まで普通に書いてきたプログラムは、関数（集合写像）よりもクライスリ圏の射だって考えた方がいいよっていう、それだけのことなんです。「クライスリ圏の射」の厳密な意味を知りたかったら圏論を勉強しないといけませんけど、使うだけなら勉強する必要はないです。単に、聞きなれない名前になったってだけですからね。

Haskellの関数は、もっと純粋な関数に近いものです。無限ループとか`undefined`とかあって、完全な関数でもないんですけれども、環境に対してインタラクションするとか、非決定計算を行うとか、そういう計算効果は持っていません。じゃあHaskellでも非決定計算だとか副作用だとかいう計算効果を実現したいけど、どうすればいいの? **そこでモナドが使えるんです。** リストモナドを使えば、非決定計算ができます。IOモナドを使えば、実環境との相互作用（入出力）付きの計算ができます。モナドとクライスリ圏の関係とか詳しく解説しませんけど、`m`がモナドだったら`a -> m b`がクライスリ圏の射になる、ぐらいに覚えとけばいいんじゃないですかね。

`return :: Monad m => a -> m a`を使えば、普通の（Haskellの）関数を、クライスリ圏の射にすることができます。関数`f :: a -> b`をクライスリケンの射にするには、`return`と合成して`return . f :: Monad m => a -> m b`とすればいいです。Haskellのモナドのスゴイところは、これがどんなクライスリ圏の射であるとは指定しなくていいってところです。多相によって、どんなクライスリ圏の射にもなります。（厳密には嘘です。HaskellのMonadクラスが表せるようなモナドから作れるクライスリ圏の射だけですけど。）

JavaScriptの関数がクライスリ圏の射と見なせるからといって、JavaScriptの関数が非決定計算を行うようにはなりません。一方、Haskellの関数は非決定計算どころか他の計算効果も持ちませんけれども、モナドやクライスリ圏を扱う仕組みを持っているので、好きな計算効果を追加することができます。計算効果の組み合わせごとに新しいモナドを作るのは大変ですから、モナド変換子というものがあって、これを使うと複数の計算効果を組み合わせたモナドが作れます。

計算効果を好きなように組み合わせられる。それが「Haskellは究極の手続き型言語」と言われることのある理由です。手続きって、計算効果だけで仕事をするクライスリ圏の射なんですよね。（Haskellの型で書けば`(Monad m) => a -> m ()`です。）そして、具体的なモナドを指定せずにジェネリックにしておけば、`forM_ :: Monad m => [a] -> (a -> m b) -> m ()`のように、どんな計算効果の組み合わせに対しても使える“制御構造”をライブラリで提供できます。

# モナドは（普通の意味では）遅延評価ではない。

モナドからクライスリ圏を作ることができます。計算効果を持つプログラムはクライスリ圏の射としてうまく表現できます。

評価の遅延は、関数の持つ性質でした。もっと言えば、プログラムの持つ性質です。プログラムは、呼び出すまで、実行されない。それだけのことです。それと「遅延評価」という用語が指す内容は、普通は違います。モナドからクライスリ圏を作り、クライスリ圏の射がプログラムだからといって、そのプログラムが呼び出されるまで実行されないことを、遅延評価と呼ぶのは、やはり混乱を招くのではないでしょうか。