编译原理 函数式语言的编译13

1、第十三章第十三章 函数式语言的编译函数式语言的编译本章内容本章内容 介绍一种简单的函数式编程语言介绍一种简单的函数式编程语言sfp 介绍一种抽象机介绍一种抽象机fam，它的机器语言是，它的机器语言是sfp语言的目标语言语言的目标语言 介绍介绍sfp各种语言构造到各种语言构造到fam的编译的编译13.1 函数式编程语言简介函数式编程语言简介13.1.1 语言构造语言构造 函数是构建程序的基本成分函数是构建程序的基本成分 还提供一些机制用于构造更为复杂的函数还提供一些机制用于构造更为复杂的函数 纯函数式语言禁止使用赋值语句，从而不会产生纯函数式语言禁止使用赋值语句，从而不会产生副作用，其优点是具有

2、引用透明性，有助于程序副作用，其优点是具有引用透明性，有助于程序的等式变换和推理的等式变换和推理 程序设计的任务就是定义函数程序设计的任务就是定义函数 计算机按照所定义函数的相应表达式，根据计算计算机按照所定义函数的相应表达式，根据计算规则逐步计算，最后得到所需的结果规则逐步计算，最后得到所需的结果 13.1 函数式编程语言简介函数式编程语言简介 语法论域和语法产生式语法论域和语法产生式 b：基值集，如布尔值、整数、：基值集，如布尔值、整数、. . .，用，用b示例示例 opbin：二元算符集，如：二元算符集，如+, =, and, . . . , 用用opbin示例示例 opun: 一元算符

3、集，如一元算符集，如 , 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

4、 | (opun e) | | (e1 e2) | ( v.e) | (letrec v1= e1; v2= e2; . . . vn= en in e0) 函数应用有最高优先级并且左结合函数应用有最高优先级并且左结合 算术和逻辑算符有通常的优先级算术和逻辑算符有通常的优先级 抽象选择最大可能的语法表达式作为抽象选择最大可能的语法表达式作为 v. e的体的体e,即即e延伸到表达式的结尾或碰到第一个不能配对的延伸到表达式的结尾或碰到第一个不能配对的右括号为止右括号为止 n元函数写成元函数写成 v1 vn.e的形式的形式 把把fe1 em实现为一次函数应用，而不是实现为一次函数应用，而不是m次应用

5、次应用 13.1 函数式编程语言简介函数式编程语言简介13.1.2 参数传递机制参数传递机制对于表达式对于表达式e1e2，用按需调用的方式传递参数，用按需调用的方式传递参数 值调用值调用 换名调用换名调用 按需调用按需调用又称惰性计算。从又称惰性计算。从e1的计算开始，当第一次需要的计算开始，当第一次需要e2时，计算它的值，也就计算这一次。其它访问时，计算它的值，也就计算这一次。其它访问用第一次访问时计算的值。这种方式结合了前两用第一次访问时计算的值。这种方式结合了前两种方式的优点种方式的优点 13.1 函数式编程语言简介函数式编程语言简介 例例1letrec x = 2;f = y. x +

6、 y;f = g x. g2in 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 函数式编程语言简介函数式编程语言简介 例例2letrec comp = f . g. x. f (gx);f =

7、 x. ;g = z. ;h = comp f gin h( . ) + f( . ) + g( . ) 函数可以作为函数的变元函数可以作为函数的变元 函数也可以作为函数的结果函数也可以作为函数的结果 n元函数可作为高阶函数使用元函数可作为高阶函数使用, 当作用于当作用于m (m m) 将栈中已有的将栈中已有的m个变元打包成向量个变元打包成向量 重新做成重新做成funval，和原先相比，变元多了，和原先相比，变元多了 本次函数应用到此为止，返回本次函数应用到此为止，返回pc = pcoldgp = gpoldfp = fpoldsp执行后执行后funval: pc, ,gpvector: am

8、, , a1amgpoldfpold执行前执行前fppcold. . .a1a2sp13.4 指令集和编译指令集和编译 return n指令指令(sp = fp +1 + n，没有多余参数，没有多余参数) 函数值拷贝到适当的地方，并释放当前栈帧函数值拷贝到适当的地方，并释放当前栈帧angpoldfpold执行前执行前fppcold. . .xa1spsp执行后执行后x13.4 指令集和编译指令集和编译 return指令指令(有多余参数有多余参数)函数应用消费适当个数的变元，其结果是一个函数函数应用消费适当个数的变元，其结果是一个函数 再应用到剩余变元，它们的指针仍在栈上再应用到剩余变元，它们的

9、指针仍在栈上 ( x.( yz.x + y + z)3)4 5 的执行会出现这种情况的执行会出现这种情况 am执行前执行前fp. . .a1spfunval: cf, fap, fgpvector: xk, , x1pc = cfgp = fgpan+1执行后执行后fp. . .x1amspxk. . .13.4 指令集和编译指令集和编译13.4.5 构造和计算闭包构造和计算闭包c_code e sl = / 同编译函数类似，无变元部分同编译函数类似，无变元部分pushfree fr sl;/ 将全局变量的值压栈将全局变量的值压栈mkver g;/ 把它们做成一个向量把它们做成一个向量ldl

10、l1; / 闭包代码的地址闭包代码的地址mkclos;ujmp l2; l1 :v_code e vi (glob, i ) 0; (i = 1, , n)update; l2 :13.4 指令集和编译指令集和编译update指令的效果指令的效果 用闭包的计算用闭包的计算结果去覆盖该闭包对象结果去覆盖该闭包对象 以后以后eval指令发现已经不是闭包，则不再计算指令发现已经不是闭包，则不再计算gpoldfpold执行前执行前fppcoldspyxpc = pcoldfp = fpoldgp = gpoldsp执行后执行后yy13.4 指令集和编译指令集和编译13.4.6 letrec表达式和局部

11、变量表达式和局部变量v_code (letrec v1 = e1; .; vn= en in e0) sl =repeat n alloc; / 在堆上建立在堆上建立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 ;