Syntax highlighter

2016-12-19

トップレベルの継続

この記事はLisp Advent Calendar 2016の19日目の記事です。

最近c.l.s.に面白い投稿があった。これである。 要約をすると、R7RSに以下の一文を追加しようという話になる。
It is an error to invoke the continuation of a top-level expression or the expression of a top-level definition more than once.
[訳]トップレベルの式もしくは定義の継続を二度以上起動することはエラーである。
この一文を入れる根拠が以下のコードになる(行の関係上短縮記述を使う)。
(define-library (foo)
  (import (scheme base))
  (export reload count)
  (begin
    (define counter (vector 0))              ;; (1)
    (define (count) (vector-ref counter 0))  ;; (2)
    (define reload (call/cc (lambda (k) k))) ;; (3)
    (vector-set! counter 0 (+ 1 (count)))))  ;; (4)

(import (scheme base) (scheme write) (foo))  ;; (5)

(unless (>= (count) 10)
  (display (count))
  (newline)
  (reload reload))
  
;; end of the file
トップレベルの継続はいろいろ落とし穴があるが、確かにこれはという感じものである。では、何が問題になるのか見ていこう。

継続とは

継続はSchemer以外のLisperには馴染みのない概念かもしれないので簡単に説明しておく。Schemeの仕様書を読むとなんとも面倒な言葉で書かれているが、厳密には多少違うが言ってしまえばコールグラフのことである(Clojure/Conjではスタックだと断言していた。まぁその通りである。)。 上記のコードでは以下のようにプログラムが実行される:
  (??) --> (1) --> (2) --> (3) --> (4) --> (??)
                          ^^^^^
                           捕捉
call/ccは上記のコールグラフで捕捉と書かれた部分の継続をreloadという大域変数に保存している。reloadを起動することによって(4)からの処理を再開することができる。

問題

さて、上記のコールグラフで何が問題になるのだろう?(5)があるのにわざわざ(??)書いたのには理由がある。この部分はとても曖昧なのだ。

例えばこのプログラムが1ファイルに書かれていたとしよう。そして、処理系は一つの式を読み込み、実行という順序でファイルを処理したとする。この場合に(??)にくるのは次の式を読み込むという処理になるはずだ。そうすると、保存したreloadを起動した際に起きると予測されるのは、コメント;; end of the fileが読み込まれEOFが返されることであると言える(注:unlessから始まる式は既に読まれている)。ファイルの読み込みがEOFを返した場合、通常そのファイルは全て実行されたと解釈されるので、処理は終了するのが筋である。とすれば、この継続をこの位置で起動すると処理が終了すると言える。(必ずしも処理が終了するわけではないことに注意)

さて、c.l.s.の投稿ではLarcenyで上記のプログラムを走らせた場合想定通りに動いたとされている。これはどういうことか?簡単に言えばLarcenyはvan Tonderの展開器を使っているからとなる。もう少し突っ込んで解説をすると、van Tonderの展開器はR5RS上でポータブルにライブラリ機能を追加している。R5RSにはライブラリ機能は存在しないので実行時になんとかやっているわけだ。例えば上記のプログラムは概ね以下のように解釈される。
(begin
  (let ()
    (define counter ...)
    (define (count) ...)
    (define reload ...)
    (vector-set! ...)
    (register-library '(foo) ...)
  )
  (resolve-import ...)
  (unless (>= (count) 10) ...))
このようにプログラムが展開された場合、(??)に当たる部分は何になるだろうか?そう、(register-library ...)の部分である。そして、プログラム全体が一つの式として解釈されているので、次の式を読み込む必要がない。これによりLarcenyでは見かけ上期待した結果が帰ってくるということになる。この問題はこの2つだけが予測される結末ではないのが面白いところである。

インポート

ライブラリはインポートされることで使用可能になる。では、ライブラリの定義が別ファイルにあった場合はどうなるのだろう?ここからは完全に処理系依存の挙動になるので、拙作Sagittariusの挙動はこうなるであろうというのを例に上げる。Sagittariusではライブラリが別ファイルにあった場合、import句がライブラリのコンパイル等を解決する。その際、現状では継続の境界を作る。

継続の境界とは、C側でSchemeのプログラムをCのスタックをまたぐように呼び出す際に作られるある種の境界線のことである。これが発生しかつ、継続の起動がこの境界をまたぐとSagittariusではエラーを投げる。つまり、ファイルがわかれている場合のケースではSagittariusではエラーになる。他の処理系ではエラーにならないかもしれない。

REPL

REPL上ではどうだろうか?REPLでは(vector-set! ...)が実行された後に次の式を読み込むために一旦制御が入力待ち状態になる。つまり、reloadの起動は(vector-set! ..)を実行し入力待ちの状態になるはずである(少なくともSagittarius上ではそうなる)。これももちろんREPLの実装依存になるだろう。

まとめ

トップレベルの継続を捕捉するのはいろいろ落とし穴がある。R7RSに上記の文言が追加された方が幸せになれるかもしれない。

No comments:

Post a Comment