MetaOCaml を使った部分評価器の実装
岩井亜里紗

1

(指導教員：浅井健一)

はじめにMSP のための構文は以下の通りである。
Brackets ( .h…i. )Dynamic な式をコードとして出力する

MetaOCaml は、Multi-stage programming に対応
した OCaml の拡張であり、MetaOCaml を使うことにより、コードを出力するようなプログラムが比較的容易に書けるようになる。本研究では、let-insertionをする部分評価器の作成を MetaOCaml を用いて行った。今回、部分評価器本体を継続渡し形式 (CPS) に書くことで let-insertion を実現するとともに、コードを残す部分では K 正規形を返すことで、結果を直接形式で得るようにしている。更に部分評価器の入力言語にshift/reset を加える方法についても議論する。

2

Escape ( .∼ (…) )コードの一部分を Static な式として実行する
Run ( .!(…) )コード全体を実行する
これらを用いた簡単なインタプリタを以下に記す。
let rec eval e env =match e withInt(i) → .hVInt(i)i.
| Var(s) → env s| App(e1, e2) →.h((take fun .∼ (eval e1 env)).∼ (eval e2 env)i.
| Add(e1, e2) →.hVInt((f int.∼ (eval e1 env))+(f int.∼ (eval e2 env)))i.
.
.
.

部分評価

部分評価とは、プログラム中で評価できることが明らかな部分を評価したプログラムを作成する処理である。これにより、計算時間の短縮などが期待される。
ここで扱う部分評価は、プログラムを事前に評価可能 (Static) な部分と評価不可能 (Dynamic) な部分に分け、それから評価していくというものである。
例えば、(fun n → n * (1 + 2)) という式の場合、(1 + 2) は評価できるので Static、n の値がわからず、n * (1 + 2) は評価できないため、これは Dynamicとなる。よって、この式を部分評価すると、(fun n →n * 3) のようになる。

3| Fun(s, e2) →.hVFun(fun v →.∼ (eval e2 (ext env s .hvi.)))i.
こ の イ ン タ プ リ タ は 、Int(i) の よ う な 数 字は、.hVInt(i)i. のように数字のコードに、Add(e1,e2) のような足し算は、e1、e2 の二つの式をそれぞれコードに変換し、出てきた二つのコードを足すようなコードを返している。例えば (fun x → x + 1) (2+ 3) という式を上のインタプリタにかけると、# eval App(Fun("x", Add(Var "x", Int 1)),Add(Int 2, Int 3)) env0;;- : (’a, ’b value) code =.h(match(VFun (fun v 2 →(f int v 2) + (f int (VInt 1)))) with| VFun(f 1) →(f 1 (VInt((f int (VInt 2)) + (f int(VInt 3)))))| → (raise Notmatch))i.のようになる。このように、この段階ではすべてDynamic となり、全てコードとして出力される。そして、これを# .!(eval App(Fun("x", Add(Var "x", Int1)), Add(Int 2, Int 3)) env0);;- : (’a value) code = VInt 6

shift/reset

継続とは、計算のある時点における残りの計算のことであり、shift は継続を取ってくるための命令、reset は継続の範囲を指定する命令である。例えば，1 +reset(2 * shift(fun k → k (k 3))) という式の場合、shift で取ってくる継続は、reset の中から shift を除いた 2 * [] という部分である。この継続は (fun n→ 2 * n) と書けるので、k (k 3) の部分は、(funn → 2 * n) ((fun n → 2 * n) 3) となり、結果は 12 である。これで reset の中身は切り取られたため、残りの 1 + [] の [] に 12 を渡して、式全体の結果は 13 となる。

4

継続渡し形式

継続渡し形式 (CPS : Continuation Passing Style)とは、継続を引数として渡すことで全ての関数呼び出しを末尾呼び出しの形にしたプログラム形式のことである。また、末尾呼び出しとは、関数を呼び出した後に覚えておかなくてはならない作業がないような関数呼び出しのことを言う。

5MetaOCamlのように .! を用いて実行すると、確かに答えの 6 が返ってくることがわかる。

MetaOCaml は、Multi-stage programming(MSP)に対応した OCaml の拡張である。また、MSP とは、Static な式と Dynamic な式を扱うプログラミングのことである。
65

実装

6

let-insertion を行わない部分評価器にかけると、結果は .hfun f → fun x → xi. となり、x という結果が返ってくる関数に変わってしまう。そのため、(f x)を式に残すことが必要である。
そこで Dynamic な関数適用が現れた場合、.hfun f → fun x → let a = (f x) in xi.のように let 文を用いてその関数適用を継続の前に残すようにする。これにより、上のように部分評価器にかけたために結果が変わってしまうことを防ぐことができる。
これを実装するため、まずインタプリタを CPS で書き換え、関数適用の部分を以下のようにした。
| App(e1, e2) →eval3 e1 env (fun e1’ →eval3 e2 env (fun e2’ →Dyn(.hlet a =(take fun .∼ (d to code e1’)).∼ (d to code e2’) in∼. (d to code(k (Dyn(.hai.))))i.)))

本研究では、[1] を参考にして以下のような順で部分評価器の実装を行った。

6.1

Static/Dynamic の導入

入力言語に Static/Dynamic を導入したインタプリ
タを以下に記す。
let rec eval2 e env =match e withInt(i) → (Dyn(.hVInt(i)i.))| IntS(i) → (VInt(i))| Var(s) → (env s)| App(e1, e2) →Dyn(.h(((take fun .∼ (eval2 e1 env)).∼ (eval2 e2 env)i.)| AppS(e1, e2) →(((take fun .∼ (eval2 e1 env)).∼ (eval2 e2 env)
| Add(e1, e2) →Dyn(.hVInt((f int .∼ (eval2 e1 env))+(f int .∼ (eval2 e2 env)))i.)| AddS(e1, e2) →VInt((f int(eval2 e1 env))+(f int(eval2 e2 env))).
.
.

返すコードの初めに let 文を挿入して、関数適用を変数にいれ、その後 CPS による継続にその変数を渡すようになっている。
上の式をこのインタプリタにかけると、確かに、# eval3 (Fun ("f", Fun ("x", AppS (FunS("y", Var "x"), App (Var "f", Var "x")))))
env0 k0;;- : (’a value) code =Dyn.h(VFun (fun v 1 →(VFun (fun v 2 →let a 3 = (take fun v 1) v 2 inv 2)))))i.のように返ってくる。

| Fun(s, e2) →Dyn(.hVFun(fun v →.∼ (eval2 e2 (ext env s .hvi.)))i.)| FunS(s, e2) →VFun(fun v → eval2 e2 (ext env s v))| Lift(e) →Dyn(.h.∼ (lift (eval2 e env))i.)6.3

この場合、返ってくる式には Static のものと Dynamic のものがあるため、Dynamic なものは Dyn(. . .)とする。また、入力言語に関して IntS のように、S がついているものは Static なものである。
上の式の (2 + 3) を Static にした式をこのインタプ
リタにかけると、# eval2 App(Fun("x", Add(Var "x", Int 1)),Lift(AddS(IntS 2, IntS 3))) env0;;- : (’a, ’b value) code =.h(match(VFun (fun v 2 →(f int v 2) + (f int (VInt 1)))) with| VFun(f 1) → (f 1 (VInt 5))| → (raise Notmatch))i.のようになり、Static な式のみが実行されていることがわかる。

6.2

shift/reset の導入

インタプリタを CPS に変換したため、継続が使えるようになり、shift/reset の導入が可能となった。現在、[2] を参考に、Static な shift/reset の導入が終わっている。

7

まとめと今後の課題

本研究では、MetaOCaml を用いて、let-insertion をする部分評価器の実装を行った。これにより、ステージングを行うことでコンパイラや部分評価器を得られることがわかった。その一方で、出力されるコードには多くのタグが入ってしまうこともわかった。現在、Staticな shift/reset の導入までは終わっているため、今後はDynamic な shift/reset の導入も進めていきたい。

参考文献

let-insertion の導入[1] Walid Taha “A Gentle Introduction to Multistage Programming”, Domain-Speciﬁc Program
Generation 2003, pp. 30–50, (2003).

.hfun f → fun x →.∼ ((fun y → x) .hf xi.)i.のような式 (ただし、.h … i. はコードとして残す Dynamic な部分、.∼ ( … ) は Dynamic な式の中に存在する Static な部分) において、関数 f がループしてしまう場合、実際には答えが出ないはずだが、この式を[2] Kenichi Asai “Logical Relations for Call-by-value
Delimited Continuations”, In A chapter of Trends
in Functional Programming, Vol, 6, pp. 63–78,
Intellect (2007).
66