一般的なプログラミング言語の場合、関数を呼び出す前に引数が評価され、その結果が関数に渡されます。これを「正格 (strict) な評価」といいます。これに対し、引数や変数の値が必要になるまで評価を行わない方法もあります。具体的には、引数や引数を参照するときに評価が行われます。これを「遅延評価 (delayed evaluation または lazy evaluation)」といいます。
プログラミング言語では関数型言語の Haskell が遅延評価です。F# は「lazy 式 (遅延式)」を使って式を遅延評価することができます。そして、その評価結果は保存されることに注意してください。再度変数や引数を参照すると、保存されている値が返されます。今回は F# の遅延評価について簡単に説明します。
lazy 式の構文を示します。
lazy expression => 遅延オブジェクト
lazy 式は式 expression を評価しないで、クラス Lazy<'T> のインスタンスを返します。本稿では、Lazy<'T> のインスタンスを「遅延オブジェクト」と呼ぶことにします。評価はメソッド Force() で行います。このとき、評価結果が遅延オブジェクトに保存されることに注意してください。再度 Force() を評価すると、保存された値が返されます。
簡単な使用例を示します。
> let a = lazy (printfn "oops"; 2 + 3);; val a: Lazy<int> = Value is not created. > a.Force();; oops val it: int = 5 > a.Force();; val it: int = 5
遅延オブジェクトを変数 a にセットします。このとき、引数の式はまだ評価されていません。a.Force() を評価すると、lazy 式に渡された式が評価されるので、画面に oops が表示されて計算結果の 30 が返されます。a.Force() を再度評価すると、同じ式を再評価しないで遅延オブジェクトに保存された値を返します。この場合 oops は表示されません。
遅延評価の簡単な例題として「たらいまわし関数」を取り上げます。次のリストを見てください。
リスト : たらいまわし関数 let rec tarai x y z = if x <= y then y else tarai (tarai (x - 1) y z) (tarai (y - 1) z x) (tarai (z - 1) x y) let rec tak x y z = if x <= y then z else tak (tak (x - 1) y z) (tak (y - 1) z x) (tak (z - 1) x y)
関数 tarai(), tak() は「たらいまわし関数」といって、再帰的に定義されています。これらの関数は、引数の与え方によっては実行に時間がかかるため、Lisp などのベンチマークに利用されることがあります。tarai() は通称「竹内関数」と呼ばれていて、日本の代表的な Lisper である竹内郁雄先生によって考案されたそうです。tak() は tarai() のバリエーションで、John Macarthy 先生によって作成されたそうです。たらいまわし関数が Lisp のベンチマークで使われていたことは知っていましたが、このような由緒ある関数だとは思ってもいませんでした。
それでは、さっそく実行してみましょう。実行環境は Ubunts 22.04 (WSL2), Intel Core i5-6200U 2.30GHz です。
> let rec tarai x y z = - if x <= y then y - else tarai (tarai (x - 1) y z) (tarai (y - 1) z x) (tarai (z - 1) x y);; val tarai: x: int -> y: int -> z: int -> int > let rec tak x y z = - if x <= y then z - else tak (tak (x - 1) y z) (tak (y - 1) z x) (tak (z - 1) x y);; val tak: x: int -> y: int -> z: int -> int > #time;; --> 今すぐタイミング オン > tarai 14 7 0;; リアル: 00:00:01.686、CPU: 00:00:01.880、GC 全般0: 0, 全般1: 0, 全般2: 0 val it: int = 14 > tak 22 11 0;; リアル: 00:00:01.854、CPU: 00:00:02.050、GC 全般0: 0, 全般1: 0, 全般2: 0 val it: int = 11
このように、たらいまわし関数は引数の値が小さくても実行に時間がかかります。
たらいまわし関数は遅延評価を使って高速化することができます。tarai() のプログラムを見てください。x <= y のときに y を返しますが、このとき引数 z の値は必要ありませんね。引数 z の値は x > y のときに計算するようにすれば、無駄な計算を省略することができます。ただし、もう一つの tak() は遅延評価で高速化することはできません。ご注意くださいませ。
lazy 式を使うと、たらいまわし関数は次のようになります。
リスト : lazy 式による遅延評価
let rec taraiLazy x y (z: Lazy<int>) =
if x <= y then y
else
let zz = z.Force()
taraiLazy (taraiLazy (x - 1) y z)
(taraiLazy (y - 1) zz (lazy x))
(lazy (taraiLazy (zz - 1) x (lazy y)))
遅延評価したい処理を lazy に包んで引数 z に渡します。そして、x > y のときに引数 z を評価 (z.Force()) します。すると、遅延オブジェクト内の式が評価されて z の値を求めることができます。たとえば、lazy 0 を z に渡す場合、z.Force() とすると返り値は 0 になります。lazy x を渡せば、x に格納されている値が返されます。lazy (taraiLazy ...) を渡せば、taraiLazy が評価されてその値が返されるわけです。
それでは実行してみましょう。
> let rec taraiLazy x y (z: Lazy<int>) = - if x <= y then y - else - let zz = z.Force() - taraiLazy (taraiLazy (x - 1) y z) - (taraiLazy (y - 1) zz (lazy x)) - (lazy (taraiLazy (zz - 1) x (lazy y)));; val taraiLazy: x: int -> y: int -> z: Lazy<int> -> int > #time;; --> 今すぐタイミング オン > taraiLazy 140 70 (lazy 0);; リアル: 00:00:00.002、CPU: 00:00:00.000、GC 全般0: 0, 全般1: 0, 全般2: 0 val it: int = 140
tarai() の場合、遅延評価の効果はとても大きいですね。
ところで、lazy 式を使わなくても、ラムダ式 (クロージャ) だけで遅延評価を行うことができます。次のリストを見てください。
リスト : クロージャによる遅延評価
let rec taraiLazy1 x y z =
if x <= y then y
else
let zz = z()
taraiLazy1 (taraiLazy1 (x - 1) y z)
(taraiLazy1 (y - 1) zz (fun () -> x))
(fun () -> taraiLazy1 (zz - 1) x (fun () -> y))
遅延評価したい処理をクロージャに包んで引数 z に渡します。そして、x > y のときに引数 z の関数を呼び出します。すると、クロージャ内の処理が評価されて z の値を求めることができます。たとえば、fun () -> 0 を z に渡す場合、z() とすると返り値は 0 になります。fun () -> x を渡せば、x に格納されている値が返されます。fun () -> taraiLazy1 ... を渡せば、taraiLazy1 が評価されてその値が返されるわけです。ただし、クロージャでは評価結果を保存 (キャッシュ) できないことに注意してください。
> let rec taraiLazy1 x y z = - if x <= y then y - else - let zz = z() - taraiLazy1 (taraiLazy1 (x - 1) y z) - (taraiLazy1 (y - 1) zz (fun () -> x)) - (fun () -> taraiLazy1 (zz - 1) x (fun () -> y));; val taraiLazy1: x: int -> y: int -> z: (unit -> int) -> int > #time;; --> 今すぐタイミング オン > taraiLazy1 140 70 (fun () -> 0);; リアル: 00:00:00.001、CPU: 00:00:00.000、GC 全般0: 0, 全般1: 0, 全般2: 0 val it: int = 140