こんにちは、びしょ〜じょです。 気づいたら1月も終わりますね。 お前も俺も、もう終わりだ。

1. はじめに

研究ではコルーチンを使っている。 ここでひとつコルーチンについてまとめておきたい。 特にstackfulnessについての考察をこれまでおこなっていなかったため、そこに重点を置く。 本稿では文献[1] を参考にする。

2. 対称性による分類

コルーチンとは、一時停止、再開のできるサブルーチンを指す。 コルーチンを呼び出した呼び出し元にコントロールを戻す操作の有無により、コルーチンを対称コルーチンと対称コルーチンの2種類に分けることができる(図2.1 )。

2.1 . コルーチンの対称性による分類

対称コルーチン 非対照コルーチン
“戻る” 操作 ない ある

対称コルーチンを持つプログラム言語は筆者は知らない。 非対称コルーチンはわりとメジャーな機能で、コルーチンやFiberと言われる言語機能は概ね非対称コルーチンと思われる。 “戻る” 操作とは、多くの非対称コルーチンを持つプログラム言語ではyieldというキーワードや関数名として使うことができる。

yield example
coroutine.create(function()
  -- callerに"戻る"
  coroutine.yield(3)
end)

3. stackfulnessによる分類

コールスタックをまたいで yieldできるかどうかで、非対称コルーチンをさらに2つに分類できる(表3.1 )。

3.1 . stackfulnessによる分類

stackful stackless
またいでyield できる できない
examples Luaのcoroutine, RubyのFiber Rustのcoroutine, JSのGenerator

stackful coroutinesは単に “coroutine” 、 あるいは “fiber” と呼ばれ、 stackless coroutinesは “generator” と称される傾向にある。

では、 “コールスタックをまたげる” とはどういうことか? これはyieldがネストした関数呼出しから一気にコルーチンの呼び出し元まで戻れる、またyieldした位置にコントロールを戻せるということである。 次の例を見てみる(プログラム3.2 , プログラム3.3 )。

プログラム3.2 . stackfull example in Lua
local send = function(x)
  local y = yield(x)
  return y + 3
end

local co = coroutine.create(function()
  local x = send(10)
  return x + 10
end)

print(resume(co)) -- prints 10
print(resume(co, 2)) -- prints 15

プログラム3.3 . stackless example in JS
/* syntax error
function send(x) {
  yield x
}
*/

const co = (function*() {
  const x = yield 10
  return x + 10
})

console.log(co.enxt())  // prints 10
console.log(co.next(3)) // prints 13

3.2 を見てみる。 関数sendの中でyieldしているが、send自体はただの関数である。 sendをコルーチンcoの中で呼び出すと、このyieldで一時停止する。 2度目のresumeで渡した2が、yieldの戻り値となり、sendの戻り値は2 + 3となる。

一方3.3 は、コルーチン(generator)の中でしかyieldできない。 特にJSはyieldがキーワードとして扱われ、generatorの中でしか書けないというsyntacticな制約がある。

4. pros/cons

非対称コルーチンをさらにstaclful、stacklessの2種類に分類した。 利点と欠点をまとめてみると、次のようになる(表4.1 )。

4.1 . 利点・欠点まとめ

stackful stackless
利点 関数呼出しをまたいだyieldができ、
stacklessよりも表現力が高い
ステートマシンに変換でき、実装が簡潔な
だけでなく実行のパフォーマンスも良い
欠点 実装が煩雑となり、コンテキストスイッチの
オーバーヘッドがかかる
表現力が低い

stackful coroutinesの利点・欠点が、逆にstackless coroutinesの欠点・利点と、一長一短となっている。

5. 研究との関連性

筆者の研究では “ネストした関数呼出しから一気に飛び出せる” というstackful coroutinesの特性を利用している。 そのためstackless coroutinesではすぐには代替できない。 stackful coroutines → stackless coroutinesの変換がある場合はなんとかなるかもしれないので、教えてください。

6. おわりに

という話をゼミでやった。 (研究の進捗は)ないです

なんかわかりやすいやつ

Background:I’m asking this because I currently have an application with many (hundreds to thousands) of threads. Most of those threads are idle a great portion of the time, waiting on work items …


  1. Moura, Ana Lúcia De, and Roberto Ierusalimschy. “Revisiting coroutines.” ACM Transactions on Programming Languages and Systems (TOPLAS) 31.2 (2009): 6.