AS3で遅延評価を実装してみました

as3 SICP

最近読んでいるSICPの理解度を確かめるために、AS3で遅延評価を実装してみました。

遅延評価を理解する前に、AS3の関数呼び出しが値呼び出しであることを理解しておく必要があります。

値呼び出しというのは、例えば、

function square(x) {
	return x * x;
}
function ret2() {
	trace('called ret2');
	return 2;
}
square(ret2());

というコードがあった場合、最初にret2()が呼び出されてからsquare()の呼び出しが行われます。なので、実行結果は、

called ret2

となります。

仮にAS3が値呼び出しではなく、名前呼び出しであったとしたら、ret2()が評価される前にsquare()の評価がはじまり、途中で次のような状態になります。

return ret2() *ret2();

なので、実行結果は、

called ret2
called ret2

となります。

関数の呼び出し方法は、処理系によって決まっているため処理系のサポートがない限り変更することができません。
しかし、値呼び出しの処理系でも遅延評価のテクニックを使えば名前呼び出しと同じ順序で評価させることができます。

具体的な方法は、五十嵐先生の講義資料を参考にしました。

以下は、遅延評価の説明部分の引用です。

関数定義において，本体中でパラメータのいくつかを使用しないことがありえる．このとき，呼出し側で対応する実引数を評価するのは無駄である．実引数の評価が止まらない場合には，問題ですらある．

mini Schemeのように，関数が第一級の値である場合には，無駄な引数を評価しないために，パラメータ無しの関数として渡し，関数内部で使うときに初めて関数適用を行って引数の評価を行うというプログラミングで，この問題を避けることができる．このように，評価を遅らせるために用いられるパラメータ無しの関数を thunk と呼び，thunk を構成・評価することを，それぞれ freezing, thawing と呼ぶ．

ということで、schemeで遅延評価の実装方法が説明してあります。

(let ((p (lambda (x y) (* 2 x))))
   (p (+ 2 4) (fact 150)))

のようなプログラムを，機械的に実引数を freeze し，パラメータが使われているところで thaw するようにして，以下のように

(let ((p (lambda (x y) (* 2 (x)))))
   (p (lambda () (+ 2 4)) (lambda () (fact 150))))

のように書き換えることができる．(ここでは fact は階乗を計算するプリミティブと考えよ．)これにより，結果が使われないが時間のかかる階乗の計算をせずに，プログラムが実行される．

schemeに慣れていないと分かりづらいですが、要するに引数を匿名関数でくくって、関数内では必要になったときに引数の関数を呼び出し値を取得すれば遅延評価になるということです。

このコードをactionscriptで書くと次のようになります。

まずはfactの実装。

function fact(x) {
	if ( x == 0 ) {
		return 1;
	}
	else {
		return x * fact(x - 1);
	}
}

関数pの遅延評価なしバージョン

var p = function (x, y) {
	return 2 * x;
};
p(2 + 4, fact(150));

このバージョンだと、fact(150)の結果は使われないのに評価は行われます。

こちらが、遅延評価ありバージョン

var p_lazy = function(x, y) {
	return 2 * x(); // 引数を関数適用し、値を評価する(thawing)
};
p_lazy(function() { return 2+4;}, function() { return fact(150); }); // 引数を匿名関数で包む(freezing)

このバージョンでは、関数p_lazy()の第２引数は無視されてfact(150)は評価されません。

ここまで読むと、「で、これが何の役に立つの？」と疑問に思った人も多いと思います。
正直私も煩雑なだけでほんとに役立つのか？と思ってしまいました。

とは言いながらも色々考えてみた結果、
遅延評価が効果を発揮するのは、下記の２つの条件を満たしている場合のように思いました。

  1. 引数の値が関数内部で使われるかどうかが状態によって変化する
  2. 引数の値の取得処理に時間がかかる（計算量が多いなどの理由により）

具体的な例は、SICPを読み進めれば出てくるのだろうと思いますが今はわかりません。。。

おまけ

SICP問題1.5の復習

AS3は値呼び出しの処理系なので以下のコードを実行すると、関数testが呼び出される前に関数pが呼び出されてスタックオーバーフローになります。

function p() { p(); }

function test(x, y) {
	if ( x == 0 ) {
		return 0;
	}
	else {
		return y;
	}
}

test(0, p());

で、この問題を遅延評価に書き直すと以下のようになります。

function p() { p(); }

function test(x, y) {
	if ( x() == 0 ) {
		return 0;
	}
	else {
		return y();
	}
}

test(function() { return 0;}, function() { p(); });

これだとスタックオーバーフローが起こらないで終了します。

参考