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

《第十三章 函数式语言的编译.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、,=,and,...,用opbin示例Opun:一元算符集，如,not,...，用opun示例V：变量集，用v示例E：表达式集，用e示例eb

3、v

4、(opune)

5、(e1opbine2)

6、(ife1thene2elsee3)

7、(e1e2)//函数应用

8、(v.e)//函数抽象,如x.x+1,即f(x)=x+1

9、(letrecv1==e1;v2==e2;...vn==enine0)//联立递归定义13.1函数式编程语言简介约定eb

10、v

11、(opune)

12、…

13、(e1e2)

14、(v.e)

15、(letrecv1==e1;v2==e2;...vn==enine0)函数应用有最高优先级

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

17、静态作用域，结果等于4{x:2,f:y.x+y,F:gx.g2}是表达式2,y.x+y,gx.g2和Ff1的计算环境表达式e和它的计算环境u形成二元组(e,u)，叫做闭包。环境u用来保证e中的自由变量会被正确地解释，因此环境u和变元e需要一起传递13.1函数式编程语言简介例2letreccomp==f.g.x.f(gx);F==x.…;G==z.…;h==compFGinh(...)+F(...)+G(...)函数可以作为函数的变元函数也可以作为函数的结果n元函数可作为高阶函数使用,当作用于m(m

18、语言简介13.1.3变量的自由出现和约束出现在letrecv1==e1;v2==e2;...vn==enine0中，等号左边的v1,…,vn是这些变量的定义性出现在v1…vn.e的v1…vn中的v1,…,vn是这些变量的定义性出现变量出现在其它地方都是引用性出现引用性出现分成自由出现和约束出现在(xy.(z.x+z)(y+z))x中，自由出现的变量：x,z约束出现的变量：x,y,z13.2函数式语言的编译简介概述将按需调用语义和静态约束的函数式语言SFP的程序编译成FAM的机器语言FAM是一种抽象机，它有一个栈，生存期符合栈式管理的所有变量都分配在栈中；它还有一个堆,

19、所有其它的变量都存在堆中先用一连串的例子来启发后面从SFP程序到FAM程序的编译描述13.2函数式语言的编译简介13.2.1几个受启发的例子例11+2本表达式的结果是基值类型，可以放在栈上但是表达式结果也可能是函数，它不能放在栈上统一做法：把程序表达式的结果统一存放在堆中，在栈顶用一个指针指向堆中的结果13.2函数式语言的编译简介13.2.1几个受启发的例子例2letrecx==1/y;y==0;z==xin1+2由letrec或函数抽象引入的变量在FAM的栈上分配单元x、y和z的等式的编译：产生的指令序列不直接计算它们的右部，将来需要这些值时再计算于是，生成的指令序列构造x

20、、y和z的闭包，并将它们的指针存放在栈中y的等式无须构造闭包，因其右部不含自由变量让z和x约束到同一个闭包13.2函数式语言的编译简介13.2.1几个受启发的例子例3if(if12thentrueelsefalse)then3else4if12thentrueelsefalse的结果在栈上更好，因为假转指令jfalse希望在栈顶测试它的值由此，表达式的编译方式还依赖于上下文由上下文可知，表达式true和false也应该按照结果在栈上的方式来编译13.2函数式语言的编译简介13.2.1几个受启发的例子