函数程序设计语言 计算模型、编译技术、系统结构PDF电子书下载

第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