継続のバックアップ(No.5)

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
継続へ行く。
- 1 (2007-01-27 (土) 00:29:45)
- 2 (2007-01-27 (土) 00:29:45)
- 3 (2007-01-27 (土) 00:29:45)
- 4 (2007-01-27 (土) 00:29:45)
- 5 (2007-02-03 (土) 15:33:00)
- 6 (2007-02-03 (土) 15:33:00)
- 7 (2007-02-03 (土) 15:33:00)
- 8 (2007-02-03 (土) 15:33:00)

継続とは?
実際の使用例
- 参考文献
継続サーバ
Ocsigen OCamlによる継続ベースWeb programming framework.

継続とは? &dagger;

まず、大域脱出の例を見てみましょう。 SEND+MORE=MONEY でも、 return"ラベル"を定義して、

(return (list S E N D '+ M O R E '= M O N E Y))

なんてことをやっています。

リストlisと述語手続きpredを取り、lisの各要素に順にpredを適用して、 predが真の値を返したら直ちにその要素を返すような関数findはこう書きます。

(define (find pred lis)
  (call/cc
    (lambda (return)
      (for-each (lambda (elt) (if (pred elt) (return elt))) lis)
      #f)))

lambda (return) はちょっと奇妙です。私は脳内で、

(define (find pred lis)
  (let/cc
   return
   (for-each (lambda (elt) (if (pred elt) (return elt))) lis)
   #f))

と読んでいます。

この継続を、グローバル変数などに保存しておくこともできます。例えば、継続ccを取り出して、グローバル変数 k に保存してみましょう。

(define k #f)

(+ 1 (call/cc (lambda (return)
	 	(set! k return)
		 (return 1))))
= 2

return、および k には、あそこに戻る継続が入っています。それで、

(k 10)
= 11
(k 50)
= 51

になります。

継続というのは、計算のスタックを取り出したものです。ここのスタックは、

<>
1
+

でした。そして、 return = k = (+ 1 <>) です。lambda式で書くと return = k = (lambda (x) (+ 1 x)) です。

実は、計算のスタックは、lambda式で書きなおすことができます。

(print (+ 1 2)) = ((lambda (x) (print x)) ((lambda (x) (+ 1 x)) 2))
(* 3 (+ 1 2)) = ((lambda (x) (* 3 x)) ((lambda (x) (+ 1 x)) 2))

スタックのコピーである継続がなぜlambda計算から自然と生まれたのか、わかる気がします。

↑

発展学習 CPS "Continuation Passing Style" 継続渡しスタイル &dagger;

さきほどの"計算のスタックをlambda式で書き直す"は、CPSと呼ばれる書きかたです。 range 関数を書いてみます。 range 0 9 = (0,...,9)

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

(print (range 0 2)) のスタックはこうなるでしょう。

[]
cons 2
cons 1
cons 0
print

lambda式で書き直すと、

((lambda (x) (print x)) ((lambda (x) (cons 0 x)) ((lambda (x) (cons 1 x)) ((lambda  (x) (cons 2 x)) []))))

となります。

継続渡しスタイルは、このlambda (x)流の書きかたを陽にする書きかたです。 range 関数はこうなります。

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

実際に (range 0 3 (lambda (x) (print x))) と実行してごらんなさい。

ときほぐすと、

((lambda (x) (print x)) ((lambda (x) (cons 0 x)) ((lambda (x) (cons 1 x)) ((lambda (x) (cons 2 x)) []))))

と等しくなることを確かめなさい。

この k に入っているものこそ、継続です。

↑

何ができるの? &dagger;

大域脱出
例外処理
コルーチン(軽量スレッド)

↑

天使のオペレータ amb &dagger;

非決定性

amb@Wiliki

例えば、
(let ((i (amb 4 6 7))
       (j (amb 5 8 11)))
  (if (prime? (+ i j))
       (list i j)
       (amb)))
;Value 23: (6 5)
のようにすると '(4 6 7) と '(5 8 11) のうちから二つの数の和が素数になる組の１つを返します。

これを理解するのに、自分は3ヶ月かかりました。 ambは、バックトラック演算子です。動きを大雑把に言うと、

(let (i (amb 4 6 7))で、 i に 4 が入ると同時に、この時点のツヅキ、

		"6 7))
     (j (amb 5 8 11)))
 (if (prime? (+ i j))
     (list i j)
     (amb)))"

を取り出して、スタックにpush。

次の行、 (j (amb 5 8 11))で、 j に 5が入ると同時に、この時点のツヅキ、

		"8 11)))
 (if (prime? (+ i j))
     (list i j)
     (amb)))"

を取り出して、スタックにpush。

(prime? (+ 4 5))は偽。(amb)が動く。amb関数は、引数なしで呼ばれると、スタックをpopして、中身の、ツヅキを実行。

		"8 11)))
 (if (prime? (+ i j))
     (list i j)
     (amb)))"

が実行されて、jに8が入ると同時に、この時点のツヅキ、

		  "11)))
 (if (prime? (+ i j))
     (list i j)
     (amb)))"

を取り出して、スタックにpush...という感じです。

↑

実際の使用例 &dagger;

論理パズル(カロタンパズルや地図の塗り分け)が紹介されています

SEND+MORE=MONEY [#x0d17572]

(use srfi-1)

;; stack of cc.
(define fail '())

;; nondeterminsm operator
(define (amb li)
  (if (null? li)
      ((pop! fail))
      (call/cc
       (lambda (cc)
	  (push! fail (lambda ()
		        (cc (amb (cdr li)))))
	  (car li)))))

(define (toint li)
  (fold (lambda (a b) (+ a (* b 10))) 0 li))

(define (solve)
  (let ((digs (iota 10 0))
         (digs1 (iota 9 1)))
    (let* ((S (amb digs1))
            (E (amb (lset-difference = digs (list S))))
            (N (amb (lset-difference = digs (list S E))))
            (D (amb (lset-difference = digs (list S E N))))
            (M (amb (lset-difference = digs1 (list S E N D))))
            (O (amb (lset-difference = digs (list S E N D M))))
            (R (amb (lset-difference = digs (list S E N D M O))))
            (Y (amb (lset-difference = digs (list S E N D M O R)))))
      (if
       (= (+ (toint (list S E N D))
              (toint (list M O R E)))
          (toint (list M O N E Y)))
       (list S E N D '+ M O R E '= M O N E Y)
       (amb '())))))

(print
 (call/cc
  (lambda (cc)
    ;; initial value for fail
    (push! fail
	    (lambda ()
	      (cc 'no-choise)))
    (solve))))

↑

参考文献 &dagger;

↑

継続サーバ &dagger;

↑

Ocsigen OCamlによる継続ベースWeb programming framework. &dagger;

論文 Typing web interaction with Objective Caml
継続ベースWebプログラミング Continuation-based Web programming
XHTMLの静的チェック Static checking of XHTML
セッションの自動管理 Automatic management of sessions
モジュール指向 Concise and modular programming
Webサーバ、実装は協調スレッドによる。 Web server, implemented with cooperative threads
カウンタはこう書けます。

let compt = 
  let next =
    let c = ref 0 in
      (fun () -> c := !c + 1; !c)
  in
  register_new_service 
    ~url:["compt"]
    ~get_params:unit
    (fun _ () () ->  return
      (html
       (head (title (pcdata "counter")) [])
       (body [p [pcdata (string_of_int (next ()))]])))

See this example here

継続 のバックアップ(No.5)