My First MetaOCaml Program

上一次寫 OCaml 已經是一年前的事了，感覺好陌生 XD。不過我還是成功把第一個 MetaOCaml 程式湊出來啦！這是 Neil Jones 講 partial evaluation 用的例子：一個簡單 postfix calculation 語言的 interpreter。這個語言之下的程式是由一連串的指令組成，每個指令可能是 variable、addition、或 multiplication：

type instr = Var | Add | Mul;;

這種程式的執行參數是一個固定值 x 和一個 runtime stack。Var 指令把 x 推入 stack；Add 把 stack 最頂端的兩個元素拿出來相加後把結果放回 stack；Mul 則是相乘。我們可以根據這個操作語意寫一個 interpreter：

let rec eval ts x s = match ts with
  | [] -> (match s with a :: tail -> a)
  | t :: ts -> (match t with
    | Var -> eval ts x (x :: s)
    | Add -> (match s with
      | a :: b :: tail -> eval ts x ((a + b) :: tail))
    | Mul -> (match s with
      | a :: b :: tail -> eval ts x ((a * b) :: tail)))
;;

到這裡都還是基本的 OCaml。接下來根據 First Futamura Projection，若我們把這個 interpreter 針對某個 source program 特化，效果就相當於編譯那一份 source program。

let rec comp ts x s = match ts with
  | [] -> .<match .~s with a :: tail -> a>.
  | t :: ts -> match t with
    | Var -> comp ts x .<.~x :: .~s>.
    | Add -> .<match .~s with
      | a :: b :: tail -> .~(comp ts x .<(a + b) :: tail>.)>.
    | Mul -> .<match .~s with
      | a :: b :: tail -> .~(comp ts x .<(a * b) :: tail>.)>.
;;

可以看到 comp 和 eval 只差在一些 .< ... >.、.~ 的 annotations。用 .< >. 括起來的部份是 "code"，當下不會執行，但裡面用 .~（"escape"）修飾的算式又會立刻被執行。因此在 MetaOCaml 裡面可以很輕鬆地（呃，至少是比較輕鬆地）指定哪些部份要立刻執行，哪些部份稍後才執行。以 partial evaluator 為例，只和特化期（specialisation time）資訊相關的部份可以先算（例如 interpreter 辨別指令種類所用的 pattern matching），和執行期資訊有關的部份則產出 code，等真正執行拿到引數時再算。

現在定義

let compiler ts = .<fun x -> .~(comp ts .<x>. .<[]>.)>.;;

令 ts = [Var;Var;Var;Add;Mul;Var;Add;Var;Var;Add;Mul]，MetaOCaml 會產出以下的 specialised program text：

.<fun x_1 ->
   (match [x_1; x_1; x_1] with
    (a_2 :: b_3 :: tl_4) ->
     (match ((a_2 + b_3) :: tl_4) with
      (a_5 :: b_6 :: tl_7) ->
       (match (x_1 :: (a_5 * b_6) :: tl_7) with
        (a_8 :: b_9 :: tl_10) ->
         (match (x_1 :: x_1 :: (a_8 + b_9) :: tl_10) with
          (a_11 :: b_12 :: tl_13) ->
           (match ((a_11 + b_12) :: tl_13) with
            (a_14 :: b_15 :: tl_16) ->
             (match ((a_14 * b_15) :: tl_16) with (a_17 :: tl_18) -> a_17))))))>.

可以看到判斷指令種類的 pattern matching 都消失了，相鄰的 Var 指令都被合併在一起… 等等的變化。原本的 postfix 程式結構已經融入殘存的計算當中。我的希望是 specialised program 可以變成最單純的算式啦（也就是不要出現 runtime stack），可是好像有點難 XD。

--
真是太炫了！XD