型の違うCPS表現への変換
前回に続いてCPS変換の話。
前回はパーサから帰ってくるExp.t
型のASTを同じExp.t
型のCPS形式になっているASTに変換してからインタプリタに実行させていた。
インタプリタが(特にビルトイン関数について)関数の最終引数を継続だと認識するようになったので、CPS変換前のASTはExp.t
型なのに実行できないようになっていた(実行時エラーになる)。それだったらむしろ型をわけて、そもそもCPS変換前のASTをインタプリタに渡そうとするのはコンパイルエラーになるようにしたい。
ついでに
- ifの条件部分がsimpleならCPS変換しない
- 関数定義はsimpleな式として扱う
の二点も一緒に実装してしまう。
前回との差分:
コード
新しく導入したCPS変換後のASTを表すCexp
モジュール:
type t = | Const of int | Var of string | If of t * t * t | Proc of string list * t | Call of t * t list
実は定義はExp.t
とまったく同一。今後変えていく可能性あり。
この型の導入に伴い、Eval.eval'
関数を微調整:
let rec eval' env = function | Cexp.Const n -> Val.Num n | Cexp.Var s -> (match Env.find env s with | Some v -> v | None -> failwith "Variable not found in environment") | Cexp.If (e1, e2, e3) -> (match eval' env e1 with | Val.Bool b -> eval' env (if b then e2 else e3) | _ -> failwith "Using non-boolean if-condition") | Cexp.Proc (ss, e) -> Val.Proc (ss, e, env) | Cexp.Call (e1, es) -> (match eval' env e1 with | Val.Proc (ss, e, env') -> let vs = List.map (eval' env) es in let env'' = Env.extend_list env' ss vs in eval' env'' e | Val.Op (_, f) -> let args = List.map (eval' env) es in (match List.rev args with | (Val.Proc([s],e,env'))::es' -> let v = f (List.rev es') in let env'' = Env.extend env' s v in eval' env'' e | _ -> failwith "") | _ -> failwith "Calling non-procedure")
コードは長いが、変更箇所はExp.Const
などでパターンマッチしていたのがCexp.Const
になっただけ。
式を評価した結果となる「値」が定義されているValenv
モジュールのvalt
型も修正:
type valt = Num of int | Bool of bool | Op of string * (valt list -> valt) | Proc of string list * Cexp.t * envt
関数の本体となる式がExp.t
からCexp.t
型になった。
最後にCPS変換のロジックが集中しているTocps
モジュールを見ていく。
まずはis_simple
関数:
let is_simple = function | Exp.Const _ | Exp.Var _ | Exp.Proc _ -> true | _ -> false
Exp.Proc
がsimpleだと認定されるようになった。
次にsimpleなExp.t
式をCexp.t
型に修正するsimple_transform
関数:
and simple_transform = function | Exp.Const n -> Cexp.Const n | Exp.Var s -> Cexp.Var s | Exp.Proc(ss,body) -> let v = gensym () in Cexp.Proc(ss@[v], g (Cexp.Var v) body) | Exp.Call _ | Exp.If _ -> failwith "Simple transform of complex expression"
Exp.Const
、Exp.Var
の場合はそのままCexp.Const
、Cexp.Var
に変換。
Exp.Call
やExp.If
のようなsimpleでない式を変換しようとすると実行時エラー。
Exp.Proc
の変換の時に関数の本体をCPS変換する必要が出るのでg
関数と相互再帰になっている。関数の仮引数の最後に新しく作った変数を入れ、その変数を継続として関数本体の式に対してCPS変換を行う。
あとは本体のg
関数:
let rec g k e = match e with | Exp.Const _ | Exp.Var _ | Exp.Proc _ -> Cexp.Call(k,[simple_transform e])
simpleな式であるところのExp.Const
、Exp.Var
、そしてExp.Proc
はsimple_transform
してから「継続に渡す」(継続を関数、simple式を引数として関数適用)。
関数適用の変換:
| Exp.Call(proc,es) -> let es = proc::es in let es' = List.filter (fun e -> not @@ is_simple e) es in let vs' = List.map (fun _ -> gensym ()) es' in let evs = List.rev @@ List.combine es' vs' in let f e = match List.assoc_opt e evs with | None -> simple_transform e | Some v -> Cexp.Var(v) in let es = List.map f es in let cont_body = Cexp.Call(List.hd es,List.tl es @ [k]) in let g' cont_body (e, v) = g (Cexp.Proc([v],cont_body)) e in List.fold_left g' cont_body evs
前回とほどんど変わっていない。変換後の型がCexp.t
になるように修正したり、simpleな形の関数・引数をsimple_transform
で変換(f
のパターンマッチでのNone
ケース)したりといった微調整。
最後にExp.If
の変換:
| Exp.If(cond,yes,no) -> if is_simple cond then Cexp.If(simple_transform cond,g k yes,g k no) else let v = gensym () in let cont = Cexp.Proc([v],Cexp.If(Cexp.Var(v),g k yes,g k no)) in g cont cond
変更は二点:
- 変換後はCexp.t型にする
- 「ifの条件部分がsimpleならCPS変換しない」ために
if is_simple cond
で条件分岐を入れている
使ってみる
まずは単純な例から:
(+ 1 2)
これをCPS変換して文字列出力すると:
(+ 1 2 (proc [gensym0] gensym0))
前回とまったく変わらない出力となる。しかしOCamlの高機能REPLであるutopなどで変換結果をそのまま見てみると:
Cexp.Call (Cexp.Var "+", [Cexp.Const 1; Cexp.Const 2; Cexp.Proc (["gensym0"], Cexp.Var "gensym0")])
このとおりExp
ではなくCexp
で定義されているコンストラクタが使われていることがわかる。のでCPS変換でうまく型もExp.t
からCexp.t
に変わっているようだ。
次にif
の条件部分にsimpleな変数を使ってみる:
(if true (+ 1 2) (+ 3 (* 4 5)))
これを変換すると以下のようになる:
(if true (+ 1 2 (proc [gensym0] gensym0)) (* 4 5 (proc [gensym1] (+ 3 gensym1 (proc [gensym0] gensym0)))))
条件の部分はそのままCPS変換されず残っているので成功。
最後に関数適用内で関数定義をした場合:
((proc [n] (+ n 1)) 2)
これが以下のように変換される:
((proc [n gensym1] (+ n 1 gensym1)) 2 (proc [gensym0] gensym0))
関数定義はちゃんと最終引数に継続をとるように変換され、その上で関数適用の中に入ったまま(変数としてくくり出されずに)引数としてリテラルと終端継続を渡されている、のでこれも成功。
次回
次は継続と継続の適用をProc
とCall
とは別の式にしてみる。最終的にインタプリタは関数と継続で同じ処理をすることになるが、式としては区別することで最終出力前の最適化の段階でメリットがあるらしい。