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

この記事へのコメント
今日も雪降るのかなぁさん、
直っているはずです。リロードしてご確認を。
Dan the Typo Generator
Posted by at 2008年02月04日 16:54
> 慌てるな、ループは急に止まらない
> 実行してみると、2となるはずだ

1じゃないですかねぇ・・・
Posted by 今日も雪降るのかなぁ at 2008年02月04日 10:23