第一台电子计算机是个模样古怪的庞然大物，它填满了几个房间，消耗的电力相当于一家规模不小的工厂，耗费了1940年的成百万美元，但其计算能力只不过相当于今天的一部普通手持计算器。使用这部机器的程序员都知道机器的时间远比自己的时间更宝贵。他们用机器语言编程序。机器语言就是能直接控制处理器的二进制位的序列，可以用于指挥它在适当的时候去做加法、比较，或把数据从一个地方搬到另一个地方，如此等等。在这种细节层面上描述程序是一件极端单调乏味的工作。下面这个程序用欧几里得算法计算两个整数的最大公约数（GCD），它是用MIPS R4000处理器的机器语言写的，用十六进制（以16为基）数的形式表示的。

随着人们开始着手写更大的程序，事情也逐渐变得越来越明显了：我们需要有一种更不容易出错的记法形式。这促使人们发明了汇编语言，它使人可以采用有助记忆的缩写形式描述计算机操作。用MIPS的汇编语言重写上面的GCD程序，大致是下面的样子：

在开始时，人们设计的汇编语言也就是要在助记形式与机器语言指令之间建立一一对应关系，如上面例子所示。从这种助记形式到机器语言的翻译工作由一个称为汇编器（assembler）的系统程序完成。后来汇编器被进一步扩充，增加了“宏展开”机制，使程序员可以为公共指令序列定义参数化的简写形式。当然，在汇编语言和机器语言之间的对应关系仍然是显而易见的，程序设计还是一种以机器为中心的事业：对不同类型的计算机，都必须用它自己的汇编语言编写程序，而程序员也只能基于这种机器能实际执行的指令去思考问题。

随着计算机的发展和变化，出现了许多互相竞争的不同设计，为每种新机器重新写程序逐渐变成一种越来越使人感到沮丧的工作。要求人们去掌握大型汇编语言程序里的各种细枝末节也变得越来越困难。人们开始期待一种独立于机器的语言，特别是希望有一种语言，使人可以用某种类似数学公式的形式描述数值计算（这是当时最主要的一类程序）。这种期待导致了20世纪50年代中期Fortran语言最初版本的开发。Fortran被认为是第一个高级程序设计语言。其他高级语言接踵而来，特别值得提出的是Lisp和Algol。

从高级程序设计语言到汇编语言或机器语言的翻译工作由一种称为编译器（compiler）的系统程序完成。编译器远比汇编器复杂得多，因为当源形式是高级语言时，源程序与目标程序之间的一一对应关系已不复存在了。Fortran最初也是慢慢被接受的，因为程序员只要付出一些努力，总能写出对应的汇编语言程序，使之比编译器生成的程序运行得更快。当然，随着时间的流逝，这种差异也在逐步缩小，并最后反了过来。随着硬件变得越来越复杂（由于流水线、多个功能部件等），随着编译器技术持续不断的进步，今天最新的编译器通常能够生成出比人写的程序更好的代码。即使是在那些人可能做得更好的地方，计算机速度和程序规模的增长也已使得降低程序员成本变得越来越重要了。不仅在程序的初始构造中，而且与随后的程序维护（升级和纠正错误）也关系密切。劳动力的成本已经远远超过了计算机硬件的成本。

1.1 语言设计的艺术

The Art of Language Design

今天已经有了成千种高级程序设计语言，而且新语言还在不断涌现。人们已经只把汇编语言用于一些很特殊的应用。在典型的本科生课程里，使用几种不同语言也是很常见的事情。为什么会有这么多语言呢？这个问题有着多种不同的回答。

发展进步  计算机科学是一门新兴学科，人们还一直在努力探索做事情的更好方式。在20世纪60年代末期到70年代前期出现了“结构化程序设计”革命，使得如Fortran、Cobol和Basic一类语言中基于goto的控制流让位于while循环、case语句及其他类似的高级结构。在80年代后期，如Algol、Pascal和Ada一类语言里的嵌套块结构，又开始让位于Smalltalk、C++、Eiffel及其他类似语言里的面向对象结构。

特殊用途  许多语言的设计是为了某个特殊的问题域。各种Lisp方言的长处在于操作符号性的数据和复杂的数据结构；Snobol和Icon特别适合操作字符串；C特别适合底层的系统程序设计；Prolog的长处在于对数据间的逻辑关系做推理。这些语言里的每一个都能成功地用于范围广泛的工作任务，但其强项显然在一些特定的用途之中。

个人偏爱  不同的人喜欢不同的东西。有关程序设计的大部分偏狭观念其实不过是个人的不同口味。有些人喜爱C的紧凑，另一些人恨这种东西。有些人认为递归地思考问题很自然，另一些人却偏爱迭代。一些人愿意用指针工作，另一些人更喜欢Lisp、Clu、Java和ML里面隐式的引用。个人偏爱的强度和多样性，也使开发出一种能被所有人接受的程序设计语言成为不大可能的事情。

当然，有些语言比其他语言更成功。在人们设计出的这么多语言里，得到广泛使用的并不多。是什么使一个语言成功呢？同样也有多种不同的回答。

表达能力  一种常见的中心论点是某种语言比另一种语言更“强大”，虽然在某种形式化的数学意义上它们都是图灵等价的——每种语言都可以写出所有的算法，即使可能有些笨拙。还有，语言的特征肯定对程序员写出清晰、紧凑和易于维护的代码有着极其重要的影响，特别是对大型系统。以早期版本的Basic为一边，以Common Lisp或者Ada为另一边是无法比较的。对描述能力有贡献的各种因素，特别是各种抽象机制，也是本书讨论的重点。

新人容易上手  由于Basic很容易入手，因此谁也无法阻止它的成功。这种成功应特别归因于它很低的“学习曲线”。Logo在基础教育工作者中流行也是同样的原因，因为连5岁的孩子也能学会它。在许多年里，Pascal一直被用作程序设计引论课程的教学语言，比另一些更“严肃的”语言用得更多，也是因为其紧凑和易学。最近几年Java已经在扮演类似的角色。虽然Java比Pascal复杂得多，但又比（例如）C++简单不少。

易于实现  除了很低的学习曲线外，Basic的成功还在于它很容易在非常小的、只有很少资源的机器上实现。Forth有一小批忠实追随者，原因也很类似。有关Pascal的成功，人们提出的一个重要因素是其设计者Niklaus Wirth为该语言开发的一个简单而又易于移植的实现，且免费将它提供给全世界的大学使用（见例子1.12）。Java的设计者也走了类似的路，将他们的语言提供给几乎所有需要它的人。

开放源码  今天的大部分程序设计语言都有至少一个开放源码的编译器或者解释器，但是与其他语言相比，有些语言——特别是C——与自由传播、同行评议、社团支持的计算的关系更密切些。C语言在20世纪70年代初由Dennis Ritchie和Ken Thompson在贝尔实验室开发，与Unix操作系统的设计携手并进。经过许多年的发展，Unix演化为世界上最具可移植性的操作系统，成为计算机科学学术界首选的操作系统，而C与之密切相关。随着C的标准化，该语言在极其广泛的平台上都可以使用。开放源码操作系统的领袖Linux也是用C语言写的。2005年3月，在sourceforge.net上进行的60%的项目都是用C及其后裔编写的。

优秀的编译器  Fortran的成功在很大程度上归功于其特别优秀的编译器。这一情况部分来源于历史的偶然性。Fortran在我们周围晃荡的时间比其他任何语言都长，公司投入了大量时间和金钱，努力使编译器能生成出特别快速的代码。当

然，在这里也有语言设计的因素，在Fortran 90之前的Fortran版本里都没有递归和指针，而正好是这些语言特征使生成快速代码（至少是对那些不用这些特征也能以合理方式写出的程序）的工作大大复杂化。还有一些类似情况，一些语言（例如Common Lisp）的成功也应部分地归功于它们有很好的编译器和支持工具，这些工具在帮助程序员管理大型项目方面可能起极好的作用。

经济、支持者和惯性  最后，还有一些非技术因素也会对语言的成功产生很大影响。强有力的支持者作为后盾就是其中之一。Cobol和PL/I的生存之本，至少有很大一部分应归功于IBM。Ada出生于美国国防部，虽然它包含了众多绝佳的特征和想法，但是如果没有美国国防部作为后盾，其极高的实现复杂性恐怕早就致它于死地了。与此类似，C#虽然也有些技术优点，但如果没有微软作为后盾，恐怕根本就不会有人注意它。在生存周期的另一端，有些语言仍被广泛使用，虽然“更好的”替代物早已存在，原因就是已经形成了安装好的软件和程序员专家的坚实基础，取代这些的代价可能太高了。

引言

在本书中，像这样的旁白用于强调语言的设计和实现的相互作用，除了其他内容外，这里将特别考虑下面这些问题：

¨  一些特别的情况（例如本节所提到的一些情况），其实现的难易程度对语言的成功产生了重要的影响；

¨  语言特征，许多设计师认为是错误的，至少部分原因在于其实现太困难；

¨  一些语言里抛弃了可能很有用的特征，主要是认为它们的实现太慢或者太难；

¨  被采纳的语言限制，至少部分原因在于实现的复杂性或者代价；

¨  一些语言特征，引进它们的至少一部分原因在有利于高效而优美的实现；

¨  一些情况，其中机器的体系结构使某些合理特征的代价极其高昂；

¨  各种各样的利弊权衡，其中实现问题扮演了重要的角色。

附录B里完整列出了所有旁白。

事情很清楚，并没有某个唯一因素能决定某个语言是不是“好”。因此，当我们研究程序设计语言时，就需要从许多不同观点出发去考虑问题。特别的，我们需要从程序员和语言实现者的两种观点出发去考虑问题。有时这两种观点是一致的，例如对于速度的追求。然而事情经常不是这样，这两种追求也常常相互矛盾，此消彼长，常常需要在对一种特征的概念诉求与其实现代价之间做出某种平衡。当实现所要求的代价不仅影响到使用有关特征的程序，也影响到并不使用这些特征的程序时，如何选择的问题就变得特别棘手了。

在早期计算的日子里，实现者的观点占据着支配地位。程序设计语言一直在作为一种告诉计算机去做什么的工具而不断演化。然而无论如何，对程序员而言，最好是把语言定义为一种表述算法的工具。就像自然语言限制着人们解释和论述的方式一样，程序设计语言也限定了什么可以表达，什么不能表达，并对程序员能够怎样思考问题有着深刻而微妙的影响。Donald Knuth（计算机算法和计算机排版的一位先驱）提议将程序设计看作一种艺术，用于去告知其他人自己希望计算机做些什么 [Knu84]。这一定义有可能成为最好的折中定义，因为它承认，概念清晰性和实现效率都是最基本的追求。本书将试着抓住这种折中的精神，在它所涵盖的每个论题上，都尽可能同时考虑有关的概念方面和实现方面。