eval-sv:理論

• eval-sv

• eval/svに要求された仕様

このページはまだ書きかけで不完全です。

eval/svに要求された仕様

(この項目は、eval/svを自分または他人が再実装する際のメモ目的です)

目的は、停止問題(制御が戻ってこない状態)になるのを防ぐ事。

具体的に、制御が戻らなくなるような原因には、以下の種類がある。

• ブロッキングの発生する入出力port。
• マクロの無限展開。
• do系の無限ループ(繰り返し条件が常に真)。
• letrec、named let、define系の無限ループ(無限再帰)。
• 循環リストや循環木構造由来の無限ループ(無限リストをwriteする等)。
• 継続実行による無限ループ
• Yコンビネータ(を生成する事のできるlambda)

単純に言えば、これら全てに何らかの対策を入れればよい、という事になる。

• 結構膨大なので、実際の作業は単純ではないが……。

ブロッキング以外の全ての無限ループは、間に監視procが入る事で、制御が戻らなくなる事を防ぐ事が出来る。

• 具体的には、

  (let loop ()
    (loop))
  

• では監視が入らないので制御は戻らないが、

  (let loop ()
    (監視proc呼び出し)
    (loop))
  

• ならば、監視proc内で大域(というかeval/sv)脱出の継続を呼び出して脱出できる。

よって、こまめに、あちこちに監視procの呼び出しを挿入する事が主な対策方法となる。

具体的には、それぞれ、以下のような対策を取る。

• ブロッキングの発生する入出力portは、eval/sv内には持ち込まないようにする。
• マクロは自前で一段階ずつ展開し、その毎回の展開毎に監視procを呼び出し、マクロ展開を途中で中断するかを選択できるようにする。
• do系、letrec系は、body部分に監視procをこっそり含める。
• 循環リストを受け取ると問題のある系は、以下のどちらかを行う。
  • 循環構造を持っていてもそれらしく機能するように自前で実装し直す。具体的には、writeであれば、pairの一部分を出力する毎に監視procを呼び出すようにする等。
  • リストが循環構造を持つかどうかを処理前にチェックし、循環構造を持っていた時はそれらしく対応する(エラー例外を投げる等)。
  • これが一番膨大で大変
• call/ccとlambdaは、生成された継続/手続きを実行する際にも、監視procによる監視が付くようにする。