Pascal之父：尼克劳斯·沃思

凡是学过一点计算机知识的人大概都知道“数据结构十算法= 程序”这一著名公式。提出这一公式并以此作为其一本专著的书名的瑞士计算机科学家尼克劳斯·沃思（Niklaus Wirth）由于发明了多种影响深远的程序设计语言，并提出结构化程序设计这一革命性概念而获得了1984年的图灵奖。他是至今惟一获此殊荣的瑞士学者。

　　沃思1934年2月15日生于瑞士北部离苏黎世不远的温特图尔（Winterthur），其父瓦尔特是一位地理学教授。沃思小时就喜欢动手动脑，组装飞机模型是他的最大爱好。中学毕业以后，沃思进入在欧洲甚至全世界都很有名气的苏黎世工学院（ETH），1958年取得学士学位。之后他远渡大西洋到加拿大的莱维大学深造（Laval是和加拿大名城魁北克隔圣劳伦斯河相望的一座城市），于1960年取得硕士学位。之后他又一次迁移，到美国加利福尼亚，进入加州大学伯克利分校，于1963年获得博士学位。

　　学成以后，沃思受聘到斯坦福大学刚刚成立的计算机科学系工作。著名的斯坦福大学门槛极高，怎么会看中了这个来自欧洲小国的毛头小伙子呢？原来在20世纪50年代末、60年代初的情况下，沃思的计算机经验和成就相当引人注目：在苏黎世工学院时，他曾听过瑞士的计算机先驱斯帕塞（A．P．Speiser，他曾出任IFIP的主席）的课，用过由斯帕塞开发的计算机ERMETH（虽然作为学生，机会并不多）；在莱维大学时，沃思学了数值分析，用过 Alvac III E计算机（虽然这台计算机经常出故障而不能开机）；在伯克利时，沃思先是有一台Bendix G-15计算机可用，后来又参加了为IBM 704开发 NELIAC语言编译程序器的科研小组。 NELIAC的全称是 Navy Electronics Laboratory International Algol Compiler，即美国海军电子学实验室国际 Algol编译程序语言，该语言用于数值计算和一些逻辑处理，其特点是用自己的语言写自己的编译程序，然后进行自编译，是一个类似于 Aled 58但具有开创性意义的语言。沃思在撰写博士论文时，Algol 60报告已经发表。 这是第一个清晰定义的语言，其语法是用严格公式化的方法说明的。当时已有一些学者认识到，清晰的规格说明对于可靠而有效的实现是必需的，但是并不充分：Aled 60报告中还存在一些缺陷和不足。

　　沃思在和 Algol的设计者之一、荷兰人范·维京格尔藤（Andrian van Wijingaarden,他曾任阿姆斯特丹数学中心计算部主任，在开发Algol 68中提出了二级文法，又叫w文法以解决上下文有关这一难题。他曾启发1972年图灵奖获得者狄克斯特拉走上计算机科学之路）多次接触和讨论以后，决定对 Algol 60作进一步改进，并以此作为自己的博士论文课题。这就诞生了由沃思所设计的第一个语言——Euler。Euler虽然在实用性上考虑并不十分周到，但在学术上却非常优美，为编译器的系统设计创造了一个很好的基础。此外，它还对 Algo 60进行了若干扩充，主要是增加了表处理能力。正是由于以上原因，斯坦福大学看中了沃思。与此同时，IFIP也注意到了Euler语言，决定吸收沃思参加对Algol语言进行完善与扩充的工作小组。当时，这个小组中有两派，一派主张设计一个新语言，以便树立一个新的里程碑；另一派则觉得时间太紧，主张对 Algo 60进行适当扩充。沃思参加进去以后，自称同时属于这两派，并提交了一份建议书。这份建议书经过霍尔（Tony Hoars）等人的修改、完善以后获得通过，这就是Aigol W（W是沃思名字的首字母）。

　　第二年，也就是1966年，Algol W在斯坦福大学的第一台 IBM 360上成功实现并正式应用。这中间还有一个小插曲：IBM 360当时只提供汇编语言和 FORTRAN语言，但沃思和他的学生都觉得这两者并不适宜于作为设计编译器的工具。于是，沃思用了两个星期时间写出了一个用来描写Algol编译器的新的语言的定义，然后用了4个月时间在宝来公司的B－5000计算机上完成了交叉编译程序，而沃思的一个学生则把这个交叉编译程序移植到 IBM 360上去。这些额外的工作极大地加快了 Algol W编译器的开发，同时催生了一个新的语言 PL 360。 PL 360虽然是作为辅助工具而设计、开发的，但后来却在许多地方获得应用，取得了意想不到的成功。

　　Algol W及 PL 360奠定了沃思作为世界级程序设计语言大师的地位，一举成名。但沃思是一个具有强烈爱国心的人，成名后的他谢绝了斯坦福大学的挽留，于1967年回到祖国，先在苏黎世大学任职，但第二年就回到他的母校苏黎世工学院。在这里，他首先设计与实现了 PASCAL语言（Philips Automatic Sequence CAlculator Language的缩写），这是在 CDC 6600上开发成功的。 PASCAL在数据结构和过程控制结构方面都有很多创造。对于前者，除一般的整型、实型、布尔型数据外，PASCAL还增加了字符型、子域类型、记录结构类型、文件类型、集合类型和指针类型；对于后者，除保留了无条件转移的GOTO语句外，又增加了if-then-else、case、while、repeat和for等多种控制结构，还允许复合语句和处理记录变量的分量使用with语句这种编写形式。可以说，现代程序设计语言中常用的数据结构和控制结构绝大多数都是由PASCAL语言奠定基础的，因此它在程序设计语言的发展史上具有承上启下的重要里程碑意义。

　　说来有趣，沃思开发PASCAL的初衷是为了有一个适合于教学的语言，并没有想到商业应用。但一经推出，由于它的简洁明了，它所提供的丰富的数据结构和控制结构为程序员提供了极大的方便与灵活性，也由于它特别适合于由微处理器所组成的计算机系统，竟然大受欢迎，广泛地流传开来。在C语言问世以前，PASCAL是风靡全球、最受欢迎的语言之一，创下了发行拷贝数最多的世界记录。单是沃思的一个学生菲力浦·凯恩（Phillipe Kahn），从 ETH毕业以后，在美国加利福尼亚州办了一个软件公司，就卖出了100多万个PASCAL拷贝，成为百万富翁。

　　1971年，沃思基于其开发程序设计语言和编程的实践经验，在4月份的 Communications of ACM上发表了论文“通过逐步求精方式开发程序’（Program Development by Stepwise Refinement），首次提出了“结构化程序设计”（structure programming）的概念。这个概念的要点是：不要求一步就编制成可执行的程序，而是分若干步进行，逐步求精。第一步编出的程序抽象度最高，第二步编出的程序抽象度有所降低…… 最后一步编出的程序即为可执行的程序。用这种方法编程，似乎复杂，实际上优点很多，可使程序易读、易写、易调试、易维护、易保证其正确性及验证其正确性。结构化程序设计方法又称为“自顶向下”或“逐步求精”法，在程序设计领域引发了一场革命，成为程序开发的一个标准方法，尤其是在后来发展起来的软件工程中获得广泛应用。有人评价说沃思的结构化程序设计概念“完全改变了人们对程序设计的思维方式”，这是一点也不夸张的。1983年1月，ACM在纪念 Communications of ACM创刊 25周年时，从其 1／4个世纪发表的大量论文中评选出有“里程碑意义的研究论文” 25篇，每年１篇，沃思的这篇论文就是其中之一。

　　PASCAL的成功也罢，结构化程序设计思想的巨大影响也罢，都没有停止沃思继续创造性的研究与开发工作。20世纪70年代中期，为适应并发程序设计的需要，沃思又成功开发了一个获得广泛应用的语言Modula。M0dula除了提供并发程序设计功能之外，另外一个重要特征是引进了模块概念（这也是这个语言叫做Modula的原因）。此外，它还引进了“进程”（process）这一和并发程序相联系而产生的重要概念。Modula语言还特别适合于书写系统程序。但是，比Modula具有更加重大得多意义的却是它的第二个版本Modula．2。这是 1976年，沃思再次赴美国，到 Xerox公司的 Palo Alto研究中心参与Alto计算机的设计与开发工作。Alto是世界上第一个具有图形用户界面的个人计算机系统（可惜Xerox公司没有把它商品化，而由Apple公司学去了它的技术而推出 Macintosh）。

　　沃思回到瑞士以后，参考Alto的经验，设计、开发Lilith个人计算机系统。为了和Lilith的体系结构相配合，沃思决定在Modula的基础上开发新版本，作为整个系统的开发语言。Modula－2与Modula相比，语法更加简洁，更加强调界面设计，模块的可重用性更好。它共有3个编译单元，即程序模块、定义模块和实规模块。在定义模块（definition module）中，只给出那些和模块外部交往所必需的信息。例如，对模块内部的子程序说明而言，在定义模块中只给出子程序名、参数名及其类型等，而不给出子程序体本身，也就是说，在定义模块中只给出模块外部可见的信息。在实规模块（implementation module）中，则给出那些在模块外部不可见的信息，例如，在模块内部定义的子程序说明的子程序体。这样的安排既提高了可读性，又有助于分别编译。M0dula－2在优美性（elegance）和简洁性（simplicity）两方面都比Modula更进一步。

　　Lilith的操作系统、图形软件包、数据库系统、网络协议套件、文件服务器等基本系统和大量应用模块全都是用M0dula－2开发的。目前世界上已经开发了近百个Modula－2的编译系统，北美和欧洲的许多大学已经用Modula－2代替PASCAL作为计算机系本科生的第一门程序设计课程。Modula－2的标准化工作则早在1984年就已由英国开始进行，ISO则于1987年对它进行标准化，并采用由IBM的维也纳实验室提出的VDM－SL和经过沃思本人加以扩充的BNF（即EBNF,见下）表达语言的语法与语义，在形式化方面达到了一个新的水平。在Lilith项目中，沃思坚持将计算机体系结构、语言、操作环境这三者统一起来考虑，实行集成化、一体化设计的成功经验是具有革命性的创举，从而使这个项目在计算机科学史上占有重要地位。

　　近年来沃思致力于一个新的计划，即Oberon计划。Oberon是将程序设计语言和操作系统结合在一起的、面向单用户的个人工作站的一个系统。因为沃思认为，在因特网日益普及的情况下，今后联网的计算机主要将是个人工作站，因此如何使个人工作站功能更加强大、更加方便使用是一个十分重大的课题。沃思把这个计划取名为Oberon是寓意深长的，因为Oberon是希腊神话中的仙境之王和女神Titania的丈夫。沃思的目标是要使Oberon语言超越PASCAL和Modula，设计出的操作系统和编译器功能更加强劲。1992年他写了两本书向读者推荐Oberon（见后），可见其对这个计划的重视。

　　除了程序设计语言之外，沃思在其他方面也有许多创造。为了定义和描述语言，沃思对著名的“巴科斯-诺尔范式”BNF进行了扩充，成为EBNF（Extended BNF）。我们目前所看到的许多语言的 BNF实际上是EBNF，不过人们往往忽略掉这个E字。和BNF一起出现的，还常常有一些看上去像铁路图那样的图形，称作“语法图”（syntax chart或 syntax diagram）或“铁路图”（railroad diagram），这也是由沃思所设计与发明的，这种图形标记法的描述能力等价于BNF，但当然更易于阅读与理解，更加直观。在语法图中，用圆圈表示终结符，用方框表示非终结符，用有向弧表示走向，图上一条通路就表示该语法结构的一种正确定义方法。语法图的4种基本构造方法如下。

　　(1) 若产生式为W→W1W2W3,则语法图如图1。

　　(2) 若产生式为W→W1W2|W3a|bcW4 ，则语法图如图2。

　　(3) 若产生式为W→abW，则语法图如图3。

　　(4) 若产生式为W→ab|abW,则语法图如图4。

　　对于较复杂的产生式，其语法图一般可通过上述4种语法图进行组合而得。

　　在对上下文无关文法的研究中，一个很重要的问题是如何确定两个符号之间的优先关系。现在一般采用的办法也是由沃思和他的同事韦伯提出来的，就叫沃思-韦伯优先关系（Wirth－ Weber precedence relation），或叫简单优先关系。它规定上下文无关文法 G中任意两个符号的优先关系如下。

　　（1）X<Y，当且仅当有产生式 A→αXBβ，且有推导B+→Yr。

　　（2）X=Y，当且仅当有产生式A→αXYβ。

　　（3）X> Y，当且仅当有产生式 A→αBYβ，且有推导B+→rX及Y →*aδ。

　　其中A、B为非终结符，X、Y为待定优先关系的两个任意符号，α、β、Υ和δ为由终结符和非终结符组成的任意符号串，可以是空串。a是终结符。

　　沃思的学术著作很多，主要有如下几种，其中一些原版是用德文写的，翻译成了英文。

　　《系统程序设计导论》（ Systematic Programming: An Introduction，Prentice－ Hall，1973。其德文版已出至第 5版）

　　《算法十数据结构=程序》（Algorithms＋ Data Structures＝ Programs，Prentice－Hall，1976）

　　《算法和数据结构》（Algorithms and Data Structures， Prentice - Hall ，1986）

　　《Modula－2程序设计》（Programming in M0dula－2，Spring6r，1988，第4版）

　　《PASCAL用户手册和报告： ISO PASCAL标准》 （PASCAL UserManual and Report： ISO PASCAL Standard， Sprillger， 1991）

　　《Oberon计划：操作系统和编译器的设计》（ Project Oberon：the Design of an Operating System and Compiler，ACM Pr.，1992）

　　《Oberon程序设计：超越Pascal和Modula》（Programming in Oberon: Steps beyond Pascal and Modula, ACM Pr，1992）

　　《数字电路设计教材》（Digital Circuit Design for Computer Science Students：An Introductory Textbook， Spnnger， 1995）

　　《编译器构造的原理和技术》（Theory and Techniques of Compiler Construction，Addison- Wesley，1996）

　　ACM除了1984年授予沃思图灵奖外，1987年又授予他“计算机科学教育杰出贡献奖”。另一重要的国际学术组织IEEE也授予过沃思两个奖项： 1983年的 Emanual Piore奖和 1988年的计算机先驱奖（Computer Pioneer Award）。1992年，加州大学伯利分校命名沃思为“杰出校友”。

　　沃思是在1984年10月于旧金山举行的ACM年会上接受图灵奖的。沃思发表了题为“从程序设计语言设计到计算机建造”（From Programming Language Design to Computer Construction）的图灵奖演说，回顾了自己在计算机领域所做的工作。演说全文刊载于Communications of ACM，1985年 2月，159－ 164页，也可见《前 20年的 ACM图灵奖演说集》（ACM Turing Award Lectures——The First 20 Years：1966－1985，ACM Pr．），179－196页。沃思在演说中强调了程序设计语言简 性的重要意义，也讨论了它所需的硬件和软件环境（因为沃思一直很重视语言的实现问题）。他介绍了在设计Modula－2和Lilith中的经验，指出第一手经验和选择良好开发工具的无比价值。

　　沃思现仍在苏黎世工学院任教，他的电子箱为：wirth @ inf.ethz.ch