shift/reset何もわからない
shift/resetの挙動を理解するために、https://nymphium.github.io/2018/07/19/delimited-continuationの夏.html のコードをプログラミング言語の基礎概念のEvalDContML4に置き換えて考えてみる
code:lisp
(reset (- 4 (shift k (+ 3 (k 20)))))
は
code:ocaml
{4 - shift k in 3 + k 20}
で
code:deriv
|- {4 - shift k in 3 + k 20} by E-Reset
|- 4 - shift k in 3 + k 20 by E-BinOp
|- 4 >> {_ - shift k in 3 + k 20} by E-Int
4 => {_ - shift k in 3 + k 20} by C-EvalR
|- shift k in 3 + k 20 >> {4 - _} by E-Shift
k = {4 - _} |- 3 + k 20 by E-BinOp
k = {4 - _} |- 3 >> {k = {4 - _} |- _ + k 20} by E-Int
3 => {k = {4 - _} |- _ + k 20} by C-EvalR
k = {4 - _} |- k 20 >> {3 + _} by E-App
k = {4 - _} |- k >> {k = {4 - _} |- _ 20} >> {3 + _} by E-Var
{4 - _} => {k = {4 - _} |- _ 20} >> {3 + _} C-EvalArg
k = {4 - _} |- 20 >> {{4 - _} _} >> {3 + _} by E-Int
20 => {{4 - _} _} >> {3 + _} by C-EvalFunC
20 => {4 - _} >>> {3 + _} by C-Minus
-16 => _ >>> {3 + _} by C-RetCont
-16 => {3 + _} by C-Plus
-13 by C-RetRet
で-13に評価される
これはcallccと同じなので別に問題ないさんすうができなくてじかんをむだにしました
言い訳をすると、EvalContML4だと継続が捨てられるタイミングが継続が評価されるとき(C-EvalFuncC)だったのだけれど、EvalDContML4だと継続を取るとき(E-Shift)なので混乱してしまった
shiftが今の限定継続を奪って環境に突っ込む
限定継続kが継続から環境にshiftするってワケ
code:lisp
(- 4 (reset (shift k (+ 3 (k 20)))))
は
code:ocaml
4 - {shift k in 3 + k 20}
で
code:deriv2
|- 4 - {shift k in 3 + k 20} by E-BinOp
|- 4 >> {|- _ - {shift k in 3 + k 20}} by E-Int
4 => {|- _ - {shift k in 3 + k 20}} by C-EvalR
|- {shift k in 3 + k 20} >> {4 - _} by E-Reset
|- shift k in 3 + k 20 >>> {4 - _} by E-Shift
k = _ |- 3 + k 20 >>> {4 - _} by E-BinOp
k = _ |- 3 >> {k = _ |- _ + k 20} >>> {4 - _} by E-Int
3 => {k = _ |- _ + k 20} >>> {4 - _} by C-EvalR
k = _ |- k 20 >> {3 + _} >>> {4 - _} by E-App
k = _ |- k >> {k = _ |- _ 20} >> {3 + _} >>> {4 - _} by E-Var
_ => {k = _ |- _ 20} >> {3 + _} >>> {4 - _} by C-EvalArg
k = _ |- 20 >> {_ _} >> {3 + _} >>> {4 - _} by E-Int
20 => [_ _] >> {3 + _} >>> {4 - _} by C-EvalFunC
20 => _ >>> {3 + _} >>> {4 - _} by C-RetCont
20 => {3 + _} >>> {4 - _} by C-Plus
23 => _ >>> {4 - _} by C-RetCont
23 => {4 - _} by C-Minus
-19 => _ >>> __ by C-RetRet
で-19に評価される
shiftで取れる限定継続kの評価のイメージは
値をshiftの中に入れる
shiftを囲むresetを評価する
それがkを評価した値になる
なるほどこれは型付けがめんどい
ところでこれ、shiftの中でkを呼ばなかったらどうなるんだろう
code:ocaml
{4 - shift k in 3 + 20}
code:deriv3
|- {4 - shift k in 3 + 20} by E-Reset
|- 4 - shift k in 3 + 20 by E-BinOp
|- 4 >> {|- _ - shift k in 3 + 20} by E-Int
4 => {|- _ - shift k in 3 + 20} by E-EvalR
|- shift k in 3 + 20 >> {4 - _} by E-Shift
k = {4 - _} |- 3 + 20
resetからshiftまでの計算が消える了解！
この領域を継続として取り出しているので当たり前ではある
TODO
resetの中でshiftを何回も使ったらどうなるんだろう
control/promptもしりたいね