(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の本質が掴めてない。
