CPS 継続渡しスタイル がわかってきた。

range 関数を考える。

シンプルに、

(define (range a b)
  (if (> a b) 
      []
      (cons a (range (+ a 1) b))))

これは、最後に呼び出される関数が cons なので、末尾再帰ではない。

末尾再帰にすると、

(define (range a b l)
  (if (> a b)
      (reverse! l)
      (range (+ a 1) b (cons a l))))

これだと reverse! の分だけ遅くなるので、本当は逆から作るといい。

さあ、CPSだ！

(define (range a b cont)
  (if (> a b)
      (cont [])
      (range (+ a 1) b (lambda (x) (cont (cons a x))))))

本題はここから。
(lambda (x) (cont のあたりで、なんともいえない違和感を感じないか？

さて、(range 1 4 (lambda (x) (print x)))をほぐすと、

((lambda (x)
  ((lambda (x)
     ((lambda (x)
	((lambda (x)
	   ((lambda (x)
	      (print x))
	    (cons 1 x)))
	 (cons 2 x)))
      (cons 3 x)))
   (cons 4 x)))
 [])

となる。やはり違和感がある。
実はこれは、

((lambda (x) (print x))
 ((lambda (x) (cons 1 x))
  ((lambda (x) (cons 2 x))
   ((lambda (x) (cons 3 x))
    ((lambda (x) (cons 4 x))
     [])))))

を還元した形だ。ここまでなおすと、違和感が消える。それに、スタックに

cons 4
cons 3
cons 2
cons 1
print

と積んだ様子を、連想しやすい。

CPSだと強力な状態遷移機械（オートマトン）が作れる、コンパイラにとって重要だというのは、これが、スタックを使うプッシュダウン・オートマトンと同じだからだ。

CPSの修得が難しいのは、一段階還元された形を扱うために、違和感があるからだ。

CPSは、スタックをクロージャに保存しているだけともいえる。
最初のコレを見て ・・・(1)

(define (range a b)
  (if (> a b) 
      []
      (cons a (range (+ a 1) b))))

CPSのコレが ・・・(2)

(define (range a b cont)
  (if (> a b)
      (cont [])
      (range (+ a 1) b (lambda (x) (cont (cons a x))))))

イメージできるようになろう。
(1)は、範囲の長さ分、スタックを消費する。
(2)は末尾再帰だからスタックは消費しないが、範囲の長さ分、クロージャが作られる。
(1)と(2)の計算量のオーダーは同じだ。