M.Hiroi's Home Page

Lua Programming

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

[ PrevPage | L u a | NextPage ]

継続渡しスタイル

今回は「継続渡しスタイル (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 にはコルーチンという機能があり、コルーチンを使うともっと簡単にイテレータを作成することができます。


初版 2011 年 4 月 30 日
改訂 2019 年 12 月 28 日

コルーチン

前回作成したイテレータは、クロージャを呼び出すたびに中断していたプログラムの実行を再開し、次の要素を呼び出した側に返してプログラムの実行を中断します。これをさらに一般化して、複数のプログラム間で実行の中断や再開を相互に行わせることができます。このようなプログラムのことを「コルーチン (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 を使うともっと簡単になります。

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

初版 2011 年 4 月 30 日
改訂 2019 年 12 月 28 日

Copyright (C) 2011-2019 Makoto Hiroi
All rights reserved.

[ PrevPage | L u a | NextPage ]