Arantium Maestum

プログラミング、囲碁、読書の話題

型の違うCPS表現への変換

前回に続いてCPS変換の話。

前回はパーサから帰ってくるExp.t型のASTを同じExp.t型のCPS形式になっているASTに変換してからインタプリタに実行させていた。

インタプリタが(特にビルトイン関数について)関数の最終引数を継続だと認識するようになったので、CPS変換前のASTはExp.t型なのに実行できないようになっていた(実行時エラーになる)。それだったらむしろ型をわけて、そもそもCPS変換前のASTをインタプリタに渡そうとするのはコンパイルエラーになるようにしたい。

ついでに

  • ifの条件部分がsimpleならCPS変換しない
  • 関数定義はsimpleな式として扱う

の二点も一緒に実装してしまう。

前回との差分:

github.com

コード

新しく導入した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.ConstExp.Varの場合はそのままCexp.ConstCexp.Varに変換。

Exp.CallExp.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.ConstExp.Var、そしてExp.Procsimple_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))

関数定義はちゃんと最終引数に継続をとるように変換され、その上で関数適用の中に入ったまま(変数としてくくり出されずに)引数としてリテラルと終端継続を渡されている、のでこれも成功。

次回

次は継続と継続の適用をProcCallとは別の式にしてみる。最終的にインタプリタは関数と継続で同じ処理をすることになるが、式としては区別することで最終出力前の最適化の段階でメリットがあるらしい。