這幾天一直在忙學校的比賽,到了今天終于有空了。
Lazy Script的語法實在是很復雜,因此不得不在進行第一步的名字檢查之后把原本的語言轉換為內部使用的一種元語言。這種元語言設計的原則是盡量簡單。譬如[y|y<-xs , y<x]這樣的語法和do-end語句就需要被轉換掉。進行了轉換以后,就需要對元語言進行一個類型方程組的建立。這一步暫時還沒有建模好,而且實際工作需不需要真的構造出一組方程組還不知道。目前還比較沒有頭緒的就是如何對模板函數的類型方程建模。
舉個例子,譬如我們對上一篇文章中提到的代碼進行類型方程組的構造:
1 makelist num list = if (num<=0)
2 list
3 (makelist (num-1) ([num]++list));
我們找到的已定義名稱有:
·(<=) :: Int -> Int -> Bool | Float -> Float -> Bool
·if :: Bool -> T -> T -> T
·(++) :: [T] -> [T] -> [T]
·(-) :: Int -> Int -> Int | Float -> Float -> Float
·0 :: Int
·1 :: Int
為上面的程序建立方程組,我們可以得到:
T(makelist) T(num) T(list) =
(Bool -> T0 -> T0 -> T0)
((<=)::(Int -> Int -> Bool | Float -> Float -> Bool) T(num) Int)
T(list)
(T(makelist)
((-)::(Int -> Int -> Int | Float -> Float -> Float) T(num) Int)
((++)::([T1] -> [T1] -> [T1]) [T(num)] T(list))
)
對上面的函數調用類型進行進一步的推導,我們可以得到:
Bool = (<=)::(Int -> Int -> Bool | Float -> Float -> Bool) T(num) Int
T0 = T(list)
T0 = T(makelist) ((Int -> Int -> Int | Float -> Float -> Float) T(num) Int) ((++)::([T1] -> [T1] -> [T1]) [T(num)] T(list))
T(makelist) T(num) T(list) = T0
緊接著繼續推導,我們有:
(<=)::(Int -> Int -> Bool | Float -> Float -> Bool) T(num) = Int
(-)::((Int -> Int -> Int | Float -> Float -> Float) T(num) = Int
[T1] = [T(num)]
[T1] = T(list)
根據上面的式子我們可以得到:
T(num)=Int
T1=Int
T(list)=[Int]
(++)::[Int] -> [Int] -> [Int]
(<=)::Int -> Int -> Bool
(-):: Int -> Int -> Int
T0 = [Int]
if :: Bool -> [Int] -> [Int]
makelist :: [Int] -> [Int] -> [Int]
至于如何為上面的整個過程建模,還得在這幾天內想出辦法來。現在唯一知道的就是,構造一個類型方程組需要確定解的名字,然后求解。解還有若干種,譬如確定解,模板解等等。具體細節還需要繼續斟酌。
posted on 2008-04-27 10:16
陳梓瀚(vczh) 閱讀(2139)
評論(0) 編輯 收藏 引用 所屬分類:
Vczh Lazy Script