継続渡しによる階乗計算をトレースしてみる

Scheme

僕のカニみそ級の脳みそでは、無名関数が混じっていると混乱してしまうっぽいので、適当に名前を付けながらトレースしてみました。

(define fact/cps 
  (lambda (n cont)
    (cond
     ((= n 0) (cont 1))
     (else (fact/cps (- n 1) (lambda (m) (cont (* m n))))))))

(define cont (lambda (a) a))

のとき

(fact/cps 3 cont)

の評価過程を見ていきたいと思います。

(fact/cps 3 cont)
	-> (fact/cps 2 cont3)
		-> (fact/cps 1 cont2)
			-> (fact/cps 0 cont1)	;; 再帰の境界条件
			-> (cont1 1)
		-> (cont2 (* 1 1))
		-> (cont2 1)
	-> (cont3 (* 2 1))
	-> (cont3 2)

    

  • > (cont (* 3 2))
    • 

  • > (cont 6)
    • 

  • > 6
    •

...っと、こんな感じでしょうか。
ただし、cont3とcont2とcont1は

(define cont3 (lambda (v3) (cont (* 3 v3))))
(define cont2 (lambda (v2) (cont3 (* 2 v2))))
(define cont1 (lambda (v1) (cont2 (* 1 v1))))

となる関数です。

名前をつけたら混乱せずにたどれました。
ということで動きは理解できましたよ。