サブルーチンのサブルーチンたるゆえんは、それがメイン・ルーチンという”親”から呼び出されることにある。サブルーチンに与えられた自由は親に帰ること(return)だけである。つまり、メイン・ルーチンはサブルーチンよりも偉いという厳然たる階層構造の上に成り立っている。そして、サブルーチン呼び出しはメイン・ルーチンを中断することで行われるという遂次性ゆえに、現在の遂次実行型の計算機アーキテクチャにぴったりはまるわけである。
ところで、すべての応用システムがサブルーチン型の制御構造でうまく実現できるかというとそうでもない。世の中には問題自体が並列的なものが数多くある。代表的な例が将棋や`ェスのような対戦型のゲームである。この場合は、2人のプレーヤをメイン・ルーチンとサブルーチンのように階層化できない。もう一段上位のレベルを考えて、プレーヤをそのサブルーチンと考えれば実現できないこともないが、実在しない階層を考えるのも不自然である。もっと問題なのは、サブルーチンではリターンのたびに局所変数が初期化されてしまうことで、将棋の持ち駒のような個々のプレーヤの実行時のコンテクストは別のデータとしてサブルーチンの外に持たねばならなくなってしまう。
対戦型ゲームを自然にプログラムしようとすると、コンテクストを保存した上でプレーヤに対応するサブルーチン間で制御を渡し合える仕組みが欲しくなる。それを実現するのがConwayによって考えられたコルーチン(co-routine)である。
これはcoという接頭語からわかるように、主従関係がないプログラム単位である。コルーチンは自分の実行を中断して、ほかのコルーチンに制御を渡すことができる。これはサブルーチンにおけるリターンと似ているが、中断直後の処理から再開できる点（resume）に本質的な違いがある。サブルーチン実行中のコンテクスト（局所変数）はその終了とともに消え去るが、実行が中断されているコルーチンのコンテクストはそのまま存在しているからである。
ところで、コルーチンはどういう仕組みで実現されるのだろうか？CやPascalではプログラムの実行時コンテクストはスタックに置かれている。コンテクストを保存したまま他のプログラムに制御を渡すためにはスタックの状態をどこかに保存しておけばよい。したがって、一番簡単な方法はコルーチンごとに別のスタック空間を与え、その上でコルーチンの本体を実行させる方法である。
別のコルーチンはまた別のスタック空間から動くから、それによってコンテクストが変わることはない。ほかにスタックの内容をプログラム中の配列にコピーしてしまう方法もあるが、これはコンテクスト・スイッチに時間がかかるのであまり実用的ではない。また、マルチプロセスのOSで子プロセスの生成を行うことがあるが、これも本質的には同じことである。大きな違いは、子プロセスは親プロセスと並行して実行されるが、コルーチンは制御の切り替えをプログラム中に明示することである。
つまり、マルチプロセスと本質は同じであり、それをプログラム中に自然に書けるメカニズムがコルーチンであるといえる。そのため、コルーチンを擬似マルチプロセスと呼ぶこともあるつまり、今時のCPUやOSはコルーチンを実装するのになんら不自由はないのである。強いて問題といえば、それを仕様に取り込んでいる言語があまり普及していないことであろう。
コルーチンがあれば簡単に書ける応用問題というのは結構たくさんある。特に、待ち行列や離散系シュミレータなどは状態を待つオブジェクトを自然に記述できればよいわけであるから、まさしくコルーチン向きである。筆者も勉強がてらLispにコルーチンが書けるような拡張をしてロジック・シュミレータを書いてみたが、なかなかきれいに書けた。個々の論理素子が一個のコルーチンとして表現でき、素子の動作記述も素子のカテゴリ単位に個別に行えるからカプセル化も自然にできてしまう。
初期化されたコルーチンは、データとしてのコンテクストとそれに対する操作として手続きを閉じ込めているからオブジェクト指向におけるオブジェクトとして考えても良いだろう。
コルーチンを扱える処理系が少ないという点も最近ではModula-2のように仕様に取り入れているものもあるし、スレッドやライトウェイト・プロセスとしてOSレベルでコルーチン的な制御構造を実現できるようになってきている。決して新しい概念ではないが、環境が整ってきた今、違う視点から問題を見直すと意外にきれいな解決法があるかもれない。
Conwayの論文を発掘して読んでみたら、なんとCobolのコンパイラを作る方法としてコルーチンを論じていた。