[MetaOCaml] Taste for fun

唔唔,
希望開學前能擠出一點東西
所以這幾天也撥了一點時間在看MSP的東西

根據之前看到的東西所歸納出的結論
還是去稍微玩一下MetaOCaml才會對MSP比較熟
這樣應該會比較有點想法(希望XD)
不過也許partial evaluation那裡也會需要補?
這個還是未定數,之後再說

回到主題

MetaOCaml可以到這裡下載
我下載的是309_alpha_030
安裝環境是Mac OS X 10.5.4

unzip以後裡面有INSTALL檔案一個
照該檔案的步驟安裝即可
安裝好以後在console鍵入

$ metaocaml

就可以進入interpreter之中

接著開始第一個MetaOCaml程式
首先, 開一個檔案 hello.ml
並且鍵入內容如下

let rec power (n, x) = match n with
0 -> .<1>. | n -> .<.~x * .~(power (n-1, x))>.;;

let power2 = .! . .~(power (2,..))>.;;

然後打開metaocaml並且讀入該檔案

$ metaocaml -init hello.ml

接著console會顯示

MetaOCaml version 3.09.1 alpha 030
#

在 # 之後就可以直接開始輸入指令來做測試
別忘記以 ;; 結尾

現在先來試試看

# power (5,.<3>.);;
- : ('a, int) code = .<(3 * (3 * (3 * (3 * (3 * 1)))))>.
# power2 5;;
- : int = 25

很好跑起來沒問題
現在我們來看一下上面的code是什麼意思

let rec power (n, x) =
match n with
0 -> 1 | n -> x * power (n-1, x);;

這是原本的power的定義
這個function基本上很好用
因為他可以當作是"任何x的n次方"來用
可是他有一點小問題
只要我們的n比1大的話
不管n取多小, 整個function都會需要recursive call數次不等

例如說 power (2,x) 不論x是多少
整個evaluation都會有兩次的recursive call
可是如果今天我們用手來算就不會這樣寫
我們一定會直接寫 1*x*x

那麼, 可不可以在知道n的時候
就把整個function變成1*x*x*...這樣的形式?
也就是去除那些function call的成本

答案當然是可以的
不然這篇文章不就是在自打嘴巴? XD

在MetaOCaml裡面的作法很簡單
我們只要用一些stage annotation來annotating原本的code
讓它具有stage evaluating的能力
這樣我們就可以在知道n的後就把整個function改寫成快速的版本

這些annotation就是

.< >.
.~
.!

依序分別可以用口語解釋成 "將某段code當作是data",
"將某段data當作是code" 和 "某段data當作是program來運算"
相當於LISP裡的

`
,
eval

所以我們新的staged power就是這樣

let rec power (n, x) = match n with
0 -> .<1>. | n -> .<.~x * .~(power (n-1, x))>.;;

如果n是零,就回傳"1"當作是data
如果不是零,就先去算power(n-1,x)的值
然後在前面加上"x*",最後在整串當作data回傳回去
因為整個算出來是data
所以要求值就須要用 .! 去跑

# .! (power (2,.<3>.));;
- : int = 9