継続

scheme

使いたい人のための継続入門にトライ。とりあえず例示されている以下の手続きの使い方がよく分からぬ。

(define (fact/cps n cont)
  (if (= n 0)
      (cont 1)
      (fact/cps (- n 1) (lambda (a) (cont (* n a))))))

cont に何を渡せば良いか、というと引数を一つ取る手続き。例示されているのは

gosh> (fact/cps 10 (lambda (a) (* 2 a)))

だと (* 2 (fact 10)) なソレと同じと書いてある。10 は微妙なので 5 あたりで。

(fact/cps 5 (lambda (a) (* 2 a)))
| (fact/cps 4 (lambda (a) ((lambda (a) (* 2 a)) (* 5 a))))
|| (fact/cps 3 (lambda (a) ((lambda (a) ((lambda (a) (* 2 a)) (* 5 a))) (* 4 a))))
||| (fact/cps 2 (lambda (a) ((lambda (a) ((lambda (a) ((lambda (a) (* 2 a)) (* 5 a))) (* 4 a))) (* 3 a))))
|||| (fact/cps 1 (lambda (a) ((lambda (a) ((lambda (a) ((lambda (a) ((lambda (a) (* 2 a)) (* 5 a))) (* 4 a))) (* 3 a))) (* 2 a))))
||||| (fact/cps 0 (lambda (a) ((lambda (a) ((lambda (a) ((lambda (a) ((lambda (a) ((lambda (a) (* 2 a)) (* 5 a))) (* 4 a))) (* 3 a))) (* 2 a))) (* 1 a))))

でいっちゃん最後の cont に 1 が渡されて評価。

((lambda (a) ((lambda (a) ((lambda (a) ((lambda (a) ((lambda (a) ((lambda (a) (* 2 a)) (* 5 a))) (* 4 a))) (* 3 a))) (* 2 a))) (* 1 a))) 1)

目視ベースですが、確かに階乗になっている。ちょっと不思議。でも継続渡しなソレは感じます。感じるのが大切なんだ (何
置き換えたら分かるな。もらった cont を適用する手続きをさらに lambda でくるんで渡してるのが継続渡しのナニだな。

gosh> (define (fact/cps n cont)
  (if (= n 0)
      (cont 1)
      (fact/cps (- n 1) (lambda (a) (cont (* n a))))))
fact/cps
gosh> (fact/cps 5 (lambda (a) a))
120
gosh> (* 1 2 3 4 5)
120
gosh>

続

で、現在出勤後の千代田図書館なんですが、宿で文書の先を読んでると identity 等という手続きがあるのを発見。なるほどね。

((lambda (a) a) 1)

は

(identity 1)

で良いんだ。なんか無知をサラケ出しているようでナニですがスルー。
実は以前にもこの文書はちらっと見たコトありまして、SICP のおかげなのかプログラミング Gauche のおかげ (どちらかと言えばこっちだと思う) なのかは不明ですが脳への入りが随分違う感触。
で、call/cc の解説に突入なんですが、プログラミング Gauche (今日は持ち歩いてない) とは違った切り口、なのかなぁ。

  • 最初に call-with-procedure を作るとしたら (って実装例もある
  • 次に call-with-continuation-procedure だとどうか
  • 最後に call-with-current-continuation

で、これが出てくる

;; fact/cpsをcall-with-continuation-procedureを使って定義する
(define (fact/cps n cont)
  (call-with-continuation-procedure cont (lambda (c) (c (fact n)))))

置き換えてみよう。call-with- は call/cp で短縮。ちなみに call/cp の定義は

;; call-with-continuation-procedureの定義
(define (call-with-continuation-procedure cont proc)
  (proc cont))

との事。では置き換えを

(fact/cps 5 (lambda (a) (* 2 a)))
|(call/cp (lambda (a) (* 2 a)) (lambda (c) (c (fact 5))))
||((lambda (c) (c (fact 5))) (lambda (a) (* 2 a)))
|||((lambda (a) (* 2 a)) (fact 5))
||||(* 2 (fact 5))

むむ。なんかボケてる感満点なんですがいいのかなぁ。一応きちんと置き換えれているようにも見えるんですが。
でもなんだかスラスラ読めるぞ。わははは。調子に乗って練習問題をヤッてみる。

;; 環境破壊実験の準備3
(define k #f)  ;; 継続保存用

(define x 1)   ;; 環境に定義

((identity +) x (call/cc (lambda (cont) (set! k cont) 2)) x)

で

;; 環境破壊
(set! x 10)
(set! + max)

;; さて結果は?
(k 2)
  1. はそのままで先頭の x は 1 だけどケツの x は 10 で戻りは 13?

答えは見ずに処理系で確認

gosh> (set! x 10)
10
gosh> (set! + max)
#<subr max>
gosh> (k 2)
10
gosh>

なにー。てコトは + は max になってしまったのか。あ、そうか_足す気満々_にダマサれた。よく考えたら + も変数なんだよな。k が束縛している継続は書き方違うかもしれんけど

(lambda (a) (+ 1 a x))

なのかなぁ。で、+ を見てみたら

gosh> +
#<subr max>
gosh>

なんですが、自分的には

(lambda (a) (#<subr +> 1 a x))

なんだと思っていた、というのがわし的な見方でした。ここまで書いて解説を見てみる。

解答見て

わははは。と笑うしかないカンジ。なんつーか凄い所に足ツッコンでる気がしてきた。次はパズルな模様。ここで一旦エントリ投入しとこ。でびあん勉強会な準備もしといた方が良さげ。

追記

パズル以降は帰りの飛行機でヤる事に。さくっと追い掛けてみたんですが頭がふらふらする。これは書きながらやらないと脳内ふんちゃらはわしのアタマでは無理ッス。