継続渡しとコンパイル(2)〜末尾再帰の場合

前のエントリでループの度にヒープにクロージャを生成しているのが無駄だと思う人がいるかもしれないが、それは例に挙げた関数が末尾再帰になっていないからだ。継続渡しは末尾再帰の時に最も真価を発揮する。
というわけで階乗計算の末尾再帰版。

(define (fact_tailrec n)
  (define (fact-aux n r)
    (if (> n 1)
        (fact-aux (1- n) (* n r))
        r))
  (fact-aux n 1))

これを継続渡しスタイルにしたものがこれ。

(define (fact_tailrec_cps n k)
  (define (fact-aux n r k)
    (if (> n 1)
        (fact-aux (1- n) (* n r) k)
        (k r)))
  (fact-aux n 1 k))

さらにこれを前のエントリと同様の規則で変換すると、

fact_tailrec_cps:
        (r1, r2, r3) := (r1, 1, r2)
        jmp fact-aux

fact-aux:
        r0 := r1 - 1
        if (r0 <= 0) jmp L1
        r0 := r1 - 1
        r4 := r0
        r0 := r1 * r2
        r5 := r0
        (r1, r2, r3) := (r4, r5, r3)
        jmp fact-aux

L1:
        (r1) := (r2)
        jmp r3

なんと、このように本物のループになってしまった（大げさ）。
ということで、継続渡しスタイルは効率が悪いというのは正しくない。