お気楽 Lua プログラミング超入門

はじめに

今回は「継続渡しスタイル (Continuation Passing Style : CPS)」という手法について説明します。Scheme と Ruby には「継続」という他の言語にはない強力な機能がありますが、使いこなすのはちょっと難しいといわれています。継続渡しスタイルはクロージャを使った汎用的な方法で、クロージャがあるプログラミング言語であれば、継続渡しスタイルでプログラムを作成することができます。

●継続とは？

最初に継続について簡単に説明します。継続は「次に行われる計算」のことです。たとえば、次のプログラムを例に考えてみましょう。

> function foo() print("foo") end
> function bar() print("bar") end
> function baz() print("baz") end
> function test() foo(); bar(); baz() end
> test()
foo
bar
baz

関数 test は関数 foo, bar, baz を順番に呼び出します。foo の次に実行される処理は bar, baz の関数呼び出しです。この処理が foo を呼び出したあとの「継続」になります。同様に、bar のあとに実行されるのは baz の呼び出しで、この処理がこの時点での「継続」になります。また、baz を呼び出したあと、test の中では次に実行する処理はありませんが、test は関数呼び出しされているので、関数呼び出しから元に戻る処理が baz を呼び出したあとの「継続」になります。

このように、あるプログラムを実行しているとき、そのプログラムを終了するまでには「次に実行する処理 (計算)」が必ず存在します。一般に、この処理 (計算) のことを「継続」といいます。Ruby や Scheme の場合、次の計算を続行するための情報を取り出して、それを保存することができます。Ruby や Scheme では、この保存した情報を「継続」といって、通常のデータ型と同様に取り扱うことができます。

●継続渡しスタイルとは？

一般のプログラミング言語では、Ruby や Scheme のように継続を取り出して保存することはできません。そこで、継続 (次に行う処理) を関数 (クロージャ) で表して、それを引数に渡して実行することにします。これを「継続渡しスタイル (CPS)」といいます。次の例を見てください。

> function test_cps(cont) foo(); bar(); cont() end
> test_cps(baz)
foo
bar
baz

関数 test_cps は foo, bar を呼び出したあと、引数の cont を実行します。関数 baz を渡せば foo, bar, baz と表示されますし、他の処理を渡せばそれを実行することができます。

もう一つ簡単な例を示しましょう。継続に値を渡して処理を行うこともできます。

> function add_cps(x, y, cont) return cont(x + y) end
> add_cps(10, 20, function(x) return x end)
30
> add_cps(10, 20, function(x) print(x) end)
30

関数 add_cps は引数 a と b を加算して、その結果を継続 cont に渡します。cont で引数 x をそのまま返すと、計算結果を返すことができます。また、cont で print(x) を実行すれば、計算結果を表示することができます。

●再帰呼び出しと CPS

CPS を使うと再帰呼び出しを末尾再帰に変換することができます。たとえば、階乗の計算を CPS でプログラムすると次のようになります。

リスト 1 : 階乗の計算 (CPS)

function fact_cps(n, cont)
  if n == 0 then
    return cont(1)
  else
    return fact_cps(n - 1, function(x) return cont(x * n) end)
  end
end

引数 cont が継続を表します。n が 0 のときは、cont に階乗の値 1 を渡します。それ以外の場合は、階乗の計算を継続の処理にまかせて fact_cps を再帰呼び出します。ここで、fact_cps の呼び出しは末尾再帰になることに注意してください。

継続の処理 function(x) return cont(x * n) end では、継続の引数 x と fact_cps の引数 n を掛け算し、その結果を cont に渡します。この継続の中で階乗の式が組み立てられていきます。n の階乗を求めるとき、継続を表すブロックの引数 x には (n - 1)! の値が渡されることに注意してください。そして、n が 0 のとき継続に引数 1 を渡して実行すると、今まで組み立てられた式が計算されて階乗の値を求めることができます。

それでは実際に実行してみましょう。

> for i = 1, 15 do fact_cps(i, print) end
1
2
6
24
120
720
5040
40320
362880
3628800
39916800
479001600
6227020800
87178291200
1307674368000

●二重再帰と CPS

次はフィボナッチ数列を求める関数を CPS で作りましょう。リスト 2 を見てください。

リスト 2 : フィボナッチ関数 (CPS)

function fibo_cps(n, cont)
  if n == 0 or n == 1 then
    return cont(n)
  else
    return fibo_cps(n - 1,
                    function(x)
                      return fibo_cps(n - 2, function(y) return cont(x + y) end)
                    end)
  end
end

関数 fibo_cps は、引数 n が 0 または 1 のとき継続 cont(n) を実行します。それ以外の場合は fibo_cps を再帰呼び出しします。n - 1 の値が求まると、その値は匿名関数の引数 x に渡されます。この中で、今度は n - 2 の値を求めます。すると、その値は匿名関数の引数 y に渡されます。したがって、fibo_cps n の値は x + y で求めることができ、この値を fibo_cps n の継続 cont に渡せばいいわけです。

それでは実際に実行してみましょう。

> for i = 0, 20 do fibo_cps(i, print) end
0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765

ところで、fibo_cps は末尾再帰になっていますが、関数の呼び出し回数は二重再帰の場合と同じです。同じ値を何度も求めるていることに変わりはないので、二重再帰よりも実行速度が高速になることはありません。Lua の場合、CPS のほうが遅くなりました。また、二重再帰の場合は関数呼び出しによりスタックが消費されますが、CPS の場合はクロージャが生成されるのでメモリ (ヒープ領域) が消費されます。このように、再帰呼び出しを CPS に変換したからといって、効率の良いプログラムになるとは限りません。ご注意くださいませ。

●末尾再帰と繰り返し

ここで「末尾再帰」について考えてみましょう。末尾再帰の「末尾」とは、関数の最後で行われる処理のことです。とくに末尾で関数を呼び出すことを「末尾呼び出し (tail call)」といいます。関数を呼び出す場合、返ってきたあとに行う処理のため、必要な情報を保存しておかなければいけません。ところが、末尾呼び出しはそのあとに実行する処理がありません。呼び出したあと元に戻ってくる必要さえないのです。

このため、末尾呼び出しはわざわざ関数を呼び出す必要はなく、アセンブリ言語のような低水準のレベルではジャンプ命令に変換することができます。これを「末尾呼び出し最適化 (tail call optimization)」とか「末尾最適化」といいます。とくに末尾再帰は末尾で自分自身を呼び出しているので、関数の中で繰り返しに変換することができます。

また、相互再帰やもっと複雑な再帰呼び出しの場合でも、末尾最適化を適用することで、繰り返しに変換できる場合もあります。このように、再帰プログラムを繰り返しに変換してから実行することを「末尾再帰最適化 (tail recursion optimization)」といいます。厳密にいうと末尾最適化なのですが、一般的には末尾再帰最適化と呼ばれることが多いようです。

末尾再帰最適化を行うプログラミング言語、たとえば Scheme の場合、次に示すような関数呼び出しは、スタックを消費せずに実行することができます。処理系は Gauche を使いました。

gosh> (define (foo) (foo))
foo
gosh> (foo)
=> 無限ループになる

Lua も末尾再帰最適化を行うので、次のプログラムは無限ループになります。

> function foo() return foo() end
> foo()
=> 無限ループになる

ただし、次のプログラムは無限ループにはなりません。

> function bar() bar() end
> bar()
stdin:1: stack overflow
stack traceback:
    ・・・省略・・・

Lua の場合、return func() の形式を「末尾呼び出し」として扱います。return 文は break 文と同様に、ブロックの最後にしか書くことが許されていません。Lua では return func() を末尾呼び出しと判断して末尾再帰最適化を行います。詳しい説明は Lua のリファレンスをお読みください。

●CPS による木の巡回

次は配列を「木」とみなして、木を巡回するプログラムを作ってみましょう。ここでは、配列を節 (node) とし要素を葉 (leaf) と考えます。木を巡回するプログラムは簡単です。次のリストを見てください。

リスト 3 : 木の巡回

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

-- for 文を再帰に変換
function for_each_rec(fn, tree, n)
  if type(tree) ~= 'table' then
    fn(tree)
  elseif n <= #tree then
    for_each_rec(fn, tree[n], 1)
    for_each_rec(fn, tree, n + 1)
  end
end

関数 for_each_tree は木 tree を巡回して、各要素に関数 fn を適用します。for_each_tree は関数 fn の副作用が目的なので、返り値に意味はありません。最初に、関数 type でデータ型をチェックします。返り値はデータ型を表す文字列です。tree の型が 'table' でなければ、tree は配列ではありません。fn(tree) を実行します。tree が配列の場合、for 文で配列の要素を取り出し、for_each_tree に渡して再帰呼び出しします。これで木 tree を巡回することができます。

for 文を再帰呼び出しに変換することもできます。関数 for_each_rec を見てください。引数 n が配列の添字を表します。n の値が #tree 以下であれば、tree[n] の要素を for_each_rec に渡して再帰呼び出しします。このとき、n は先頭要素の位置を表す 1 を渡します。そのあと、tree をそのまま for_each_rec に渡して再帰呼び出しします。このとき、n の値を +1 することに注意してください。これで for_each_tree と同じ動作になります。

簡単な実行例を示します。

> for_each_tree(print, {1,{2,{3,4,5},6,7},8,9})
1
2
3
4
5
6
7
8
9
> for_each_rec(print, {1,{2,{3,4,5},6,7},8,9}, 1)
1
2
3
4
5
6
7
8
9

for_each_rec を CPS に変換すると、次のようになります。

リスト 4 : 木の巡回 (CPS)

function for_each_cps(fn, tree, n, cont)
  if type(tree) ~= 'table' then
    fn(tree)
    return cont()
  elseif n <= #tree then
    return for_each_cps(fn, tree[n], 1,
      function()
        return for_each_cps(fn, tree, n + 1,
          function() return cont() end)
      end)
  else
    return cont()
  end
end

for_each_cps は副作用が目的なので、継続に値を渡す必要はありません。tree が葉の場合は fn を適用してから cont を呼び出します。次に、for_each_cps を再帰呼び出しして先頭要素の部分木をたどり、その継続の中で残りの部分木をたどります。そして、その継続の中で cont を呼び出します。n が #tree より大きい場合は継続 cont を呼び出すだけです。これで生成された継続を呼び出して、木を巡回することができます。

それでは実際に試してみましょう。

> for_each_cps(print, {1,{2,{3,4,5},6,7},8,9}, 1, function() return false end)
1
2
3
4
5
6
7
8
9
false

このように、CPS でも木を巡回して各要素に関数 fn を適用することができます。

●CPS による継続の保存と実行の再開

木の巡回を CPS に変換すると、クロージャを使ってイテレータ (iterator) と同様な動作を行わせることができます。次のリストを見てください。

リスト 5 : 木の巡回 (イテレータ)

function for_each_iter(tree, n, cont)
  if type(tree) ~= 'table' then
    return tree, function() return cont() end
  elseif n <= #tree then
    return for_each_iter(tree[n], 1,
      function()
        return for_each_iter(tree, n + 1,
          function() return cont() end)
      end)
  else
    return cont()
  end
end

for_each_iter は木を巡回してその要素を順番に出力します。要素を返すとき、継続をクロージャに格納していっしょに返すところがポイントです。このようにクロージャを使って CPS の継続を保存することで、プログラムの実行を一時的に中断することができます。そして、そのクロージャを呼び出すことでプログラムの実行を再開し、次の要素を求めることができます。

なお、for_each_iter を呼び出すときに渡す継続が一番最後に呼び出されるので、終端を表す値 (たとえば nil や false など) を返すようにプログラムしてください。

簡単な実行例を示しましょう。

> a, b = for_each_iter({1,{2,{3,4,5},6},7}, 1, function() return false end)
> a
1
> b
function: 0x7fffdc51f640
> a, b = b()
> a
2
> a, b = b()
> a
3
> a, b = b()
> a
4
> a, b = b()
> a
5
> a, b = b()
> a
6
> a, b = b()
> a
7
> a, b = b()
> a
false
> b
nil

正常に動作していますね。なお、Lua にはコルーチンという機能があり、コルーチンを使うともっと簡単にイテレータを作成することができます。