とりあえず http://pllab.is.ocha.ac.jp/~asai/cw2011tutorial/main-j.pdf を読む
概要
call/cc は引数に関数をとって、その時点での残りの処理、つまり継続を引数としてその関数を実行するcall/cc みたいなやつを第一級継続機構っていうらしい？call/cc のようなそれ以降全ての計算を継続として取る ←→ そうでない限定的な計算だけを継続として取るものは限定継続shift/reset は限定継続を扱うための機構っぽい2.1 継続とは
5 * (2 * 3 + 3 * 4)2 * 3, 型: int5 * ([・] + 3 * 4), 型: int(if 2 = 3 then "hello" else "hi") ^ " world"2 = 3, 型: bool(if [・] then "hello" else "hi") ^ " world", 型: stringfst (let x = 1 + 2 in (x, x))1 + 2, 型: intfst (let x = [・] in (x, x)), 型: intstring_length ("x" ^ string_of_int (3 + 1))
次に実行すべき式: 3 + 1, 型: int
継続: string_length ("x" ^ string_of_int [・]), 型: int2.2 限定継続とは
⟨ ⟩ を使う2.3 継続を限定する命令 reset
reset 命令で継続を限定する20 * 30 + 3 + 2 という式があった時に、 ⟨20 * 30 + 3⟩ + 2 という限定をすると継続は [・] + 3 だけになる2.4 限定継続をとって来る命令 shift
shift 命令
call/cc の限定継続版っぽそうに見える2.7 継続の保存
Done | Next(n, k) で包む(* print_nodes : tree_t -> unit *)
let print_nodes tree =
let rec loop r = match r with
Done -> () (* no more nodes *)
| Next (n, k) ->
print_int n; (* print n *)
loop (k ()) in (* and continue *)
loop (start tree) ;;2.9 答の型の変化
reset (fun () -> 3 + [5 * 2]) における答の型は intreset (fun () -> string_of_int [5 * 2]) における答の型は string
5 * 2 の答の型は多相であると言うT -> T' T -> T'' みたいな関数があって、 T を渡したら T’ や T’’ が帰ってくるから
+ は int -> int (int -> int -> int に 3 を渡してるから) と、 string_of_int の int -> string があるから多相になっているshift が入ると変わる
reset (fun () -> shift (fun k -> (fun () -> "hello"))) みたいな時は限定継続 k を捨てて fun () -> "hello" を返しているので常に答の型は unit -> string になる2.10 継続の包み込み：状態モナド
継続の適用を関数で包みこむと reset の外側の引数にアクセスすることができる。この方法を上手に使うと「状 態」をサポートすることができる。
reset (...) arg みたいな時に fun () -> (shift(fun k -> (fun a -> k a))) とすると継続に reset の外にある arg を引数として与えることができるという話？なんか k state state と二回 state を渡している、理由を読んでもよくわからない
一つ目はその shift 全体の戻り値？ 二つ目は新たなステート？のように扱えそう
❯ ochacaml
> Caml Light version 0.75 + shift/reset
# let get () = shift(fun k -> fun state -> k state state);;
get : unit => 'a = <fun>
# let succ () = shift(fun k -> fun state -> k () (state+1));;
succ : unit => unit = <fun>
# let run_state thunk = reset (fun () ->
let result = thunk () in
fun state -> result
) 0 ;;
run_state : (unit => 'a) => 'b = <fun>
# run_state (fun () ->
succ ();
succ ();
get ()
);;
- : int = 2run_state を使って試すlet state = 0;
const succ = () => {
state += 1;
};
const get = () => {
return state;
};これで動くのはわかった、次は run_state の仕組みを知りたい
2.11 継続を使った実行順序の変更（発展）
2.12 継続の複製
k a; k b とすると 2 つの値を返すような関数として機能する？
これまでの例は、どれもとってきた継続を 1 度しか使わなかったが、複数回、使うようにすると、バックトラッ クを実現できる
# let either a b = shift (fun k -> k a; k b) ;;
# reset (fun () ->
let p = either true false in
let q = either true false in
if (p || q) && (p || not q) && (not p || not q)
then (print_string (string_of_bool p);
print_string ", ";
print_string (string_of_bool q);
print_newline ())) ;;
true, false
- : unit = ()for i in [true, false] {
for j in [true, false] {
if (略) {
println!("{}, {}", i, j);
return;
}
}
}3.4 型規則
ここで、σ ≻ τ は型 τ が型スキーム σ のインスタンスになっていることを示し、Gen(τ, Γ) は、型 τ 中の型変数のうち Γ に出てこない型変数について ∀ を付けることで得られる型スキーム
軽く読み終わった
reset/shift 以外にも control/prompt もあるらしい