Document

継続と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）

Download Report