程序设计语言理论 第2版PDF|Epub|txt|kindle电子书版本网盘下载

程序设计语言理论 第2版PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

第1章 引言1

1.1　基本概念1

1.1.1 程序设计语言的建模1

1.1.2　λ表示法2

1.1.3　符号和约定4

1.2　等式、归约和语义4

1.2.1　公理语义5

1.2.2　操作语义5

1.2.3　指称语义6

1.3　类型和类型系统7

1.3.1 类型和类型系统7

1.3.2　类型化语言的优点8

1.4 归纳法10

1.4.1　表达式上的归纳10

1.4.2 证明上的归纳11

1.4.3 良基归纳14

习题16

第2章　泛代数和代数数据类型17

2.1 引言17

2.2　代数、基调和项18

2.2.1 代数18

2.2.2　代数项的语法19

2.2.3　代数以及项在代数中的解释21

2.2.4　代换引理24

2.3　等式、可靠性和完备性25

2.3.1 等式25

2.3.2　项代数26

2.3.3 语义蕴涵和等式证明系统27

2.3.4　完备性的形式33

2.3.5 同余、商和演绎完备性33

2.3.6 非空类别和最小模型完备性36

2.4　同态和初始性37

2.4.1 同态和同构37

2.4.2 初始代数38

2.5　代数数据类型43

2.5.1　代数数据类型43

2.5.2　初始代数语义和数据类型归纳44

2.5.3　解释没有意义的项47

2.5.4　错误值的其他解决方法51

2.6 重写系统51

2.6.1　基本定义51

2.6.2　合流性和可证的相等性54

2.6.3　终止性54

2.6.4　临界对59

2.6.5　左线性无重叠重写系统63

2.6.6　局部合流、终止和合流之间的联系65

2.6.7　代数数据类型的应用67

习题70

第3章　简单类型化λ演算76

3.1 引言76

3.2　类型和项77

3.2.1　类型的语法77

3.2.2　上下文有关语法78

3.2.3　λ→项的语法79

3.2.4 带积、和及其他类型的项84

3.2.5　定型算法89

3.3　证明系统90

3.3.1 等式和理论90

3.3.2 归约规则95

3.3.3 有其他规则的归约97

3.4　通用模型、可靠性和完备性98

3.4.1 通用模型和项的含义98

3.4.2　应用结构、外延性和框架99

3.4.3　环境条件100

3.4.4　类型可靠性和等式可靠性103

3.4.5　没有空类型的完备性106

3.4.6 有空类型的完备性107

3.4.7　其他类型的通用模型108

3.5　可计算函数编程语言110

3.5.1 概述110

3.5.2　PCF的语法111

3.5.3　声明和语法美化113

3.5.4　程序和结果115

3.5.5　公理语义115

3.5.6　操作语义117

3.5.7 由各种形式的语义定义的等价关系118

3.5.8　记录和n元组120

3.6　各种归约策略121

3.6.1 归约策略121

3.6.2 最左归约和惰性归约123

3.6.3 并行归约126

3.6.4 急切归约127

习题128

第4章　类型化λ演算的模型135

4.1 引言135

4.2　递归函数和不动点算子135

4.2.1　递归函数和不动点算子135

4.2.2　有不动点算子的急切归约138

4.2.3 PCF语言的编程实例140

4.3　论域理论模型和不动点144

4.3.1　递归定义和不动点算子144

4.3.2　完全偏序集合、提升和笛卡儿积145

4.3.3 连续函数148

4.3.4　不动点和完备连续层级151

4.3.5　PCF的CPO模型156

4.4　不动点归纳159

习题162

第5章　命令式程序的语义173

5.1 引言173

5.2　Kernel语言175

5.2.1　存储单元175

5.2.2　表达式的解释176

5.2.3　程序状态177

5.3　操作语义178

5.3.1　表达式的求值178

5.3.2　命令的执行180

5.4　指称语义182

5.4.1 带状态的类型化λ演算182

5.4.2　语义函数184

5.4.3 操作语义和指称语义的等价187

5.5　Kernel语言的Hoare逻辑189

5.5.1 一阶断言189

5.5.2　证明规则191

5.5.3　可靠性194

5.5.4　小结195

习题196

第6章　递归类型201

6.1 引言201

6.2　归纳和余归纳202

6.2.1　余归纳现象202

6.2.2 归纳和余归纳指南205

6.2.3　代数和余代数207

6.3　递归类型210

6.3.1　递归类型总览210

6.3.2　递归的数据结构212

6.4　归纳类型和余归纳类型214

6.4.1 归纳类型和余归纳类型总览214

6.4.2　帮助理解的实例217

习题219

第7章　多态性222

7.1　引言222

7.1.1　概述222

7.1.2　类型作为函数变元222

7.2　直谓式多态演算227

7.2.1　类型和项的语法227

7.2.2 和其他形式多态性的比较232

7.2.3 等式证明和归约236

7.2.4　ML风格的多态声明237

7.3　非直谓式多态演算238

7.3.1 引言238

7.3.2 非直谓式多态λ演算的表达力239

7.3.3 归约的终止性241

7.4　数据抽象和存在类型242

7.5　类型表达式的分类247

7.5.1 类型表达式的种类247

7.5.2　类型表达式的定类与相等248

7.5.3　项的定型249

习题250

第8章　依赖类型254

8.1 引言254

8.2　带依赖类型的演算255

8.2.1　依赖积类型255

8.2.2　依赖和类型259

8.3 带依赖类型的程序设计260

8.3.1 简化DML的实例260

8.3.2　简化DML的定义263

8.4 广义积与广义和266

8.4.1　广义积与广义和概念266

8.4.2 带广义积与广义和的直谓式演算266

8.4.3　ML模块语言270

8.4.4　用积与和来表示模块276

8.4.5 直谓性以及两个全域之间的联系277

习题279

第9章　命题和类型281

9.1 引言281

9.2　构造逻辑282

9.2.1　构造语义282

9.2.2　构造逻辑283

9.2.3　命题当作类型286

9.3　经典逻辑288

9.3.1 经典逻辑和构造逻辑的区别与联系288

9.3.2 经典逻辑的规则289

9.3.3　推导消去形式293

9.3.4　证明的动态性294

习题295

第10章　子定型296

10.1 引言296

10.2　有子定型的简单类型化λ演算298

10.3　记录303

10.3.1 记录子定型的一般性质303

10.3.2 带记录和子定型的类型化演算304

10.4　子定型的语义模型307

10.4.1　概述307

10.4.2　子定型的转换解释307

10.4.3 类型的子集解释314

10.5　对象的递归记录模型315

10.5.1　递归记录类型315

10.5.2　递归类型的子定型319

习题322

第11章　类型推断325

11.1 引言325

11.2　带类型变量的λ→类型推断328

11.2.1 语言λ→328

11.2.2　代换、实例与合一329

11.2.3　主定型算法332

11.2.4　隐式定型336

11.2.5　定型和合一的等价338

11.3 带多态声明的类型推断339

11.3.1　ML类型推断和多态变量339

11.3.2 两组隐式定型规则341

11.3.3　类型推断算法344

习题349

参考文献351