Haskell の遅延評価ってこういうことじゃないのかなぁ
C とか Java だと 「関数呼び出し*1」 って言いますけど、Haskell だと 「関数適用*2」 って言うんですよね。つまり Haskell は Java とかの関数呼び出しとは全く異なる機構だって言ってもいいんじゃないかと思うわけです。*3
実際、Haskell の関数適用は、C のマクロに似ていたりしまして、ためしに
#define hoge(x, y) ((x) + 1) 〜 int result = hoge(1 + 2, 3 * 4);
というプログラムをプリプロセッサに食わせると
int result = ((1 + 2) + 1)
ってなりますよね。3 * 4 がざっくり消去されるのを見ると「ああ、遅延されてるな」とか感じてしまうわけです。*4
ところで、書き換えに１つだけ規則がありまして、
int result = hoge(123, hoge(456, 789));
を”１回”書き換えたときに
int result = hoge(123, ((456) + 1));
とするのか
int result = ((123) + 1);
とするのかで意味が変わっちゃうことがあります。前者を最内簡約、後者を最外簡約と言ったりしますが、Haskell では原則として後者を採用しています。外側を先に書き換えるということは、内側つまり引数が遅延するということですよね (^-^;;
「必要になるまで評価が遅延される」 って考えると 「いつ必要になるのか」 を考える必要があってだいぶ難しくなりますが、これは Haskell の２つの性質から導き出される結果だと考えればわかりやすくて、
- Haskell の関数適用は“ソースコード≒項”の書き換え(最外簡約)
- つまり、不要な項は書き換え中に消去される
- Haskell には副作用がない
- いつ値を計算しても、常に値は同じになる
- つまり、いつ計算しても良い
以上から、書き換えて最後まで残った項が”必要な項”で、その項を最後に計算したものが、最終的な式の値です。
ただ、”必要な項”はこれだけじゃなくて、例えば式の値によって項書き換えパターンそのものを変えるときなどには、書き換え中に式の値が必要になります。具体的にはこんな感じ。
もし cond が true ならば、expr01 に書き換える もし cond が false ならば、expr02 に書き換える
見ての通り、if-then-else の条件式です。他にもパターンマッチングの条件式も該当します。
- 「必要な式」とは、最後まで残った式か、あるいは書き換え途中に値が必要な式*5
この条件を自力で見つけた id:amachang はやっぱり天才だなぁ……と思うのですよ。
さて、以上の知識から試しに
fact n = if n == 1 then 1 else n * fact (n - 1)
のとき
fact 3
の書き換えを行ってみます。
変換ルールを予め整理しておきますと、
- fact n を
- if n == 1 then 1 else n * fact (n - 1) に書き換え
- if cond then expr1 else expr2 を
- cond を評価した結果が true ならば expr1 に書き換え
- cond を評価した結果が false ならば expr2 に書き換え
それではどうぞ。書き換えは１ステップずつ。意味が変わらないように適宜 ( 〜 ) が挿入されています。
fact 3
if 3 == 1 then 1 else 3 * fact (3 - 1)
3 * fact (3 - 1)
3 * (if (3 - 1) == 1 then 1 else (3 - 1) * fact ((3 - 1) - 1))
3 * ((3 - 1) * fact ((3 - 1) - 1))
3 * ((3 - 1) * (if ((3 - 1) - 1) == 1 then 1 else ((3 - 1) - 1) * fact (((3 - 1) - 1) - 1)))
3 * ((3 - 1) * (1))
これで書き換えが終了したので、3 * ( (3 - 1) * (1) ) ) を計算した結果の 6 が fact 3 の結果になります。*6
ということで、Haskell の遅延評価は積極的にやっているものではなく、Haskell の関数適用ルールに従うと自然にそうなってしまうという話でした。
実はこの項書き換えで Monad も説明できそうな気がするんですが勉強不足です。ごめんなさい。
こう考えると、つまり C のマクロを拡張してしまえば Haskell Hackathon は何とかなっちゃうんじゃないかと思ってたりします。再帰は…… Y コンビネータを使えば何とかなるかなぁｗ
ただ、実行時にせこせこ書き換えたり同じ式を何度も評価したりするのはめっちゃ非効率なので、これを何とか効率的にできないかとか色々考えるのが処理系製作者さんの腕の見せ所なわけです。
