一般的なプログラミング言語の場合、関数を呼び出す前に引数が評価され、その結果が関数に渡されます。これを「正格 (strict) な評価」といいます。これに対し、引数や変数の値が必要になるまで評価を行わない方法もあります。具体的には、引数や引数を参照するときに評価が行われます。これを「遅延評価 (delayed evaluation または lazy evaluation)」といいます。
プログラミング言語では関数型言語の Haskell が遅延評価です。また、Scheme でも delay と force を使って遅延評価を行うことができます。そして、その評価結果は保存されることに注意してください。再度変数や引数を参照すると、保存されている値が返されます。
なお、値の保存 (キャッシング) をしないでよければ、クロージャ (ラムダ式) を使って遅延評価を行うこともできます。C# はクロージャをサポートしているので、遅延評価を実装することは簡単です。今回は C# で遅延評価を行うクラス Delay<T> を作ってみましょう。
Delay<T> のコンストラクタは遅延評価を行う処理をラムダ式で受け取ります。実行はメソッド Force() で行います。このとき、評価結果がインスタンスに保存されることに注意してください。本稿では、Delay<T> のインスタンスを「遅延オブジェクト」と呼ぶことにします。再度 Force() を実行すると、保存された値が返されます。
プログラムは次のようになります。
リスト : 遅延評価 (delay.csx)
class Delay<T> {
T Result { set; get; }
bool Flag { set; get; }
Func<T> Fn { get; }
public Delay(Func<T> func) {
Result = default(T);
Flag = false;
Fn = func;
}
public T Force() {
if (!Flag) {
Result = Fn();
Flag = true;
}
return Result;
}
}
遅延評価する処理は引数無しのラムダ式で受け取ってフィールド Fn にセットします。引数なしで返り値のデータ型が T の関数は Func<T> で表すことができます。Flag は false で、Result は default(T) で初期化します。
メソッド Force() は最初に Flag をチェックします。偽の場合、Fn はまだ評価されていません。Fn() を実行して、その返り値を Result にセットし、Flag を true に書き換えます。Flag が true ならば Fn は評価済みなので Result を返します。
簡単な使用例を示します。
リスト : 簡単なテスト (delaytest.csx)
#load "delay.csx"
int foo(int a, int b) {
Console.Write("foo!! ");
return a + b;
}
void test() {
var p = new Delay<int>(() => foo(10, 20));
Console.WriteLine("{0}", p.Force());
Console.WriteLine("{0}", p.Force());
}
// 実行
test();
$ dotnet script delaytest.csx foo!! 30 30
遅延オブジェクトを変数 p にセットします。このとき、ラムダ式は評価 [*1] されていません。p.Force() を実行するとラムダ式が評価されるので、画面に foo!! が表示されて計算結果の 30 が返されます。p.Force() を再度実行すると、同じ式を再評価しないで Result に格納された値を返します。この場合 foo!! は表示されません。
遅延評価の簡単な例題として「たらいまわし関数」を取り上げます。次のリストを見てください。
リスト : たらいまわし関数 (tarai.csx)
int tarai(int x, int y, int z) {
if (x <= y)
return y;
else
return tarai(tarai(x - 1, y, z),
tarai(y - 1, z, x),
tarai(z - 1, x, y));
}
int tak(int x, int y, int z) {
if (x <= y)
return z;
else
return tak(tak(x - 1, y, z),
tak(y - 1, z, x),
tak(z - 1, x, y));
}
void test() {
DateTime s = DateTime.Now;
Console.WriteLine("{0}", tarai(14, 7, 0));
DateTime e = DateTime.Now;
Console.WriteLine("{0}", e - s);
s = DateTime.Now;
Console.WriteLine("{0}", tak(22, 11, 0));
e = DateTime.Now;
Console.WriteLine("{0}", e - s);
}
// 実行
test();
関数 tarai(), tak() は「たらいまわし関数」といって、再帰的に定義されています。これらの関数は、引数の与え方によっては実行に時間がかかるため、Lisp などのベンチマークに利用されることがあります。tarai() は通称「竹内関数」と呼ばれていて、日本の代表的な Lisper である竹内郁雄先生によって考案されたそうです。そして、tak() は tarai() のバリエーションで、John Macarthy 先生によって作成されたそうです。たらいまわし関数が Lisp のベンチマークで使われていたことは知っていましたが、このような由緒ある関数だとは思ってもいませんでした。
それでは、さっそく実行してみましょう。実行環境は Ubunts 22.04 (WSL2), Intel Core i5-6200U 2.30GHz です。
$ dotnet script tarai.csx 14 00:00:03.1759029 11 00:00:03.1384750 $ dotnet script -c Release tarai.csx 14 00:00:01.0677794 11 00:00:01.1115052
このように、たらいまわし関数は引数の値が小さくても実行に時間がかかります。
たらいまわし関数は遅延評価を使って高速化することができます。tarai() のプログラムを見てください。x <= y のときに y を返しますが、このとき引数 z の値は必要ありませんね。引数 z の値は x > y のときに計算するようにすれば、無駄な計算を省略することができます。ただし、tak() は遅延評価で高速化することはできません。ご注意くださいませ。
クラス Delay<T> を使うと、たらいまわし関数は次のようになります。
リスト : Delay<T> による遅延評価 (tarai1.csx)
#load "delay.csx"
int TaraiLazy(int x, int y, Delay<int> z) {
if (x <= y) {
return y;
} else {
int zz = z.Force();
return TaraiLazy(TaraiLazy(x - 1, y, z),
TaraiLazy(y - 1, zz, new Delay<int>(() => x)),
new Delay<int>(() => TaraiLazy(zz - 1, x, new Delay<int>(() => y))));
}
}
void test() {
DateTime s = DateTime.Now;
Console.WriteLine("{0}", TaraiLazy(140, 70, new Delay<int>(() => 0)));
DateTime e = DateTime.Now;
Console.WriteLine("{0}", e - s);
}
// 実行
test();
TaraiLazy() のプログラムを見てください。遅延評価したい処理を Delay に包んで引数 z に渡します。そして、x > y のときに引数 z を評価 (z.Force()) します。すると、遅延オブジェクトのラムダ式が実行されて z の値を求めることができます。たとえば、() => 0 を Delay に渡す場合、z.Force() とすると返り値は 0 になります。() => x を渡せば、x に格納されている値が返されます。() => TaraiLazy( ... ) を渡せば、関数 TaraiLazy() が実行されてその値が返されるわけです。
それでは実行してみましょう。
$ dotnet script tarai1.csx 140 00:00:00.2744634 $ dotnet script -c Release tarai1.csx 140 00:00:00.2695864
tarai() の場合、遅延評価の効果はとても大きいですね。
ところで、Delay<T> を使わなくても、ラムダ式 (クロージャ) だけで遅延評価を行うことができます。次のリストを見てください。
リスト : クロージャによる遅延評価 (tarai2.csx)
int TaraiLazy1(int x, int y, Func<int> z) {
if (x <= y) {
return y;
} else {
int zz = z();
return TaraiLazy1(TaraiLazy1(x - 1, y, z),
TaraiLazy1(y - 1, zz, () => x),
() => TaraiLazy1(zz - 1, x, () => y));
}
}
void test() {
DateTime s = DateTime.Now;
Console.WriteLine("{0}", TaraiLazy1(140, 70, () => 0));
DateTime e = DateTime.Now;
Console.WriteLine("{0}", e - s);
}
// 実行
test();
遅延評価したい処理をクロージャに包んで引数 z に渡します。そして、x > y のときに引数 z の関数を呼び出します。すると、クロージャ内の処理が評価されて z の値を求めることができます。たとえば、() => 0 を z に渡す場合、z() とすると返り値は 0 になります。() => x を渡せば、x に格納されている値が返されます。() => TaraiLazy1( ... ) を渡せば、TaraiLazy1() が実行されてその値が返されるわけです。ただし、クロージャでは評価結果を保存 (キャッシュ) できないことに注意してください。
$ dotnet script tarai2.csx 140 00:00:00.2695692 $ dotnet script -c Release tarai2.csx 140 00:00:00.2843250