一般的なプログラミング言語の場合、関数を呼び出す前に引数が評価され、その結果が関数に渡されます。これを「正格 (strict) な評価」といいます。これに対し、引数や変数の値が必要になるまで評価を行わない方法もあります。具体的には、引数や変数を参照するときに評価が行われます。これを「遅延評価 (delayed evaluation または lazy evaluation)」といいます。
プログラミング言語では純粋な関数型言語である Haskell が遅延評価です。また、Scheme でも delay と force を使って遅延評価を行うことができます。そして、その評価結果は保存されることに注意してください。再度変数や引数を参照すると、保存されている値が返されます。
なお、値の保存 (キャッシング) をしないでよければ、クロージャを使って遅延評価を行うこともできます。Ruby はクロージャ (手続きオブジェクト) をサポートしているので、遅延評価を実装することは簡単です。今回は Ruby で遅延評価を行うクラス Delay を作ってみましょう。
Delay.new() は遅延評価を行う処理を手続きオブジェクトで受け取ります。実行はメソッド force() で行います。このとき、評価結果がインスタンスに保存されることに注意してください。本稿では、Delay のインスタンスを「遅延オブジェクト」と呼ぶことにします。再度 force() を実行すると、保存された値が返されます。
プログラムは次のようになります。
リスト : 遅延評価
class Delay
def initialize(&func)
@func = func
@flag = false
@value = false
end
def force
unless @flag
@value = @func.call
@flag = true
end
@value
end
end
遅延評価する処理はブロック引数 &func で受け取って変数 @func にセットします。@flag は false で初期化します。メソッド force() は最初に @flag をチェックします。偽の場合、@func はまだ評価されていません。@func.call() を実行して、その返り値を @value にセットし、@flag を true に書き換えます。@flag が true ならば @func は評価済みなので @value を返します。
簡単な使用例を示します。
irb> p = Delay.new {
irb> puts "oops!"
irb> 10 + 20
irb> }
=> #<Delay: ... @func=#<Proc: ... >, @flag=false, @value=false>
irb> p.force
oops!
=> 30
irb> p.force
=> 30
遅延オブジェクトを変数 p にセットします。このとき、手続きオブジェクトは実行されていません。p.force() を実行すると手続きオブジェクトが評価されるので、画面に oops! が表示されて計算結果の 30 が返されます。p.force() を再度実行すると、同じ式を再評価しないで @value に格納された値を返します。この場合 oops! は表示されません。
遅延評価の簡単な例題として「たらいまわし関数」を取り上げます。次のリストを見てください。
リスト : たらいまわし関数 def tarai(x, y, z) return y if x <= y tarai(tarai(x - 1, y, z), tarai(y - 1, z, x), tarai(z - 1, x, y)) end def tak(x, y, z) return z if x <= y tak(tak(x - 1, y, z), tak(y - 1, z, x), tak(z - 1, x, y)) end
関数 tarai() と tak() は「たらいまわし関数」といって、再帰的に定義されています。これらの関数は、引数の与え方によっては実行に時間がかかるため、Lisp などのベンチマークに利用されることがあります。tarai() は通称「竹内関数」と呼ばれていて、日本の代表的な Lisper である竹内郁雄先生によって考案されたそうです。そして、tak() は tarai() のバリエーションで、John Macarthy 先生によって作成されたそうです。たらいまわし関数が Lisp のベンチマークで使われていたことは知っていましたが、このような由緒ある関数だとは思ってもいませんでした。
それでは、さっそく実行してみましょう。実行環境は Ubunts 22.04 LTS (WSL2, Windows 10), Core i7-2670QM 2.20GHz です。
irb> require "benchmark"
=> true
irb> load "tarai.rb"
=> true
irb> Benchmark.realtime { tarai(14, 7, 0) }
=> 24.046061818999988
irb> Benchmark.realtime { tak(20, 10, 0) }
=> 3.852315803000238
実行環境 : Ruby 3.0, Ubunts 22.04 LTS (WSL2, Windows 10), Intel Core i5-6200U 2.30GHz
このように、たらいまわし関数は引数の値が小さくても実行に時間がかかります。
たらいまわし関数は遅延評価を使って高速化することができます。tarai() のプログラムを見てください。x <= y のときに y を返しますが、このとき引数 z の値は必要ありませんね。引数 z の値は x > y のときに計算するようにすれば、無駄な計算を省略することができます。ただし、tak() は遅延評価で高速化することはできません。ご注意くださいませ。
クラス Delay を使うと、たらいまわし関数は次のようになります。
リスト : Delay による遅延評価
def tarai_lazy(x, y, z)
return y if x <= y
tarai_lazy(tarai_lazy(x - 1, y, z),
tarai_lazy(y - 1, z.force, Delay.new { x }),
Delay.new { tarai_lazy(z.force - 1, x, Delay.new { y }) })
end
tarai_lazy() のプログラムを見てください。遅延評価したい処理を Delay に包んで引数 z に渡します。そして、x > y のときに引数 z を評価 (z.force()) します。すると、遅延オブジェクトが評価されて z の値を求めることができます。
たとえば、{ 0 } を Delay に渡す場合、z.force() とすると返り値は 0 になります。{ x } を渡せば、x に格納されている値が返されます。{ tarai_lazy( ... ) } を渡せば、関数 tarai_lazy() が実行されてその値が返されるわけです。
それでは実行してみましょう。
irb> Benchmark.realtime { tarai_lazy(14, 7, Delay.new {0}) }
=> 0.00015410000014526304
irb> Benchmark.realtime { tarai_lazy(140, 70, Delay.new {0}) }
=> 0.005250799999885203
tarai() の場合、遅延評価の効果はとても大きいですね。
ところで、Delay を使わなくても、手続きオブジェクト (クロージャ) だけで遅延評価を行うことができます。次のリストを見てください。
リスト : クロージャによる遅延評価
def tarai_lazy1(x, y, z)
return y if x <= y
zz = z.call
tarai_lazy1(tarai_lazy1(x - 1, y, z),
tarai_lazy1(y - 1, zz, proc { x }),
proc { tarai_lazy1(zz - 1, x, proc { y }) })
end
irb> Benchmark.realtime { tarai_lazy1(140, 70, proc {0}) }
=> 0.005714298999919265
遅延評価したい処理をクロージャに包んで引数 z に渡します。そして、x > y のときに引数 z の関数を呼び出します。すると、クロージャ内の処理が評価されて z の値を求めることができます。たとえば、proc {0} を z に渡す場合、z.call とすると返り値は 0 になります。proc {x} を渡せば、x に格納されている値が返されます。proc { tarai_lazy1( ... ) } を渡せば、tarai_lazy1() が実行されてその値が返されるわけです。ただし、クロージャでは評価結果を保存 (キャッシュ) できないことに注意してください。