継続とは? †

まず、大域脱出の例を見てみましょう。 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))

と読んでいます。

この継続を、グローバル変数などに保存しておくこともできます。 例えば、継続returnを取り出して、グローバル変数 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) のうちから二つの数の和が素数になる組の1つを返します。 

これを理解するのに、自分は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;

OCamlでcall/cc &dagger;

Leroyのcall/ccライブラリ http://pauillac.inria.fr/~xleroy/software.html があります。

継続サーバ &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


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2007-11-27 (火) 23:40:12 (4711d)