#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) のうちから二つの数の和が素数になる組の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...という感じです。 * 実際の使用例 [#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]] *OCamlでcall/cc [#v1ede6b7] Leroyのcall/ccライブラリ http://pauillac.inria.fr/~xleroy/software.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]]