《编译原理和技术》课程PPT教学课件：第十三章 函数式语言的编译

第十三章函数式语言的编译 本章内容 介绍一种简单的函数式编程语言SFP 介绍一种抽象机FAM,它的机器语言是SFP 语言的目标语言 介绍SFP各种语言构造到FAM的编译

第十三章 函数式语言的编译 本章内容 • 介绍一种简单的函数式编程语言SFP • 介绍一种抽象机FAM，它的机器语言是SFP 语言的目标语言 • 介绍SFP各种语言构造到FAM的编译

131函数式编程语言简介 13.1.1语言构造 函数是构建程序的基本成分 还提供一些机制用于构造更为复杂的函数 纯函数式语言禁止使用赋值语句,从而不会产生 副作用,其优点是具有引用透明性,有助于程序 的等式变换和推理 程序设计的任务就是定义函数 计算机按照所定义函数的相应表达式,根据计算 规则逐步计算,最后得到所需的结果

13.1 函数式编程语言简介 13.1.1 语言构造 • 函数是构建程序的基本成分 – 还提供一些机制用于构造更为复杂的函数 – 纯函数式语言禁止使用赋值语句，从而不会产生 副作用，其优点是具有引用透明性，有助于程序 的等式变换和推理 • 程序设计的任务就是定义函数 – 计算机按照所定义函数的相应表达式，根据计算 规则逐步计算，最后得到所需的结果

131函数式编程语言简介 语法论域和语法产生式 B:基值集,如布尔值、整数、.,用b示例 Op bint:二元算符集,如+,=,and,,用qpbm示例 O un 元算符集,如-,not,,,用opm示例 V:变量集,用ν示例 E:表达式集,用e示例 e>b v(opun el(ej opbin e,l (if e, then e? else e3) l(e1e2)∥函数应用 1(A.e)∥函数抽象,如入xx+1,即f(x)=x+1 (etrec v1==e1; v2==e2;.vu==en in eo ∥联立递归定义

13.1 函数式编程语言简介 • 语法论域和语法产生式 – B：基值集，如布尔值、整数、. . .，用b示例 – Opbin：二元算符集，如+, =, 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 ) // 联立递归定义

131函数式编程语言简介 约定 e→bν(opme)…|(e1e2)|(xe) I (letrec v==e1; v2==e2;..Vn==en in eo) 函数应用有最高优先级并且左结合 算术和逻辑算符有通常的优先级 入抽象选择最大可能的语法表达式作为e的体e, 即延伸到表达式的结尾或碰到第一个不能配对的 右括号为止 n元函数写成v1…,vne的形式 把1…,tm实现为一次函数应用,而不是m次应用

13.1 函数式编程语言简介 • 约定 e → b | v | (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次应用

131函数式编程语言简介 13.1.2参数传递机制 对于表达式e1e2,用按需调用的方式传递参数 值调用 换名调用 按需调用 又称惰性计算。从e1的计算开始,当第一次需要 e2时,计算它的值,也就计算这一次。其它访问 用第一次访问时计算的值。这种方式结合了前两 种方式的优点

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

131函数式编程语言简介 例1 letrecx== 2 ∫=λy.x+y F== Ng x g2 in Ff1 静态作用域,结果等于4 {x:2,f:yx+y,F:Agx.g2}是表达式2,px+y, λgx.g2和Ff1的计算环境 表达式e和它的计算环境u形成二元组(e,u),叫做 闭包。环境u用来保证e中的自由变量会被正确地 解释,因此环境u和变元e需要一起传递

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需要一起传递

131函数式编程语言简介 例2 letrec comp==nf.ng. xf(gx); F== 2x G== h==comp FG in(…)+F(…)+G(…) 函数可以作为函数的变元 函数也可以作为函数的结果 n元函数可作为高阶函数使用,当作用于m(m<n) 个变元时,结果是一个(n-m)元的函数

13.1 函数式编程语言简介 • 例2 letrec comp == f .g. x. f (gx); F == x. …; G == z. …; h == comp F G in h( ... ) + F( ... ) + G( ... ) – 函数可以作为函数的变元 – 函数也可以作为函数的结果 – n元函数可作为高阶函数使用, 当作用于m (m < n) 个变元时，结果是一个( n − m )元的函数

131函数式编程语言简介 13.13变量的自由出现和约束出现 在 letrec y=e1 = e in e中,等号 左边的v1,…,v是这些变量的定义性出现 在丸v1…n,e的丸n1…,n中的v,…,v是这些变量的 定义性出现 变量出现在其它地方都是引用性出现 引用性出现分成自由出现和约束出现 在Axy.(zx+)(+z)x中, 自由出现的变量:x,z 约束出现的变量:x,y,z

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. x + z) (y + z ) ) x中， 自由出现的变量：x, z 约束出现的变量：x, y, z

132函数式语言的编译简介 概述 将按需调用语义和静态约束的函数式语言SFP的 程序编译成FAM的机器语言 FAM是一种抽象机,它有一个栈,生存期符合栈 式管理的所有变量都分配在栈中;它还有一个堆, 所有其它的变量都存在堆中 先用一连串的例子来启发后面从SFP程序到FAM 程序的编译描述

13.2函数式语言的编译简介 • 概述 – 将按需调用语义和静态约束的函数式语言SFP的 程序编译成FAM的机器语言 – FAM是一种抽象机，它有一个栈，生存期符合栈 式管理的所有变量都分配在栈中；它还有一个堆, 所有其它的变量都存在堆中 – 先用一连串的例子来启发后面从SFP程序到FAM 程序的编译描述

132函数式语言的编译简介 1321几个受启发的例子 例11+2 本表达式的结果是基值类型,可以放在栈上 但是表达式结果也可能是函数,它不能放在栈上 统一做法: 把程序表达式的结果统一存放在堆中,在栈顶用 个指针指向堆中的结果

13.2函数式语言的编译简介 13.2.1 几个受启发的例子 例1 1 + 2 – 本表达式的结果是基值类型，可以放在栈上 – 但是表达式结果也可能是函数，它不能放在栈上 – 统一做法： 把程序表达式的结果统一存放在堆中，在栈顶用 一个指针指向堆中的结果