機能検討 - 継続の除去

Schemeには call-with-current-continuation (多くの実装では call/cc の別名もある.) という関数があり, 呼び出した時点の継続 (実行コンテキスト) を取り出し、そこから再開できます。Common Lisp には仕様上, 継続はありませんが, cl-cont - A Common Lisp Delimited Continuations Library というライブラリで delimited continuations が使えます。

どうして検討が必要かというと、Ruby にも callcc 関数があるから。ただ, 次の警告が表示され、廃れる予定。よい。 

x86_64-linux/continuation.so: warning: callcc is obsolete; use Fiber instead.

継続, ファイバ, コルーチン

継続が表に出ているのは Scheme ぐらいで, 多くのプログラミング言語はコルーチンやファイバを提供している。

http://cl-www.msi.co.jp/solutions/knowledge/lisp-world/articles/three-dogmas-of-scheme [リンク切れ] が説得力があります。フルの継続というのは, 過剰に強力で、実際に必要とされるのはそんなに強力な手続きではない。他方、処理系がフルの継続を提供するには、実装が大きく制約されてしまう。突然全然関係ない場所にジャンプできる, というのは, プログラミングを非常に難しくします。

保存できる実行コンテキストがただ一つの場合は, setjmp() - longjmp(), POSIX の sigsetjmp() - siglongjmp() がある。

他方, 外側から順番にサブルーチンに降りてきたり順に外側に戻るだけでなく, 関数の実行を途中で一旦停止して そこから 再開したい、という需要はある。

下表の二つを総称してコルーチンと呼ばれることも多い。また, 狭く async function のことを指すこともある。

使い方による分類
分類 コルーチン, 対称 (symmetric) コルーチン, fiber semi-coroutine, 非対称 (asymmetric) コルーチン
挙動 transfer や switch などのメソッドで実行コンテキストを切り替える. コルーチンはyield で一時停止して値を返し, 外側から resume で一時停止した箇所から再開させる.

いずれの場合も、一時停止した箇所から再開させるのがポイント。

加えて, 非対称コルーチンは, 実装の制約による分類もある。Stackful coroutines は, スタックを保存する。いつでも suspend してもよい。他方 stackless coroutines は, コルーチン内から呼び出された関数での suspend を禁止する。開発者のコードを制約して, スタック保存を省略する (パフォーマンスもよいはず)。後者だからダメということはない。C++20 コルーチンは stackless. JavaScript の generator も stackless. yield キーワードは字面上 generator の中でしか書けない.

また, 継続を拡張したものとして, 限定継続 delimited continuation というものもあるようだ (拡張したのに限定とは?). 継続が保存するスタックを一部でカットして, 戻り値を取り出せるようにする。Hole に後から埋められると考えると, ただの継続より分かりやすいかも。See scheme - What exactly is a "continuation prompt?" - Stack Overflow

minilangには, call/cc のような形で継続を取り出す方法は提供しません。コルーチンとして, スタックトレースの深い方向へ (見た目的にはループの外側から内側へ) ジャンプする機能を用意し, 現在の処理を pending にして別の処理をおこなう, ということができるようにします。●●そのうちやる. [[未実装]]

Ruby の継続で fiber を実装

継続を使えば、対称コルーチン (ファイバ) を作るのは容易い. 次の短いコードで実現できる。transfer() で切り替える。呼出しの親子関係はないので、例外をどのように取り扱うか難しい。

Ruby
[RAW]
  1. require "continuation"
  3. # Fiberを継続 (実行コンテキスト) を使って実装する。
  4. # 実行コンテキストとは、スタック、PC, その他のレジスタの意味.
  5. # 次のようにしたい.
  6. # c1 = FakeFiber.new do p 1; c2.transfer; p 3 end
  7. # c2 = FakeFiber.new do p 2; c1.transfer; abort end
  8. # c1.transfer #=> 1, 2, 3
  9. class FakeFiber
  10. @@first = @@cur = FakeFiber.new # 一番最初の transfer() で戻り先を記録
  12. def initialize &block
  13. @cont = Proc.new do
  14. block.call
  15. @alive = false
  16. cont = @@first.instance_variable_get(:@cont)
  17. @@first = @@cur = FakeFiber.new
  18. cont.call # 最初の transfer() の直後に戻る
  19. end
  20. @alive = true
  21. end
  23. def alive?; @alive end
  25. def transfer
  26. raise 'This Fiber Terminated' if !@alive
  28. callcc do |cont| # 戻ってくるポイント (呼出し元) を保存しておく
  29. @@cur.instance_variable_set(:@cont, cont)
  30. @@cur = self
  31. @cont.call
  32. end
  33. end
  34. end
  36. def test
  37. $c1 = FakeFiber.new do p 1; $c2.transfer; raise end
  38. $c2 = FakeFiber.new do p 2; $c3.transfer; p 4 end
  39. $c3 = FakeFiber.new do p 3; $c2.transfer; raise end
  40. $c1.transfer #=> 1, 2, 3, 4
  41. p $c1.alive?, $c2.alive? #=> true, false
  42. p 5
  43. end
  45. test
  46. test

新しい Ruby では, 同機能の Fiber クラスが組込みで提供されており、自分で継続を使う必要はなくなっている。

(Semi-) コルーチン

ファイバがあれば非対称コルーチンの実装も容易い。 ●●サンプルコード

retry

Rubyには, 例外が発生したときに, その例外が発生した文を含むブロックからやりなおす retry というメソッドがあります。rescue 節だけに書ける。

これは Smalltalk の #retry メソッド由来。とはいえ, 解説では避けろ, 特に #retryUsing: は, みたいなのもあって、あまり勧められない。実際、例外が発生した文をもう一度実行して、今度は上手くいく、というのは想定しづらい。

Common Lisp も例外を再開できるが、セマンティクスが異なる。例外の代わりに指定した値を戻り値として再開する、という挙動。R の invokeRestart() も同じ。このほうがまだまとも。Smalltalk の #resume: の挙動。どうしてこちらにしなかった?

Smalltalk pharo-wiki/General/Exceptions.md

再開セマンティクス Exception handling (programming) - Wikipedia but after ten years of use, there was only one use of resumption left in the half million line system

minilangではコンパイル時エラーです。

外部イテレータ

継続がないと, 内部イテレータで外部イテレータを作れません。

Rubyはさまざまな場所で each() (内部イテレータ) が使われているため簡単ではありません。minilang コアライブラリについては, まず先に外部イテレータを定義して, それを利用して内部イテレータを作るようにしてみました。