Tokuda Lab. NISHIMURA Taichi 継続と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変換の例 末尾再帰になっている cont（残りの計算＝継続）に identityを与えればfactと等価 (define (fact n) (if (= n 0) 1 (* n (fact (- n 1))))) (define (fact/cps n cont) (cont 1) (fact/cps (- n 1) (lambda (a) (cont (* n a)))))) cont（残りの計算＝継続）に identityを与えればfactと等価 　　　末尾再帰になっている

継続の保存 (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))

継続の保存 1つずつ解を取り出すことができる (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 1つずつ解を取り出すことができる

明示的に継続を生成する Schemeではcall/cc、あるいはcall-with-current-continuationを使う > (+ (* 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)))) > (cont 2) 4 > (cont 5) 7

明示的に継続を生成する例 リストの2つ目の要素は contに与えられた値がそのまま返る x=0という束縛は > (define x 0) > (define y 2) > (define cont #f) > (list x (call/cc (lambda (c) (set! cont c) 1)) y) (0 1 2) > (cont 3) (0 3 2) > (set! x 4) > (set! y 6) (0 3 6) リストの2つ目の要素は contに与えられた値がそのまま返る x=0という束縛は 継続contに含まれているので変化なし 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）