前回作成したイテレータは、クロージャを呼び出すたびに中断していたプログラムの実行を再開し、次の要素を呼び出した側に返してプログラムの実行を中断します。これをさらに一般化して、複数のプログラム間で実行の中断や再開を相互に行わせることができます。このようなプログラムのことを「コルーチン (co-routine)」といいます。
「サブルーチン (sub-routine)」は call してから return するまで途中で処理を中断することはできませんが、コルーチンは途中で処理を中断し、そこから実行を再開することができます。また、コルーチンを使うと複数のプログラムを (擬似的に) 並行に動作させることができます。この動作は「スレッド (thread)」とよく似ています。
一般的なスレッドは、一定時間毎に実行するスレッドを強制的に切り替えます。このとき、スレッドのスケジューリングは処理系が行います。これを「プリエンプティブ (preemptive)」といいます。コルーチンの場合、プログラムの実行は一定時間ごとに切り替わるものではなく、プログラム自身が実行を中断しないといけません。これを「ノンプリエンプティブ (nonpreemptive)」といいます。
コルーチンで複数のプログラムを並行に動作させるには、あるプログラムだけを優先的に実行するのではなく、他のプログラムが実行できるよう自主的に処理を中断する、といった協調的な動作を行わせる必要があります。そのかわり、スレッドと違って排他制御といった面倒な処理を考える必要がなく、スレッドのような切り替え時のオーバーヘッドも少ないことから、スレッドよりも動作が軽くて扱いやすいといわれています。
Lua はコルーチンをサポートしています。コルーチンの操作関数はテーブル coroutine にまとめられています。Lua のコルーチンには親子関係があり、コルーチン A からコルーチン B を呼び出した場合、A が親で B が子になります。このように主従関係を持つコルーチンを「セミコルーチン (semi-coroutine)」といいます。コルーチンの親子関係は木構造と考えることができます。
新しいコルーチンは関数 create(f) で生成します。プログラムは引数 f に関数として渡します。create はコルーチンに対応するスレッドオブジェクトを返します。コルーチンを実行 (または再開) するには関数 resume(co, ...) を使います。引数 co は再開 (または実行) するコルーチンです。resume を呼び出したほうが親、呼び出されたほうが子になります。子コルーチンの中で関数 yield(...) を実行すると、そこでプログラムの実行を中断して親コルーチンに戻ります。このとき、yield の引数が親コルーチンで呼び出した reusme の返り値になります。また、resume に引数を渡して実行を再開すると、それが yield の返り値となります。
簡単な例を示しましょう。コルーチンを使うとイテレータを簡単に作ることができます。たとえば、配列の要素をひとつずつ取り出して返すイテレータは次のようになります。
リスト 6 : 配列のイテレータ
function make_array_iter(ary)
return coroutine.create(
function()
for i = 1, #ary do
coroutine.yield(ary[i])
end
return false
end)
end
for 文のブロックの中で yield を使って要素 ary[i] を返すだけです。これで for 文の実行か中断され、resume を呼び出すと実行が再開されます。
簡単な実行例を示しましょう。
> co = make_array_iter({1,2,3,4,5})
> coroutine.resume(co)
true 1
> coroutine.resume(co)
true 2
> coroutine.resume(co)
true 3
> coroutine.resume(co)
true 4
> coroutine.resume(co)
true 5
> coroutine.resume(co)
true false
> coroutine.resume(co)
false cannot resume dead coroutine
resume は 1 つ以上の値を返します。最初はエラーの有無を表す真偽値です。正常に動作した場合は true を、エラーが発生した場合は false を返します。次に yield で渡された値が返されます。
コルーチンは関数の実行が終了した場合、関数の返り値が yield に渡されます。make_array_iter の場合、返り値の false がイテレータが返す最後の値となります。そのあと、resume を実行すると cannot resume dead coroutine というエラーになります。
コルーチンの操作は関数 coroutine.wrap を使うともっと簡単になります。
coroutine.wrap(f)
関数 coroutine.wrap は引数の関数 f をコルーチンに変換して、コルーチンを実行 (再開) するための関数を返します。引数の f は通常の関数で、coroutine.create を使う必要はありません。その中で coroutine.yield を使って値を返すことができます。この値が coroutine.wrap の返す関数の返り値になります。
簡単な例を示しましょう。
> function foo() coroutine.yield(1); coroutine.yield(2);
coroutine.yield(3); return false end
> bar = coroutine.wrap(foo)
> bar()
1
> bar()
2
> bar()
3
> bar()
false
> bar()
stdin:1: cannot resume dead coroutine
stack traceback:
[C]: in function 'bar'
stdin:1: in main chunk
[C]: in ?
coroutine.wrap を使うと for - in 文と組み合わせることもできます。
> function foo1() coroutine.yield(1); coroutine.yield(2); coroutine.yield(3) end > for i in coroutine.wrap(foo1) do print(i) end 1 2 3
for - in 文で使用する場合、戻り値なし (retrun を省く) か、nil を返すようにしてください。そうしないと、次のように for - in 文の繰り返しが正しく終了しません。
> for i in coroutine.wrap(foo) do print(i) end
1
2
3
false
stdin:1: cannot resume dead coroutine
stack traceback:
[C]: in for iterator 'for iterator'
stdin:1: in main chunk
[C]: in ?
ご注意くださいませ。
コルーチンを使うと高階関数をイテレータに変換することも簡単にできます。たとえば、前回作成した木を巡回する高階関数 for_each_tree を考えてみましょう。
リスト 7 : 木の巡回
function for_each_tree(fn, tree)
if type(tree) ~= 'table' then
fn(tree)
else
for i = 1, #tree do
for_each_tree(fn, tree[i])
end
end
end
このような高階関数をイテレータに変換する場合もコルーチンを使うと簡単にできます。次のリストを見てください。
リスト 8 : 高階関数からイテレータを生成
function make_iterator(fn, ...)
local args = {...}
return coroutine.wrap(
function()
fn(function(x) coroutine.yield(x) end, table.unpack(args))
return nil
end)
end
引数 fn は高階関数、そのあとに fn に渡す引数を可変引数式で受け取ります。なお、関数 fn は第 1 引数に関数を受け取るものとします。まず最初に、可変引数式を配列に変換して、ローカル変数 args にセットします。これは可変引数式のスコープがレキシカルスコープと異なるためで、直近の function で定義された可変引数式だけしか参照できません。ご注意ください。
次に、wrap に渡す関数の中で関数 fn を呼び出します。このとき、第 1 引数に匿名関数を渡して、その中で yield を実行します。他の引数は args を unpack して渡します。これで fn が実行されて、第 1 引数で渡した匿名関数が呼び出されると、yield により引数 x を resume に返して実行が中断されます。fn の実行が終了したら return で nil を返します。
それでは実行してみましょう。
> iter = make_iterator(for_each_tree, {1,{2,{3,4,5},6},7})
> iter()
1
> iter()
2
> iter()
3
> iter()
4
> iter()
5
> iter()
6
> iter()
7
> iter()
nil
> iter()
stdin:1: cannot resume dead coroutine
stack traceback:
[C]: in function 'iter'
stdin:1: in main chunk
[C]: in ?
> for x in make_iterator(for_each_tree, {1,{2,{3,4,5},6},7}) do print(x) end
1
2
3
4
5
6
7
もうひとつ簡単な例として、順列を生成するイテレータを作ってみましょう。順列を生成する処理を高階関数でプログラムすると次のようになります。
リスト 9 : 順列の生成
function member(x, ary)
for i = 1, #ary do
if x == ary[i] then return true end
end
return false
end
function permutations(fn, n, m, a)
if #a == m then
fn(a)
else
for x = 1, n do
if not member(x, a) then
table.insert(a, x)
permutations(fn, n, m, a)
table.remove(a)
end
end
end
end
関数 permutations は 1 から n までの数値から m 個を選ぶ順列を生成します。選んだ数字は配列 a に追加します。そして、a にはない数字を選んで追加します。最初の呼び出しで 1 つの数字を選び、次の再帰呼び出しで 2 つめの数字を選びます。
#a が m と等しい場合、m 個の数字を選んだので fn(a) を実行します。そして、再帰呼び出しから戻ったあと、remove で選んだ数字を削除して新しい数字を選びます。もしも選ぶ数字がなければ、その前の再帰呼び出しに戻って数字を選び直します。これで順列をすべて生成することができます。
それでは実行してみましょう。
> permutations(function(x) print(table.concat(x, ',')) end, 3, 3, {})
1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1
table.concat は配列を文字列に変換する関数です。要素は第 2 引数の値で連結されます。
関数 permutations も make_iterator でイテレータに変換することができます。簡単な実行例を示します。
> iter = make_iterator(permutations, 3, 3, {})
> table.concat(iter(), ',')
1,2,3
> table.concat(iter(), ',')
1,3,2
> table.concat(iter(), ',')
2,1,3
> table.concat(iter(), ',')
2,3,1
> table.concat(iter(), ',')
3,1,2
> table.concat(iter(), ',')
3,2,1
> iter()
nil
> iter = make_iterator(permutations, 3, 3, {})
> for x in iter do print(table.concat(x, ',')) end
1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1
最後にコルーチンを使って素数を求めるプログラムを作ってみましょう。考え方は簡単です。最初に、2 から始まる整数列を生成するコルーチンを用意します。この場合、コルーチンを「遅延ストリーム」として使います。
一般に、データの流れを抽象化したデータ構造を「ストリーム (stream)」と呼びます。たとえば、ファイル入出力はストリームと考えることができます。また、配列を使ってストリームを表すこともできます。ただし、単純な配列では有限個のデータの流れしか表すことができません。ところが、遅延評価を用いると擬似的に無限個のデータを表すことができます。これを「遅延ストリーム」と呼びます。
遅延ストリームの基本的な考え方は、必要になったときに新しいデータを生成することです。このときに遅延評価を用います。具体的にはデータを生成する関数を用意し、それを遅延評価してストリームに格納しておきます。そして、必要になった時点で遅延評価しておいた関数を呼び出して、新しいデータを求めればよいわけです。コルーチンを使えば遅延ストリームを簡単に作成することができます。
2 は素数なので、この整数列から 2 で割り切れる整数を取り除き除きます。ここでもコルーチンを使って、入力ストリームから 2 で割り切れる整数を取り除いたストリームを返すフィルターを作ります。
2 で割り切れる整数が取り除かれたので、次の要素は 3 になります。今度は 3 で割り切れる整数を取り除けばいいのです。これもフィルターを使えば簡単です。このとき、入力用のストリームは 2 で割り切れる整数が取り除かれています。したがって、このストリームに対して 3 で割り切れる整数を取り除くようにフィルターを設定すればいいわけです。
このように、素数を見つけたらそれで割り切れる整数を取り除いていくアルゴリズムを「エラトステネスの篩」といいます。ようするに、2 から始まる整数ストリームに対して、見つけた素数 2, 3, 5, 7, 11, ... を順番にフィルターで設定して素数でない整数をふるい落としていくわけです。
プログラムは次のようになります。
リスト 10 : エラトステネスの篩
-- n から始まる整数列
function integers(n)
return coroutine.wrap(
function()
while true do
coroutine.yield(n)
n = n + 1
end
end)
end
-- フィルター
function filter(pred, src)
return coroutine.wrap(
function()
while true do
local m = src()
if pred(m) then
coroutine.yield(m)
end
end
end)
end
function sieve(x)
local nums = integers(2)
for i = 1, x do
local n = nums()
io.write(n)
io.write(" ")
nums = filter(function(x) return x % n ~= 0 end, nums)
end
end
関数 integers は n から始まる整数列を生成するストリームです。関数 filter は引数 pred で渡された述語が偽を返す要素をストリーム src から取り除きます。src() で要素を取り出して m にセットします。pred(m) が真であれば yield(m) で親コルーチンに m を返します。これで述語が偽を返す要素を取り除くことができます。
素数を求める関数 sieve も簡単です。引数 x は求める素数の個数です。最初に、2 から始まる整数列を integers で生成して変数 nums に セットします。このストリーム nums の先頭要素が素数になります。nums() でストリームから素数を取り出して n にセットします。次に n を表示して、n で割り切れる整数を取り除くフィルターを生成して nums にセットします。つまり、x 個の素数を求めるために、x 個のフィルターをストリームに重ねていくわけです。
それでは実際に sieve(100) を実行してみましょう。
> sieve(100) 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541