一般的なプログラミング言語の場合、関数を呼び出す前に引数が評価され、その結果が関数に渡されます。これを「正格 (strict) な評価」といいます。これに対し、引数や変数の値が必要になるまで評価を行わない方法もあります。具体的には、引数や引数を参照するときに評価が行われます。これを「遅延評価 (delayed evaluation または lazy evaluation)」といいます。
プログラミング言語では純粋な関数型言語である Haskell が遅延評価です。また、Scheme でも delay と force を使って遅延評価を行うことができます。そして、その評価結果は保存されることに注意してください。再度変数や引数を参照すると、保存されている値が返されます。
なお、値の保存 (キャッシング) をしないでよければ、クロージャ (ラムダ式) を使って遅延評価を行うこともできます。Java はラムダ式をサポートしているので、遅延評価を実装することは簡単です。今回は Java で遅延評価を行うクラス Delay<T> を作ってみましょう。
Delay<T> のコンストラクタは遅延評価を行う処理をラムダ式で受け取ります。実行はメソッド force() で行います。このとき、評価結果がインスタンスに保存されることに注意してください。本稿では、Delay<T> のインスタンスを「遅延オブジェクト」と呼ぶことにします。再度 force() を実行すると、保存された値が返されます。
プログラムは次のようになります。
リスト : 遅延評価 (Delay.java)
package immutable;
import java.util.function.Supplier;
public final class Delay<T> {
private T item;
private boolean flag;
final private Supplier<T> func;
private Delay(Supplier<T> f) {
flag = false;
func = f;
}
public static <T> Delay<T> delay(Supplier<T> f) {
return new Delay<T>(f);
}
public T force() {
if (!flag) {
item = func.get();
flag = true;
}
return item;
}
}
Delay<T> はパッケージ immutable の中に定義します。遅延オブジェクトはスタティックメソッド delay() で生成します。遅延評価する処理は関数型インターフェース Supplier<T> に適合するラムダ式で、フィールド変数 func にセットします。flag は false で初期化します。
メソッド force() は最初に flag をチェックします。偽の場合、func はまだ評価されていません。func.get() を実行して、その返り値を item にセットし、flag を true に書き換えます。flag が true ならば func は評価済みなので item を返します。
簡単な使用例を示します。
jshell> import immutable.Delay
jshell> var a = Delay.delay(() -> {System.out.println("oops!!"); return 10 + 20;})
a ==> immutable.Delay@25f38edc
jshell> a.force();
oops!!
$3 ==> 30
jshell> a.force();
$4 ==> 30
遅延オブジェクトを変数 a にセットします。このとき、ラムダ式は評価 [*1] されません。a.force() を実行するとラムダ式が評価されるので、画面に oops!! が表示されて計算結果の 30 が返されます。a.force() を再度実行すると、同じ式を再評価しないで item に格納された値を返します。この場合 oops!! は表示されません。
遅延評価の簡単な例題として「たらいまわし関数」を取り上げます。次のリストを見てください。
リスト : たらいまわし関数
public class Tarai {
static 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));
}
static 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));
}
public static void main(String[] args) {
long start = System.currentTimeMillis();
System.out.println(tarai(14, 7, 0));
long end = System.currentTimeMillis();
System.out.println((end - start) + "ms");
start = System.currentTimeMillis();
System.out.println(tak(22, 11, 0));
end = System.currentTimeMillis();
System.out.println((end - start) + "ms");
}
}
メソッド tarai() と tak() は「たらいまわし関数」といって、再帰的に定義されています。これらの関数は、引数の与え方によっては実行に時間がかかるため、Lisp などのベンチマークに利用されることがあります。tarai() は通称「竹内関数」と呼ばれていて、日本の代表的な Lisper である竹内郁雄先生によって考案されたそうです。そして、tak() は tarai() のバリエーションで、John Macarthy 先生によって作成されたそうです。たらいまわし関数が Lisp のベンチマークで使われていたことは知っていましたが、このような由緒ある関数だとは思ってもいませんでした。
それでは、さっそく実行してみましょう。実行環境は Ubunts 22.04 (WSL2), Intel Core i5-6200U 2.30GHz です。
$ javac Tarai.java $ java Tarai 14 975ms 11 1160ms
このように、たらいまわし関数は引数の値が小さくても実行に時間がかかります。
たらいまわし関数は遅延評価を使って高速化することができます。tarai() のプログラムを見てください。x <= y のときに y を返しますが、このとき引数 z の値は必要ありませんね。引数 z の値は x > y のときに計算するようにすれば、無駄な計算を省略することができます。ただし、tak() は遅延評価で高速化することはできません。ご注意くださいませ。
クラス Delay<T> を使うと、たらいまわし関数は次のようになります。
リスト : Delay<T> による遅延評価
static int taraiLazy(int x, int y, Delay<Integer> z) {
if (x <= y) {
return y;
} else {
int zz = z.force();
return taraiLazy(taraiLazy(x - 1, y, z),
taraiLazy(y - 1, zz, Delay.delay(() -> x)),
Delay.delay(() -> taraiLazy(zz - 1, x, Delay.delay(() -> y))));
}
}
taraiLazy() のプログラムを見てください。遅延評価したい処理を Delay に包んで引数 z に渡します。そして、x > y のときに引数 z を評価 (z.force()) します。すると、遅延オブジェクトのラムダ式が実行されて z の値を求めることができます。
たとえば、() -> 0 を Delay に渡す場合、z.force() とすると返り値は 0 になります。() -> x を渡せば、x に格納されている値が返されます。() -> taraiLazy( ... ) を渡せば、関数 taraiLazy() が実行されてその値が返されるわけです。
それでは実行してみましょう。
taraiLazy(1000, 500, Delay.delay(() -> 0)) => 1000 54ms
tarai() の場合、遅延評価の効果はとても大きいですね。
ところで、Delay<T> を使わなくても、ラムダ式 (クロージャ) だけで遅延評価を行うことができます。次のリストを見てください。
リスト : クロージャによる遅延評価
static int taraiLazy1(int x, int y, Supplier<Integer> z) {
if (x <= y) {
return y;
} else {
int zz = z.get();
return taraiLazy1(taraiLazy1(x - 1, y, z),
taraiLazy1(y - 1, zz, () -> x),
() -> taraiLazy1(zz - 1, x, () -> y));
}
}
遅延評価したい処理をクロージャに包んで引数 z に渡します。そして、x > y のときに引数 z の関数を呼び出します。すると、クロージャ内の処理が評価されて z の値を求めることができます。たとえば、() -> 0 を z に渡す場合、z() とすると返り値は 0 になります。() -> x を渡せば、x に格納されている値が返されます。() -> taraiLazy1( ... ) を渡せば、taraiLazy1() が実行されてその値が返されるわけです。ただし、クロージャでは評価結果を保存 (キャッシュ) できないことに注意してください。
//
// Delay.java : 遅延評価
//
// Copyright (C) 2016-2021 Makoto Hiroi
//
package immutable;
import java.util.function.Supplier;
public final class Delay<T> {
private T item;
private boolean flag;
final private Supplier<T> func;
private Delay(Supplier<T> f) {
flag = false;
func = f;
}
public static <T> Delay<T> delay(Supplier<T> f) {
return new Delay<T>(f);
}
public T force() {
if (!flag) {
item = func.get();
flag = true;
}
return item;
}
}