Download - (call/cc (lambda (cont) (cont 知見)))

Transcript
Page 1: (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会

Page 2: (call/cc (lambda (cont) (cont 知見)))

おまえか

• すしす

• アレ系

• ヒwiヒヒer: @susisu2413

• GitHub: susisu

• Scheme 素人です

Page 3: (call/cc (lambda (cont) (cont 知見)))

継続

• "継続(けいぞく、continuation)とは、プログラムの実行においてある時点において評価されていない残りのプログラム(the rest of the program)を意味するものであり、手続き(procedure)として表現されるものである。"

継続 - Wikipedia https://ja.wikipedia.org/wiki/

%E7%B6%99%E7%B6%9A

Page 4: (call/cc (lambda (cont) (cont 知見)))

殺伐としたスライドに S 式が

(+ 1 2)

Page 5: (call/cc (lambda (cont) (cont 知見)))

2 から見た継続

(+ 1 (...))

Page 6: (call/cc (lambda (cont) (cont 知見)))

ラムダ式では

(lambda (x) (NEXT (+ 1 x) ))

NEXT はそこで評価を終了する仮想の処理

Page 7: (call/cc (lambda (cont) (cont 知見)))

c a l l / c c

• 略さずに言うと call-with-

current-continuation

• 現在の継続を引数として,

与えられた関数を呼び出す

• 継続はただの関数なので,

保存しておいて, 別の場所から呼び出すことも可能

Page 8: (call/cc (lambda (cont) (cont 知見)))

(+ 1 2)

Page 9: (call/cc (lambda (cont) (cont 知見)))

2 を c a l l / c c の式で置き換えてみる

(+ 1 (call/cc (lambda (cont) (cont 2)) ))

Page 10: (call/cc (lambda (cont) (cont 知見)))

c a l l / c c の引数 (関数 ) に渡される継続

(+ 1 (...))

Page 11: (call/cc (lambda (cont) (cont 知見)))

ラムダ式では

(lambda (x) (NEXT (+ 1 x) ))

Page 12: (call/cc (lambda (cont) (cont 知見)))

つまりこういうこと

(+ 1 ( (lambda (cont) (cont 2)) (lambda (x) (NEXT ( (+ 1 x) ))) ))

Page 13: (call/cc (lambda (cont) (cont 知見)))

評価を進める

(+ 1 (NEXT (+ 1 2) ))

Page 14: (call/cc (lambda (cont) (cont 知見)))

3

Page 15: (call/cc (lambda (cont) (cont 知見)))

何に使えるのか

• ループ脱出 (break)

• 例外処理 (throw)

• コルーチン (yield)

• return, goto, etc.

• 要は突入と脱出

Page 16: (call/cc (lambda (cont) (cont 知見)))

つよい

Page 17: (call/cc (lambda (cont) (cont 知見)))

実装した

Page 18: (call/cc (lambda (cont) (cont 知見)))

どういう実装

• 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 の例をいくつか試したところ期待通りに動作したので、たぶん上手くいっている

Page 19: (call/cc (lambda (cont) (cont 知見)))

継続の生成 (単純化したもの )

• 式 Expr

• 式の評価 eval : Expr → Res ― 厳密には環境も必要

• 評価結果 Res = Ok Val ― 成功

| Cont Val (Res → Res) ― 継続

| Next Val ― 評価終了

Page 20: (call/cc (lambda (cont) (cont 知見)))

継続の生成

• 例えば、複数の式を順番に評価するような式

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

Page 21: (call/cc (lambda (cont) (cont 知見)))

継続の生成

• トップレベルには中身の式の評価結果が Ok v ならば

Next v となる式を置いておく

• eval “(call/cc f)” = Cont f (λx → x)

• (call/cc f) を含む式を評価すると Cont f c が得られる

• 最後に c (f c) を計算すれば (そのうち) 値が出てくる

Page 22: (call/cc (lambda (cont) (cont 知見)))

?

Page 23: (call/cc (lambda (cont) (cont 知見)))

D E M O

Page 24: (call/cc (lambda (cont) (cont 知見)))

継続は力