第十三章 函数式语言的编译.ppt

1、第十三章 函数式语言的编译,本章内容 介绍一种简单的函数式编程语言SFP 介绍一种抽象机FAM，它的机器语言是SFP语言的目标语言 介绍SFP各种语言构造到FAM的编译,13.1 函数式编程语言简介,13.1.1 语言构造 函数是构建程序的基本成分 还提供一些机制用于构造更为复杂的函数 纯函数式语言禁止使用赋值语句，从而不会产生副作用，其优点是具有引用透明性，有助于程序的等式变换和推理 程序设计的任务就是定义函数 计算机按照所定义函数的相应表达式，根据计算规则逐步计算，最后得到所需的结果,13.1 函数式编程语言简介,语法论域和语法产生式 B：基值集，如布尔值、整数、. . .，用b示例 Op

2、bin：二元算符集，如+, =, and, . . . , 用opbin示例 Opun: 一元算符集，如, not, . . .，用opun示例 V ：变量集，用v 示例 E ：表达式集，用e 示例e b | v | (opun e) | (e1 opbin e2) | (if e1 then e2 else e3)| (e1 e2) / 函数应用| (v.e) / 函数抽象, 如x.x+1, 即f (x) = x+1| (letrec v1= e1; v2= e2; . . . vn= en in e0)/ 联立递归定义,13.1 函数式编程语言简介,约定 e b | v | (opun e

3、) | | (e1 e2) | (v.e)| (letrec v1= e1; v2= e2; . . . vn= en in e0) 函数应用有最高优先级并且左结合 算术和逻辑算符有通常的优先级 抽象选择最大可能的语法表达式作为v. e的体e,即e延伸到表达式的结尾或碰到第一个不能配对的右括号为止 n元函数写成v1 vn.e的形式 把fe1 em实现为一次函数应用，而不是m次应用,13.1 函数式编程语言简介,13.1.2 参数传递机制 对于表达式e1e2，用按需调用的方式传递参数 值调用 换名调用 按需调用又称惰性计算。从e1的计算开始，当第一次需要e2时，计算它的值，也就计算这一次。其它访

4、问用第一次访问时计算的值。这种方式结合了前两种方式的优点,13.1 函数式编程语言简介,例1 letrec x = 2;f = y. x + y;F = g x. g2 in F f 1 静态作用域，结果等于4 x :2, f : y. x + y, F : g x. g2是表达式2, y.x+y, g x. g2和F f 1的计算环境 表达式e和它的计算环境u形成二元组(e, u)，叫做闭包。环境u用来保证e中的自由变量会被正确地解释，因此环境u和变元e需要一起传递,13.1 函数式编程语言简介,例2 letrec comp = f .g. x. f (gx); F = x. ;G = z.

5、 ;h = comp F G in h( . ) + F( . ) + G( . ) 函数可以作为函数的变元 函数也可以作为函数的结果 n元函数可作为高阶函数使用, 当作用于m (m n)个变元时，结果是一个( n m )元的函数,13.1 函数式编程语言简介,13.1.3 变量的自由出现和约束出现 在letrec v1= e1; v2= e2; . . . vn= en in e0中，等号左边的v1, , vn是这些变量的定义性出现 在v1 vn.e的v1 vn中的v1, , vn是这些变量的定义性出现 变量出现在其它地方都是引用性出现引用性出现分成自由出现和约束出现在 (x y. (z.

6、x + z) (y + z ) ) x中，自由出现的变量：x, z约束出现的变量：x, y, z,13.2函数式语言的编译简介,概述 将按需调用语义和静态约束的函数式语言SFP的程序编译成FAM的机器语言 FAM是一种抽象机，它有一个栈，生存期符合栈式管理的所有变量都分配在栈中；它还有一个堆,所有其它的变量都存在堆中 先用一连串的例子来启发后面从SFP程序到FAM程序的编译描述,13.2函数式语言的编译简介,13.2.1 几个受启发的例子例1 1 + 2 本表达式的结果是基值类型，可以放在栈上 但是表达式结果也可能是函数，它不能放在栈上统一做法：把程序表达式的结果统一存放在堆中，在栈顶用一个指

7、针指向堆中的结果,13.2函数式语言的编译简介,13.2.1 几个受启发的例子例2 letrec x = 1/y; y = 0; z = x in 1 + 2 由letrec或函数抽象引入的变量在FAM的栈上分配单元x、y和z 的等式的编译：产生的指令序列不直接计算它们的右部，将来需要这些值时再计算 于是，生成的指令序列构造x、y和z的闭包，并将它们的指针存放在栈中y的等式无须构造闭包，因其右部不含自由变量 让z 和x 约束到同一个闭包,13.2函数式语言的编译简介,13.2.1 几个受启发的例子例3 if (if 12 then true else false) then 3 else 4

8、if 1 2 then true else false的结果在栈上更好，因为假转指令jfalse希望在栈顶测试它的值 由此，表达式的编译方式还依赖于上下文 由上下文可知，表达式true和false也应该按照结果在栈上的方式来编译,13.2函数式语言的编译简介,13.2.1 几个受启发的例子例4 letrec f = y z. if z = 0 then 1 else 1/y;x = 5in f 1 (x + 1) 由于y z. if z = 0 then 1 else 1/y是函数表达式，需把它的闭包进一步做成FUNVAL对象 FUNVAL对象和一般闭包的区别仅在于前者还包含存放变元指针的存储

9、空间 为保证1和x + 1仅在需要时计算，将它们以闭包 (包含一个指令序列和一个约束向量)的形式传递,13.2函数式语言的编译简介,13.2.1 几个受启发的例子例5 letrec x = 2 + 1;f = a b. g a + h b; g = x. . . .h = y. . . .in f x x 以闭包或值形式的表达式的指针可以拷贝多份 总是值的指针和闭包的指针而不是它们本身在传递，将它们存于约束向量和栈帧中 每个表达式只有一个实例存在 表达式对应变量的首次使用引起该表达式闭包的计算,13.2函数式语言的编译简介,13.2.1 几个受启发的例子例6 letrec f = letrec

10、 x = 2in y. x + y in f 5 该例可用来说明命令式语言和函数式语言在局部变量生存期上的区别 为了把f 作用于5，需要计算由较内letrec构造的函数。若该letrec已经计算，栈式管理会忘掉属于这个letrec的一切东西，包括局部变量x 高阶函数的出现需要延长局部变量的生存期,13.2函数式语言的编译简介,13.2.2 编译函数 表达式在不同的上下文中会编译成不同的指令序列 P：编译完整的程序表达式。结果在堆中，栈顶有一指针指向它 B：结果必须是基值并且存在栈上 V：结果在堆中，栈顶有一指针指向它。这是计算的正常情况 C：结果必须是被编译表达式的闭包。函数的变元和递归等式的

11、右部总是这种情况,13.2函数式语言的编译简介,13.2.3 环境与约束 名字的定义性出现总是关联到一个闭包1、一个等式被编译时，其左部的名字总是关联到 其右部的闭包2、抽象中的约束名字是在函数应用时关联到该 次应用的变元的闭包 名字引用性出现的编译：获得相关联的定义性出现的值 符号表在此称为编译环境 当函数抽象的体或letrec中的表达式开始编译时，新引入的局部变量必须被加入编译环境,13.2函数式语言的编译简介,13.2.3 环境与约束 编译环境包含1、变量的性质：自由(GLOB)还是约束(LOC)2、变量的位置：相对地址或下标 存储分配1、表达式中的局部变量在栈上分配存储单元, 使用栈帧

12、的相对地址 2、全局变量存储单元的指针分配在约束向量中， 依据约束向量中下标可以找到这些指针,13.3 抽象机的体系结构,从本节开始, 逐步描述FAM 的体系结构和指令集, 以及把SFP编译到FAM的编译方案 FAM的存储器包含：程序存储区PS、栈ST、堆HP FAM的程序1、每条指令占一个单元2、某些指令含一个运算对象3、程序计数器PC总是保留当前指令的地址,13.3 抽象机的体系结构,13.3.1 抽象机的栈 和第6章的活动记录栈类似，但这里栈向下增长 基值、各种地址都只占一个单元 函数应用的栈帧如图 SP是栈顶指针 FP是当前栈帧指针 继续地址就是返回地址 FPold是老FP的值 GPo

13、ld是老的全局变量构成的向量的指针,13.3 抽象机的体系结构,13.3.1 抽象机的栈 和第6章的活动记录栈类似，但这里栈向下增长 基值、各种地址都只占一个单元 闭包计算的栈帧如图，无需实在参数域建立和释放栈帧可以用一组固定的指令,13.3 抽象机的体系结构,13.3.2 抽象机的堆 堆对象有四类 BASIC：存放基值的单元b FUNVAL：对象表示一个函数值。它有三个成分1、cf：指向程序区中函数体开始的地方2、fap：指向函数变元向量3、fgp：函数各全局变量值的指针所组成的向量的指针后两个向量也存在堆中,13.3 抽象机的体系结构,13.3.2 抽象机的堆 堆对象有四类 BASIC：存

14、放基值的单元b FUNVAL：对象表示一个函数值 CLOSURE：对象是一个闭包，有两个成分1、cp：代码指针2、gp：全局变量值的指针向量的指针,13.3 抽象机的体系结构,13.3.2 抽象机的堆 堆对象有四类 BASIC：存放基值的单元b FUNVAL：对象表示一个函数值 CLOSURE：对象是一个闭包 VECTOR：对象是堆对象指针的向量1、存放函数变元的指针，或2、存放FUNVAL对象的全局变量的指针，或3、存放CLOSURE对象的全局变量的指针,13.3 抽象机的体系结构,13.3.2 抽象机的堆 建立堆对象的指令如下 mkbasic：建立基值 mkfunval：建立函数值 mkc

15、los：建立闭包 mkvec n：建立有n分量的向量 alloc：建立空闭包,13.3 抽象机的体系结构,13.3.3 名字的寻址 问题 函数定义的编译必须考虑函数应用允许变元不足和变元过剩的情况 编译函数应用e e1 . em时，编译器并非总能知道被应用函数的变元个数 这给编译时确定栈帧中变元和局部变量的地址带来困难,13.3 抽象机的体系结构,13.3.3 名字的寻址 考虑执行函数应用e e1 . em时名字的寻址 若基于FP访问，编译函数定义时，由于不知 实参个数， 局部变量 的寻址困 难,13.3 抽象机的体系结构,13.3.3 名字的寻址 考虑执行函数应用e e1 . em时名字的寻

16、址 以左图中目前SP的位置为基准较好，但需要克服 SP动态变 化带来 的困难,13.3 抽象机的体系结构,13.3.3 名字的寻址 考虑执行函数应用e e1 . em时名字的寻址 选择动态地址sp0作为寻址的基地址 SP的当前值spa和sp0的值之间的差， 对函数体的每点来说是静态可 确定的，因为已出现的新局部 变量和中间结果数目是已知的 这个差值在编译时保存在 编译参数sl中，在程序点的值用 sla表示，则有关系式 spa = sp0 + sla 1,13.3 抽象机的体系结构,13.3.3 名字的寻址 考虑执行函数应用e e1 . em时名字的寻址 选择动态地址sp0作为寻址的基地址 sp

17、a和sp0的值之间的关系spa = sp0 + sla 1 生成的指令可以使用编译时 确定的值sla和运行时spa来计算 运行时的值sp0,13.3 抽象机的体系结构,13.3.4 约束的建立 对每个函数定义及表达式，自由变量集静态可知 这些变量的地址存在一个向量中 该向量的指针存放在堆中作为FUNVAL或CLOSURE对象的一部分 在计算闭包或函数应用时，该指针复写到GP，即运算时可以通过GP去寻找该向量的元素,13.4 指令集和编译,本节一步步地描述编译和所需要的FAM指令 使用4个编译函数P_code、B_code、V_code和C_code 对代码执行结果的不同期望决定使用不同的编译函

18、数 这些函数有三个参数：被编译的表达式e，变量环境 和栈标高sl（sl定义了被生成的代码执行前SP寄存器的值和地址sp0的差）课堂上的介绍比较宏观，需课后了解抽象机 各指令后才能完全明白,13.4 指令集和编译,13.4.1 表达式 1、程序表达式P_code e = V_code e 0；stop 环境为空 栈标高sl是0,13.4 指令集和编译,13.4.1 表达式 2、简单表达式（结果是基值并在栈上，例举）B_code b sl = ldb bB_code (e1 opbin e2) sl = B_code e1 sl;B_code e2 sl+1;opbinB_code e sl =

19、/ e不是基值、算符和if表达式 V_code e sl ;getbasic,13.4 指令集和编译,13.4.1 表达式 2、简单表达式（结果是基值并在堆上，例举）V_code b sl = B_code e sl; mkbasicV_code (if e1 then e2 else e3) sl =B_code e1 sl;false l1;V_code e2 sl;ujmp l2;l1 : V_code e3 sl;l2 :,13.4 指令集和编译,13.4.2 变量的引用性出现V_code v sl = getvar v sl;evalC_code v sl = getvar v sl

20、getvar v sl = let (p, i) = (v)in if p = LOC then pushloc sl - ielse pushglob ifigetvar为局部变量和形式参数产生pushloc指令， 为全局变量产生pushglob指令,13.4 指令集和编译,13.4.3 函数定义V_code (v1 . vn. e) sl = C_code ( v1 . vn. e ) slC_code ( v1 . vn. e) sl = pushfree fr sl; / 拷贝全局变量的值的指针mkvec g; mkvec 0; / 空的变元向量ldl l1; / 函数代码的地址mkf

21、unval;ujmp l2; l1 : targ n; / 测试变元个数V_code e (vi(LOC, i)vj (GLOB, j) 0;return n; (i = 1, , n) ( j = 1, , g)l2 :,13.4 指令集和编译,13.4.3 函数定义fr = v1, , vg = list (freevar ( v1 . vn. e) )pushfree v1, , vg sl =getvar v1 sl;getvar v2 (sl +1);. . .getvar vg (sl + g 1)1、fr表示 v1 . vn. e中的自由变量表2、pushfree生成将这些变量的

22、指针压栈的指令序列,13.4 指令集和编译,13.4.4 函数应用V_code (e e1 . em ) sl = / e eemark l; /建新栈帧, 保留当前继续地址l, FP, GP C_code em (sl + 3); /为变元在堆上建立闭包, . . . /并把闭包的指针压栈 C_code e1 (sl + m + 2);V_code e (sl + m + 3); / 计算e, 结果指针压栈apply;l :,13.4 指令集和编译,apply指令执行前后情况 FUNVAL中已有变元a1, , an，本次调用还有变元已先行进栈 PC修改成函数代码起始地址,13.4 指令集和编

23、译,targ n 指令发现变元不足(n m) 将栈中已有的m个变元打包成向量 重新做成FUNVAL，和原先相比，变元多了 本次函数应用到此为止，返回,13.4 指令集和编译,return n指令(SP = FP +1 + n，没有多余参数) 函数值拷贝到适当的地方，并释放当前栈帧,13.4 指令集和编译,return指令(有多余参数)函数应用消费适当个数的变元，其结果是一个函数再应用到剩余变元，它们的指针仍在栈上 (x.(yz.x + y + z)3)4 5 的执行会出现这种情况,13.4 指令集和编译,13.4.5 构造和计算闭包C_code e sl = / 同编译函数类似，无变元部分pu

24、shfree fr sl; / 将全局变量的值压栈mkver g; / 把它们做成一个向量ldl l1; / 闭包代码的地址mkclos;ujmp l2;l1 : V_code e vi (GLOB, i ) 0; (i = 1, , n)update; l2 :,13.4 指令集和编译,update指令的效果 用闭包的计算结果去覆盖该闭包对象 以后eval指令发现已经不是闭包，则不再计算,13.4 指令集和编译,13.4.6 letrec表达式和局部变量 V_code (letrec v1 = e1; .; vn= en in e0) sl = repeat n alloc; / 在堆上建立

25、n个空对象, 将指针压栈 C_code e1 sl; / 为ej 建立闭包rewrite n; / 覆盖对应的空闭包对象C_code e2 sl;rewrite n 1;. . . C_code en sl;rewrite 1;V_code e0 sl; / 生成计算e0的指令序列slide n / 放弃e1, ., en在栈顶指针，剩下e0指针,13.4 指令集和编译,13.4.6 letrec表达式和局部变量 V_code (letrec v1 = e1; .; vn= en in e0) sl = repeat n alloc; / 在堆上建立n个空对象, 将指针压栈 C_code e1 sl; / 为ej 建立闭包rewrite n; / 覆盖对应的空闭包对象. . . = vi (LOC, sl + i 1) (i = 1, , n) 依据全局变量和v1, ., vn，为e0, e1, ., en建立同样的环境 sl= sl + n n次alloc使SP的值增加n,习 题,