2008/07/15

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>.)>.
;;
可以看到 compeval 只差在一些 .< ... >..~ 的 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

Labels: , ,

<< 回到主頁