末尾呼出し - Scheme VM を書く
(let* ([g (lambda (x) x)] [f (lambda (a) (g a))]) (f 2))
f における g の呼出しは末尾呼出し。
g を call する直前にはもはや f の引数はスタックに積まれている必要がなくて、g の引数だけが積まれていれば良い。
これを実現するには g の引数をスタック上で f の引数を上書きする方向に shift すればよい。
スタックのレイアウトの順が引数が後に積まれるスタイルだからこの方法が簡単に実現できる。
コンパイラの変更は2つ。
- 末尾呼出しでは frame 命令を差し込まない
- 末尾呼出し時には新しい引数を shift する shift 命令が生成される
VM の変更は1つ。shift 命令のサポート。
早速試してみよう。上に挙げたコードは let* を使っているが lambda で書き直しておく。
((lambda (g) ((lambda (f) (f 2)) (lambda (a) (g a)))) (lambda (x) x))
コンパイル結果。
;; 以前のコード (frame () (close 0 (refer-local 0 (return 1)) (argument (close 0 (frame (return 1) (refer-local 0 (argument (close 1 (frame (return 1) (refer-local 0 (argument (refer-free 0 (apply))))) (argument (close 0 (frame (return 1) (constant 2 (argument (refer-local 0 (apply))))) (apply))))))) (apply))))) ;; 末尾呼出し最適化コード (frame () (close 0 (refer-local 0 (return 1)) (argument (close 0 (refer-local 0 (argument (close 1 (refer-local 0 (argument (refer-free 0 (shift 1 1 (apply))))) (argument (close 0 (constant 2 (argument (refer-local 0 (shift 1 1 (apply))))) (shift 1 1 (apply))))))) (apply)))))
