『Ruby でつくる Ruby』などでお世話になっているラムダノートが、新しい雑誌「n月刊ラムダノート」を創刊しました。

コンピュータ関係の技術情報の記事だけが載るそうです。創刊号は、『TCPの再送制御機構』、『「コルーチン」とは何だったのか？』、『MLOpsの歩き方』、の 3 本です。

『TCP の再送制御機構』は、パケットを送ってから返事が来るまでの RTT (Round-Trip Time) を計測する方法や、RTT を使った再送のアルゴリズムや、RTT を使わない再送のアルゴリズムなど、TCP の再送に関する仕様・実装の歴史から最新提案までを、日本語話者の中では間違いなく世界一詳しい第一人者である西田佳史さん（@nsd）が広く深く紹介しています。
『「コルーチン」とは何だったのか？』は、ぼくが書きました。伝統的なコルーチンの説明から、JavaScript 界隈から始まった言葉の転用までを駆け足で紹介しています。
『MLOps の歩き方』は、MLOps とは DevOps の ML 版 *1 ということで、機械学習を実際のサービス運用で使っていく上で発生する課題や解決を、この分野のプロの practitioner であり『仕事ではじめる機械学習』の著者の一人でもある有賀康顕さん（@chezou）が最新状況を網羅的に解説しています。

とんでもなくマニアックな雑誌ですね。

さて、ラムダノートと相談して、『「コルーチン」とは何だったのか？』の草稿を公開することにしました。上記の通りこの雑誌は多方向にマニアックで、けっしてこの記事が「n月刊ラムダノート」の方向性を代表するようなものではないのですが、なんとなく雰囲気を感じて頂ければ幸いです。

執筆と草稿公開の経緯

さっさと草稿を見たい人はこの節をスキップ。

執筆のきっかけは、最初は↓の不用意なツイートです。

Python 3.7 で async/await が新キーワードとして追加されたと聞いて、互換性軽視っぷりに驚いたんだけど、それに加えて async/await で書いたものをコルーチンと呼んでいて頭を抱えている。
Python は Guido が独裁者を辞めた途端、おかしくなってしまったのだろうか……。https://t.co/RvsuzMzx4O pic.twitter.com/Q87NcEVunY
— Yusuke Endoh (@mametter) 2018年11月19日

「独裁者を辞めた途端」云々は、"Ruby is dead" みたいな軽口だったんですが、あまり上品じゃなかったですね。反省してます。

このツイートにはいくつかご意見や情報をいただきましたが、Python が（ぼくの知っていた）コルーチンとは違うものをコルーチンと呼んでいるのは確かなようでした。現状をまとめてみようと思い、最初はブログ記事として書き始めました。

しかし初期の草稿を @bonotake さんに見てもらい、そこからさらに掘り下げて調べていくうちに、自分の勘違い *2 や複雑な経緯がわかってきて、うまくまとめられず放置してました。

そんなとき、ラムダノートの鹿野さん（@golden_lucky）から雑誌を創刊すると聞いて、この記事の出口が決まりました。もう少し正確に言うと、昨年末頃に鹿野さんから「雑誌創刊するから記事ないですか」と言われたときには、コルーチンの記事を完全に忘れていて、「考えとく」で終わりました。今年になって、鹿野さんやうちの奥さん（@hirekoke）とコルーチンや継続について雑談していて、日本語での体系的な解説が欲しいという話になり、「そういえばこんなブログ記事を書きかけてた」と言って見せたら、「えっこれ雑誌に載せられるのでは」ってなりました。雑談は大切。

草稿を公開することにした理由ですが、

もともとブログ用に書いていたものなので、できれば一般公開して広く知ってもらいたかった（遠藤の気持ち）
草稿を公開することで「n月刊ラムダノート」の雰囲気を知ってもらったり、ラムダノートでの執筆プロセスが身近であることを知ってもらったりしたい（ラムダノートの気持ち）

ということで、著者と出版社の希望がかさなったためです。ここで公開するこの草稿はわりとファイナルに近いもの（ラムダノートに内容・構成レベルの改善提案をいただいて直した後のもの）です。それでもまだまだ適当な状態ですね……。「★なんかそれっぽい書き出し」とか。図もまったくありません。参考文献は、Slack で適当にリンク貼りつけて伝えました。そのあたりがいい感じになっているのは、だいたいラムダノートによる「編集」です。ということでみなさんも、ちょっと気合を入れたブログ記事を書いたら、公開する前にラムダノートに提案をしてみるといい感じになるかもしれません *3 。ちょうど記事募集をはじめたらしいので、見てみるとよいのではないでしょうか。

ということでここから草稿です↓

「コルーチン」という用語が指すもの（仮題）

★なんかそれっぽい書き出し

「コルーチン」という言葉が指すものが、プログラミング言語の文化圏によってだいぶ変わってしまっているようです。

調べた限りで分かった状況をまとめてみたいと思います。間違ってるところがあったら、ご指摘ください。

1. 伝統的なコルーチン

まず、伝統的なコルーチンである「対称コルーチン」と「非対称コルーチン」を説明します。

1.1. 対称コルーチン

対称コルーチンは、互いに制御を渡し合う手続きのようなものです。疑似コードで示します。

coroutine A() {
  print("A-start");
  B.transfer();
  print("A-end");
}

coroutine B() {
  print("B-start");
  A.transfer();
  print("B-end");
}

A.transfer(); //=> "A-start", "B-start", "A-end"

X.transfer() で、コルーチン X に処理を渡します。このように、対称コルーチンでは飛び先を常に明示します。非常に原始的・明示的で分かりやすい反面、実用上はなかなか扱いにくく、実際にはほとんど使われていません。

対称コルーチンは、コルーチンの発案者（の一人）とされる Conway の 1963 年の論文に登場する、元祖のコルーチンです。メインルーチン・サブルーチンのような親子関係ではなく、対等に協調し合うルーチンとして考案されました。COBOL コンパイラを実装する上で、lexer と parser を別モジュールとして実装するためのテクニックだったようです。 transfer で中断したコルーチンを再開するのは、完全にプログラマの責任になります。再開し忘れると、コードが実行されないことになります。上の例でも print("B-end") が実行されていません。再開しそこねて、後処理（ファイルのクローズとか）が抜けると、痛い目にあいます。対称コルーチンの提案は構造化プログラミング（1969 年）より前なので、現代的なプログラミングと相性がよくないのはしかたないですが、現代で使われていないのはこういう不便さのためだと思われます。

対称コルーチンが実装されている例。

Conway の原論文（機械語）
Modula-2
Ruby の Fiber#transfer
Boost.Coroutine の symmetric_coroutine

1.2. 非対称コルーチン

対称コルーチンの間に親子関係を持たせることで使いやすくしたものです。次の疑似コードを見てください。

coroutine A {
  print("foo");
  yield "bar";
  print("baz");
}

// 呼び出し側
x = A.resume(); //=> "foo"
print(x);       //=> "bar"
A.resume();     //=> "baz"

A.resume() でコルーチン X を起動し、yield でコルーチンを「中断」し、呼び出し側に制御を一旦もどします。すると、A.resume() の呼び出しがリターンして、yield の引数であった "bar" が変数 x に代入されます。その後、print(x) を実行してから、再度 X.resume() すると、コルーチンの中断箇所から実行を再開します。すると、yield "bar" が終了し、最後の print("baz") が実行されます。コルーチン A は、resume のたびに、yield までを細切れに実行できる関数のように振る舞います。

重要なことなのでもう一度言っておきます。非対称コルーチンで「中断」と言ったら、「呼び出し側に制御を一旦もどす（そのあとで再度 resume されたら中断箇所から再開する）」という意味です。後の説明でも出てくるので覚えておいてください。

元祖のコルーチンと区別を明示するために、元祖の方を対称コルーチン（symmetric coroutine）、こっちを非対称コルーチン（asymmetric coroutine）と言います（参照: http://www.inf.puc-rio.br/~roberto/docs/MCC15-04.pdf）。しかし、前述の通り、元祖のコルーチンはほとんど使われていないので、単にコルーチンと言ったらだいたい非対称コルーチンを指します（少なくとも後述する JavaScript の「イディオム」が登場するまでは）。他に、非対称コルーチンは semi-coroutine や fiber という名前で呼ばれることもあります。

対称コルーチンとの違いは、resume で別のコルーチンを呼び出した場合、必ず制御が戻ってくることです（呼び出されたコルーチンが yield または終了すると戻ってくる）。これにより、必ず実行してほしい後処理が抜ける心配が大きく減ります。ただし、yield で中断したコルーチンが再度 resume されてくるかどうかはプログラマ次第なので、yield の後に必ず実行してほしい後処理を書くのはちょっと注意が必要です。（余談ですが、この問題は本質的に解決不可能で、Ruby で未解決の最古のバグチケット #595 にもなっています）

次は、非対称コルーチンを実装した言語・ライブラリの例です。

Simula
Lua の SemiCoroutine
Ruby の Fiber#resume / Fiber.yield や、Enumerator
Python の generator (PEP 342)
JavaScript の function* / yield
C# のイテレータ (yield で IEnumerator を得る。Unity の文化圏ではコルーチンとも呼ぶ)
Boost.Coroutine の asymmetric_coroutine
Scala や Java での実験的な実装

あとで出てくるのでもう一度いっておきますが、「JavaScript の function*/yield」＝「Python の generator」は、非対称コルーチンです。

1.3. コルーチンの利用例

伝統的なコルーチンの代表的なユースケースは、無限長の列を表現することです。非対称コルーチンで説明します。

coroutine natural_numbers() {
  i = 1;
  while(true) {
    yield i;
    i += 1;
  }
}

このコルーチンは、最初に resume すると 1 を yield し、次に resume すると 2 を yield し、というのを無限に繰り返します。このように、resume するごとに次の要素を yield で返す非対称コルーチンは、無限列を表現しています。

このような無限列の表現を、ジェネレータといいます。非対称コルーチンが一部の言語で generator やイテレータと呼ばれているのは、このユースケースに特化しているためです*4。

Ruby は Enumerator と Fiber の両方を提供しています。前者はジェネレータとして使いやすい API 、後者は対称・非対称コルーチンとして使いやすい API になっているという違いがありますが、Enumerator は内部的に Fiber で実装されていて、本質的に同等です。なお、Fiber という名前はマイクロソフトの .NET の Fiber に由来します（Fiber は「繊維」という意味です。スレッド（糸）よりもメモリ使用量が少なく大量に作れる軽量スレッドという意味で名付けられたようですが、実体としてはコルーチンの再発明です。))。

他にも非対称コルーチンは、ゲームやシミュレーションのオブジェクト（resume するごとにフレームやシミュレーション単位 1 つ分だけ動作をすすめる）を表現するためなどにも使われます。

2. JavaScript における事情

ここから、JavaScript コミュニティでコルーチンと呼ばれるものの話が始まります。これまでの話とはだいぶ違うので、気持ちを切り替えて読んでください。

2.1. JavaScript の言語的特徴

ご存じのとおり、JavaScript は、ブラウザの上で動く言語です。マウスクリックのようなユーザ操作のイベントが起きたときに呼ばれる関数（コールバック）を書くのが元々の想定ユースケースでした。一方で、JavaScript はシングルスレッドの言語です*5。そのため、コールバックの中で時間のかかる処理（sleep や IO 待ちなど）を行うと、その間は他のイベントが処理できなくなってしまいます。

これを解決するために、JavaScript の世界では、「すべての関数は一瞬でリターンする」という API 設計が徹底されています。たとえば n ミリ秒間待ってから何かを行いたい場合、JavaScript 以外の言語では sleep(n) のような「呼び出しから n ミリ秒後にリターンする関数」を使いますが、JavaScript では setTimeout(function() { ... }, n) のように「呼び出しから n ミリ秒後にコールバックする関数を登録する関数」を使います。

// 普通の言語の 1 秒待ち
sleep(1000);
print("foo");

// JavaScript の 1 秒待ち
setTimeout(function() {
  print("foo");
}, 1000);

この言語設計は非常に合理的ですが、結果的に JavaScript のプログラムはコールバックであふれることになりました。コールバックの中にコールバックを書く、ということも日常的に行われます。

// 普通の言語で 1 秒ごとに foo 、bar 、baz という
sleep(1000);
print("foo");
sleep(1000);
print("bar");
sleep(1000);
print("baz");

// JavaScript で 1 秒ごとに foo 、bar 、baz という
setTimeout(function() {
  print("foo");
  setTimeout(function() {
    print("bar");
    setTimeout(function() {
      print("baz");
    }, 1000);
  }, 1000);
}, 1000);

このように、インデントがどんどん深まって行きます。この現象でコードが読み書きしづらくなることは、コールバック地獄と呼ばれています。

2.2. コルーチンを使ったイディオム

実は、このインデントの現象は、非対称コルーチンできれいに解決できます。疑似コードで説明します。

coroutine A {
  yield setTimeout(function() { A.resume(); }, 1000);
  print("foo");

  yield setTimeout(function() { A.resume(); }, 1000);
  print("bar");

  yield setTimeout(function() { A.resume(); }, 1000);
  print("baz");
}

A.resume();

A.resume() を呼ぶと、コルーチン A は setTimeout によってコールバックを設定し、yield で一旦呼び出し側に処理を戻します。それから 1 秒後にコールバックが呼ばれ、そのコールバックは A.resume() を行います。これにより、yield したところから再開して print("foo") が実行されます。そしてまた setTimeout をして yield します。これを繰り返すことで、1 秒ごとに何かやる処理を表現できます。

JavaScript でも、非対称コルーチンである function*/yield を用いて、次のようなコードを書くのが流行しました。

const co = require('co')
co(function* () {
  yield new Promise(function(f) { setTimeout(f, 1000); });
  print("foo");

  yield new Promise(function(f) { setTimeout(f, 1000); });
  print("bar");

  yield new Promise(function(f) { setTimeout(f, 1000); });
  print("baz");
})

co とか new Promise(...) とか登場人物が増えてややこしいのですが、簡単に説明すると

new Promise(...) は、コールバック関数の登録を受け付ける "Promise" オブジェクトを返します。
co は、渡された非対称コルーチンを resume し、yield で中断したら "Promise" オブジェクトにコールバックを登録し、コールバックが起きたら再度 resume する、を繰り返す補助関数です。

これらによって本質的には上のコルーチンのコードと同等になっています*6。

さて、JavaScript コミュニティでは、このイディオムを漠然と「コルーチン」と呼ぶようです。その理由を推測すると、

function/yield は実際に非対称コルーチンであるから（ただし、JavaScript では通常 function/yield のことをジェネレータと呼びます）
「ブロック処理があったら関数実行が中断する」という説明がなんとなく「中断できる関数」という非対称コルーチンの説明に似ているから

というのが何となく絡み合って、慣習になったのだと思われます。実際、このあたりを混乱したような説明をしばしば見かけます。しかし、ここで言っている「中断」は、非対称コルーチンで言っていた「中断」とはもはや意味が違うことに注意してください。このイディオムの説明で言う「中断」は、「ブロック処理を待つこと」であって、「呼び出し側に処理を一旦返すこと」ではなくなっています。この言葉の使い方は、同期的なブロック処理 API を避けている JavaScript の事情に特化したものになっています。

（これ以下削除で良さそう）上のイディオムの中で、具体的に何をコルーチンと呼んでいるかは、人によって異なるようです。少なくとも以下が観測できました。

promise を yield する function*/yield のこと ("Coroutines are, in short, generator functions that yield promises.")
function*/yield から promise に変換する関数（上の例でいうと co 関数）の名前（npm の co 、bluebird の Promise.coroutine 、他多数)
このイディオム全体のこと

★promise が未定義語になってしまった

2.3. async function の登場

JavaScript の人たちは、コルーチンを使ったイディオムでは満足せず、async/await という専用の文法を導入するに至りました。C# の async/await を参考に取り込んだと思われます。

async function asyncABC() {
  await sleep(1000);
  print("foo");

  await sleep(1000);
  print("bar");

  await sleep(1000);
  print("baz");
}

これはしばしば、前述の「イディオム」への構文糖として説明されます*7。

async function foo() { ... } は function foo() { co(function* () { ... }) } 相当*8
await bar は yield bar 相当

ざっと調べた限り、JavaScript の言語仕様においては、async function で定義された関数は "async function" と呼ぶようで、これのことをコルーチンとは呼んでいないと思います。前述のイディオムとの区別が曖昧になりますしね。

async function と伝統的コルーチンは、全くの別物であることに注意してください。async function は function*/yield の構文糖ではありますが、非対称コルーチンの特徴を失っています。というのも、co が暗黙的に埋め込まれるので、「呼び出し側に処理を一旦戻す」ということができなくなっているのです。await で非対称コルーチンの yield を呼んでも、co がそれを拾って勝手に resume してしまうので、非対称コルーチンでいう「中断」にはなりません。

また、他にも異なる点があります。伝統的なコルーチンでは、コルーチンが transfer/resume/yield したとき、次にどのコルーチンが再開するかはプログラマは完全に把握できるものでした。よって、「次にどのコルーチンが再開するかをプログラマが制御する・制御できる」という性質もコルーチンの特徴のひとつと考えられていました。しかし JavaScript では、イベント処理のために async function を使うことが多かったので、await してからいつどれが再開するかはプログラマにも把握できず、場合によっては複数の async function が再開可能な状態になる、という状況が生まれました。どの async function が再開するかは、言語やライブラリが用意したスケジューラが勝手に決める（プログラマが管理しない・できない）ということになります。

重要なのでもう一度いいますが、async function と伝統的コルーチンは、全くの別物です。

3. 「コルーチン」の新たな意味の誕生

JavaScript の async function は非同期処理の記述として大ヒットし、他言語にも取り入れられるようになりました。

3.1. Python のコルーチン

Python は 3.5 から async/await を導入しました。このとき、JavaScript が async function と呼んでいるものを、Python は「コルーチン」と名付けました。

Python に async/await を提案した PEP 492 によると、「generator から native coroutine を切り出す」と書かれています。これだけ読むと「generator = 非対称コルーチン」を意識していると思えますが（実際、PEP 342 の方は generator = (asymmetric) coroutine を明確に意識しています）、読み進めると、この提案は完全に JavaScript のイディオムを念頭においているようです。PEP 492 には、JavaScript の他に HHVM 、Dart 、Scala などを参考にしたと書かれていますが、ざっと調べた限りこれらは誰も async function を「コルーチン」と呼んでいません。JavaScript コミュニティでなんとなく呼ばれている「コルーチン」を、なんとなく持ってきたのだと思います。

ここにきて、async function を指して「コルーチン」と呼ぶ用法が確立したようです。

少し補足すると、Python の async は暗黙的に co 相当の機能を埋め込むわけではなくもう少しややこしいもののようです。async function と future と組み合わせれば、対称コルーチンをエンコードすることも出来るようです。ただ、これをもって「async で定義された関数は対称コルーチンである」とは（普通は）言わないと思います。

3.2. Kotlin のコルーチン

Kotlin では、非対称コルーチン（ジェネレータ）と async function をすべてまとめて「コルーチン」と呼ぶようです。

sequence { ... } と書けば非対称コルーチンが、async { ... } と書けば async function が得られるようです。

Kotlin は規格策定のときにいろいろサーベイをした様子が伺え、伝統的なコルーチンから JS や Python の状況までを踏まえて、このようにしたのではないかと思います。

4. まとめ

コルーチンという言葉はプログラミング言語文化圏によって、いろいろなものを指します。とくにこの 10 年で、その意味はとても拡散してしまったようです。

繰り返しですが、調べながら書いたもので、特に JS には詳しくありません。なんか事実誤認があったらご指摘ください。

謝辞

この文書をまとめるにあたって、調査やレビューを @bonotake さんや笹田耕一さんにご協力いただきました。ありがとうございました。

付録A. Promise と JavaScript

Promise は、並行処理を記述する言語機能です。JavaScript 以外の言語の Promise は、こんな感じに動きます。

// 1 秒かかる計算を Promise にする
x = new Promise(function() { sleep(1000); return 42; });

// Promise の生成は一瞬で終わる（1 秒待たされない）

// get を呼ぶと、sleep(1) が終わるのを待って、計算結果の 42 が得られる
print(x.get()); //=> 42

しかし JavaScript では、sleep(1) は書けないですし、それを同期的に待ち受ける get() 関数も書けません。そこで、例によってコールバックを使います*9。

x = new Promise(function(f) { setTimeout(function() { f(42); }, 1000); });

x.then(function(r) { print(r) }); //=> （1 秒後に）42

Promise オブジェクトに対して then メソッドで関数を渡すと、Promise の計算が終わったあとでコールバックしてくれます。

2 つの Promise を連続で待ちたい場合、単純に考えると入れ子にする必要があります。

x = new Promise(function(f) { setTimeout(function() { f(42); }, 1000); });

x.then(function(r) {
  print(r); //=> （1 秒後に）42

  y = new Promise(function(f) { setTimeout(function() { f(43); }, 1000); });

  y.then(function(r) {
    print(r); //=> (さらに 1 秒後に）43
  });
});

これではインデント問題は解決されません。しかし JavaScript の then は少し工夫されていて、コールバックを含めた全体の Promise を返します。つまり、次のように書けます。

x = new Promise(function(f) { setTimeout(function() { f(42); }, 1000); });

x.then(function(r) {
  print(r); //=> （1 秒後に）42

  y = new Promise(function(f) { setTimeout(function() { f(43); }, 1000); });

  return y;
}).then(function(r) {
  print(r); //=> (さらに 1 秒後に）43
});

これにより、インデント問題は解決されました。しかし、then を大量に書く必要があり、あまり簡潔とは言えません。そのため、本文のコルーチンを使ったイディオムに進化していったようです。

付録B. 継続とコルーチンの関係

たまにコルーチンと混同される言語機能に、「継続」という非常に強力な言語機能があります。継続とは何かを説明するととても長いのですが、関係だけを一言で言えば、継続はコルーチンの上位互換です。継続を使うと、コルーチンを表現できます。つまり、継続を使えば、resume や yield を普通の関数として定義できてしまいます。

しかし、継続＝コルーチンではありません。継続にできてコルーチンにできない典型的な例だけを挙げておきます。

for i in 0..2 do
  for j in 0..2 do
    for k in 0..2 do
      puts "(%d, %d, %d)" % [i, j, k]
    end
  end
end

というコードは、(0, 0, 0) から (2, 2, 2) まで辞書順に出力するコードです。これは、要素の数だけインデントが深まるというインデント地獄になっています。

コルーチンでは、このインデント地獄を解決することはできません。しかし継続を使うと、

try do
  i = amb(0..2)
  j = amb(0..2)
  k = amb(0..2)
  puts "(%d, %d, %d)" % [i, j, k]
end

というコードで同じ動作をする関数 amb が書けます。

ポイントは、amb(0..2) という 1 回の関数呼び出しが 3 回リターンする（それぞれ 0 、1 、2 を返す）というところです。これはコルーチンにはできず、継続にはできるところです。詳細は、Scheme/継続の種類と利用例 - Wikibooks や他の参考書を見てください。

*1:Meta Language ではなく Machine Learning のほう。

*2:コルーチンはプログラミング言語理論の中で生まれたと思い込んでましたが、出自はもっと実践的なものだったとか。くわしくは記事の方で。

*3:さすがに「★なんかそれっぽい書き出し」とかはひどいので、なるべくちゃんと書きましょう（自省）。

*4:歴史的には、ジェネレータは 1970 年代に CLU や Icon という言語の中で登場していますが、当時の論文にはコルーチンの語が出てこないので、おそらく独立して再発明されたものと思われます。

*5:シングルスレッドの理由としては、性能の低い計算機でも動かせること、バグの元であるマルチスレッドプログラミングをユーザに課さないこと、元々の想定ユースケースではシングルスレッドで問題なかったこと、などが考えられます。なお、WebWorker のような拡張を使うとマルチスレッドができますが、これは置いておきます。

*6:"Promise" については、付録 A で簡単に説明します。

*7:もちろん、実際の実装が構文糖になっているわけではないと思います。

*8:簡単のため、引数は無視しています。

*9:コールバックによる Promise は Python の Twisted ライブラリの deferred から持ってきたようです。

まめめも

新雑誌「n月刊ラムダノート」の『「コルーチン」とは何だったのか？』の草稿を公開します