こんにちは､びしょ〜じょです｡気づいたら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. stackful 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. おわりに

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

他

なんかわかりやすいやつ

How do stackless coroutines differ from stackful coroutines?

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 ...

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