编程语言:原理与范型(第2版)

编程语言:原理与范型(第2版)"

作者:
ISBN:9787302166931
定价:¥68
字数:千字
页数:
出版时间:2008.01.01
开本:
版次:1-1
装帧:
出版社:清华大学出版社
简介

前言

  

自该书第1版于1999年出版以来,编程语言的研究已得到迅猛发展。例如,从CS1开始,Java已经成为计算机科学课程一门重要的语言。敏捷编程与软件设计如影随形,且其语言习惯有别于传统的程序。用正规的方法进行软件设计已渐入主流,且作用显著。

有鉴于此,新版希望能够适应在当前和未来编程语言设计过程中所伴随的的激励和新挑战。例如,新版对全部4种程序设计范例及其所用的语言在广度和深度上都有进一步的提高,如表0-1所示。

表0-1  语言覆盖范围

范    例

第1版

第2版

命令式(第12章)

C、Ada、Perl

面向对象(第13章)

Java

Java、Smalltalk、Python

函数式(第14章)

Scheme、Haskell

Scheme、Haskell

逻辑式(第15章)

Prolog

Prolog

新版第二个主要的变化是大大丰富了第2~11章关于语言设计原理的内容。我们使用不太正式的描述风格,增加了新的来自流行编程语言(如Python 和 Perl)的例子。此外,对于已经不再广泛应用的语言(如Pascal和Modula),新版多已略去。

第2、 4、 5、 7、 9章主要讲述编程语言的核心原理--语法、名称、类型、语义和函数。这几章与第1版相比较,为上机学习这些原理提供了更广泛、更深入的语言和范例。

如果您希望了解语法、类型系统、语义、函数和存储管理的具体实现原理,可以在第3、6、8、10和11章中找到这些材料。读者可以有选择地学习这几章,以丰富相关的核心原理。例如通过学习第3章中编译器的词汇和语法段,可加深和巩固对第2章的学习。注意,可以跳过部分或全部的章节,特别是初学编程语言的学生。

有3章包括了需要较多数学背景知识的可选部分。附录B提供了这些章节中主要的离散数学问题和概念,供需要快速复习的学生使用。

最后,第16、17和18章详细介绍了事件处理、并发性和程序正确性。第1版涵盖其中的两部分(事件处理和并发性),但新版加入了关于程序正确性的介绍。

总之,新版在编程语言的原理、范例和专题方面涵盖的范围更广、更深。本书共有18章。由于不同的教师对编程语言课程强调的重点有不同的看法,所以本书提供了多种选择。

0.1  提示

本书强调在编程语言设计中对于关键问题的全面实践操作。它为老师和学生提供了理论与实现相结合的经验。基于实现的经验包括C语言简单子集的设计和实施的上机操作,这被称作Clite。为便于参考,在附录A中给出了完整定义。

如上所述,本版对于主要编程范例进行了扩展。我们相信,为了掌握一个范例,学生们必须积极运用范例去解决编程问题。例如,如果学生没有函数式编程的经验,建议他们充分学习Scheme或者Haskell,完成一个说得过去的编程项目。引用一个评论者的评语:

为了明白一个范例,您自己必须实现这个范例。

另一方面,如果您的预备课程离散数学,或者AI课程已经包括函数式程序设计,可以选择跳过这一章,重点学习其他的范例或专题。

0.2  本书的结构

图0-1解释了正文如何分为3个主要的部分:

● 原理。

● 范例。

● 专题。

在第1部分,第2、4、5、7、9章包括5个核心原理—— 语法、名称、类型、语义和函数。该部分剩余章节(第3、6、8、10、11章)有助于加深对这些主题的理解。

图0-1  各章之间的内容关系

另一方面,高年级或研究生课程可能会包括其中的一些内容,而没有强调的材料在后续的章节中介绍。

本书的第2部分包含4个主要的程序范例:

● 命令式编程。

● 面向对象编程。

● 函数式编程。

● 逻辑式编程。

这些章之间相对独立并且可以按任意顺序学习。尽管如此,一个学期的课程安排除了原理之外,一般只包括命令式编程和面向对象。当然,范例的选择可能会根据教师的侧重和该学期课程内容的不同而不同。例如,如果该学期已经有面向对象设计课程,就可以跳过第13章。

新版中的第12章是全新的内容,这一章阐述了在C、Ada和Perl 3种不同的语言中命令式编程中的关键特点,选择C语言是因为它说明了弱类型引起的问题。相反,Ada是强类型,提供了和C语言生动的对比。最后,选择Perl是由于它阐述了一种动态类型脚本语言。对讲授第12章的教师,建议在安排趣味编程项目时,包含至少一门有足够深度的语言,并且学生不熟悉这门语言。

第13章在第1版的基础上进行了较多改写。新版中,使用Java、Smalltalk和Python来研究面向对象语言的特点。使用Smalltalk主要是因为它的简单性,使用Java主要是因为它的广泛性,而使用Python主要是因为它在脚本应用程序上的灵活性。对于已经在预备课程里学过Java但没有学习过面向对象设计的学生,或许会从学习其他两门语言之一受益。面向对象范例今后一直会很重要。

函数式编程和逻辑式编程的范例(第14和15章)陆续会在其应用程序和各自的编程类型上予以区分。在介绍函数式编程时,涵盖了对并行Scheme和Haskell的讨论,所以学生只学习其中任意一种语言就可以掌握函数式编程的思想。

本书第3部分包括3个专题:

● 事件处理。

● 并发性。

● 正确性。

大学编程语言课程通常只涉及这些主题中的一个,而没有时间去涉及其他的主题。老师在决定编程语言课程中包含哪一个主题时应考虑到这些主题在其他课程中出现的情况。

第16和17章的主题是事件处理和并发性,叙述了反常控制问题,在编程语言的学习中需要认真对待这个问题。在编程应用中,特别是在科学计算和嵌入系统方面,二者的作用日渐凸现。学生们需要学习的主要内容包括:通信、死锁、信息传递、非确定性、事件处理、交互处理通信,以及种类繁多的具体应用(如操作系统、GUI交互和家用报警系统)中的某些个案。

最后,第18章关于正确性的内容将让人耳目一新,这一章主要分析了编程语言在支持常用方法上的发展。例如, Spark Ada的开发人员宣称使用“由架构保证正确性”的技术使编程错误数目降低了99%,并使生产率提高了3~5倍。我们认为未来对编程语言而言,软件设计中对形式方法的支持将日渐重要(很像现今面向对象编程重要一样),因此,希望老师能在编程语言课程中加入这一章。

第18章一开始回顾了公理语义学及其在命令式编程检验中的应用。这一章涵盖了在面向对象语言中“契约设计(design by contract)”的概念及其使用Java建模语言的具体应用,并延伸了这一理论。本章也涉及了结构化归纳的概念及其在检验函数式程序的正确性方面的应用。

需要说明的是,后面章节的一些问题应该在其他课程中学习,而不是仅在编程语言和范例中学习。比如,并发性、事件驱动编程和程序正确性都应该作为一门独立的课程进行学习。此外,在第3、6、8、10和11章中很多的内容可以作为编译课程的基础。因为很多大学课程安排中没有提供这些主题的专门课程,本书只是在编程语言课程中作入门性的简单介绍。

0.3  本书预备知识和学习指导

在学习这门课之前应该至少已经完成一门预科课程或者学习过数据结构。在数据结构课程中,应该已经熟悉了链表、堆栈、稀疏矩阵和哈希表。

此外,在第3、6、8、16和17章任何含有程序执行的内容中,Java知识是学习的先决条件。如果没有学习过Java,也应该通过数据结构课程来熟悉C、C++或C#方面的知识。

建议学生准备一个好的Java指南、参考手册和编程环境。这些在网络上很容易获得(如http://java.sun.com/docs/books/tutorial/)。我们讨论的某些内容需要Java 1.4和Java 1.5引入的新特性的支持。这些特性在文中已清楚标明。

我们也希望学生有一定的数学知识,即初等离散数学和离散结构课程的相关知识。尽管这不是必需的,但是对于要学习数学因素浓厚的某些章节(第3、6、8、10和18章)的学生而言还是非常必要的。附录B中回顾了基本的函数、集合、逻辑和证明的内容。

本书与Computing Curricula 2001  [ CC 2001]的介绍是一致的。本书涵盖了Liberal Arts Model Curriculum [Walker and Schneider, 1996]及其2005年未定稿版本中描述的编程语言课程中所涉及的所有问题。

本书涵盖了Computing Curricula 2001的核心知识部分关于编程语言的所有主题(从1到11部分),还涉及该部分的其他主题,例如,事件驱动和并发编程(PF6)、内存管理(OS5)、函数及逻辑式编程(IS)和软件工程(SE)。相对于Computing Curricula 2001,本书对每个主题都用了更多的篇幅进行讲解

0.4  编程语言资源和Web站点

本文所涉及的软件都可在Java 1.5或者更高的版本中执行,而且我们已经使用SUN公司开发的Java 1.5执行过书中的程序。表0-2是我们推荐的一系列网络资源,包括书中涉及的主要编程语言的学习指南和其他信息。

表0-2  编程语言与Web站点

语    言

Web资源地址

Ada

www.gnu.org

C、C++

www.gnu.org

Haskell

www.haskell.org

Java 1.5

www.java.sun.com

Perl

www.perl.com 

(续表)   

语    言

Web资源地址

Prolog

www.python.org

Python

www.drscheme.org

Scheme

www.drscheme.org

Smalltalk

www.squeak.org

与该书配套的软件和相关的资料可以在www.mhhe.com/tucker站点找到,具体包括包括:

● Clite的Java语法、类型系统和语义的完整Java实现过程。

● 本文所有可运行程序的下载包。

● 与本书配套的授课幻灯片。

● 课后作业答案(教师可通过密码认证获得)。

0.5  致谢

在写作过程中,很多人给予了指导。James Lu是第1版初稿的最主要合作者。William学院的Bill Bynum、Holy Cross学院的Mary和Laurie King分别撰写了第4章和第8章。William学院的David Coppit介绍了第18章中出现的校验树的使用。Bowdoin学院和William and Mary学院的学生为第1版和第2版的早期版本作出了贡献。还要特别提到的是,Doug Vail对一些富于挑战性的问题提出了解决的办法。Wyatt Dumas帮助重写了第2版中的程序,并在其中两章的内容上使我们受益匪浅。我们要感谢所有的审阅者:

Qi Cheng                     Oklahoma大学

Rainey Little                  Mississippi州立大学

Jay-Evan J. Tevis               Auburn大学

John Hannan                  Pennsylvania州立大学

Neelam Soundarajan            Ohio州立大学

Robert van Engelen            Florida州立大学

Shannon Tauro                California大学Irvine分校

Gloria Melara                 California州立大学Northridge学院

Amer Diwan                  Colorado大学Boulder学院

Susan Gauch                  Kansas大学

Henri Casanova               California大学San Diego学院

Cristina V. Lopes               California大学Irvine学院

Salih Yurttas                  Texas A&M大学

Roman W. Swiniarksi          San Diego州立大学

Amar Raheja California State Polytechnic大学Pomona学院

Franck Xia                    Missouri大学Rolla学院

Rajendra K. Raj                Rochester技术学院

Randall D. Beer                Case Western Reserve大学

Robert M. Cubert               Florida大学

Liang Cheng                   Lehigh大学

David Hemmendinger           Union学院

正是他们仔细的阅读、富有建设性的评审和集体智慧,极大地推动了本书第1版和第2版的出版。也正是通过他们集体而卓越的洞察力使得本书第1和第2版有了本质的提高。作者还要特别感谢Union学院的David Hemmendinger为本书所作的认真编辑和详尽建议,其中大部分已经融入到书中。

最后,我还要感谢我们的编辑Rebecca Olson和Alan Apt,感谢他们的见识、指导和支持。他们非凡的技巧使得第二版有了更大的发展。

Allen B. Tucker             Robert E. Noonan

Bowdoin                    William and Mary学院

??

VI

编程语言:原理与范型(第2版)

XI

前    言

目录

  

第1章  概论 1

1.1  原理 2

1.2  范例 3

1.3  专题 5

1.4  编程语言发展简史 5

1.5  关于语言设计 10

1.5.1  设计约束 11

1.5.2  结果和目标 13

1.6  编译器和虚拟机 17

1.7  小结 19

1.8  练习 19

第2章  语法 21

2.1  文法 22

2.1.1  BNF文法 22

2.1.2  推导 24

2.1.3  语法分析树 25

2.1.4  结合性和优先级 27

2.1.5  歧义性文法 29

2.2  BNF扩展 32

2.3  小语言CLITE的语法 34

2.3.1  词法 36

2.3.2  具体语法 37

2.4  编译器和解释器 41

2.5  语法和语义学链接 44

2.5.1  抽象语法 45

2.5.2  抽象语法树 47

2.5.3  Clite的抽象语法 48

2.6  小结 50

2.7  练习 51

第3章  词法和语法分析 55

3.1  Chomsky层次结构 55

3.2  词法分析 58

3.2.1  正则表达式 59

3.2.2  有穷状态机 61

3.2.3  从设计到代码 64

3.3  语法分析 68

3.3.1  基本定义 69

3.3.2  递归下降分析 73

3.4  小结 79

3.5  练习 79

第4章  命名 83

4.1  语法问题 84

4.2  变量 85

4.3  作用域 87

4.4  符号表 89

4.5  解析引用 90

4.6  动态作用域 92

4.7  可见性 93

4.8  重载 94

4.9  生存期 96

4.10  小结 97

4.11  练习 97

第5章  类型 99

5.1  类型错误 100

5.2  静态类型和动态类型 101

5.3  基本类型 102

5.4  非基本类型 110

5.4.1  枚举 110

5.4.2  指针 111

5.4.3  数组和列表 112

5.4.4  串 117

5.4.5  结构体 118

5.4.6  变体记录和共用体 119

5.5  递归数据类型 121

5.6  作为类型的函数 122

5.7  类型等价 123

5.8  子类型 124

5.9  多态和通用类 125

5.10  自定义类型 129

5.11  小结 130

5.12  练习 130

第6章  类型系统 133

6.1  Clite的类型系统 135

6.2  隐式类型转换 142

6.3  规范Clite类型系统 146

6.4  小结 149

6.5  练习 149

第7章  语义 151

7.1  动机 151

7.2  表达式语义 153

7.2.1  表示法 153

7.2.2  结合律和优先级 154

7.2.3  短循环求值 156

7.2.4  表达式的意义 157

7.3  程序状态 158

7.4  赋值语义 160

7.4.1  多重赋值 160

7.4.2  赋值语句与赋值

表达式 160

7.4.3  语义的引用和复制 161

7.5  流程控制语义 161

7.5.1  顺序执行语句 162

7.5.2  条件语句 162

7.5.3  循环语句 164

7.5.4  GoTo争议 165

7.6  输入/输出语句 167

7.6.1  基本概念 167

7.6.2  随机访问文件 172

7.6.3  I/O错误处理语义 175

7.7  异常处理语义 177

7.7.1  策略和设计理念 178

7.7.2  Ada、C++和Java中的

异常处理 180

7.7.3  异常和断言 188

7.8  小结 192

7.9  练习 192

第8章  语义解释 195

8.1  状态转换和局部函数 195

8.2  Clite语义 196

8.2.1  程序的意义 197

8.2.2  语句的语义 198

8.2.3  表达式语义 202

8.2.4  表达式的副作用 206

8.3  动态类型语义 207

8.4  语义的规范化处理 211

8.4.1  状态和状态转换 212

8.4.2  程序的表示型语义 213

8.4.3  语句的表示型语义 214

8.4.4  表达式的表示型语义 218

8.4.5  规范化语义模型的

局限性 220

8.5  小结 220

8.6  练习 220

第9章  函数 225

9.1  基本术语 226

9.2  函数调用和返回 226

9.3  参数 227

9.4  参数传递机制 229

9.4.1  传值调用 229

9.4.2  按引用传递 231

9.4.3  值结果和结果传递 233

9.4.4  按名传递 234

9.4.5  Ada中的参数传递 236

9.5  活动记录 236

9.6  递归函数 237

9.7  运行时堆栈 239

9.8  小结 241

9.9  练习 242

第10章  函数实现 245

10.1  Clite中的函数声明与

调用 245

10.1.1  具体句法 246

10.1.2  抽象句法 247

10.2  编译Clite类型系统 249

10.3  函数调用与返回的语义 251

10.3.1  非void函数 252

10.3.2  重访问的副作用 253

10.4  类型和语义的规范处理 254

10.4.1  Clite类型映射 254

10.4.2  规范化Clite类型

规则 255

10.4.3  规范Clite语义 257

10.5  小结 262

10.6  练习 262

第11章  内存管理 265

11.1  堆 266

11.2  动态数组的实现 267

11.3  垃圾回收 270

11.3.1  引用计数 271

11.3.2  标记扫描 272

11.3.3  复制收集 275

11.3.4  策略优劣比较 277

11.4  小结 277

11.5  练习 278

第12章  命令式编程 279

12.1  命令式语言的产生 279

12.2  过程抽象 281

12.3  表达式和赋值 283

12.4  支持数据结构的库 284

12.5  命令式编程和C语言 286

12.5.1  一般特征 287

12.5.2  示例:Grep 288

12.5.3  示例:Average 290

12.5.4  示例:符号微分法 290

12.6  命令式编程和Ada语言 294

12.6.1  一般特征 295

12.6.2  示例:Average 297

12.6.3  示例:Matrix 

Multiplication 299

12.7  命令式编程和Perl语言 300

12.7.1  一般特性 301

12.7.2  示例:Grep 302

12.7.3  示例:Mailing 

Grades 305

12.8  小结 308

12.9  练习 309

第13章  面向对象编程 311

13.1  抽象数据类型 311

13.2  对象模型 317

13.2.1  类 317

13.2.2  可见性和信息隐藏 320

13.2.3  继承 321

13.2.4  多重继承 325

13.2.5  多态 326

13.2.6  模板 327

13.2.7  抽象类 328

13.2.8  接口 329

13.2.9  虚拟方法表 331

13.2.10  运行时类型标识 333

13.2.11  反射 333

13.3  Smalltalk 334

13.3.1  一般特性 335

13.3.2  示例:多项式 338

13.3.3  示例:复数 340

13.3.4  示例:银行账户 342

13.4  Java 343

13.4.1  示例:符号微分 343

13.4.2  示例:回溯 346

13.5  PYTHON 350

13.5.1  一般特性 353

13.5.2  示例:多项式 354

13.5.3  示例:分数 356

13.6  小结 358

13.7  练习 359

第14章  函数式编程 363

14.1  函数和λ演算 364

14.2  Scheme语言 368

14.2.1  表达式 368

14.2.2  表达式求值 369

14.2.3  列表 370

14.2.4  元素值 372

14.2.5  控制流 373

14.2.6  定义函数 373

14.2.7  let表达式 376

14.2.8  示例:Clite语义 378

14.2.9  示例:符号微分 382

14.2.10  示例:八皇后问题 384

14.3  Haskell语言 388

14.3.1  简介 389

14.3.2  表达式 390

14.3.3  列表及其产生 391

14.3.4  基本类型和值 394

14.3.5  控制流 394

14.3.6  定义函数 395

14.3.7  元组 398

14.3.8  示例:Clite语义 399

14.3.9  示例:符号微分 402

14.3.10  示例:八皇后问题 404

14.4  小结 406

14.5  练习 406

第15章  逻辑式编程 411

15.1  逻辑和horn 语句 412

15.2  Prolog语言中的逻辑式

编程 415

15.2.1  Prolog程序元素 415

15.2.2  Prolog语言的实际

应用 423

15.3  Prolog程序示例 427

15.3.1  符号微分法 427

15.3.2  猜字谜 429

15.3.3  自然语言处理 430

15.3.4  Clite的语义 434

15.3.5  八皇后的问题 437

15.4  小结 439

15.5  练习 440

第16章  事件驱动编程 443

16.1  事件驱动控制 444

16.1.1  模型-视图-控制器 445

16.1.2  Java中的事件 446

16.1.3  Java GUI应用程序 448

16.2  事件处理 450

16.2.1  单击鼠标 450

16.2.2  鼠标移动 451

16.2.3  按钮 452

16.2.4  标签、文本域和

文本框 453

16.2.5  组合框 455

16.3  3个示例 456

16.3.1  简单的GUI接口 456

16.3.2  设计Java Applet 462

16.3.3  基于事件驱动的

交互式游戏 464

16.4  其他事件-驱动应用程序 472

16.4.1  ATM自动取款机 472

16.4.2  家庭保安系统 473

16.5  小结 475

16.6  练习 475

第17章  并发编程 479

17.1  并发的概念 480

17.1.1  历史和定义 481

17.1.2  线程控制与通信 482

17.1.3  竞争和死锁 483

17.2  同步策略 485

17.2.1  信标 485

17.2.2  监视器 487

17.3  Java中的同步 489

17.3.1  Java线程 489

17.3.2  示例 491

17.4  进程间通信 500

17.4.1  IP地址、端口和

套接字 501

17.4.2  一个客户/服务器

示例 502

17.5  其他语言中的并发 508

17.6  小结 510

17.7  练习 510

第18章  程序的正确性 513

18.1  公理语义 514

18.1.1  基本概念 515

18.1.2  赋值规则 518

18.1.3  推理规则 518

18.1.4  Max函数的正确性 519

18.1.5  循环程序的正确性 520

18.1.6  形式化方法的观点 523

18.2  形式化方法工具:JML 525

18.3  面向对象程序的正确性 532

18.3.1  按照契约设计 532

18.3.2  类常量 533

18.3.3  示例:堆栈应用的

正确性 535

18.3.4  总结 540

18.4  函数程序的正确性 541

18.4.1  递归与归纳 541

18.4.2  结构化归纳示例 542

18.5  小结 544

18.6  练习 545

附录A  Clite的定义 549

A.1  Clite词汇和具体句法 549

A.2  Clite的抽象句法 550

A.3  Clite的类型系统 551

A.4  Clite的语义 552

A.5  Clite的加法函数 554

A.5.1  词汇以及具体语法 554

A.5.2  抽象句法 555

A.5.3  类型系统 555

A.5.4  语义 556

附录B  离散数学回顾 557

B.1  集合和关系 557

B.2  视图 561

B.3  逻辑 562

B.4  推理规则和直接证明 566

B.5  归纳证明 568

??

XVI

编程语言:原理与范型(第2版)

XVII

目    录

作者简介

编辑推荐

作者寄语

电子资料

www.luweidong.cn

下一个