はじめに
BER-MetaOCamlはOCamlを拡張したプログラミング言語です。BER-MetaOCamlを使うと、型安全にメタプログラミングを行うことができます。
BER-MetaOCamlのインストール方法や簡単な使い方は以下のpasberthさんの記事を参照してください。
簡単な使い方の復習
コードの構築
BER-MetaOCamlではコードがfirst-classなオブジェクトです。コードを構築するには、式を.<と>.で囲みます。この.<と>.のことをブラケットとよびます。
$ metaocaml
BER MetaOCaml toplevel, version N 102
OCaml version 4.02.1
# let a = .<1 + 2>.;;
val a : int code = .<1 + 2>.
コードの型は'a codeのようになります。
例えば、
# .<"hello">.;;
- : string code = .<"hello">.
-
# .<fun x -> x * 2>.;;
- : (int -> int) code = .<fun x_1 -> x_1 * 2>.
-
# .< .< 123 >. >.;;
- : int code code = .<.< 123 >.>.
のような感じです。関数のコードやコードのコードを作ることもできます。
コードの合成
.~オペレータを使うと、コードの中に別のコードを埋め込むことができます。
# let a = .<1 + 2>.;;
val a : int code = .<1 + 2>.
# let b = .<.~a + .~a>.;;
val b : int code = .<(1 + 2) + (1 + 2)>.
.~aと書いた場所にaに束縛されたコード.<1 + 2>.がブラケットを外された状態で埋め込まれていることがわかると思います。この.~のことをエスケープとよびます。
以下のようにエスケープの中に別のブラケットを入れて、その中にさらに別のブラケットを入れることができます。
# .< .~.< .~a >. >.;;
- : int code = .<1 + 2>.
コードの実行
コードを実行するには、Runcodeモジュールのrun関数を使います。
# Runcode.run;;
- : 'a code -> 'a = <fun>
# Runcode.run .<2 * 3>.;;
- : int = 6
コード生成でより良い(例えば高速だとかメモリ使用量が少ないとか)コードを生成し、run関数でコードを実行できます。
コードの保存
コードは他のOCamlオブジェクト同様マーシャリングしてファイルに書きだしたり、ファイルから読み込んだり、ネットワーク経由で転送したりできます。
保存
# let a = .<1 + 2>.;;
val a : int code = .<1 + 2>.
# let och = open_out "test.code";;
val och : out_channel = <abstr>
# Marshal.to_channel och a [];;
- : unit = ()
# close_out och;;
- : unit = ()
読み込み
# let ich = open_in "test.code";;
val ich : in_channel = <abstr>
# let code : int code = Marshal.from_channel ich;;
val code : int code = .<1 + 2>.
# Runcode.run code;;
- : int = 3
CSP (Cross-Stage Persistent)
さて、ブラケットによって構築されたコードは、内部では抽象構文木の形で保持されています。一方、ブラケットの外ではプログラムはバイトコードのプログラムとして動いています。ブラケットの内部から、このバイトコードの世界の関数を呼び出すことができると便利な場合があります。この外の世界のプログラムを参照する機能のことをCSP (Cross-Stage Persistent)とよびます1。まずは簡単な例を見てみます。
# let f x = x * 2;;
val f : int -> int = <fun>
# let c = .< f 10 >.;;
Characters 11-12:
let c = .< f 10 >.;;
^
Warning 22: The CSP value is a closure or too deep to serialize
val c : int code = .<(* CSP f *) 10>.
この例ではコードの中で、コードの外の関数fを呼び出しています。fはバイトコードのプログラムなので、MetaOCamlのプリンタは表示する術がありません。そのため(* CSP f *)と表示されています。
ちなみにCSPを含むコード出会っても、実行時にfが存在するのであれば以下のように何の問題もなく実行できます。
# Runcode.run c;;
- : int = 20
以下もCSPの例です。
# let x = 12;;
val x : int = 12
# .< x >.;;
- : int code = .<12>.
xはブラケットの外の値です。今回は単純な値なのでMetaOCamlを.<12>.と分かりやく表示してくれています。
実はこれまでも出てきた以下のコードですがこれもCSPを使っています。どこがCSPかわかりますか？
# .<1 + 2>.;;
- : int code = .<1 + 2>.
答えは+の部分です。+という関数はブラケットの外で定義されている関数です。それをブラケットの内部で使っているわけですからCSPになります。この場合もMetaOCamlは+を知っているので見やすく表示してくれています。
定番の例 (power関数)
ここではMetaOCamlの定番の例題であるpower関数を詳しく見てみたいと思います。
power関数は$x^n$を求める関数のことです。power関数はOCamlでは以下のように自然に書くことができます。
# let rec power n x =
if n == 0 then 1
else x * power (n - 1) x;;
val power : int -> int -> int = <fun>
# power 5 2;;
- : int = 32
このpower関数をコード生成により引数nに特化したコードを生成するようにしたいと思います。上のプログラムはプログラムにブラケットとエスケープを追加するだけでコードを生成するように書き換えることができます。そのような変更を施したコードは以下のようになります。
# let rec spower n x =
if n == 0 then .<1>.
else .< .~x * .~(spower (n - 1) x) >.;;
val spower : int -> int code -> int code = <fun>
このspower関数を使ってn = 5に特化したコードを生成するには以下のようにします。
# let power5_code = .<fun x -> .~(spower 5 .<x>.)>.;;
val power5_code : (int -> int) code = .<
fun x_1 -> x_1 * (x_1 * (x_1 * (x_1 * (x_1 * 1))))>.
上のプログラムで特に注目して欲しいのは、spower関数に閉じていない(funで束縛されていない)コードである.<x>.を渡しているところです。MetaOCamlではこのように閉じていないコードを扱うことができます。コード.<x>.はspower関数の引数xとなって、開いたコードのまま再帰によりコードが生成が実行されます。spowerの戻り値は、.<x * (x * (x * (x * (x * 1))))>.という開いたコードになります。この開いたコードが.<fun x -> .~(...)>.の...の部分に埋め込まれることで、閉じたコードとなり最終的に閉じた関数のコードが得られます。このコードは実行することで、power5関数を得ることができます。
# let power5 = Runcode.run power5_code;;
val power5 : int -> int = <fun>
# power5 2;;
- : int = 32
このpower5関数は以下のように部分適用して得られるpower5関数とは意味は同じですが動作が異なります。
# let power5 = power 5;;
val power5 : int -> int = <fun>
コード生成を使った版では完全にループが展開されていて再帰呼び出しのオーバーヘッドが完全になくなっています。
改善したpower関数
上の例ではわかりやすさのために愚直にxを5回掛けていますが、出来れば以下のようなもっと効率の良いコードを生成したいと思うことでしょう。
let power5 x =
let x' = x * x in
let x'' = x' * x' in
x'' * x;
このようなコードを生成するのはMetaOCamlの非常に良い練習問題になるのでぜひ一度自力で考えてみてください。実装例はこの記事の一番最後に掲載します。私の実装では以下のようなコードが生成されました。
fun x_1 ->
x_1 * (let x'_2 = x_1 * x_1 in let x'_3 = x'_2 * x'_2 in x'_3 * 1)>.
最後の* 1を消して代わりにx_1を掛けるような実装に挑戦するのも面白いと思います。
ref型を使ったpower関数
BER-MetaOCamlではコード生成にref型を使うこともできます。以下はref型を使って手続き的にpower関数を生成する例です。
# let mpower n x =
let code = ref .<1>. in
for i = 1 to n do
code := .<.~x * .~(!code)>.
done;
!code;;
val mpower : int -> int code -> int code = <fun>
以下のように再帰で書いた場合と同様に動きます。
# let power5_code = .<fun x -> .~(mpower 5 .<x>.)>.;;
val power5_code : (int -> int) code = .<
fun x_1 -> x_1 * (x_1 * (x_1 * (x_1 * (x_1 * 1))))>.
# let power5 = Runcode.run power5_code;;
val power5 : int -> int = <fun>
# power5 2;;
- : int = 32
MetaOCamlは本当に安全か
ここではいくつかの実験的なコードでMetaOCamlが本当に安全であるかどうか試してみましょう。
ref型を使った実験
以下はref型を用いて作ったグローバル変数に閉じていないコードを代入して実行できるかを試してみた例です。
まず、グローバル変数を作ります。
# let g = ref .<1>.;;
val g : int code ref = {contents = .<1>. }
次に、エスケープの中からgに代入します。
# .<fun x -> .~( g := .<x + 1>.; .<1>. )>.;;
- : (int -> int) code = .<fun x_1 -> 1>.
ここまではエラーがでません。次にgを実行しようとします。
# Runcode.run !g;;
Exception:
Failure
"The code built at Characters 22-27:\n is not closed: identifier x_1 bound at Characters 6-7:\n Runcode.run !g;;\n ^\n is free".
例外Failureが発生しました。閉じたコードを実行しようとすると、例外が発生することがわかりました。例外なので、try-withで実行時にハンドリングできます。
ところでこのようにグローバル変数にコードを代入する例は全てエラーなのでしょうか。以下を試して見ました。
まず、グローバル変数を作ります。
# let g = ref .<1>.;;
val g : int code ref = {contents = .<1>. }
次に、エスケープの中からgに代入します。
# .<fun x -> .~( g := .<1 + 2>.; .<1>.) + x>.;;
- : (int -> int) code = .<fun x_2 -> 1 + x_2>.
何事もなく実行できました。問題は次です。
# Runcode.run !g;;
- : int = 3
なんと今度は正しく実行できました。MetaOCamlではこのように、実行時にコードが閉じているかどうかの判定を行なっています。
例外を使った実験
例外でエスケープの中から外に向かってコードを投げて、そのコードを受け取って実行することは可能でしょうか。実際にやってみました。
# exception Code of int code;;
exception Code of int code
# let f () = raise (Code .<1 + 2>.);;
val f : unit -> 'a = <fun>
# try f () with Code c -> Runcode.run c;;
- : int = 3
関数fの内部でコードを投げて外側でキャッチして正しく実行できていることが確認できます。次に、閉じていないコードを投げてみましょう。
# try .<fun x -> .~(raise (Code .<x>.); .<x>.)>.
with Code c -> .<fun y -> .~c>.;;
Characters 18-36:
try .<fun x -> .~(raise (Code .<x>.); .<x>.)>. with Code c -> .<fun y -> .~c>.;;
^^^^^^^^^^^^^^^^^^
Warning 21: this statement never returns (or has an unsound type.)
Exception:
Failure
"Scope extrusion detected at Characters 64-76:\n try .<fun x -> .~(raise (Code .<x>.); .<x>.)>. with Code c -> .<fun y -> .~c>.;;\n ^^^^^^^^^^^^\n for code built at Characters 10-11:\n try .<fun x -> .~(raise (Code .<x>.); .<x>.)>. with Code c -> .<fun y -> .~c>.;;\n ^\n for the identifier x_3 bound at Characters 10-11:\n try .<fun x -> .~(raise (Code .<x>.); .<x>.)>. with Code c -> .<fun y -> .~c>.;;\n ^\n".
なんかごちゃごちゃと出てきましたが、やはり例外が発生するということが分かります。
MetaOCamlは一応安全だが...
BER-MetaOCamlでは閉じていないコードを実行しようとすると実行時に例外として報告し、決して閉じていないコードを実行することはないという事がわかります。実行時ではなくコンパイル時にこのような判定が行われるとユーザとしてはとてもありがたいのですが、やはり技術的に困難だという事でしょうか。今後の技術進歩に期待しましょう。
まとめ
この記事では、MetaOCamlの簡単な使い方を復習して、MetaOCaml定番の例であるpower関数を詳しく見てみました。そして、実験的なコードを使ってMetaOCamlが本当に安全であるかどうかの検証を行いました。ここまで読んでいただけた方であれば、MetaOCamlで何ができて何ができないのかといった全体像を把握することができたと思います。あとはバリバリMetaOCamlでプログラミングをするだけです。
練習問題の解答
解答例1
let rec spower_opt1 n x =
if n == 0 then .<1>.
else if n mod 2 == 0 then
.<let x' = .~x * .~x in
.~(spower_opt1 (n / 2) .<x'>.)>.
else
.< .~x * .~(spower_opt1 (n - 1) x) >.
解答例2
let spower_opt2 n x =
let rec loop n x k=
if n == 0 then
k .<1>.
else if n == 1 then
k x
else if n mod 2 == 0 then
.<let x' = .~x * .~x in
.~(loop (n / 2) .<x'>. (fun c ->
k c))>.
else
loop (n - 1) x (fun c -> k .< .~c * .~x >.)
in
loop n x (fun y -> y)
このプログラムは以下のようなコードを生成します。
# .<fun x -> .~(spower_opt2 5 .<x>.)>.;;
- : (int -> int) code = .<
fun x_1 -> let x'_2 = x_1 * x_1 in let x'_3 = x'_2 * x'_2 in x'_3 * x_1>.
-
厳密には自分自身より上位に属するステージ(レベル)の値を参照する機能です。 ↩