継続 のバックアップソース(No.8)

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• バックアップ を表示
• 継続 へ行く。
  • 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)

#contents
*継続とは?[#y87e71e0]

まず、大域脱出の例を見てみましょう。
[[SEND+MORE=MONEY:http://tsukimi.agusa.i.is.nagoya-u.ac.jp/~sydney/ocaml/index.php?%A5%CD%A5%BF%B5%AD%CF%BF%B8%CB#if874cf2]]
でも、
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" 継続渡しスタイル [#r00582eb]

さきほどの"計算のスタックを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 に入っているものこそ、継続です。
バトー、忘れないで。あなたがプログラムを書くとき、継続は必ずあなたの側にいる。

**何ができるの? [#c933f2be]
- 大域脱出
- 例外処理
- コルーチン(軽量スレッド)
**天使のオペレータ amb [#u2719f75]
- [[非決定性:http://www.shido.info/lisp/scheme_amb.html]]
- [[amb@Wiliki:http://www.shiro.dreamhost.com/scheme/wiliki/wiliki.cgi?amb]]
 例えば、
 (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...という感じです。
* 実際の使用例 [#s806e503]
- 論理パズル(カロタンパズルや地図の塗り分け)が[[紹介されています:http://www.sampou.org/scheme/t-y-scheme/t-y-scheme-Z-H-16.html#node_chap_14]]
- 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))))
**参考文献 [#vf61a3fe]
-[[SICP.Nondeterministic Computing:http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-4.html#%_toc_%_sec_4.3]]
-[[独習 Scheme 三週間:http://www.sampou.org/scheme/t-y-scheme/t-y-scheme-Z-H-16.html#node_chap_14]]
-[[なんでも継続:http://www.shiro.dreamhost.com/scheme/docs/cont-j.html]]
-[[Scheme:なぜSchemeにはreturnが無いのか:http://www.shiro.dreamhost.com/scheme/wiliki/wiliki.cgi?Scheme%3a%e3%81%aa%e3%81%9cScheme%e3%81%ab%e3%81%afreturn%e3%81%8c%e7%84%a1%e3%81%84%e3%81%ae%e3%81%8b]]
-[[Schemeを作ろう 第3回:http://www.jah.ne.jp/~naoyuki/Writings/VScheme3.html]]
-[[Scheme入門 継続:http://www.shido.info/lisp/scheme_cc.html]]
- 継続には副作用がある。
[[Scheme:call/ccと副作用:http://www.shiro.dreamhost.com/scheme/wiliki/wiliki.cgi?Scheme%3acall%2fcc%e3%81%a8%e5%89%af%e4%bd%9c%e7%94%a8]]
-[[名大の謎の天才h003149b氏:http://www.ice.nuie.nagoya-u.ac.jp/~h003149b/lang/index.html]]

*継続サーバ [#z633f1a1]
-[[もとネタになった、Queinnec氏の論文PDF:http://www-spi.lip6.fr/~queinnec/PDF/webcont.pdf]]
-[[境界を越える: 継続とWeb開発、そしてJavaプログラミング:https://www-06.ibm.com/jp/developerworks/java/060412/j_j-cb03216.shtml]]
-[[継続サーバの実装の最先端、Seaside:http://www.seaside.st/]]
-[[Seasideの開発者が継続のゆくえについて語る:http://smallthought.com/avi/?p=14]]
-[[Haskellの継続サーバWASH:http://www.informatik.uni-freiburg.de/~thiemann/haskell/WASH/]]
-[[SchemeによるCPSスタイルの継続サーバKahua:http://www.kahua.org/]]
-[[WebBasedアプリケーションと継続について、わかりやすい説明:http://www.shiro.dreamhost.com/scheme/wiliki/wiliki.cgi?Scheme%3aCPS]]
* [[Ocsigen:http://www.ocsigen.org/]] OCamlによる継続ベースWeb programming framework. [#pa3f7bb9]
- [[論文 Typing web interaction with Objective Caml:http://www.pps.jussieu.fr/~balat/publications/2006mlworkshop-balat-ocsigen.pdf]]
- 継続ベース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:http://www.ocsigen.org/tuto/compt]]