今回は関数型言語で用いられているテクニックを紹介します。Lisp などの関数型言語では、関数を生成する関数を簡単に作ることができます。このとき使われる機能が「クロージャ (closure)」です。クロージャは評価する関数と参照可能なローカル変数をまとめたものです。クロージャは関数のように実行することができますが、クロージャを生成するときに参照可能なローカル変数を保存するところが異なります。なお、参照可能なローカル変数の集合を環境と呼ぶことがあります。
Lua でクロージャを生成するには匿名関数を使うか、局所的な関数を定義して、その関数を返します。たとえば、「引数を n 倍する関数」を生成する関数は、匿名関数を使うと次のようになります。
> function foo(n) return function(x) return x * n end end > foo10 = foo(10) > foo10(1) 10 > foo10(2) 20 > foo5 = foo(5) > foo5(10) 50 > foo5(20) 100
関数 foo は引数を n 倍する関数を生成します。変数 foo10 に foo(10) の返り値をセットします。すると、foo10 は引数を 10 倍する関数として使うことができます。同様に、変数 foo5 に foo(5) の返り値をセットすると、foo5 は引数を 5 倍する関数になります。
匿名関数で関数を生成するとき、評価する関数のほかに、そのとき参照可能なローカル変数、つまり「環境」もいっしょに保存されます。この場合、参照可能なローカル変数は foo の引数 n です。そして、クロージャを実行するときは、保存されているローカル変数を参照することができるのです。
foo(10) を実行して匿名関数を生成するとき、定義されているローカル変数は n で、その値は 10 です。この値がクロージャに保存されているので、foo10 の関数は引数を 10 倍した結果を返します。foo(5) を評価すると n の値は 5 で、それがクロージャに保存されているので、foo5 の関数は引数を 5 倍した結果を返すのです。
また、局所的な関数を定義して、その関数を返してもクロージャを生成することができます。リスト 11 を見てください。
リスト 11 : マップ関数のカリー化
function map(func)
local function _map(ary)
local result = {}
for i = 1, #ary do
table.insert(result, func(ary[i]))
end
return result
end
return _map
end
関数 map は引数 func に関数を受け取り、その関数を呼び出すマップ関数を返します。局所関数 _map はクロージャとして機能するので、map の引数 func にアクセスすることができます。
簡単な実行例を示しましょう。
> map2 = map(function(x) return x * x end)
> p(map2({1,2,3,4,5}))
1 4 9 16 25
> p(map(function(x) return x * x end)({1,2,3,4,5}))
1 4 9 16 25
最初の例は map で生成した関数を変数 map2 にセットし、それから map2 を関数呼び出しします。次の例は、map の返り値を直接関数呼び出ししています。カッコが多くなりますが、2 引数の map と同じように呼び出すことができます。これでも配列の要素を 2 乗することができます。
2 番目の例は、最初の引数を受け取って新しい関数を生成して返し、その関数に次の引数を適用して値を求めるという動作になります。このように、関数の引数が一つでも、「関数を返す関数」を使うことで、複数の引数を処理することができます。このような関数を「カリー化関数 (curried function)」といいます。
関数型言語には、カリー化関数をサポートしているプログラミング言語、たとえば Haskell や ML (SML/NJ, Ocaml) などがあります。これらのプログラミング言語では、高階関数はカリー化関数として定義されています。また、関数を合成して新しい関数を作ることも簡単にできます。
クロージャの応用例として「ジェネレータ (generator)」というプログラムを紹介しましょう。ジェネレータは呼び出されるたびに新しい値を生成していきます。たとえば、Lua の関数 math.random は実行するたびに乱数を返します。つまり、random は乱数列を発生するジェネレータと考えることができます。
簡単な例題として、奇数列 ( 1, 3, 5, ..... ) を発生するジェネレータを作ってみます。関数名は gen_odd_number としましょう。グローバル変数を使うと、次のようになります。
> function gen_odd_num() prev_num = prev_num + 2; return prev_num end > prev_num = -1 > gen_odd_num() 1 > gen_odd_num() 3 > gen_odd_num() 5 > gen_odd_num() 7 > gen_odd_num() 9
グローバル変数 prev_num は、gen_odd_num が返した値を記憶します。新しい値は、この prev_num に 2 を足せばいいのです。
このように、グローバル変数を使うと簡単にジェネレータを作ることができますが問題点もあります。それは、複数のジェネレータが必要になる場合です。単純に考えると、必要な数だけグローバル変数と関数を用意すればいいのですが、数が増えるとグローバル変数や関数を定義するだけでも大変な作業になります。
ところがクロージャを使うと、もっとスマートにジェネレータを用意できます。まず、ジェネレータを作る関数を定義します。
リスト 12 : ジェネレータを作る関数
function make_gen_odd_num()
local prev_num = -1
return function()
prev_num = prev_num + 2
return prev_num
end
end
関数 make_gen_odd_num はクロージャを返します。そして、このクロージャがジェネレータの役割を果たすのです。それでは、実際に実行してみましょう。
> a = make_gen_odd_num() > a() 1 > a() 3 > a() 5 > a() 7 > b = make_gen_odd_num() > b() 1 > b() 3 > b() 5
make_gen_odd_num で作成したクロージャを変数 a にセットして実行します。実行するたびに 1, 3, 5 と奇数列を生成していますね。次に新しいクロージャを変数 b にセットします。このクロージャを実行すると、新しい奇数列を生成します。確かにジェネレータとして動作しています。
プログラムのポイントはローカル変数 prev_num です。クロージャで保存される環境は変数 prev_num です。この値は make_gen_odd_num が実行されたときに -1 で初期化されています。クロージャにはこの値が保存されます。次は a にセットしたクロージャを実行します。匿名関数はクロージャに保存されたローカル変数にアクセスするので、prev_num += 2 の値は 1 になり、クロージャに保持されている prev_num の値は 1 に更新されます。
環境はクロージャによって異なります。a のクロージャが評価されると、そのクロージャの環境が更新されるのであって、ほかのクロージャに影響を与えることはありません。したがって、ジェネレータが発生する奇数列が、ほかのジェネレータに影響を与えることはないのです。あとは必要な数だけジェネレータを make_gen_odd_num で作り、そのクロージャを変数もしくは配列に格納しておけばいいわけです。
最後に、再帰を使った面白い関数を紹介しましょう。次のリストを見てください。
リスト 13 : たらいまわし関数
function tarai(x, y, z)
if x <= y then
return y
else
return tarai(tarai(x - 1, y, z), tarai(y - 1, z, x), tarai(z - 1, x, y))
end
end
function tak(x, y, z)
if x <= y then
return z
else
return tak(tak(x - 1, y, z), tak(y - 1, z, x), tak(z - 1, x, y))
end
end
tarai や tak は「たらいまわし関数」といって、再帰的に定義されている関数です。これらの関数は Lisp などでベンチマークとして利用されることがあります。オリジナルプログラムは Web サイト「ぬえ 鵺 NUE」 (https://www.nue.org/nue/index.html) の TAK Function をお読みください。
tarai は通称「竹内関数」と呼ばれていて、日本の代表的な Lisper である竹内郁雄氏によって考案されたそうです。そして、tak は tarai のバリエーションで、John Macarthy 氏によって作成されたそうです。たらいまわし関数がベンチマークで使われることは M.Hiroi も知っていましたが、このような由緒ある関数だとは思ってもいませんでした。
それでは、たらいまわし関数を Lua で実行してみましょう。実行環境は Ubunts 18.04 (Windows Subsystem for Linux), Intel Core i5-6200U 2.30GHz です。結果は次のようになりました。
tarai(14, 7, 0) : 39.4 秒 tak(22, 11, 0) : 38.8 秒
Lua の実行速度はスクリプト言語の中では速いほうで、Perl や Python よりも高速です。
たらいまわし関数が遅いのは、同じ値を何度も計算しているためです。この場合、表 (table) を使って処理を高速化することができます。同じ値を何度も計算することがないように、計算した値は表に格納しておいて、2 回目以降は表から計算結果を求めるようにします。このような手法を「表計算法」とか「メモ化」といいます。
Lua は関数型言語の機能を備えているので、関数を「メモ化」するメモ化関数を作成することができます。次のリストを見てください。
リスト 14 : メモ化関数
function memoize(func)
local tbl = {}
local function _memo_func(...)
local key = table.concat({...}, ',')
if not tbl[key] then
tbl[key] = func(...)
end
return tbl[key]
end
return _memo_func
end
関数 memoize は関数 func を引数に受け取り、それをメモ化した関数を返します。memoize は局所関数 _memo_func を返すので、その中で memoize の引数 func やローカル変数 tbl にアクセスすることができます。
変数 tbl はハッシュとして使います。キーは引数で、値が func の返り値になります。キーを生成するため、{...} で可変引数式を配列に変換し、関数 table.concat で文字列に変換します。要素は第 2 引数の文字 ( , ) で連結されます。tbl[key] が偽の場合は func を呼び出して値を求め、それを tbl にセットします。あとは tbl[key] の値を返すだけです。
関数 memoize の使い方は簡単です。次の例を見てください。
リスト 15 : メモ化関数の使い方 tarai = memoize(tarai) tak = memoize(tak)
とても簡単ですね。それでは実際に実行してみましょう。
tarai(192, 96, 0) : 0.21 秒 tak(192, 96, 0) : 0.68 秒
このように、引数の値を増やしても高速に実行することができます。メモ化の効果は十分に出ていると思います。また、同じ計算を再度実行すると、メモ化の働きにより値をすぐに求めることができます。
関数 tarai は「遅延評価」を行う処理系、たとえば関数型言語の Haskell では高速に実行することができます。また、Scheme でも delay と force を使って遅延評価を行うことができます。
tarai のプログラムを見てください。x <= y のときに y を返しますが、このとき引数 z の値は必要ありませんね。引数 z の値は x > y のときに計算するようにすれば、無駄な計算を省略することができます。なお、関数 tak は x <= y のときに z を返しているため、遅延評価で高速化することはできません。ご注意くださいませ。
完全ではありませんが、Lua でもクロージャを使って遅延評価を行うことができます。次のリストを見てください。
リスト 16 : クロージャによる遅延評価
function tarai_lazy(x, y, z)
if x <= y then
return y
else
local zz = z()
return tarai_lazy(tarai_lazy(x - 1, y, function() return zz end),
tarai_lazy(y - 1, zz, function() return x end),
function()
return tarai_lazy(zz - 1, x, function() return y end)
end)
end
end
遅延評価したい処理をクロージャに包んで引数 z に渡します。そして、x > y のときに引数 z を評価します。すると、クロージャ内の処理が実行されて z の値を求めることができます。たとえば、function() return 0 end を z に渡す場合、z() とすると返り値は 0 になります。function() return x end を渡せば、x に格納されている値が返されます。function() return tarai( ... ) end を渡せば、関数 tarai が実行されてその値が返されるわけです。
それでは、実際に実行してみましょう。
tarai_lazy(192, 96, function() return 0 end) : 0.02 秒
このように、たらいまわし関数は遅延評価でも高速化することができます。