(call/cc (lambda (cont) (cont 知見)))
-
Upload
susisu -
Category
Engineering
-
view
204 -
download
5
Transcript of (call/cc (lambda (cont) (cont 知見)))
( c a l l / c c ( l a m b d a ( c o n t ) ( c o n t 知見 ) ) )
2 0 1 5年1 0月1 8日 第2回 O U C C LT会
おまえか
• すしす
• アレ系
• ヒwiヒヒer: @susisu2413
• GitHub: susisu
• Scheme 素人です
継続
• "継続(けいぞく、continuation)とは、プログラムの実行においてある時点において評価されていない残りのプログラム(the rest of the program)を意味するものであり、手続き(procedure)として表現されるものである。"
継続 - Wikipedia https://ja.wikipedia.org/wiki/
%E7%B6%99%E7%B6%9A
殺伐としたスライドに S 式が
(+ 1 2)
2 から見た継続
(+ 1 (...))
ラムダ式では
(lambda (x) (NEXT (+ 1 x) ))
NEXT はそこで評価を終了する仮想の処理
c a l l / c c
• 略さずに言うと call-with-
current-continuation
• 現在の継続を引数として,
与えられた関数を呼び出す
• 継続はただの関数なので,
保存しておいて, 別の場所から呼び出すことも可能
(+ 1 2)
2 を c a l l / c c の式で置き換えてみる
(+ 1 (call/cc (lambda (cont) (cont 2)) ))
c a l l / c c の引数 (関数 ) に渡される継続
(+ 1 (...))
ラムダ式では
(lambda (x) (NEXT (+ 1 x) ))
つまりこういうこと
(+ 1 ( (lambda (cont) (cont 2)) (lambda (x) (NEXT ( (+ 1 x) ))) ))
評価を進める
(+ 1 (NEXT (+ 1 2) ))
3
何に使えるのか
• ループ脱出 (break)
• 例外処理 (throw)
• コルーチン (yield)
• return, goto, etc.
• 要は突入と脱出
つよい
実装した
どういう実装
• https://github.com/susisu/js-sandbox/blob/master/continuation/src/v2.js
• AST インタプリタ in JavaScript
• 基礎は前回の LT で発表したものの流用
http://susisu.hatenablog.com/entry/2015/07/12/142250
• Scheme の例をいくつか試したところ期待通りに動作したので、たぶん上手くいっている
継続の生成 (単純化したもの )
• 式 Expr
• 式の評価 eval : Expr → Res ― 厳密には環境も必要
• 評価結果 Res = Ok Val ― 成功
| Cont Val (Res → Res) ― 継続
| Next Val ― 評価終了
継続の生成
• 例えば、複数の式を順番に評価するような式
e = (e1 : Expr, e2 : Expr, ..., eN : Expr) : Expr
r = eval e, ri = eval ei ― 評価結果
• ri = Ok v ⇒ ei+1 以降の評価を続ける, i = N ならば r = Ok v
• Cont f c ⇒ r = Cont f ((λx → eval ([r1, ..., ri-1,] x, ei+1, ..., eN)) ○ c)
• Next v ⇒ r = Next v
継続の生成
• トップレベルには中身の式の評価結果が Ok v ならば
Next v となる式を置いておく
• eval “(call/cc f)” = Cont f (λx → x)
• (call/cc f) を含む式を評価すると Cont f c が得られる
• 最後に c (f c) を計算すれば (そのうち) 値が出てくる
?
D E M O
継続は力