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

第十三章函数式语言的编译 本章内容介绍一种简单的函数式编程语言sfp介绍一种抽象机fam 它的机器语言是sfp语言的目标语言介绍sfp各种语言构造到fam的编译 13 1函数式编程语言简介 13 1 1语言构造函数是构建程序的基本成分还提供一些机制用于构造更为复杂的函数纯函数式语言禁止使用赋值语句 从而不会产生副作用 其优点是具有引用透明性 有助于程序的等式变换和推理程序设计的任务就是定义函数计算机按照所定义函数的相应表达式 根据计算规则逐步计算 最后得到所需的结果 13 1函数式编程语言简介 语法论域和语法产生式b 基值集 如布尔值 整数 用b示例opbin 二元算符集 如 and 用opbin示例opun 一元算符集 如 not 用opun示例v 变量集 用v示例e 表达式集 用e示例e b v opune e1opbine2 ife1thene2elsee3 e1e2 函数应用 v e 函数抽象 如 x x 1 即f x x 1 letrecv1 e1 v2 e2 vn enine0 联立递归定义 13 1函数式编程语言简介 约定e b v opune e1e2 v e letrecv1 e1 v2 e2 vn enine0 函数应用有最高优先级并且左结合算术和逻辑算符有通常的优先级 抽象选择最大可能的语法表达式作为 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静态作用域 结果等于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 n 个变元时 结果是一个 n m 元的函数 13 1函数式编程语言简介 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 z 13 2函数式语言的编译简介 概述将按需调用语义和静态约束的函数式语言sfp的程序编译成fam的机器语言fam是一种抽象机 它有一个栈 生存期符合栈式管理的所有变量都分配在栈中 它还有一个堆 所有其它的变量都存在堆中先用一连串的例子来启发后面从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 y和z的闭包 并将它们的指针存放在栈中y的等式无须构造闭包 因其右部不含自由变量让z和x约束到同一个闭包 13 2函数式语言的编译简介 13 2 1几个受启发的例子例3if if1 2thentrueelsefalse then3else4if1 2thentrueelsefalse的结果在栈上更好 因为假转指令jfalse希望在栈顶测试它的值由此 表达式的编译方式还依赖于上下文由上下文可知 表达式true和false也应该按照结果在栈上的方式来编译 13 2函数式语言的编译简介 13 2 1几个受启发的例子例4letrecf yz ifz 0then1else1 y x 5inf1 x 1 由于 yz ifz 0then1else1 y是函数表达式 需把它的闭包进一步做成funval对象funval对象和一般闭包的区别仅在于前者还包含存放变元指针的存储空间为保证1和x 1仅在需要时计算 将它们以闭包 包含一个指令序列和一个约束向量 的形式传递 13 2函数式语言的编译简介 13 2 1几个受启发的例子例5letrecx 2 1 f ab ga hb g x h y infxx以闭包或值形式的表达式的指针可以拷贝多份总是值的指针和闭包的指针而不是它们本身在传递 将它们存于约束向量和栈帧中每个表达式只有一个实例存在表达式对应变量的首次使用引起该表达式闭包的计算 13 2函数式语言的编译简介 13 2 1几个受启发的例子例6letrecf letrecx 2in y x yinf5该例可用来说明命令式语言和函数式语言在局部变量生存期上的区别为了把f作用于5 需要计算由较内letrec构造的函数 若该letrec已经计算 栈式管理会忘掉属于这个letrec的一切东西 包括局部变量x高阶函数的出现需要延长局部变量的生存期 13 2函数式语言的编译简介 13 2 2编译函数表达式在不同的上下文中会编译成不同的指令序列p 编译完整的程序表达式 结果在堆中 栈顶有一指针指向它b 结果必须是基值并且存在栈上v 结果在堆中 栈顶有一指针指向它 这是计算的正常情况c 结果必须是被编译表达式的闭包 函数的变元和递归等式的右部总是这种情况 13 2函数式语言的编译简介 13 2 3环境与约束名字的定义性出现总是关联到一个闭包1 一个等式被编译时 其左部的名字总是关联到其右部的闭包2 抽象中的约束名字是在函数应用时关联到该次应用的变元的闭包名字引用性出现的编译 获得相关联的定义性出现的值符号表在此称为编译环境当函数抽象的体或letrec中的表达式开始编译时 新引入的局部变量必须被加入编译环境 13 2函数式语言的编译简介 13 2 3环境与约束编译环境包含1 变量的性质 自由 glob 还是约束 loc 2 变量的位置 相对地址或下标存储分配1 表达式中的局部变量在栈上分配存储单元 使用栈帧的相对地址2 全局变量存储单元的指针分配在约束向量中 依据约束向量中下标可以找到这些指针 13 3抽象机的体系结构 从本节开始 逐步描述fam的体系结构和指令集 以及把sfp编译到fam的编译方案fam的存储器包含 程序存储区ps 栈st 堆hpfam的程序1 每条指令占一个单元2 某些指令含一个运算对象3 程序计数器pc总是保留当前指令的地址 13 3抽象机的体系结构 13 3 1抽象机的栈和第6章的活动记录栈类似 但这里栈向下增长基值 各种地址都只占一个单元函数应用的栈帧如图sp是栈顶指针fp是当前栈帧指针继续地址就是返回地址fpold是老fp的值gpold是老的全局变量构成的向量的指针 13 3抽象机的体系结构 13 3 1抽象机的栈和第6章的活动记录栈类似 但这里栈向下增长基值 各种地址都只占一个单元闭包计算的栈帧如图 无需实在参数域建立和释放栈帧可以用一组固定的指令 13 3抽象机的体系结构 13 3 2抽象机的堆堆对象有四类basic 存放基值的单元bfunval 对象表示一个函数值 它有三个成分1 cf 指向程序区中函数体开始的地方2 fap 指向函数变元向量3 fgp 函数各全局变量值的指针所组成的向量的指针后两个向量也存在堆中 13 3抽象机的体系结构 13 3 2抽象机的堆堆对象有四类basic 存放基值的单元bfunval 对象表示一个函数值closure 对象是一个闭包 有两个成分1 cp 代码指针2 gp 全局变量值的指针向量的指针 13 3抽象机的体系结构 13 3 2抽象机的堆堆对象有四类basic 存放基值的单元bfunval 对象表示一个函数值closure 对象是一个闭包vector 对象是堆对象指针的向量1 存放函数变元的指针 或2 存放funval对象的全局变量的指针 或3 存放closure对象的全局变量的指针 13 3抽象机的体系结构 13 3 2抽象机的堆建立堆对象的指令如下mkbasic 建立基值mkfunval 建立函数值mkclos 建立闭包mkvecn 建立有n分量的向量alloc 建立空闭包 13 3抽象机的体系结构 13 3 3名字的寻址问题函数定义的编译必须考虑函数应用允许变元不足和变元过剩的情况编译函数应用ee1 em时 编译器并非总能知道被应用函数的变元个数这给编译时确定栈帧中变元和局部变量的地址带来困难 13 3抽象机的体系结构 13 3 3名字的寻址考虑执行函数应用ee1 em时名字的寻址若基于fp访问 编译函数定义时 由于不知实参个数 局部变量的寻址困难 13 3抽象机的体系结构 13 3 3名字的寻址考虑执行函数应用ee1 em时名字的寻址以左图中目前sp的位置为基准较好 但需要克服sp动态变化带来的困难 13 3抽象机的体系结构 13 3 3名字的寻址考虑执行函数应用ee1 em时名字的寻址选择动态地址sp0作为寻址的基地址sp的当前值spa和sp0的值之间的差 对函数体的每点来说是静态可确定的 因为已出现的新局部变量和中间结果数目是已知的这个差值在编译时保存在编译参数sl中 在程序点的值用sla表示 则有关系式spa sp0 sla 1 13 3抽象机的体系结构 13 3 3名字的寻址考虑执行函数应用ee1 em时名字的寻址选择动态地址sp0作为寻址的基地址spa和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对代码执行结果的不同期望决定使用不同的编译函数这些函数有三个参数 被编译的表达式e 变量环境 和栈标高sl sl定义了被生成的代码执行前sp寄存器的值和地址sp0的差 课堂上的介绍比较宏观 需课后了解抽象机各指令后才能完全明白 13 4指令集和编译 13 4 1表达式1 程序表达式p codee v codee 0 stop环境为空 栈标高sl是0 13 4指令集和编译 13 4 1表达式2 简单表达式 结果是基值并在栈上 例举 b codeb sl ldbbb code e1opbine2 sl b codee1 sl b codee2 sl 1 opbinb codee sl e不是基值 算符和if表达式v codee sl getbasic 13 4指令集和编译 13 4 1表达式2 简单表达式 结果是基值并在堆上 例举 v codeb sl b codee sl mkbasicv code ife1thene2elsee3 sl b codee1 sl falsel1 v codee2 sl ujmpl2 l1 v codee3 sl l2 13 4指令集和编译 13 4 2变量的引用性出现v codev sl getvarv sl evalc codev sl getvarv slgetvarv sl let p i v inifp locthenpushlocsl ielsepushglobifigetvar为局部变量和形式参数产生pushloc指令 为全局变量产生pushglob指令 13 4指令集和编译 13 4 3函数定义v code v1 vn e sl c code v1 vn e slc code v1 vn e sl pushfreefr sl 拷贝全局变量的值的指针mkvecg mkvec0 空的变元向量ldll1 函数代码的地址mkfunval ujmpl2 l1 targn 测试变元个数v codee vi loc i vj glob j 0 returnn i 1 n j 1 g l2 13 4指令集和编译 13 4 3函数定义fr v1 vg list freevar v1 vn e pushfree v1 vg sl getvarv1 sl getvarv2 sl 1 getvarvg sl g 1 1 fr表示 v1 vn e中的自由变量表2 pushfree生成将这些变量的指针压栈的指令序列 13 4指令集和编译 13 4 4函数应用v code ee1 em sl e e e markl 建新栈帧 保留当前继续地址l fp gpc codeem sl 3 为变元在堆上建立闭包 并把闭包的指针压栈c codee1 sl m 2 v codee sl m 3 计算e 结果指针压栈apply l 13 4指令集和编译 apply指令执行前后情况 funval中已有变元a1 an 本次调用还有变元已先行进栈 pc修改成函数代码起始地址 13 4指令集和编译 targn指令发现变元不足 n m 将栈中已有的m个变元打包成向量 重新做成funval 和原先相比 变元多了 本次函数应用到此为止 返回 13 4指令集和编译 returnn指令 sp fp 1 n 没有多余参数 函数值拷贝到适当的地方 并释放当前栈帧 13 4指令集和编译 return指令 有多余参数 函数应用消费适当个数的变元 其结果是一个函数 再应用到剩余变元 它们的指针仍在栈上 x yz x y