継続渡し形式

gauche

継続渡し形式が私にはよく理解できなかったので、細かく追って見ました.
http://practical-scheme.net/wiliki/wiliki.cgi?Scheme%3A%E4%BD%BF%E3%81%84%E3%81%9F%E3%81%84%E4%BA%BA%E3%81%AE%E3%81%9F%E3%82%81%E3%81%AE%E7%B6%99%E7%B6%9A%E5%85%A5%E9%96%80
上のリンクでは、例として二つの階乗計算が示されています.

;; 階乗の普通の定義
(define (fact n)
  (if (= n 0)
      1
      (* n (fact (- n 1)))))

;; 継続渡し形式の階乗の定義
(define (fact/cps n cont)
  (if (= n 0)
      (cont 1)
      (fact/cps (- n 1) (lambda (a) (cont (* n a))))))
;; 次の計算は同じ
(* 2 (fact 10))
(fact/cps 10 (lambda (a) (* 2 a)))

頭の中で、二つの計算を考えてみたものの…(^p^)あうあうあーっていう感じになってしました.
とりあえず、普通のfactから展開していきます.

(fact 3)
;; (* 3 (* 2 (* 1 1))) ∴3!

次は、継続渡し形式のfact/cpsを追って見ます。

  • n = 3 のとき
(fact/cps 3 (lambda(a) (* 2 a)))
;;call -> (fact/cps 2 (lambda(a) (* 3 a)))
;;cont -> (lambda (a) (* 2 a))
  • n = 2 のとき contの内容が変更されていることに注意
(fact/cps 2 (lambda(a) (cont (* 3 a))))
;;call -> (fact/cps 1 (lambda(a) (cont (* 2 a))))
;;cont -> (lambda (a) (cont (* 3 a)))
  • n = 1 のとき
(fact/cps 1 (lambda(a) (cont (* 2 a))))
;;call -> (fact/cps 0 (lambda(a) (cont (* 1 a))))
;;cont -> (lambda (a) (cont (* 2 a)))
  • n = 0 のとき
(fact/cps 0 (lambda(a) (cont (* 1 a))))
;;call -> (cont 1)

基底条件にnが達したので、(cont 1)がコールされます。このcontは、[n=1]のcontです。
contに1をいれていますので、(lambda(1)…)と等価です。

  • n = 1の時のcont
(lambda (1) (cont (* 2 1)))
;; -> (lambda (1) (cont 2))

このcontは、[n=2]のcontでした。こっからは、一気に見てきます。

(lambda (2) (cont (* 2 3))
;;      -> (lambda (2) (cont 6)
;; cont -> (lambda (a) (* 2 a))
(lambda (6) (lambda (* 2 6))) 
;; 　　　　-> 12

計算をおってみると、3!×2であることがわかりました。継続渡し形式で階乗の計算をしています。

contの内容が変化することに対応できずに初期値の(lambda(a)...)の値を
contの値と勘違いしていたために、(^p^)あうあうあーになってしまいました.