多段階計算

programming-paradigmcomputer-science

プログラムの実行を複数のステージに分け、あるステージで次ステージのコードを生成・合成・実行する技法（multi-stage programming, MSP）。「コード値」を第一級に扱い、quasiquote で囲んで生成・run で実行する。MetaOCaml が代表。

3つの基本演算子（MetaOCaml）

演算子名前意味型
.< e >.bracket / quotee を今は評価せずコード値にするe : t なら .<e>. : t code
.~eescape / splicebracket の中で、別のコード値を埋め込むe : t code を bracket 内に挿入
Runcode.run erunコード値をコンパイル＋実行して値にするt code -> t

.<>. がコードを1段上に持ち上げ、.~ がその中に開けた穴へ既存コードを縫い込み、run が降ろして走らせる。.~ は必ず .<>. の内側にしか書けない（level の整合）。

実コード: べき乗の段階的特化

指数 n を生成時に固定し、x のかけ算だけが残る特化コードを作る古典例（MetaOCaml）：

(* power : int -> int code -> int code
   n は今のステージで既知、x は次ステージの値（コード値）*)
let rec power n x =
  if n = 0 then .< 1 >.
  else .< .~x * .~(power (n - 1) x) >.

(* 指数 5 で特化したコードを生成する *)
let power5_code : (int -> int) code =
  .< fun x -> .~(power 5 .< x >.) >.
(* 生成されるコード: .< fun x -> x * (x * (x * (x * (x * 1)))) >. *)

(* run で実機関数にコンパイル → ループも再帰も消えた直線コード *)
let power5 : int -> int = Runcode.run power5_code
let _ = power5 2   (* = 32 *)

power 自体の再帰（n に対する）は生成時に完全に展開され尽くし、残るコードには n も再帰も if も現れない。これが「汎用の power を指数で特化して高速化する」MSP の核心。重要なのは生成コードが型付き（int code）であること — 不正なコードは生成段階で型エラーになる（cf. Template Haskell の Q Exp は型が弱い）。

部分評価との違い

部分評価（自動）多段階計算（手動）
制御処理系が static/dynamic を判定プログラマが bracket/escape/run で明示
生成コードの型安全保証は実装依存型安全なコード生成（生成物も型付け）
狙い既知入力での特化段階的な特化・コード生成全般

両者は「汎用に書いて使用時に特化する」動機を共有する。

用途

近縁: Template Haskell、Scala LMS、Terra、staging 全般。

押さえどころ（カード化候補）

関連

Graph

Backlinks