コルーチンプログラミング
$ f_{n} = f_{n-1} + f_{n-2}で定義されるフィボナッチ数列を計算するプログラムは以下のように再帰的に書くことができる。
code:fib1.js
function fib(n){
if(n == 0) return 1;
if(n == 1) return 1;
return fib(n-1) + fib(n-2);
}
for(var i=0;;i++){
alert(fib(i));
}
今度は素数を計算するプログラムについて考えてみる。素数とは自分より小さい整数で割り切れないもののことなので、以下のような簡単なプログラムで素数を順番に計算することができる。
code:prime.js
var primes = [];
primes.push(2);
alert(2);
for(var i=3;;i++){
var r = Math.sqrt(i);
for(var j of primes){
if(j > r) break;
if(i % j ==0) break;
}
if(j > r){
primes.push(i);
alert(i);
}
}
フィボナッチ数列も素数もこのように簡単に計算することができるが、フィボナッチ数と素数を交互に出力したいときはどうすればよいだろうか? 次のフィボナッチ数を計算するメソッドや、次の素数を計算するメソッドを作れる場合は、状態をもつクラスFib, Primeを作って
code:fib2.js
class Fib {
constructor() {
this.count = 0
}
next(){
let i = this.count++
return (i < 2) ? this.ai : (this.ai = this.ai-2 + this.ai-1) }
}
code: test1.js
fib = new Fib();
prime = new Prime();
while(true){
console.log(fib.next());
console.log(prime.next());
}
のようなコードを書けばよいが、上のfib1.jsではnext()のようなメソッドは定義し辛いので、全く構造の異なるプログラムfib2.jsを書く必要がある。こういう要求があるたびにプログラムを書き直すのは面倒だしnext()のようなメソッドを作りにくい場合もある。
フィボナッチ数を計算するプログラムと素数を計算するプログラムが完全に別プロセスとして動いている場合はプログラムの構造を完全に変える必要はない。フィボナッチ数がみつかった時点で外部からの要求を待つようにしておき、要求があった時点で値を渡して次の処理に進めばよい。外部のプログラムはフィボナッチ計算プログラムと素数計算プログラムに交互にアクセスして値を受け取ればよい。つまりフィボナッチ計算プロセスと素数計算プロセスと本体計算プロセスが協調すればうまくいく。
このように、複数プロセスを利用する並列プログラミングができれば話は割と単純なのだが、大抵のプログラミング言語では複数プロセスを生成したりプロセス間の同期をとったりデータを共有したりすることが簡単にはできない。たとえばCにはpthreadのようなスレッドライブラリが存在するが、あまりポピュラーではないし利用方法も簡単ではない。
では、並列プログラミングは大変でハードルが高いけれどもちょっと並列っぽいプログラムを書きたい場合はどうすれば良いだろうか? 実は「コルーチン」というプログラミング技法が古くから提案されており、これを使うと前述のような悩みは簡単に解決できる。
コルーチン
プログラマなら誰でもサブルーチンについて良く知ってるはずだがコルーチンについては馴染みが無い人も多いかもしれない。何かの計算を依頼 コルーチンというのは....
(山本強氏の解説)
主従関係がないプログラム単位である。コルーチンは自分の実行を中断して、ほかのコルーチンに制御を渡すことができる。これはサブルーチンにおけるリターンと似ているが、中断直後の処理から再開できる点（resume）に本質的な違いがある。サブルーチン実行中のコンテクスト（局所変数）はその終了とともに消え去るが、実行が中断されているコルーチンのコンテクストはそのまま存在しているからである。
ところで、コルーチンはどういう仕組みで実現されるのだろうか？CやPascalではプログラムの実行時コンテクストはスタックに置かれている。コンテクストを保存したまま他のプログラムに制御を渡すためにはスタックの状態をどこかに保存しておけばよい。したがって、一番簡単な方法はコルーチンごとに別のスタック空間を与え、その上でコルーチンの本体を実行させる方法である。
別のコルーチンはまた別のスタック空間から動くから、それによってコンテクストが変わることはない。ほかにスタックの内容をプログラム中の配列にコピーしてしまう方法もあるが、これはコンテクスト・スイッチに時間がかかるのであまり実用的ではない。また、マルチプロセスのOSで子プロセスの生成を行うことがあるが、これも本質的には同じことである。大きな違いは、子プロセスは親プロセスと並行して実行されるが、コルーチンは制御の切り替えをプログラム中に明示することである。
つまり、マルチプロセスと本質は同じであり、それをプログラム中に自然に書けるメカニズムがコルーチンであるといえる。そのため、コルーチンを擬似マルチプロセスと呼ぶこともあるつまり、今時のCPUやOSはコルーチンを実装するのになんら不自由はないのである。強いて問題といえば、それを仕様に取り込んでいる言語があまり普及していないことであろう。
コルーチンがあれば簡単に書ける応用問題というのは結構たくさんある。特に、待ち行列や離散系シュミレータなどは状態を待つオブジェクトを自然に記述できればよいわけであるから、まさしくコルーチン向きである。筆者も勉強がてらLispにコルーチンが書けるような拡張をしてロジック・シュミレータを書いてみたが、なかなかきれいに書けた。個々の論理素子が一個のコルーチンとして表現でき、素子の動作記述も素子のカテゴリ単位に個別に行えるからカプセル化も自然にできてしまう。
初期化されたコルーチンは、データとしてのコンテクストとそれに対する操作として手続きを閉じ込めているからオブジェクト指向におけるオブジェクトとして考えても良いだろう。
Cのpthread
RubyのFiber
JSのGenerator
Array.combination みたいなのと組合せると面白いか?