11

作者:吕娜


名人堂指针就像跳转一样,疯狂地在数据结构之间到处指来指去。在高级语言里面引入指针是个退步。我们可能永远无法从这一失败之中恢复过来。


这段话出自查尔斯·霍尔(Charles A.R. Hoare),1980年他因“对程序设计语言的定义和设计方面的基础性贡献”而获得图灵奖。他26岁就发明了闻名于世的快速排序算法Quicksort。当然,他对计算机科学技术的贡献还远远不止于此,在程序设计语言的定义和设计、数据结构和算法、操作系统等许多方面,他都有许多影响深远的成果。他,查尔斯·霍尔,就是这样一个了不起的人。


早年生平


霍尔是英国人,1934年1月11日生于斯里兰卡的科伦坡。小时候的理想是当个作家,喜欢萧伯纳和罗素的作品。因为勤奋好学、少言寡语,他被同学称为“教授”。中学毕业后,他进入牛津的莫顿学院学习,对数理逻辑产生了兴趣,并首次接触到了计算机。他的第一个程序用Mercury Autocode的语言编写,解决了诺依曼书中的两人博弈问题。


崭露头角


1960年,霍尔进入Elliott兄弟伦敦公司,成为一名程序员。他接到的第一个任务,就是为Elliott 803计算机编写一个库程序,实现新发明出来的Shell排序算法。在此过程中,霍尔对不断提升代码的效率着了迷,他不仅很好地完成了任务,还发明了一种新算法,比Shell还快,而且不会多耗费太多空间——Quicksort诞生了。


随后,霍尔又接到了新任务——在公司新机型Elliott 503上实现Algol 60语言。Elliott Algol的开发非常顺利,大获成功,霍尔本人也从此受到国际学术界的重视。当然,对他来说,另一件事情更为重要,他和项目中另一位当时比自己更专业的女程序员Jill Pym相识相知,并最后结婚。


开创性成果


1968年他到北爱尔兰女王大学从事教学和研究,1977年转入牛津大学至今,目前还同时担任微软研究院的研究员。他全身心地投入到计算机科学理论的研究中,作出了许多创造性的重大贡献,尤其是程序设计理论和操作系统设计等方面,目前许多广泛流行与应用着的概念都源于霍尔的工作。


1969年10月,霍尔在Communications of the ACM上发表了有里程碑意义的论文“计算机程序设计的公理基础”。在这篇论文中,霍尔提出了公理语义学,这是继1963年用递归函数定义程序,以及在1967年基于程序流程图的归纳断言法以后,程序逻辑研究中所取得的又一个重大技术进展。


20世纪70年代后期,霍尔深入研究并实现了程序设计语言CSP,后来成为著名的并行处理语言Occam的基础。80年代中期,霍尔和S. Brools等人合作,提出了“CSP理论”,开创了用代数方法研究通信并发系统的先河,形成了“进程代数”这一新的研究领域。1995年他还和我国学者、中科院院士何积丰合作,提出了统一程序设计理论。


霍尔发表过许多高水平的论著。ACM在1983年评选出最近25年中发表在Communications of the ACM上的有里程碑式意义的25篇经典论文,只有2名学者各有2篇论文入选,霍尔就是其中之一。1972年他与O.J. Dahl和E. W. Dijkstra三位图灵奖得主合著的Structured Programming一书,更是难以逾越的高峰。


获奖经历


霍尔获奖无数,1980年获得美国计算机学会(ACM)设立的计算机界最高奖——图灵奖;1981年获得AFIPS的Harry Goode奖;1985年获得英国IEE的法拉第奖章;1990年被IEEE授予计算机先驱奖。2000年获得日本稻盛财团设立的国际大奖——京都奖(尖端技术领域)。


2009年3月他在Qcon技术会议上发表了题为“Null引用:代价十亿美元的错误”的演讲,回忆自己1965年设计第一个全面的类型系统时,未能抵御住诱惑,加入了Null引用,仅仅是因为实现起来非常容易。它后来成为许多程序设计语言的标准特性,导致了数不清的错误、漏洞和系统崩溃,可能在之后40年中造成了十亿美元的损失。他在同月出版Communications of the ACM中表示,如何证明程序的正确性仍然是计算机科学中有待解决的重大课题。


(本文来自《程序员》杂志2010年1月刊)


 


转播到腾讯微博

----->立刻申请加入《程序员》杂志读者俱乐部,与杂志编辑直接交流,参与选题,优先投稿

7 Responses to “Quicksort算法之父——1980年图灵奖获得者查尔斯·霍尔”

  1. wutsang 说道:

    又一座泰山!!!

  2. karl 说道:

    仰止。

  3. Spring 说道:

    真地很了不起!现在对指针的释放仍然有点模糊!要求有人能清楚地分析就好了!

  4. shouwangzhe101 说道:

    致敬

  5. 流年 说道:

    厉害

  6. nils 说道:

    仰望一下。。不过说到指针。。有利有弊。。。 用得好的。。指针是一把利器。。用不好的可能会带来灾难性的结果。。。

  7. liangerhu 说道:

    高山,中国有流水吗?

请评论

preload preload preload
京ICP备06065162