第1章 引论 1
1.1 函数式程序设计语言 1
1.1.1 APL语言 2
1.1.2 FP语言 2
1.1.3 ML语言 2
1.1.4 Lisp语言 3
1.1.5 SASL，KRC和Miranda语言 3
1.1.6 Haskell语言 4
1.1.7 其它的函数语言 4
1.2 函数语言的基本特征和实现论题 4
1.2.1 函数语言的基本特征 4
1.2.2 程序的执行效率 5
1.2.3 主要实现论题 5
1.3 函数语言的图重写实现技术 6
1.4 本章小结 9
第2章 函数式程序设计语言 10
2.1 函数语言的特点 10
2.1.1 变量名和值 10
2.1.2 执行顺序 11
2.1.3 循环和递归 11
2.1.4 数据结构 12
2.1.5 函数作为值 13
2.2 ML语言简介 14
2.2.1 ML的特点 14
2.2.2 类型 14
2.2.3 几点说明 16
2.3 SML标准类型 16
2.3.1 基本类型 16
2.3.2 表类型 17
2.3.3 元组类型 17
2.3.4 函数的类型和表达式 18
2.4 SML标准函数 19
2.4.1 标准布尔型函数 19
2.4.2 标准算术运算函数和运算符的重载 19
2.4.3 标准字符串函数 19
2.4.4 标准表函数 19
2.4.5 字符、字符串和表 21
2.4.6 比较运算符 22
2.5 SML函数定义 22
2.5.1 函数 22
2.5.2 约束变量的类型 23
2.5.3 定义 24
2.5.4 条件表达式 24
2.5.5 递归和函数定义 25
2.5.6 访问元组约束变量中的元素 25
2.5.7 模式匹配 26
2.5.8 局部定义 28
2.6 SML类型 28
2.6.1 类型表达式和类型缩写（abbreviated types） 28
2.6.2 类型变量和多态性 29
2.6.3 定义新类型 32
2.6.4 抽象数据类型 35
2.6.5 树 36
2.7 本章小结 38
第3章 入演算 39
3.1 入演算的基本概念和定义 40
3.2 入演算的归约 42
3.3 递归定义 46
3.4 纯入演算中的算术 50
3.5 本章小结 50
第4章 函数语言的归约计算方法 51
4.1 归约计算的语义 51
4.2 正规序归约的语用 52
4.2.1 串归约（string reduction） 52
4.2.2 标准环境归约（standard environment reduction） 53
4.2.3 图归约（graph reduction） 54
4.2.4 全惰性图归约（full lazy graph reduction） 55
4.2.5 惰性图归约（lazy graph reduction） 57
4.2.6 图归约的特点 58
4.3 组合子图归约（combinator-based graph reduction） 59
4.3.1 基本思想 59
4.3.2 组合子及其性质 63
4.3.3 超组合子性质 66
4.4 本章小结 67
第5章 函数语言的图重写计算模型 69
5.1 计算对象的描述形式 69
5.2 计算的操作方式 70
5.3 计算的控制方式 73
5.3.1 并行性开发策略 73
5.3.2 并行计算的控制管理方法 78
5.3.3 并行计算任务的粒度（granularity） 82
5.4 本章小结 83
第6章 编译中间语言 87
6.1 中间语言的基本概念 87
6.2 CIL程序的基本描述形式 88
6.3 CIL程序例子 92
6.4 CIL程序执行算法 94
6.5 CIL语言对函数式程序的支持 96
6.5.1 TermL模式结构的转换 97
6.5.2 非平坦TermL的转换 99
6.5.3 标记TermR 100
6.6 本章小结 101
第7章 多态类型及类型检查 103
7.1 多态类型 103
7.2 程序的表示 105
7.3 类型推导与类型合一 106
7.4 类型变量与环境 108
7.5 类型推导算法 110
7.5.1 类型推导算法中用到的函数 110
7.5.2 类型推导算法 111
7.6 本章小结 117
第8章 自由变量的消除与优化组合子 118
8.1 入提升 118
8.1.1 入提升方法 118
8.1.2 入提升方法的评价 119
8.2 最大自由表达式（mfe）抽取 120
8.2.1 mfe抽取算法 120
8.2.2 最大自由表达式抽取方法的分析 121
8.3 函数部分作用共享分析 123
8.3.1 部分作用的共享及其表示 123
8.3.2 共享分析方法 124
8.4 优化组合子生成方法 127
8.5 本章小结 128
第9章 惰性模式匹配及其编译方法 130
9.1 模式与模式匹配 130
9.2 最小扩展模式与模式匹配树 134
9.2.1 模式匹配谓词及其性质 134
9.2.2 惰性模式匹配算法的存在性与最小扩展模式 135
9.2.3 MEPⅡ的生成和匹配树的构造 138
9.3 模式的平坦化和参量一致化变换 141
9.3.1 两个简单的转换方法及其效率 141
9.3.2 重写规则的生成方法 144
9.4 本章小结 146
第10章 惰性函数语言程序严格性分析方法 147
10.1 抽象解释和严格性分析方法 147
10.1.1 基于抽象解释的严格性分析方法 147
10.1.2 严格性分析与函数程序的并行性开发 149
10.1.3 惰性计算方式和结构数据的计算 151
10.2 投影分析分析方法 152
10.2.1 投影和计算的描述 152
10.2.2 基于投影分析的严格性分析方法 154
10.2.3 举例 157
10.3 并行性开发方法的优化 158
10.3.1 算子 158
10.3.2 并行性开发方法 159
10.4 本章小结 160
第11章 编译时粒度分析及估算方法 161
11.1 现状与问题 161
11.2 Kozen语义与分布函数 162
11.3 分布函数与程序粒度的关系 164
11.4 程序粒度分析的系统化方法 165
11.5 细粒度任务的收拢（coalescing）原理 168
11.6 任务颗粒的分类及合并 169
11.7 引入启发因素的编译时粒度分析算法HCGA 171
11.8 实验及与相关工作的比较 176
11.9 本章小结 177
第12章 存储管理及垃圾单元回收 178
12.1 概述 178
12.2 Ashoke的改进引用计数法 179
12.2.1 Ashoke算法 179
12.2.2 Ashoke算法的正确性证明 182
12.2.3 并行环境中的Ashoke算法实现 183
12.3 基于引用计数的垃圾回收技术 184
12.3.1 经典的引用计数法 185
12.3.2 ARVIND/THOMAS的带权引用计数法 185
12.3.3 垃圾单元回收的惰性方法 186
12.3.4 带权的垃圾单元惰性回收方法 187
12.4 FL/TBD/TBC/CRC与CM分立的垃圾回收开销分析 188
12.5 FL/TBD/TBC/CRC与CM混合的垃圾回收开销分析 193
12.6 并行系统中的垃圾单元回收 196
12.7 本章小结 201
第13章 多相并行图重写执行模型HPGREM 202
13.1 并行执行模型的研究现状 202
13.2 HPGREM的形式化描述 204
13.2.1 基本定义 204
13.2.2 形式化描述 206
13.3 存储管理及执行环境组织 209
13.4 并行性开发策略 214
13.4.1 并行性开发 214
13.4.2 任务分布的Lazy-Eager原理 214
13.4.3 基于LEDT原理的任务分布算法 215
13.5 并行执行模型HPGREM的多相性质 220
13.6 本章小结 220
第14章 并行抽象机PAM/TGR及体系结构 221
14.1 概述 221
14.2 存储器组织及数据表示 227
14.2.1 存储器组织 227
14.2.2 图结点及数据表示 228
14.3 并行抽象机PAM/TGR的指令系统 230
14.3.1 并行抽象机指令集 230
14.3.2 抽象机的寻址方式 230
14.3.3 并行抽象机PAM/TGR的优化编译器 232
14.4 并行抽象机的指令执行算法 238
14.4.1 环境生成指令（push）执行算法 238
14.4.2 环境拷贝指令（copy）执行算法 238
14.4.3 重写指令（grew）执行算法 239
14.4.4 重写任务的管理指令（take，mask，sndt，recv）执行算法 239
14.4.5 调用基元操作与存储管理指令（call，flsh）执行算法 240
14.5 并行抽象机PAM/TGR的体系结构 241
14.6 并行抽象机PAM/TGR的性能评价 244
14.6.1 基于Benchmark的PAM/TGR性能测试 246
14.6.2 与相关系统的性能比较 249
14.7 本章小结 251
参考文献 252