末尾呼出し最適化 - Scheme VM のお勉強

scheme

末尾呼出し最適化はコンパイル時に行われている。
末尾か？どうかの判定に tail? を定義。

(define (tail? next)
  (and (pair? next) (eq? (car next) 'return)))

next expression が return であれば末尾と判定する。分かりやすい。
理解のために実際に最適化 ON / OFF で何が違うのかを見比べてみる。

((lambda (a) ((lambda (b) 3))) 4)
=>
(frame () (constant 4 (argument (close (a) (close (b) (constant 3 (return)) (apply)) (apply)))))                   ;; 最適化 ON
(frame () (constant 4 (argument (close (a) (frame (return) (close (b) (constant 3 (return)) (apply))) (apply)))))  ;; 最適化 OFF

ぱっと見 frame / return が1つ減っていることが分かる。
なぜ減らしてもうまくいくのだろう？
分かったけど言語化が難しい。
ポイントは

  • 末尾なので「呼出し元の戻り値=今から呼び出す手続きの戻り値」であること
  • 手続き呼出しではなく、その場に body があるかのように実行できる
  • 「すかし」ができる

ということかな。

しかし VM になると物事がシンプルになるね。
楽しいし好きだ。