第十三章 函数式语言的编译
函数式程序设计语言起源于LISP，因此可以追溯到20世纪60年代初期。到了20世纪70年代末期，当新的概念和实现方法出现时，这类语言才摆脱了LISP语言的统治，成为一类比较成熟的语言，其代表有Miranda 和ML等。在函数式语言中，函数是构造程序的基本成分，并且语言还提供一些机制用于构造更为重要的函数。纯函数式语言禁止使用赋值语句，从而不会产生副作用，其优点是具有引用透明性。有助于程序的等式变换和推理。
13.1 函数式编程语言简介
13.1.1 语言构造
- 函数是构建程序的基本成分
- 还提供一些机制用于构造更为复杂的函数
- 纯函数式语言禁止使用赋值语句，从而不会产生副作用，其优点是具有引用透明性，有助于程序的等式变换和推理
- 程序设计的任务就是定义函数
- 对于表达式e1e2，用按需调用的方式传递参数
- 值调用
- 换名调用
- 按需调用
- 又称惰性计算。从e1的计算开始，当第一次需要e2时，计算它的值，也就计算这一次。其它访问用第一次访问时计算的值。这种方式结合了前两种方式的优点
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函数式语言的编译简介
- 概述
- 例1 1 + 2
本表达式的结果是基值类型，可以放在栈上
但是表达式结果也可能是函数，它不能放在栈上 - 统一做法：
把程序表达式的结果统一存放在堆中，在栈顶用一个指针指向堆中的结果 - 例2 letrec x == 1/y; y == 0; z == x in 1 + 2
由letrec或函数抽象引入的变量在FAM的栈上分配单元
x、y和z 的等式的编译：产生的指令序列不直接计算它们的右部，将来需要这些值时再计算
于是，生成的指令序列构造x、y和z的闭包，并将它们的指针存放在栈中
y的等式无须构造闭包，因其右部不含自由变量
让z 和x 约束到同一个闭包13.2.2 编译函数
- 表达式在不同的上下文中会编译成不同的指令序列
- 编译环境包含
- 1、变量的性质：自由(GLOB)还是约束(LOC)
- 2、变量的位置：相对地址或下标
- 存储分配
- 1、表达式中的局部变量在栈上分配存储单元,
- 使用栈帧的相对地址
- 2、全局变量存储单元的指针分配在约束向量中，
- 依据约束向量中下标可以找到这些指针
13.3 抽象机的体系结构
13.3.1 抽象机的栈
- 和第6章的活动记录栈类似，但这里栈向下增长
- 基值、各种地址都只占一个单元
- 闭包计算的栈帧如图，
无需实在参数域 - 建立和释放栈帧可以用
一组固定的指令13.3.2 抽象机的堆
- 堆对象有四类
- 建立堆对象的指令如下
- 问题
- 对每个函数定义及表达式，自由变量集静态可知
- 这些变量的地址存在一个向量中
- 该向量的指针存放在堆中作为FUNVAL或CLOSURE对象的一部分
- 在计算闭包或函数应用时，该指针复写到GP，即运算时可以通过GP去寻找该向量的元素
13.4 指令集和编译
13.4.1 表达式
1、程序表达式
P_code e = V_code e [ ] 0；
stop - return指令(有多余参数)