这几天一直在忙学校的比赛,到了今天终于有空了。
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) 阅读(2124)
评论(0) 编辑 收藏 引用 所属分类:
Vczh Lazy Script