CPS変換の練習をしてみた

(define (foldr fun x args) (if (null? args) x (fun (car args) (foldr fun x (cdr args))))) を、CPS変換して末尾再帰にしようとした記録。

このページ なんでも継続 を参考にする。

foldr 自身より外側にある関数適用は fun であることを意識してやると、ちょっと簡単になった。

概形

(define (foldr/cps fun x args cont) (if (null? args) (cont x) ; something... ))

変換後に最も外側に来る関数は foldr/cps である(というかそれが目的)。

(define (foldr/cps fun x args cont) (if (null? args) (cont x) (foldr/cps fun x (cdr args) ; something... ))

最後に計算される(=最も外側の) fun に、内側の foldr の結果(res とする)を渡せば最終結果となる。
最終結果は外側の foldr の引数 cont に渡して(渡されて)終了となる。

; 最終的に(たぶん最後らへんに)実行されてほしい式 (cont (fun (car args) res))

最終的に内側の foldr/cps の第4引数(cont)が実行されることになるが、cont は手続きであるから、上の式を lambda で包む。
また、内側の foldr の計算結果(res)は、この lambda (内側の foldr から見た第4引数 cont)へ引数として渡されることに注意。

; 内側の foldr/cps の第4引数(cont) (lambda (res) (cont (fun (car args) res)))

合体！もうほとんどできてる。

(define (foldr/cps fun x args cont) (if (null? args) (cont x) (foldr/cps fun x (cdr args) (lambda (res) (cont (fun (car args) res))))))) ))

これで完成！

(define (foldr/cps fun x args cont) (if (null? args) (cont x) (foldr/cps fun x (cdr args) (let ((a (car args))) ; lambdaの中に(car args)を入れると計算が遅延されてしまう気がした (lambda (res) (cont (fun a res))))))) ))

ちょちょいと動かしてみたが、どうやら正しく動作してるっぽい。保証はできないけど。

結論。俺は説明が下手だ。あと、たぶんCPSの本質が掴めてない。