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是013.4指令集和编译13.4.1表达式2、简单表达式（结果是基值并在栈上，例举） B_
codeb?sl=ldbb B_code(e1opbine2)?sl= B_codee1?
sl; B_codee2?sl+1; opbin B_codee?sl = //e不是基值、算符和
if表达式 V_codee?sl; getbasic13.4指令集和编译13.4.1表达式2、简单
表达式（结果是基值并在堆上，例举） V_codeb?sl=B_codee?sl; m
kbasic V_code(ife1thene2elsee3)?sl= B_codee1?sl
; falsel1; V_codee2?sl; ujmpl2; l1: V_codee
3?sl; l2:13.4指令集和编译13.4.2变量的引用性出现 V_codev?sl=
getvarv?sl; eval C_codev?sl=getvarv?sl
getvarv?sl=let(p,i)=?(v) inifp=LOCthenpu
shlocsl-i elsepushglobi fi getvar为局部变
量和形式参数产生pushloc指令，为全局变量产生pushglob指令13.4指令集和编译13.4.3函数定义www.z
w360.com360小说 V_code(?v1...vn.e)?sl=C_code(?v1...
vn.e)?sl C_code(?v1...vn.e)?sl= pushfree
fr?sl;//拷贝全局变量的值的指针 mkvecg; mkvec0;
//空的变元向量 ldll1; //函数代码的地址 mkfu
nval; 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)) pushf
ree[v1,…,vg]?sl= getvarv1?sl; getvarv2?(sl+
1); ... getvarvg?(sl+g?1) 1、fr表示?v1...vn.e中
的自由变量表 2、pushfree生成将这些变量的指针压栈的指令序列13.4指令集和编译13.4.4函数应用www.g
uiwenji.com鬼故事 V_code(ee1...em)?sl= //e?e?e?? mark
l;//建新栈帧,保留当前继续地址l,FP,GP C_codeem?(sl+3);//为变元在堆上
建立闭包, ... //并把闭包的指针压栈 C_codee1?(sl+m+2);
V_codee?(sl+m+3);//计算e,结果指针压栈 apply; l:13.4指令集和编
译apply指令执行前后情况 ?FUNVAL中已有变元a1,…,an，本次调用还有变元已先行进栈 ?PC修改成函数代
码起始地址a1a2...执行后SPanPC=cfGP=fgpSP执行前FUNVAL:cf,f
ap,fgpVECTOR:[an,…,a1]13.4指令集和编译targn指令发现变元不足(n>m)
?将栈中已有的m个变元打包成向量 ?重新做成FUNVAL，和原先相比，变元多了 ?本次函数应用到此为止，返回PC=
PColdGP=GPoldFP=FPoldSP执行后FUNVAL:PC,,GPVECTOR:[am,
…,a1]amGPoldFPold执行前FPPCold...a1a2SP13.4指令集和编译re
turnn指令(SP=FP+1+n，没有多余参数) ?函数值拷贝到适当的地方，并释放当前栈帧anGPoldF
Pold执行前FPPCold...xa1SPSP执行后x13.4指令集和编译return指令(有多
余参数) ?函数应用消费适当个数的变元，其结果是一个函数 ?再应用到剩余变元，它们的指针仍在栈上 ?(?x.(?yz.x
+y+z)3)45的执行会出现这种情况am执行前FP...a1SPFUNVAL:cf,fap,
fgpVECTOR:[xk,…,x1]PC=cfGP=fgpan+1执行后FP...x1am
SPxk...13.4指令集和编译13.4.5构造和计算闭包 C_codee?sl= /
/同编译函数类似，无变元部分 pushfreefr?sl; //将全局变量的值压栈 mkverg; //
把它们做成一个向量 ldll1; //闭包代码的地址 mkclos; ujmpl2; l1
: V_codee[vi?(GLOB,i)]0;(i=1,…,n) update; l2
:13.4指令集和编译update指令的效果 ?用闭包的计算结果去覆盖该闭包对象 ?以后eval指令发现已经不是闭
包，则不再计算GPoldFPold执行前FPPColdSPyxPC=PColdFP=FPoldGP
=GPoldSP执行后yy13.4指令集和编译13.4.6letrec表达式和局部变量www.libaiwu.c
om官场小说V_code(letrecv1==e1;...;vn==enine0)?sl= rep
eatnalloc;//在堆上建立n个空对象,将指针压栈 C_codee1??sl?;//为ej建立
闭包 rewriten; //覆盖对应的空闭包对象 C_codee2??sl?; rewriten?1;
C_codeen??sl?; rewrite1; V_codee0??sl?;//生成计算e0的指令序列
sliden //放弃e1,...,en在栈顶指针，剩下e0指针13.4指令集和编译13.4.6letrec表
达式和局部变量V_code(letrecv1==e1;...;vn==enine0)?sl= rep
eatnalloc;//在堆上建立n个空对象,将指针压栈 C_codee1??sl?;//为ej建立
闭包 rewriten; //覆盖对应的空闭包对象 ... ???=?[vi?(LOC,sl+i
?1)](i=1,…,n) ???依据全局变量和v1,...,vn，为e0,e1,...,en建立同样
的环境 ?sl?=sl+n ?n次alloc使SP的值增加n习题
中国科大第十三章函数式语言的编译
本章内容介绍一种简单的函数式编程语言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函数式编程语言简介例2l
etreccomp==?f.?g.?x.f(gx); F==?x.…; G==?z.…;
h==compFGinh(...)+F(...)+G(...) 函数可以作为函数的变元函
数也可以作为函数的结果n元函数可作为高阶函数使用,当作用于m(m3.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,z13.2函数
式语言的编译简介概述 将按需调用语义和静态约束的函数式语言SFP的程序编译成FAM的机器语言FAM是一种抽象机，它有一个栈，
生存期符合栈式管理的所有变量都分配在栈中；它还有一个堆,所有其它的变量都存在堆中先用一连串的例子来启发后面从SFP程序到FAM程
序的编译描述13.2函数式语言的编译简介13.2.1几个受启发的例子 例1 1+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几个受启发的例子 例3
if(if1?2thentrueelsefalse)then3else4if1?2thentru
eelsefalse的结果在栈上更好，因为假转指令jfalse希望在栈顶测试它的值由此，表达式的编译方式还依赖于上下文由上
下文可知，表达式true和false也应该按照结果在栈上的方式来编译13.2函数式语言的编译简介13.2.1几个受启发的例子
例4letrecf==?yz.ifz=0then1else1/y; x==5
inf1(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几个受启发的例子 例6letrec
f==letrecx==2 in?y.x+y inf5该例可用来说
明命令式语言和函数式语言在局部变量生存期上的区别为了把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、堆HP
FAM的程序 1、每条指令占一个单元 2、某些指令含一个运算对象 3、程序计数器PC总是保留当前指令的地址13.3抽象机
的体系结构13.3.1抽象机的栈和第6章的活动记录栈类似，但这里栈向下增长基值、各种地址都只占一个单元函数应用的栈帧如图
SP是栈顶指针FP是当前栈帧指针继续地址就是返回地址FPold是老FP的值GPold是老的全局变量构成的 向量的指针
继续地址FPoldGPold实在参数局部变量和中间结果FPSP13.3抽象机的体系结构13.3.1抽象机的
栈和第6章的活动记录栈类似，但这里栈向下增长基值、各种地址都只占一个单元闭包计算的栈帧如图， 无需实在参数域建立和释放
栈帧可以用 一组固定的指令继续地址FPoldGPold局部变量和中间结果FPSP13.3抽象机的体系结构1
3.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：对象表示一个函数值CLOSU
RE：对象是一个闭包VECTOR：对象是堆对象指针的向量 1、存放函数变元的指针，或 2、存放FUNVAL对象的全局变量的指
针，或 3、存放CLOSURE对象的全局变量的指针13.3抽象机的体系结构13.3.2抽象机的堆建立堆对象的指令如下
mkbasic：建立基值mkfunval：建立函数值mkclos：建立闭包mkvecn：建立有n分量的向量alloc：建
立空闭包13.3抽象机的体系结构13.3.3名字的寻址问题函数定义的编译必须考虑函数应用允许变元不足和变元过剩的情况
编译函数应用ee1...em时，编译器并非总能知道被应用函数的变元个数这给编译时确定栈帧中变元和局部变量的地址带来困难1
3.3抽象机的体系结构13.3.3名字的寻址考虑执行函数应用ee1...em时名字的寻址若基于FP访问，编译函数定
义时，由于不知实参个数，局部变量的寻址困难继续地址FPoldGPold实在参数局部变量和中间结果FPSP
e的FUNVAL指针em闭包的指针FPSPe1闭包的指针┇13.3抽象机的体系结构13.3.3名字的寻址考虑
执行函数应用ee1...em时名字的寻址以左图中目前SP的位置为基准较好，但需要克服SP动态变化带来的困难继续地址
FPoldGPold实在参数局部变量和中间结果FPSPe的FUNVAL指针e1闭包的指针FPSPem闭包
的指针┇13.3抽象机的体系结构13.3.3名字的寻址考虑执行函数应用ee1...em时名字的寻址选择动态地址
sp0作为寻址的基地址SP的当前值spa和sp0的值之间的差，对函数体的每点来说是静态可确定的，因为已出现的新局部变量和中
间结果数目是已知的这个差值在编译时保存在编译参数sl中，在程序点的值用sla表示，则有关系式 spa=sp0+sla?1继续地址e1闭包的指针em闭包的指针┇FPSPsp0FPoldGPold13.3抽象机的体系结构13.3.3名字的寻址考虑执行函数应用ee1...em时名字的寻址选择动态地址sp0作为寻址的基地址spa和sp0的值之间的关系 spa=sp0+sla?1生成的指令可以使用编译时确定的值sla和运行时spa来计算运行时的值sp0继续地址e1闭包的指针em闭包的指针┇FPSPsp0FPoldGPold13.3抽象机的体系结构13.3.4约束的建立对每个函数定义及表达式，自由变量集静态可知这些变量的地址存在一个向量中该向量的指针存放在堆中作为FUNVAL或CLOSURE对象的一部分在计算闭包或函数应用时，该指针复写到GP，即运算时可以通过GP去寻找该向量的元素中国科大 |
|
