第十三章 函数式语言的编译 本章内容 ·介绍一种简单的函数式编程语言SFP 介绍一种抽象机FAM,它的机器语言是SFP 语言的目标语言 ,介绍SFP各种语言构造到FAM的编译
第十三章 函数式语言的编译 本章内容 • 介绍一种简单的函数式编程语言SFP • 介绍一种抽象机FAM，它的机器语言是SFP 语言的目标语言 • 介绍SFP各种语言构造到FAM的编译
13.1函数式编程语言简介 13.1.1语言构造 函数是构建程序的基本成分 还提供一些机制用于构造更为复杂的函数 1 纯函数式语言禁止使用赋值语句，从而不会产生 副作用，其优点是具有引用透明性，有助于程序 的等式变换和推理 程序设计的任务就是定义函数 计算机按照所定义函数的相应表达式， 根据计算 规则逐步计算，最后得到所需的结果
13.1 函数式编程语言简介 13.1.1 语言构造 • 函数是构建程序的基本成分 – 还提供一些机制用于构造更为复杂的函数 – 纯函数式语言禁止使用赋值语句，从而不会产生 副作用，其优点是具有引用透明性，有助于程序 的等式变换和推理 • 程序设计的任务就是定义函数 – 计算机按照所定义函数的相应表达式，根据计算 规则逐步计算，最后得到所需的结果
13.1函数式编程语言简介 语法论域和语法产生式 -B:基值集，如布尔值、整数、·，用b示例 -Opim:二元算符集，如+，三，and,.·,用opm示例 Opm:一元算符集，如-，not,.,用OPunZ示例 -V: 变量集，用v示例 -E:表达式集，用e示例 e->b|v|(opun e)(e opbin e2)(if er then e2 else e3) (er e2) ∥函数应用 (入.e) ∥函数抽象，如入x.x+1,即f(x)=x+1 (letrec v1==e1;v2==e2;...Vn==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 ) // 联立递归定义
13.1函数式编程语言简介 ·约定 e>blv (opun e)...(er e2)(Av.e) (letrec v1==e1;v2==e2;...Vnen in eo) 一函数应用有最高优先级并且左结合 一算术和逻辑算符有通常的优先级 入抽象选择最大可能的语法表达式作为入.e的体e, 即延伸到表达式的结尾或碰到第一个不能配对的 右括号为止 n元函数写成入y.yne的形式 把，…em实现为一次函数应用，而不是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次应用
13.1函数式编程语言简介 13.1.2参数传递机制 对于表达式ee2,用按需调用的方式传递参数 -值调用 -换名调用 -按需调用 又称惰性计算。从e的计算开始，当第一次需要 e2时，计算它的值，也就计算这一次。其它访问 用第一次访问时计算的值。这种方式结合了前两 种方式的优点
13.1 函数式编程语言简介 13.1.2 参数传递机制 对于表达式e1e2，用按需调用的方式传递参数 – 值调用 – 换名调用 – 按需调用 又称惰性计算。从e1的计算开始，当第一次需要 e2时，计算它的值，也就计算这一次。其它访问 用第一次访问时计算的值。这种方式结合了前两 种方式的优点
13.1函数式编程语言简介 例1 letrec x =2; f==入八.x+Jy； F==入gx.g2 in Ff1 一静态作用域，结果等于4 {x:2,f:入.x+y,F:gx.g2}是表达式2，Jyx+ 入gx.g2和Ff1的计算环境 表达式e和它的计算环境u形成二元组(e,w),叫做 闭包。环境u用来保证e中的自由变量会被正确地 解释，因此环境u和变元需要一起传递
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需要一起传递
13.1函数式编程语言简介 例2 letrec comp==入f.入g.入x.f(gx)； F==入x..; G==入乙.…； h==comp FG inh(.)+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 )元的函数
13.1函数式编程语言简介 13.1.3变量的自由出现和约束出现 在letrec1=e12元e2.…V。=eime中，等号 左边的y1,,n是这些变量的定义性出现 在入W.Vn-e的M.Vn中的y1,,n是这些变量的 定义性出现 变量出现在其它地方都是引用性出现 引用性出现分成自由出现和约束出现 在（入x.(.x+)+乙）)x中， 自由出现的变量：x,乙 约束出现的变量：x,,乙
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
13.2函数式语言的编译简介 概述 -将按需调用语义和静态约束的函数式语言SFP的 程序编译成FAM的机器语言 AM是一种抽象机，它有一个栈，生存期符合栈 式管理的所有变量都分配在栈中；它还有一个堆！ 所有其它的变量都存在堆中 先用一连串的例子来启发后面从SFP程序到FAM 程序的编译描述
13.2函数式语言的编译简介 • 概述 – 将按需调用语义和静态约束的函数式语言SFP的 程序编译成FAM的机器语言 – FAM是一种抽象机，它有一个栈，生存期符合栈 式管理的所有变量都分配在栈中；它还有一个堆, 所有其它的变量都存在堆中 – 先用一连串的例子来启发后面从SFP程序到FAM 程序的编译描述
13.2函数式语言的编译简介 13.2.1几个受启发的例子 例1 1+2 -本表达式的结果是基值类型，可以放在栈上 但是表达式结果也可能是函数，它不能放在栈上 统一做法： 把程序表达式的结果统一存放在堆中，在栈顶用 一个指针指向堆中的结果
13.2函数式语言的编译简介 13.2.1 几个受启发的例子 例1 1 + 2 – 本表达式的结果是基值类型，可以放在栈上 – 但是表达式结果也可能是函数，它不能放在栈上 – 统一做法： 把程序表达式的结果统一存放在堆中，在栈顶用 一个指针指向堆中的结果