2008年02月04日 07:00 [Edit]
λ Calculus - まずは遅延評価から
うーん、まずY Combinatorというのはおじさんたちが悪かったかな。ギター習いたてでいきなりFの音を出すようなもんだから。
まずは、遅延評価についてきちんとおさらいしておこう。
慌てるな、ループは急に止まらない
まずは、以下の式を考えてみる。
実行してみると、1となるはずだ。しかしここで重要なのはこのことじゃない。後ろの1+1が実行されるかだ。このことはどうやって確認したらよいだろうか。以下のようにしてみればいいはずだ。
見てのとおり、ELSEは2になっている。式を見れば、この関数を実行するのに、1+1は全く必要ないにも関わらずそうなってしまう。これが、先行評価(eager evaluation)。とにかく式を見つけたら、手当たり次第評価しては値に置き換えていくというので、言語の実装もしやすいし、プログラマーにも直感的にわかりやすい。よく使われる言語のほとんどはこちらを採用している。
ところが、これだとこんなことをしたい場合に困ってしまう。
var myif = function(_cond, _then, _else){
return _cond ? _then : _else;
};
こういう定義だと、一応
myif(true, 1, 1+1);
のようなものは動くけど、
function fact(n){
return myif(n <= 1, 1, n * fact(n-1));
};
のようなものは動かない。なぜなら、n * fact(n-1)は問答無用で実行されてしまうので、無限ループになってしまうからだ。これは困った。
[あとで評価する]一番簡単な方法
しかし、amachangも気がついているように、先行評価する言語でも、クロージャーが使えるなら、それを利用して評価は後回しにできる。遅延評価(lazy evaluation)したいものを関数でくるんでしまえばいいのだ。こんな感じに。
var todo = function(){ return 1 };
値を取り出したいときは、そのクロージャーを評価すればいい。JavaScriptなら、尻に()をつけるだけ。
todo(); // 1.
厳密には、これは遅延評価ではない。クロージャーを作る部分というのは先行評価されている。しかしクロージャーを作ったら、そのクロージャーはすぐに返ってくる。「評価された値」はクロージャーそのものなのだ。中身はそのクロージャーを評価するまでおあずけってことに出来るわけだ。
以上を踏まえて、myifとfactをちょっとだけ書き換えて、実際に動くかどうか確かめてみよう。
こんどはきちんと動いた。
で、遅延評価って一体何がいいの?
ふつうの、先行評価型言語では、条件分岐というのは特別な構文で、関数ではない。理由は今まで見て来た通り。片っ端から評価してたらヤバい場合があるからだ。
ところが、遅延評価型言語では、条件分岐すらただの関数として実現できる。これならマクロすら不要である。
これって凄くない?
次は、データを関数で表現してみます。
Dan the Lazy Evaluator
Further Reading:
- 小飼弾/山下伸夫監修
- 動かしながら楽しく学ぶ 関数型言語Haskell入門
- WEB+DB PRESS vol.34 PP 80-88,
- 青木峰郎
- ふつうのHaskellプログラミング
- 404 Blog Not Found
- :λ萌え - たらいを後回し
この記事へのトラックバックURL
> 実行してみると、2となるはずだ
1じゃないですかねぇ・・・
直っているはずです。リロードしてご確認を。
Dan the Typo Generator
