程序设计语言------概念和结构(第二版)前言

本书的设计是面向有关程序设计语言的三四年级课程,至少要求前面已经学过一个有关程序设计的引论课程。如果加上一些辅助性阅读材料,这本书也可以用于研究生课程。

本版有什么新变化?

人们对语言的观点变化以及使用本书的反馈意见是本次修订的最根本动力。教师们希望能强调概念,但也要求用比较少的语言来阐述有关的概念。在此这段时期,Modula-2已逐渐淡出,而C++已占据了重要地位,被作为开发软件产品所用的程序设计语言。目前函数式程序设计语言的候选者还应该包括Standard MLHaskellMiranda

这个新版本包括15章,比原来的版本多了3章。新的这几章所扮演的角色分别是:

语言描述和语法问题移到了前面的第2章。

本书的组织

本书特别强调的是概念和它们协同工作的情况,而不是各种语言特征。因此讨论中将相关的概念放在一起,以便能够同步地给出有意思的例子和程序设计练习。对于一个语言,只是根据例子和练习的需要介绍足够多的东西,对所有有关语言的总结放在第15章。

第一部分:引论

1章讨论程序设计语言所扮演的角色及其开发过程。这里介绍了本书提出的各种程序设计风范,包括命令式、面向对象、函数式和逻辑式的程序设计。

2章讨论程序设计语言的描述问题,以便使这些东西能够应用到本书的其他部分。这章的例子主要讨论表达式,描述表达式语法的方法可以用到语言的其他部分。

第二部分:命令式程序设计

命令式语言族在第3-5章讨论。术语“命令式(imperative)”来自于命令和动作,这种计算模型就是基于基础机器的一系列动作。

3章的主题是控制流。结构化的控制结构,如while语句,能用于组织程序的控制流,形成以结构化语句为单位的程序设计,而不是以单个赋值为单位。学过主要关注命令式程序设计课程的学生一般都熟悉Pascal,因此,这章不仅讨论了赋值和结构语句,还讨论了借助不变式考虑程序设计的问题。所举例子涉及各种基本的值,例如整数和数组等。

4章讨论命令式程序设计中的数据。在PascalC出现之后,各种数据表示机制,如数组、记录和指针,已经趋于稳定。有关这些机制的讨论中也结合了它们在第6章和第7章的应用。

5章的讨论围绕着命令式程序设计的核心,也就是像PascalC一类语言的内部东西。有关论题包括:过程的源代码正文与过程活动的对比,参数传递机制,作用域规则和存储管理等。

在本书中,只要可能,就采用Pascal去展示命令式程序设计的有关问题。Pascal对于第3-5章而言已经足够了。另一种可能的选择是用C语言。

第三部分:面向对象的程序设计

随着程序变得越来越大,程序设计的自然单位也变成了一组组的数据和操作。程序结构概念的发展产生了一系列的术语,包括模块,用户定义类型(例如堆栈),以及类(在面向对象的程序设计中)。

6章开始讨论基于过程、模块和类的程序设计。这些概念服务于不同的需要,也能够互相组合,一起使用:在实现模块或者类的操作时总需要使用过程;模块能够被用作带类的程序的源代码中的静态部分。Pascal的某些版本支持模块概念,因此它们就可以用于第6章的前半部分。C++C的一种扩充,第6章里将会介绍它。

在第7章里的计算模型是独立的对象,这些对象通过互相传递消息的方式交互。这章的前三分之一是有关面向对象程序设计的一般性讨论,用了一个可以在C++Smalltalk里有相似实现的实例。其余部分是有关C++Smalltalk的独立材料,以便能用这两个语言中任何一个来研究面向对象程序设计的问题。基于教师的反馈,这里将C++放在Smalltalk之前,与原版本不同,交换位置。面向对象的程序设计用C++Smalltalk阐释,是因为它们代表了两条不同的途径。

在第3-7章里的所有概念都可以用C++语言阐述。因此,也可以直接将学生引到C++,而不是先经过C语言。

第四部分:函数式程序设计

函数式程序设计一种非常值得学习的程序设计风范,无论是就其自身,是作为一种研究类型等概念的媒介,还是作为一种描述语言的技术。第8章强调的重点还是概念,第9和第10章强调程序设计风格,第13章则是语言描述。这里的计算模型基于一个表达式解释器,表达式是通过将函数应用到一些子表达式上而构成的。

8章强调的是概念。函数式语言的简单性使它们可以非常方便地用于介绍诸如值、类型、名字和函数一类的概念。这种简单性结果源自对表达式和值的强调,与作为其基础的机器无关。本章讨论函数式语言的公共基础问题,以ML作为工作语言。

MLLisp之间的根本性差别在于ML是有类型的,类型的影响遍及整个语言。第9章用ML阐述函数和数据类型的使用。在函数式程序设计中,函数作为一级成员(一等公民),处在与其他值同等的地位。这种一级地位使我们可以构造出各种威力强大的针对数据集合的操作。

函数式程序设计始于LispLisp的程序和数据都用表来表示,甚至这个语言的名字本身也就是“表处理系统(List Processor)”的缩写形式。这种对于表的一致使用方式使得Lisp语言以其可扩充性而闻名于世。第10章将探索表的使用,以Lisp的方言Scheme作为基础。

另请参看第13章,那里包含了对Scheme的一个小子集的解释器。还有第14章,其中讨论了lambda演算。

第五部分:其他程序设计风范

在第11章里,逻辑式程序设计是结合Prolog一起讨论的。逻辑式程序设计处理的是关系而不是函数。对于合适的问题,采用这种风范写出的程序短小精悍,由规则和事实组成。这种语言利用给定的规则和事实,推导出对于查询的回答。

在第12章用Ada语言展示了并发程序设计的情况。也可以采用另一种方式,在面向对象的程序设计之后讨论并发程序设计,通过给每个对象一个计算线程,就能形成许许多多的进程。目前的组织方式是将函数式程序设计放在并发程序设计之前。

第六部分:语言的描述

13章有关语言描述方法介绍的对象是专业人员。这些方法范围广泛,从为语言翻译而用的属性,到用于类型推理的逻辑规则,再到用于澄清微妙的语言问题的解释器。

要描述一个语言,可以为它专门写一个定义性解释器,这种解释器的目的就是定义被解释的语言,效率并不是这里关心的问题。McCarthyLisp里写出了Lisp语言的最早的定义性解释器,在语言描述方面仍有重要意义,因此,这里的语言描述问题用Lisp的方言Scheme。第13章为Scheme的一个小子集开发了一个解释器。

lambda演算是函数式程序语言在智慧方面的先驱者。lambda演算具有极其简单的语法形式,这使它被广泛作为研究语言的媒介。第14章介绍了lambda演算的一些变体,这章将从纯的无类型lambda演算一直讨论到有类型的lambda演算。

15章是对本书中所用的各种语言的一个总结。

第一版的致谢

Rutgers大学的一个研究生讨论班给了我一个机会,也鼓舞我去收集有关程序设计语言的材料。我非常感谢Alex BorgidaMartin CarrollFrita HengleinNaftaly MinskyBob PaigeBarbara Ryder为这个讨论班的活跃气氛所做的贡献。

在哈佛大学的本科生课程中使用了本书的草稿,学生们写的关于该课程的评价意见都很有帮助。

本书的组织形式从许多人的意见中获益匪浅,特别是Addison-Wesley联系的匿名审稿人,提出建议的包括哈佛大学的Tom Cheatham,西肯塔基大学的John Crenshaw,伯克莱加利福尼亚大学的Paul Hilfinger,新墨西哥州立大学的Barry KurtzWilliam&Mary学院的Robert NoonanDavis加利福尼亚大学的Ron Olsson,达拉斯的德克萨斯大学的William Pervin,弗吉尼亚大学的Paul Reurolds,堪萨斯州立大学的David Schmidt,以及奥斯丁的德克萨斯大学的Laurie Werth

我非常感谢Al AhoJon BentleyGerard BerryEric CooperBruce DubaTom DuncanRich DrechslerPeggy EllisCharlie FischerDan FriedmanGeoges GonthierBob HarperMike HarrisonBruce HillyerBrian KernighanKim KingChandra KintalaDave MacQueenDianne MakiDoug McIloyJohn MitchellMike O'DonnellDennis RitchieBjarne StroustrupChris Van WykCarl Woolf在技术方面提供的帮助。

这本关于程序设计语言的书也是在一些小语言的帮助下产生出来的。图是用Brian KernighanPic语言画的,图中的灰色色块基于Rich Drechsler的工作;图表是用Mike LeskTbl程序排版;Lorinda CherryBrian KernighanEqn语言用于做数学格式和伪代码;Troff程序开始由Joe Ossanna写的,后来由Brian Kernighan保持其活力。如果没有Brian KernighanChris Van Wyk写的新Troff宏程序包,本书页面的编排必定不会这么好。建立索引的程序是Joe BentleyBrian Kernighan提供的。文中的交叉引用通过在Al Aho帮助下写出的一些脚本管理,这些脚本也用于管理“龙书”的正文。

最后,我还想感谢贝尔实验室的支持。我从同事们那里学到的东西比我所期望的要多得多。无论何时我遇到了问题,在那个建筑里总有某些人有这个问题的答案。

致谢

我真心感谢在本书第一版出版之后接到的各种评论。教师的经验和审阅者坦诚的观点指导着本次修订。

Addison-WesleyBebbie Lafferty长期守候在电话前,协调着评阅工作和各种评价,也维持着这个项目的正常进展。我现在知道,评阅人中包括Bill AppelbeMichael BarnettManuel E. BermudezRay FordAditya P. MathurL. A. OldroysHarmilton Richards,谢谢你们。

关于技术方面的帮助和讨论,我要感谢Jon BentleyLorinnda CherryBrian KernighanDave MacQueenDennis RitchieBjarne StroustrupRich Wolf。我在贝尔实验室的同事们都给了我极大的支持。

从我沉浸于这本书中以后,发生了许许多多的事情,包括一次出生,一次死亡,一次迁移,一次火灾。是Dianne Maki帮助我渡过了所有这些。

RS