随笔-341  评论-2670  文章-0  trackbacks-0
    类型推导到这里也就结束了。虽然可能有点小bug,不过这个以后遇到再处理了。接下来的一个模块是跟类型推导没有耦合的新模块,两边可以平行处理。

    Kernel FP的指令集不同于以往的指令集。因为作为一门纯函数式语言,就必须要有laziness。这就是说,凡是可以不运行的代码都一定不运行,凡是可以晚一点执行的代码一律等到需要的时候再执行。也就是说,参数传进函数的时候,传的是代码而不是值。我们可以得到一个推论就是:代码的执行顺序是不能影响程序的执行结果的,如果两个表达式耦合了,那么一定是确定了顺序的。因此指令集只能用来表达代码的逻辑结构。

    其实确定顺序是一个什么样子的东西呢?举个例子,我们拥有一个从用户那里读字符串的函数:Input,我们需要将用户输入的三个字符串传入一个函数:
    Function Input Input Input
    实际上这是不行的,因为三个Input是耦合的,因此他们必须满足嵌套关系。当然,编译器会检查出来。

    实际上怎么写呢?因为顺序要确定,所以逻辑上大概就是:
    do
        a=Input
        b=Input
        c=Input
        pack (Function a b c)
    end

    Kernel FP没有变量,因此abc只是三个表达式的别名而已。那么我们如何将代码转变为嵌套的表达式以便推导呢:我们可以产生若干临时函数:
    我们用\a->b来表达一个匿名函数,输入a返回b
    Input >>= \a->( Input >>= \b-> (Input >>= \c-> (pack (Function a b c))))
    当然,根据优先级我们可以去掉一些括号:
    Input >>= \a->Input >>= \b->Input >>= \c-> pack (Function a b c)

    这个时候仍然不能保证三个Input的执行顺序,因此我们将Input定义为一个需要一个状态参数的函数,然后定义>>=去传递状态。剩下来就是大家都无比熟悉的Monad了,略过不讲。因为产生状态只能由Input这个黑盒自己搞,所以由于类型系统的约束,第三个Input需要的状态参数由第二个Input产生,递归下去,顺序就被强制确定了。

    当然,未来的语法应该会很漂亮的。

    Kernel FP的laziness是通过对代码的推导自动获得的。这个推导跟我们在做数学题的推导是一样的。我们看一个例子:
1 def sum count xs =
2     select xs of
3         case empty : 0
4         case list x tail : if (iequ count 00 (iadd x (sum (isub count 1) tail))
5     end
6 
7 def array i = list i (array (iadd i 1))
8 
9 def main = sum 3 (array 1)

    sum count xs求数组前count项合,array i则产生[i , i+1 , i+2...]这样的无穷数组,因此main的结构必然是1+2+3=6。推导过程如下:
 1   main
 2 = sum 3 (array 1)
 3 = select (array 1) of
 4       case empty : 0
 5       case list x tail : if (iequ 3 00 (iadd x (sum (isub 3 1) tail))
 6   end
 7 = select list 1 (array (iadd 1 1)) of
 8       case empty : 0
 9       case list x tail : if (iequ 3 00 (iadd x (sum (isub 3 1) tail))
10   end
11 = if (iequ 3 00 (iadd 1 (sum (isub 3 1) (array (iadd 1 1))))
12 = iadd 1 (sum (isub 3 1) (array (iadd 1 1)))
13 = iadd 1 
14   (select (array (iadd 1 1)) of
15         case empty : 0
16         case list x tail : if (iequ (isub 3 100 (iadd x (sum (isub (isub 3 11) tail))
17   end)
18 = iadd 1
19   (select (list (iadd 1 1) (array (iadd (iadd 1 11))) of
20         case empty : 0
21         case list x tail : if (iequ (isub 3 100 (iadd x (sum (isub (isub 3 11) tail))
22   end)
23 = iadd 1 (if (iequ (isub 3 100 (iadd (iadd 1 1) (sum (isub (isub 2 11) (array (iadd (iadd 1 11)))))
24 = iadd 1 (iadd (iadd 1 1) (sum (isub 2 1) (array (iadd (iadd 1 11))))
25 = iadd 1 (iadd (iadd 1 1
26   (select (array (iadd (iadd 1 11)) of
27         case empty : 0
28         case list x tail : if (iequ (isub 2 100 (iadd x (sum (isub (isub 2 11) tail))
29   end
30   )
31 = iadd 1 (iadd (iadd 1 1
32   (select (list (iadd (iadd 1 11) (array (iadd (iadd (iadd 1 111)) of
33         case empty : 0
34         case list x tail : if (iequ (isub 2 100 (iadd x (sum (isub (isub 2 11) tail))
35   end)
36 = iadd 1 (iadd (iadd 1 1) (if (iequ (isub 2 100 (iadd (iadd (iadd 1 11) (sum (isub (isub 2 11) (array (iadd (iadd (iadd 1 111)))))
37 = iadd 1 (iadd (iadd 1 1) (iadd (iadd (iadd 1 11) (sum (isub 1 1) (array (iadd (iadd (iadd 1 111))))
38 = iadd 1 (iadd (iadd 1 1) (iadd (iadd (iadd 1 11)
39   (select (array (iadd (iadd (iadd 1 111)) of
40       case empty : 0
41       case list x tail : if (iequ (isub 1 100 (iadd x (sum (isub (isub 1 11) tail))
42   end)
43 = iadd 1 (iadd (iadd 1 1) (iadd (iadd (iadd 1 11)
44   (select (list (iadd (iadd (iadd 1 111) (array (iadd (iadd (iadd (iadd 1 1111))) of
45       case empty : 0
46       case list x tail : if (iequ (isub 1 100 (iadd x (sum (isub (isub 1 11) tail))
47   end)
48 = iadd 1 (iadd (iadd 1 1) (iadd (iadd (iadd 1 11) (if (iequ (isub 1 100 (iadd (iadd (iadd (iadd 1 111) (sum (isub (isub 1 11) (array (iadd (iadd (iadd (iadd 1 1111)))))
49 = iadd 1 (iadd (iadd 1 1) (iadd (iadd (iadd 1 110))
50 = iadd 1 (iadd 2 (iadd (iadd 2 10))
51 = iadd 1 (iadd 2 (iadd 3 0))
52 = iadd 1 (iadd 2 3)
53 = iadd 1 5
54 = 6

    接下来要做的是,确定指令集的形式了。指令集的作用有两个,产生代码以及推导代码。
posted on 2008-10-11 02:10 陈梓瀚(vczh) 阅读(1428) 评论(1)  编辑 收藏 引用 所属分类: 脚本技术

评论:
# re: Kernel FP 指令集 2008-10-14 05:34 | Lnn
How big of you!  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理