インタプリタ自作によってプログラミング言語の諸概念を学んでいく「Essentials of Programming Languages」の第5章、第6章はどちらも継続渡しスタイルについて語っている。

第5章は「インタプリタを継続渡しスタイルで書くとどうなるか」という話を掘り下げていく内容で、このブログの「めざそう言語処理系の沼」シリーズの元ネタにもなっている。

第6章は「プログラムを継続渡しスタイルに変換してから実行するインタプリタ」についての話だ。ソースに対してCPS変換を行うことで実行が末尾呼び出しの形になったり、複雑な制御フローをCPSの形として脱糖することでインタプリタの評価関数には手を入れることなく実装できたりする、らしい。さらにはCPS変換したソースは最適化した上でコンパイルするのが楽らしい。EoPLにはそういった話題はないが、「最新コンパイラ構成技法」（通称「虎本」）の著者としても有名なAppelの「Compiling with Continuations」というそのままズバリな著作もある。

後者を読んでいくための下準備としても、EoPLの第6章を読んで簡単なCPS変換を行うインタプリタを実装してみたい。

eopl-ocaml/by-lang/cpsmin at master · zehnpaard/eopl-ocaml · GitHub

実装してみた。

ソース言語

言語機能としては

S式
if分岐
多引数のビルトイン・ユーザ定義関数
関数の仮引数としての変数
リテラル整数

が存在している。letとletrecはまだない。

使用例

例１変換前：

(+ 1 (- 5 3) 2)

変換後：

(- 5 3 (proc [gensym2]
         (+ 1 gensym2 2 (proc [gensym1] gensym1))))

例２変換前：

((proc [x] (+ (* x x) 1)) 5)

変換後：

((proc [gensym7]
   (gensym7 5 (proc [gensym6] gensym6)))
 (proc [x gensym8]
   (* x x (proc [gensym9]
            (+ gensym9 1 gensym8)))))

例３変換前：

(if (zero? 3) (+ 1 2) (+ 3 4))

変換後：

(zero? 3 (proc [gensym1]
           (if gensym1
             (+ 1 2 (proc [gensym0] gensym0))
             (+ 3 4 (proc [gensym0] gensym0)))))

となる。

コード

CPS変換するためのコードはTocpsモジュールに入っている：

eopl-ocaml/tocps.ml at master · zehnpaard/eopl-ocaml · GitHub

CPS変換するためには、継続の仮引数に今まで使われていない新しい変数を割り当てる必要がある。そのためのgensym関数：

let gensym =
  let n = ref (-1) in
  let f () = incr n; "gensym" ^ (string_of_int !n) in
  f

gensym0などの変数名を作成する。本当は「継続の中に入る式を検査して自由変数が被っていないかを調べる」という手順があったほうがいいのだがめんどくさいので割愛。ソースプログラムにはgensym_という形の変数は出てこないと仮定する。（パーサの仕様でユーザが変数として使えない文字列を使っても良かったかもしれない・・・）

CPS変換する場合、関数呼び出しの一部にリテラルや変数が入っていた場合はその部分は継続化しないようにしたい（継続化してもどっちみち引数である変数がその部分に入るし・・・）。というわけでリテラルや変数かどうかを判定するis_simple関数：

let is_simple = function
| Const _ | Var _ -> true
| _ -> false

ただのパターンマッチである。

次にCPS変換の心臓部になる関数。しかし名前をつけるのが億劫だったのでg。「今からおまえの名前はgだ。いいかい、gだよ」：

let rec g k e = match e with
| Const _ | Var _ -> Call(k,[e])

gの引数は

継続k
CPS変換する式e

となる。eがリテラルや変数だった場合、継続kにその式を適用するCall(k,[e])がCPS変換の結果となる。

関数適用をCPS変換する場合：

| 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 -> e
  | Some v -> Var(v)
  in
  let es = List.map f es in
  let cont_body = Call(List.hd es,List.tl es @ [k]) in
  let g' cont_body (e, v) = g (Proc([v],cont_body)) e in
  List.fold_left g' cont_body evs

関数と実引数のうち、「変数あるいはリテラル整数」ではない（つまりis_simpleでない）ものをes'というリストに入れ、それらにgensymによる変数を割り当てる。それらだけ入れ替えたcont_bodyという式を作り、最終的にList.fold_leftを使ってis_simpleでない要素の分だけ入れ子状態の継続にしている。

ifのケース：

| If(cond,yes,no) ->
  let v = gensym () in
  let cont = Proc([v],If(Var(v),g k yes,g k no)) in
  g cont cond

条件文にあたるcondのところだけ継続化。今見直してみると、ここもis_simpleのチェックを入れたほうが良かった。

関数定義のCPS変換：

| Proc(ss,body) ->
  let v = gensym () in
  Call(k,[Proc(ss@[v], g (Var v) body)])

処理としては：

定義された関数の仮引数の最後に継続のためのものを追加
その変数を継続として関数本体の式をgでCPS変換
継続kに作成された関数を渡す（この部分は変数やリテラルの扱いと同じ）

という式を返す流れとなる。

これでgの定義は終わり。

あとは終端継続を定義して、それをgに渡すことでトップレベルの式をCPS変換するTocps.fを定義：

let f e =
  let v = gensym () in
  g (Proc([v],Var v)) e

終端継続は値を受け取ってそのまま返す(Proc([v],Var v))という関数になる。

不満

Tocps.fはExp.t -> Exp.tで、まるで「同じインタプリタで実行できる言語内での変換」であるように見える。が実際はそうではない。

前述の例をとってみると：

(+ 1 (- 5 3) 2)

(- 5 3 (proc [gensym2] (+ 1 gensym2 2 (proc [gensym1] gensym1))))

+や-といったビルトイン関数の挙動が変わっている。具体的には最終引数に継続をとるようになっている。

このことによって、(+ 1 (- 5 3) 2)をCPS変換なしにインタプリタに実行させようとすると「最後の引数が関数ではない」とエラーを吐く。

実行できないのはいいとして、それなら実行時エラーではなくコンパイルが通らないほうがいい。

というわけでCPS変換前と後では型を変えたほうがいいように思うので、次はその変更を加えてみたい。

Arantium Maestum

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

CPS変換はじめてみた

ソース言語

使用例

コード

不満