きくらげ観察日記

好きなことを、適当に。

CPS変換についての覚え書き

CPS(継続渡しスタイル)とは、関数自体に「その後の処理」を引数として渡してしまうような書き方です。

例:

;; 点(x . y)のノルムを求める
(define (norm x y)
  (sqrt (+ (expt x 2) (expt y 2))))

(norm 1 1) ; => 1.414...

;; normのcps版
(define (norm/cps x y cont)
  (expt/cps x 2 (^(x^2)
    (expt/cps y 2 (^(y^2)
      (+/cps x^2 y^2 (^(norm^2)
        (sqrt/cps norm^2 cont))))))))

(norm/cps 1 1 (^(n) ; => 1.414...
  ...))

実際はsqrt/cpsやらも定義してやらなければなりませんが、とりあえずイメージということで。



これって機械的に変換できるものなのでしょうか?
例えばソースコード中に現れるすべてのdefineとlambdaに対して

(define (hoge x y z) e1 e2 ... en)
;; ↓CPS変換
(define (hoge/cps x y z cont) (e1/cps (^(_) (e2/cps (^(_) ... (en/cps cont))))))

(lambda (x y) e1 e2 ... en)
;; ↓CPS変換
(lambda (x y cont) (e1/cps (^(_) (e2/cps (^(_) ... (en/cps cont))))))

のように変換していけばいいのでしょうか?
(lambda (x . args) ...)みたいな関数が出てきたときのためにcontは引数の頭にしておいたほうがいいとかいう話はおいておくとして。



こうして変換していく過程を見ていると、ほとんどモナドのdo記法から>>=を使った記法への変換と同じであることが分かりますね。