*練習で適当に書いた怪文章です．*
初めに
さて，メタプログラミングと聞いて皆さんはどのようなイメージを抱きますか．今日におけるプログラミング言語の流行をみる限り，おそらく多くの人はC++のマクロやTemplateを思い浮かべることができると思います．しかしながら本稿で紹介するBER MetaOCamlは，OCamlというML系言語をMulti-stage Programming (MSP，多段階プログラミング)というパラダイムで拡張した形態のプログラミング言語であり，すなわちMetaOCamlにおけるメタプログラミングは上記のものと少々異なる性質を持ちます．そこで本稿ではMSPの基礎について私が学んできたことをまとめて理解を深めると同時に，アウトプットによってこれを皆さんと共有したいと思います．
途中に(Meta)OCamlのコードが現れるためML系言語の基礎的な文法の知識は必要ですが，分からなければ適当な大学の講義資料にある演習問題などで鍛錬すれば十分だと思います．体系的なものとしては，以下のようなものが俗におすすめされているようです．
OCaml標準ライブラリについては次の公式ドキュメントを参照するとよいです．
https://caml.inria.fr/pub/docs/manual-ocaml/libref/index.html
他にもOCamlのツールチェーン等で困ったら，開発元であるこのINRIAのサイトを参照するとよいでしょう．
環境構築
まずはopam2をインストールして，その上でMetaOCamlの環境を構築します．
Ubuntuを使っている場合では，aptのデフォルトがopam1になっているので注意してください．
MacOSユーサの場合，brewで適当にコマンドを叩けば特に問題ありません．
こちらを参考に，例えばbrewの場合...
$ brew update
$ brew upgrade
$ brew install opam rlwrap
$ opam init
$ opam update
$ opam switch create 4.11.1+BER
$ eval `opam config env`
のような形になると思います．
並列ビルドが上手く行かない場合があるとのことで，-j 1をつけたほうが良いかも知れません
参考：https://github.com/ocaml/opam-repository/pull/14257
REPLは$ rlwrap metaocamlで起動します．最低限#helpを覚えて，困ったら#require, #directory, #load, #use, #showあたりのコマンドでググればOCaml生活が捗ります．
序論
メタプログラムとは，プログラムのコードをデータとして明示的に扱う計算の記述，すなわち，計算中にプログラムを生成するプログラムのことを言います．この「プログラムを生成するプログラム」の言語のことをメタ言語，「メタ言語のプログラムが生成するプログラム」の言語のことを対象言語と呼称します．
さて，一口にメタプログラミングといってもそれを実現する手法によって種類が色々あるのですが，ここではtemplate, macro, stagingの3つに分類します．私自身メタプログラミングの方法論よりもユーザーとして使い方にちょっと詳しい程度なので，直観性を重視してカジュアルに説明します．ただし，詳細な補足資料として，A Survey of Metaprogramming LanguagesやDSL Implementation in MetaOCaml, Template Haskell, and C++を挙げておきます(後者は日本語の感想記事が参考になるかも？)．
始めはtemplateです．これに当てはまるのはもちろんC++ Templateなどです．そもそもテンプレートは文章の雛形のことなどを指していいますよね．C++ Templateというのはその名の通り，C++のプログラムの雛形となるものです．ここでf(x)=x+1で定義される関数f（の記述）について考えてみると，これは変数xがある種の穴になっていて，穴の位置には適当なものを入れられるが，全体としては○+1という形をとらなければいけないという意味でテンプレートになっています．C++における関数テンプレートはこの性質を利用して，型変数によらずある一定のフォーマットをとった関数を与える（パラメータ多相性）という意味でテンプレートになっています．これが本来C++ Templateが意図しているはずの機能です．ところがC++ Templateは，C++のソースコードのコンパイル時に，テンプレートから生成された具体型に対するC++のコードをソースコード中にインライン化します．少し見方を変えてみると，これはC++のコードを生成していることになる訳ですね．冒頭の一文を思い出してください．これはメタプログラミングの定義そのものです．
次はmacroです．C++におけるmacroはコンパイラに対する命令のことですが，こういったものは，ソースコードの文字列およびASTを直接書き換えることによってコードの生成・埋め込みを扱うことができます．例えばC++ Templateは純粋な言語なのでコード生成は型安全に行われますが，こちらはそんなことはないので柔軟な反面，危険なコードも生成できてしまいます．
そして最後のカテゴリーとして，今回の主題であるstagingによるメタプログラミング，すなわちMSP（Multi-stage Programming）というものが存在します．MSPの特徴は，あるプログラミング言語を基礎(stage N)として．そこに自己言及の機能を加えて高次に拡張されたプログラミング言語を用いるところにあります．すなわちOCamlのコード(stage N)を生成するコード(stage N-1)に対して，更にそれを生成するようなコード(stage N-2)...(N=1まで同様に繰り返す）が存在し，MetaOCaml＝stage 0（初期段階）のコードはこれらを値として扱うことができます．まとめるとMetaOCamlは自分自身が対象言語であるようなメタ言語であり，対象言語での記述を.<>.という注釈によって区別することで第１級の値として扱います．この第１級の値としての対象言語の記述は対象言語のコードであることからオブジェクトコード（対象コード）と呼ばれますが，これには適切な型がついているため，オブジェクトコード同士を合成して新たなオブジェクトコードを型安全に生成することさえもできます．また変数名の衝突や閉じていない（自由変数が出現する）コードの生成なども適切に扱われます．
MSPの特徴が与える素朴な有用性をあげるとしたら，対象言語で記述されたコードに記述の構造を保存したままアノテーションを追加するだけで，これをメタプログラム上で安全に扱えるということがあります．これはコード生成による最適化の基礎となりますが，MSPによるプログラミングの例を通じてこのことを確認してみましょう．
次に示すのは，powの再帰呼び出しをインライン展開することに対応する有名な例です．
(* stage N = stage 1 = 最終段階のプログラム *)
let rec pow x n =
if n = 0 then 1
else x * pow x (n-1);;
(* stage 0のプログラム = 記述の構造は上記と全く変わらないが，再帰呼び出しがインライン展開されたけいしきコードを生成するメタプログラム *)
let rec pow_staged x n =
if n = 0 then .<1>.
else .<.~x * .~(pow_staged x (n-1))>.;;
(* これもstage 0のプログラムで上記と同等の最適化を実現するが，記述の構造が変わる別のメタプログラム *)
let pow_staged' x n =
let rec loop n =
if n = 0 then []
else x :: loop (n-1) in
loop n |> List.fold_left (fun z e -> .<.~z * .~e>.) .<1>.;;
pow_staged .<10>. 2;;
.~という演算子がありますが，これは.<>.の内部のみに現れて，オブジェクトコードを生成する際に既存のオブジェクトコードから記述をとりだして.<>.内に展開するために用いられます．
MetaOCamlをREPLで実行して以上のコードを打ち込むと次のような結果を得ることができるはずです．
# pow_staged .<10>. 2;;
- : int code = .<10 * (10 * 1)>.
今pow_staged .<10>. 2は，pow 10 2という関数呼び出しに代替され，10 * (10 * 1)という算術式を生成する役割を果たしています（ちなみにScala LMSやScala3もMSPの機能を持っていますが，これらはimplicitによって.<>.と.~を隠蔽できます）．
ちなみに，if n=0 then 1の部分をif n=1 then xとすれば惨めな*1を消去してさらに最適化することができますが，MSPの記述の構造を保つ利点を考慮すると，こういったad hocな最適化はあまり好ましくないでしょう．ケンブリッジ大学の講義資料（Multi-stage programming (I)）では，partially static monoidを導入することでもう少し高度なstagingを行う方法が紹介されています．partially staticについては後述します．
もう少し応用的な場合としてfold_rightのstagingを考えましょう．どのレベルでstagingできるかは「静的にどこまで知っているか」に依存しますが，ループを丸ごと展開できる極端な場合は次のようになるでしょう．
type 'a staged_list = 'a code list;;
let rec of_int_list : int list -> int staged_list =
function
|[] -> []
|l::ls -> .<l>. :: of_int_list ls;;
let rec read_mul : int -> int staged_list =
function
|0 -> []
|n -> .<read_int ()>. :: (read_mul @@ n-1);;
let rec fold_right_s : (('a code -> 'z code -> 'z code) * 'z code) ->
'a staged_list ->
'z code =
fun (f, zero) ->
function
|[] -> zero
|l::ls -> f l @@ fold_right_s (f,zero) ls;;
of_int_list [1;2;3;4;5;6;7;8;9;10] |> fold_right_s ((fun z x -> .<.~z + .~x>.), .<0>.);;
(*
- : int code = .<
1 + (2 + (3 + (4 + (5 + (6 + (7 + (8 + (9 + (10 + 0)))))))))>.
*)
read_mul 10 |> fold_right_s ((fun x z -> .<.~x + .~z>.), .<0>.);;
(*
- : int code = .<
(Stdlib.read_int ()) +
((Stdlib.read_int ()) +
((Stdlib.read_int ()) +
((Stdlib.read_int ()) +
((Stdlib.read_int ()) +
((Stdlib.read_int ()) +
((Stdlib.read_int ()) +
((Stdlib.read_int ()) +
((Stdlib.read_int ()) + ((Stdlib.read_int ()) + 0)))))))))>.
*)
MetaOCamlを利用する場合における基礎的な注意
f : int -> 'aの下におけるfun (x: int) -> .<f x>.というコードは，メタ言語上の関数であるfを対象言語上のプログラムに埋め込むCSPという機能を利用したものになります．これはfがスコープに存在して参照できる場合のみしか意味がないために，逆に参照できない場合には色々と困ったことになります．端的に言うとMetaOCamlのプログラムをコンパイルして利用したい場合などに問題になるのですが，その場合はとりあえずfの定義を別のファイルに移すか，fをstagingすることで避けられます．
また，MetaOCamlのbuildの仕方についてですが，私はmakeで
ocamlfind -toolchain metaocaml ocamlopt -a -o $@ -linkpkg \
-package リンクしたいパッケージ \
リンクしたいファイル
のようなコマンドを実行しています．duneなどでのやり方も英語でググったらでてきたと思います．
例えばこれなど参照．
https://qiita.com/keigoi/items/c9f43309312978acf05a
最後に
本稿ではメタプログラミングをtemplate，macro，stagingの三種類に分類し，このうちのstagingに該当するMSPの機能をもった，MetaOCamlによるメタプログラミングを紹介しました．他の２つの手法と比較して，stagingは未だアカデミアで認知されるにとどまります．しかしながら，MSPによる安全性の保証された自己言及形式のメタプログラミングは，コード生成による体系的な最適化基盤を構築する上で非常に有益であることが，読者の皆様は感じ取れたのではないかと思います．