フィボナッチ数列のCPS(継続渡しスタイル)変換

以前書いたフィボナッチ数列のCPS変換について聞かれたので、改めて解説してみようと思う。

まずは普通の再帰版

;; List.1
(define (fib n)
  (if (or (= n 1) (= n 2))
      1
      (+ (fib (- n 1))
         (fib (- n 2)))))

この中で末尾再帰になっていない部分を取り出すと、

;; list.2
(+ (fib (- n 1))
   (fib (- n 2)))

これは次のように等価変換できる。

;; list.3
(let ((v1 (fib (- n 1))))
  (+ v1 (fib (- n 2))))

;; List.4
((lambda (v1)
   (+ v1 (fib (- n 2))))
 (fib (- n 1)))

後半が少し分かりにくいかもしれないけど、要するに

;; list.5
(define k
  (lambda (v1)
    (+ v1 (fib (- n 2))))
(k (fib (- n 1)))

と書き換えられるので、特別なことは何もない。これに限らず一般にletによる変数束縛と関数呼び出しは本質的に等価だ（詳しくはなんでもλを参照）。

ここからが少しトリッキーなところ。(List.5)では(fib (- n 1))を呼び出して、その戻り値を使ってkを呼び出していた。でも、kの呼び出しをfib関数の中でやってしまえば、この式全体はfib関数への呼び出しだけで済むはず。

イメージとしてはこうなる。

;; List.6
(k (fib (- n 1)))
↓
(fib (- n 1) k)

実際にこの変形を適用したものは、

;; List.7
(fib_cps (- n 1)
         (lambda (v1)
           (+ v1 (fib (- n 2)))))

(+ v1 (fib (- n 2)))の部分も同様に変形して

;; List.8
(fib_cps (- n 1)
         (lambda (v1)
           (fib_cps (- n 2)
                    (lambda (v2)
                      (+ v1 v2)))))

最後に全体と統合すると、次の式が得られる。

;; List.9
(define (fib_cps n k)
  (if (or (= n 1) (= n 2))
      (k 1)
      (fib_cps (- n 1)
               (lambda (v1)
                 (fib_cps (- n 2)
                          (lambda (v2)
                            (k (+ v1 v2))))))))

ただし、末尾文脈での本来の戻り値を引数として継続を呼び出す必要があることに注意。

CPS変換の別の例は2006/01/31の日記で少し解説しているので、興味があればそちらも参照のこと。