めざそう言語処理系の沼 〜shift/resetへの旅 〜 その１６ shift/reset

ついにshift / resetを実装するところまで到達！

resetで区切った限定継続をshiftで取り出して使う、という言語機能だ。

shift/resetプログラミング入門に出てくるような処理が実装できるようになる：

(* (reset
      (+ 3 
         (shift [k] (* 5 (k 2)))
       -1))
   2)

この例だと限定継続kが(fn [x] (+ 3 x -1))となって、(reset ...)部分が(* 5 (+ 3 2 -1))に入れ替えられ、全体の式は(* (* 5 (+ 3 2 -1)) 2)で結果は40となる。

前回との差分：

Comparing v0.15...v0.16 · zehnpaard/kontlang · GitHub

コード解説

まずはExp.tにResetとShift式を追加する：

type t =
...
| Reset of t
| Shift of string * t

次に値を追加。shiftやresetではなく、それらを使った結果として取り出せる「限定継続」を値として表す。なのでValcontモジュールのvalt型にContを追加：

type valt =
...
| Cont of string * (string * valt) list list * contt list

保持する要素としては

• 仮引数を表す文字列（限定継続の場合は必ず引数１になる）
• resetからshiftの間で追加された変数環境
• resetからshiftの間の継続

の三点。特に変数環境については、変数名と値のリストではなく、変数名と値のリストのリストであることに注意。

例えばこんなプログラムがある場合：

(reset
  (let [(x 10) (y 11) (z 12)]
    (+ x (* y z)
       (let [(a 1) (b 2) (c 3)]
         (+ a b c (shift [k] k))))))

(let [(x 10) (y 11) (z 12)]と(let [(a 1) (b 2) (c 3)]、そしてreset自体のクロージャの三つの「変数名と値のリスト」を保持する必要がある。（限定継続は保存されてプログラムのまったく違うところで呼び出される可能性もあるため、関数と同じくクロージャを保持する必要もある）

ValcontのContモジュールの方にはpop関数を追加：

  let pop = function
  | [] -> failwith "Popping empty continuation"
  | cont::cont' -> cont, cont'

「shiftから直近のresetまでの限定継続」というのはcontt list listである継続の先頭のリストで表されている。なのでpopはその先頭のリストとその残りをわけて返す関数。

式を追加したのでMacroモジュールにも場合分けのケースを追加：

let substitute e ss es =
  let env = List.combine ss es in
  let rec f = function
  ...
  | Exp.Reset e -> Exp.Reset (f e)
  | Exp.Shift(s, e) -> Exp.Shift(s, f e)
in
f e

マクロの中にshiftやresetが出てきてもその中の式をマクロ置換できるようにしている。

Utilsモジュールにヘルパ関数を二つ追加：

let break_off n xs =
  let rec f n acc xs =
    if n = 0 then List.rev acc, xs
    else match xs with
    | [] -> failwith "Not enough elements in list to break off"
    | x::xs' -> f (n-1) (x::acc) xs'
  in f n [] xs

let rec count y = function
| [] -> 0
| x::xs -> (if x = y then 1 else 0) + count y xs

あるリストを、先頭n個の要素を取る形で二つのリストに分割する関数break_offと、ある値と一致する要素の数を数えるcount。ここらへんはPervasivesのListモジュールに入っていても良さそうだが・・・ CoreやBatteriesには入っていそう。

Envモジュール：

let pop = function
| [] -> failwith "Popping empty environment"
| svs::env -> svs, env

let rest = function
| [] -> failwith "Taking rest of empty environment"
| _::env' -> env'

今までEnv.popと呼んでいた関数をEnv.restと名付け直した。これは先頭の要素を捨てて、残りのリストを返すもの。Env.popは先頭の要素と残りのリスト両方を返す関数として再定義。

最後にこれらを踏まえてExecuteモジュールに変更を加える。

まずExecute.eval：

let eval env cont = function
...
  | Exp.Reset e ->
    let free = Utils.dedupe @@ Exp.get_free [] [] e in
    let fvals = List.map (fun v -> v, Env.find v env) free in
    Eval(Env.extend_list fvals env, []::cont, e)

reset式の中に入った時点でクロージャを作って変数環境と継続に追加している。shiftで捕捉できるようにするためで、reset内でshiftに遭遇しなければこのクロージャはあってもなくても同じ。

Execute.evalのExp.Shiftケース：

...
  | Exp.Shift(s, e) ->
    let free = Utils.dedupe @@ Exp.get_free [s] [] e in
    let fvals = List.map (fun v -> v, Env.find v env) free in
    let cont', cont'' = Cont.pop cont in
    let n = 1 + Utils.count Cont.Env cont' in
    let env', env'' = Utils.break_off n env in
    let contv = Val.Cont(s, env', cont') in
    let closure = (s, contv)::fvals in
    Eval(Env.extend_list closure env'', []::cont'', e)

限定継続とその継続に含まれるCont.Envに対応するだけの変数環境をVal.Contに保持させ、shiftに含まれる式のクロージャを作成しVal.Contも変数環境に追加して、最終的にshiftに含まれる式を（限定継続の外の継続で）評価する。余談だが、ここのresetとshiftどちらもクロージャを持つという点がなかなかわからなくて実装中はバグの元だった。

次にExecute.applyでVal.Contが呼び出された時の処理：

let apply_cont env cont v = match cont with
...
| (Cont.Call([], vs) :: cont')::cont'' -> (match List.rev (v::vs) with
...
  | Val.Cont(s, svss, cont''') :: vs' ->
    let argcount = List.length vs' in
    if argcount = 1 then
      let final_cont = cont'''::cont'::cont'' in
      let f env svs = Env.extend_list svs env in
      let env' = List.fold_left f env (List.rev svss) in
      ApplyCont(env', final_cont, v)
    else failwith @@ Printf.sprintf "Continuation %s called with incorrect number of args: expected 1 received %d" s argcount

• 実引数が１であることを確認し
• Val.Contに保持されていた限定継続を現在の継続の先頭に追加
• Val.Contに保持されていた（１つ以上の）変数環境を、現在の変数環境の先頭に追加
• 新しい継続に実引数の値を渡す

という流れになっている。実引数が２個以上なら実行時エラー。

最後に、resetがない状態でshiftが呼ばれたらどうなるのか？という問題に対処する。対応するresetがない場合、shiftは現在の限定すべてをとってくることになっている。そうすると問題になるのがそのとってきた限定（されてない）継続のクロージャで、resetで作成していないのでうまく捕捉できない。

一番簡単な解決方法として、プログラム全体をresetで括ってしまうという手段にでた。

let run e = trampoline @@ Eval(Builtins.load Env.empty, Cont.final, Exp.Reset e)
...
let run' e = trampoline' @@ Eval(Builtins.load Env.empty, Cont.final, Exp.Reset e)

パースしたASTをトランポリンで評価していく前にExp.Resetで包んでしまう。これだけでプログラム全体を評価し始めると一番最初に全体の自由変数が捕捉されてクロージャに束縛される。対応するresetのないshiftで作成される限定継続はこのクロージャを保持することになる。

これで限定継続機能のshiftとresetの実装完了！

次回はこれらを使っていろいろと他の言語機能（可変な状態やバックトラックなど）らしきものを作ってみる。