継続とWebアプリケーション Tokuda Lab. NISHIMURA Taichi 目次 継続とは何か 継続の応用 継続とWebアプリケーション 継続(Continuation)とは 現在の処理を続行するための情報 広義ではC言語の関数の戻りアドレスも継続 の一種 setjmp/longjmpのjmp_buf 演算レジスタ プログラムカウンタ スタックポインタ etc 狭義の継続 Schemeにおける継続はCのlongjmpよりもずっと 強力 ファーストクラスのクロージャによって環境を閉じ込め られる 当然スタックに依存しない 続行後の処理そのものを継続という事も多い Scheme(R5RS)の定義 「Schemeの式が評価される時、そこには評価の結果 を待つ継続が一つ待機している。継続は計算の(デ フォルトの)未来全体を表している」 CPSとは CPS: Continuation Passing Style (継続渡し形式) 「プログラムの残りの計算」を引数に取る関数を 作る形式 この引数がすなわち「継続」 任意の再帰関数はCPSに変換できる CPSは末尾再帰 CPS変換によって継続が明示的になる 関数呼び出しが一続きの鎖になる CPS変換の例 (define (fact n) (if (= n 0) 1 (* n (fact (- n 1))))) cont(残りの計算=継続)に identityを与えればfactと等価 (define (fact/cps n cont) 末尾再帰になっている (if (= n 0) (cont 1) (fact/cps (- n 1) (lambda (a) (cont (* n a)))))) 継続の保存 (define (match data pred cont) (cond ((null? data) (cont #f #f)) ((pred (car data)) (cont (car data) (lambda () (match (cdr data) pred cont)))) (else (match (cdr data) pred cont)))) (define (find-odd data) (match data odd? (lambda (found cont) (if found (begin (format #t "found:~s~%" found) (cont)) (format #t "end.~%"))))) (find-odd '(0 1 2 3 4 5)) 継続の保存 (define next #f) (define (find-odd-1 data) (match data odd? (lambda (found cont) (if found (begin (format #t "found:~s~%" found) (set! next cont)) (begin (format #t "end.~%") #f))))) gosh> (find-odd-1 '(0 1 2 3 4 5)) found:1 #<closure (match #f)> gosh> (next) found:3 #<closure (match #f)> 1つずつ解を取り出すことができる 明示的に継続を生成する Schemeではcall/cc、あるいはcall-with-currentcontinuationを使う > (+ (* 1 2) (call/cc (lambda (c) (* 3 4)))) 14 > (+ (* 1 2) (call/cc (lambda (c) (* 3 (c 4))))) 6 > (define cont #f) > (+ (* 1 2) (call/cc (lambda (c) (set! cont c) (* 3 4)))) 14 > (cont 2) 4 > (cont 5) 7 明示的に継続を生成する例 > (define > (define > (define > (list x (0 1 2) x 0) y 2) cont #f) (call/cc (lambda (c) (set! cont c) 1)) y) > (cont 3) (0 3 2) リストの2つ目の要素は contに与えられた値がそのまま返る > (set! x 4) > (cont 3) (0 3 2) x=0という束縛は 継続contに含まれているので変化なし > (set! y 6) > (cont 3) (0 3 6) yの値は新しく読み出すので変化する 継続の応用例(大域脱出) (define (sumup x) (call/cc (lambda (cont) (letrec ((sum-aux (lambda (y) (cond ((null? y) 0) ((not (number? (car y))) (cont (car y))) (#t (+ (car y) (sum-aux (cdr y)))))))) (sum-aux x))))) > (sumup '(1 33 4 0 3 7)) 48 > (sumup '(1 0 -1 a 7)) a リストの要素の合計を返す ただし、 数値以外が含まれていた場合は その要素を返す 継続の応用 大域脱出は便利 例外処理とほぼ同じ longjmpも例外処理とほぼ同じ 唯一のまともな継続の応用 継続のサンプルコードは大域脱出がほとんど でもそれだけではない Webアプリケーション 一般的に、ページ毎にプロセス生成 ステートレスなので状態を保つのは大変 セッションから状態を復帰 セッションに状態を保存 Cookie、hiddenフィールド 「戻る」ボタンの存在 継続サーバの Webアプリケーション 各リクエストの処理後に継続をキャプチャ IDを付けてセッションに保存 次のリクエストの処理前に継続に復帰 ステートフルだから自然なプログラムが書ける 欠点 重い 部分的継続によってある程度は解決可能 ユーザが慣れるのに時間がかかるかも 継続サーバの例 Kahua(Scheme) Seaside(Smalltalk) Iowa,Wee(Ruby) Continuty(Perl)
© Copyright 2024 ExpyDoc