Schemeコンパイラで、ある種の継続をsetjmpに置き換える

3impの4.7節「できそうな改善」の4.7.5項「継続をその場ジャンプにする」という項目を実装した。これはスコープ内での変数の使われ方を調べられれば、結構簡単に実装できる。

call/ccで渡された継続が呼び出しだけで、引数として使われていない場合には、関数呼び出しの内部から外部に脱出するケースしか発生しないので、通常の継続で必要となる、スタックのコピーと復元をしなくてもスタックポインタやフレームポインタを戻して次の命令から実行を再開すればよい。

論文には「単なるgoto」と書いてあって、実際に抜けたあとの飛び先もコンパイル時に決定するけれど、末尾呼び出しで引数がシフトされてスタックをいじった場合にスタック操作が煩雑になるので自分の実装ではそこまでしてなくて、新しいコールフレームを作って（コールフレームには戻り先とフレームポインタと現在のクロージャが保持されている）Cのsetjmp ~ longjmpのような形で実現した。

さらにいえば、継続が内部で使われていないことがわかれば、そのsetjmpも完全に省くことができる。なので例えばC言語のfor文っぽいマクロ

;; C言語のようなforマクロ
(defmacro for (var start end &rest body)
  `(call/cc
    (lambda (break)
       (let continue ((,var ,start))
            (when (< ,var ,end)
              ,@body
              (continue (+ ,var 1)))))))

;; 使用例
(for i 0 10
     (when (eq? i 5)
       (break))
     (print i))

を作って勝手にcall/ccを挟むマクロを書いても、breakを使用しない限りノーペナルティーだし、使ったところで実行時のmallocは発生しないので、心理的負担が軽く使える。素晴らしい。

追記

簡単なテストしかしてなかったのでいろいろダメだった。

新しいコールフレームにしてしまうと新しいクロージャを作る必要があって、自由変数のキャプチャとかが必要になってしまいmallocが発生してしまう。なのでコールフレームはcall/cc呼び出し時点でのものを拡張して使うほうがよい。

飛び先はスタック上におけるのかもしれないけど、そうした場合には余分にスタック上に格納しておく必要がある。

フレームポインタはスタックポインタの値と合成して１つの整数にできるかもしれないけど、実行中のクロージャはやはりスタック上にとっておく必要があるな。

末尾呼び出しでスタックがずれることはは考える必要がない（それまでの引数がシフトされてしまうようであればcall/ccで渡された継続もなくなっているはずなので、longjmpは呼び出されない）けど、スコープの拡張が起こるとスタック上の配置がずれてしまうので、やはり調整が必要。それにはlongjmp呼び出し地点とsetjmp地点のズレを計算するか、あらかじめスコープで使われるローカル変数をすべて計算してスタック配置を計算しておく必要がある。

追記２

継続が内部のスコープに補足される場合には、末尾呼び出しでSETJMPを保持しているフレームがなくなってしまう可能性があってやはりまずかった。

じゃあっつって自由変数としてキャプチャされる場合はSETJMP ~ LONGJMPじゃなくて普通の継続にする、としてしまうと、ループ構文は字面的にはキャプチャが発生してしまうので、ループ内部から脱出しようとするだけで通常の継続になってしまって、嬉しくない。

なので現在のところ、問題あるケースはあるが稀だろうということで、とりあえず実装してみた。