了解过“数据结构”或者搞过“算法设计与分析”的朋友，肯定对大名鼎鼎的快速排序算法QUICKSORT不陌生；而写过代码的程序员，100%用过CASE语句，那个处理条件跳转的东西。但你有没有好奇过，这些东西究竟是谁发明的呢？它们的背后英雄，是英国牛津大学的计算机科学家查尔斯·安东尼·理查德·霍尔（Charles Antony Richard Hoare），他在1980年拿下了第15届图灵奖。
不过，霍尔能拿图灵奖，靠的可不止是发明了QUICKSORT和CASE这些小伎俩。他在计算机科学这片天地里，特别是在编程语言的定义设计、数据结构算法琢磨、操作系统开发等领域，都是响当当的人物，贡献一大堆，影响深远。QUICKSORT和CASE啊，只不过是人家辉煌成就里的两颗微不足道的小成就罢了。
虽然现在面试都经常问快速排序，这是对我们而言，有难度。对霍尔来说，没什么难度，这是他当学生的时候，花了一个下午，跟他的导师打赌，就写出来了，当时他只有25岁。在讲这个故事之前，我先来讲一下他的生平。
托尼·霍尔1934年出生在锡兰科伦坡（现在的斯里兰卡），父母都是英国人。他爸爸是殖民地公务员，妈妈是茶园主的女儿。霍尔在英国牛津的龙学校（我也不知道为什么叫这个鬼名字，就是叫Dragon School，你可以搜一下，学校的校徽就是一条龙 ）和坎特伯雷的国王学校上学。
然后，他去了牛津的默顿学院学习古典学和哲学。1956年毕业后，他在皇家海军服役了18个月，在那里学了俄语。1958年，他回到牛津大学攻读统计学研究生证书，也是这时候，他开始接触计算机编程，并在Ferranti Mercury上学习了Autocode，老师是莱斯利·福克斯。后来，他作为英国文化协会的交换生前往莫斯科国立大学，在安德烈·科尔莫戈洛夫的指导下学习机器翻译。快速排序算法就是他在莫斯科国立大学当访问学生时发明的。
当时，霍尔在为国家物理实验室的一个机器翻译项目工作。作为翻译过程的一部分，他需要对俄语句子中的单词进行排序，然后在按字母顺序排列在磁带上的俄语-英语词典中查找它们。他最初想到用插入排序，但很快发现这种方法速度太慢，于是想出了一个新的算法。他在Mercury Autocode中编写了分区部分，但在处理未排序段列表时遇到了困难。回到英国后，他被要求为Shellsort编写代码。霍尔提到自己知道一种更快的算法，他的老板打赌六便士说如果他知道，这六便士就给你了。最终，他花了一个下午的时候，构思了这个算法，他的老板承认输了。
关于CASE语句，这个发明过程也非常的简单，当然，对他来说是非常简单的。在他发明快速排序算法的第二年，霍尔接受了一个新任务，为公司的新机型Elliott 503设计一种新的高级语言。
那时，他拿到了一份Algol 60报告的复印件，并参加了由狄克斯特拉（E. W. Dijkstra，1972年图灵奖获得者）等人在布赖顿举办的Algol 60培训班。他觉得与其自己设计一种不太成熟的新语言，还不如实现已经比较成熟的Algol 60在Elliott 503上。霍尔和他的同事们的这个想法得到了公司的同意，于是他主持制定了明确的目标：系统要安全可靠，生成的目标代码要简洁，工作区数据要紧凑，过程和函数的入口和出口要清晰、严密等，并明确整个编译过程采用一次扫描的原则。
这样，Elliott Algol的开发进展顺利，并取得了成功。它在1963年推出后大受欢迎，成为全球各版本Algol 60中效率、可靠性和方便性等方面的佼佼者。霍尔因此受到了国际学术界的重视。国际信息处理联盟（IFIP）后来任命霍尔为工作组2.1的负责人，这个工作组的任务是维护和发展Algol。霍尔不负众望，主持设计了Algol X，以继承和发展Algol 60。正是在设计Algol X时，霍尔发明了CASE语句。
霍尔于1968年离开Elliott公司，离开了产业界，原因是他作为学者对程序设计语言的形式化定义等偏重学术性和理论性的课题更感兴趣。离开Elliott后，他担任了一年的英国国家计算中心主任，但发现自己不适合从事行政管理，于是转入爱尔兰的昆士大学（Queen’s University）从事教学和研究。1977年，他转入牛津大学。离开Elliott后，霍尔在计算机科学理论的研究中发挥了他的特长，作出了许多创造性的重大贡献。
如果按重要贡献排名的话，我认为最重要的贡献是1969年10月，霍尔在《ACM通讯》（Communications of ACM）上发表了那篇具有里程碑意义的论文《计算机程序设计的公理基础》（An Axiomatic Basis for Computer Programming）。在这篇论文中，霍尔提出了程序设计语言的公理化定义方法，即公理语义学（axiomatic semantics），用一组公理和规则描述语言应有的性质，从而使语言与具体实现的机器无关，并且便于证明程序的正确性。这一方法继承了麦卡锡（J. McCarthy，1971年图灵奖获得者）在1963年提出的用递归函数定义程序的方法，以及弗洛伊德（R. W. Floyd，1978年图灵奖获得者）在1967年提出的基于程序流程图的归纳断言法，是程序逻辑研究中的又一个重大技术进展。
霍尔提出的方法在逻辑上与弗洛伊德提出的方法类似，但不是用流程图而是用代数法，即控制流用以下一些结构表示。大家一定见过类似BEGIN和END的关键字。利用霍尔提出的这种方法，已经成功地描述了PASCAL等语言，说明了这个方法的巨大威力。但应该指出的是，霍尔的这个方法是不完备的，因为霍尔在开发和建立这个系统时并没有追求系统的完备性，而更多地追求系统的实用性。如果你没有见过BEGIN和END，一定见过大括号，按道理说，这项成就也归功于霍尔。
另一个成就是他在分布式操作系统上的研究。20世纪70年代后期，霍尔深入研究了在不同机器上运行的程序设计语言和数据交换问题，开发了面向分布式系统的程序设计语言CSP（Communicating Sequential Processes）。在该语言中，并发系统由若干并行运行的顺序进程组成，每个进程不能对其他进程的变量赋值。进程之间只能通过一对通信原语实现协作。CSP语言后来成为著名的并行处理语言OCCAM的基础，OCCAM由INMOS公司为Transputer开发。
OCCAM是一种并行编程语言，由INMOS公司在1980年代为Transputer开发。Transputer是一种专门设计用于并行处理的微处理器，而OCCAM语言正是为充分利用这种硬件特性而设计的。OCCAM语言以CSP理论为基础，由Tony Hoare提出并发展。
20世纪80年代中期，霍尔与布鲁克斯（S. Brookes）等人合作，提出了“CSP理论”TCSP。虽然TCSP与CSP不同，但二者有一定联系。TCSP是一个代数演算系统，其基本成分是事件（或动作），进程由事件和一组算子构成。TCSP采用“广播式通信”，不同于CSP中的握手式通信，只有当并行运行的各进程都执行同一动作时，才会发生通信。此外，TCSP采用失败等价作为确定进程等价的准则，这就是著名的“失败语义”。利用失败可以构造TCSP的指称模型。霍尔为失败等价建立了一些公理系统，可以对语义上的等价关系进行形式推导。
霍尔在这方面的工作开创了用代数方法研究通信并发系统的先河，形成了所谓的“进程代数”（process algebra）这一新的研究领域，产生了重要影响。
虽然OCCAM语言和Transputer硬件在市场上的普及程度有限，但其设计理念和并行处理模型对后来的并行编程语言和并发编程理论产生了重要影响。例如，现代的Go语言和Erlang语言在某种程度上都受到OCCAM和CSP理论的启发。
这不是我说的，是别人说的。Rob Pike，Go语言的主要设计者之一，在多次访谈中提到CSP理论对Go语言的影响。例如，在2012年的一篇题为《Go Concurrency Patterns》的演讲中，Pike详细介绍了CSP理论如何影响了Go的并发模型设计。Joe Armstrong，Erlang语言的创造者之一，也在多次访谈和文献中提到CSP理论和消息传递模型对Erlang的设计影响。例如，在《Programming Erlang》一书中，Armstrong讨论了Erlang的并发模型和消息传递机制，并提到受到了CSP理论的启发。
再多讲一下，为什么我来评价他最主要的贡献是这两项呢？我算个屁啊，是吧。实际上，这不是我评价的，而是科学家评价的。ACM在1983年评选出过去25年中发表在《ACM通讯》上的25篇里程碑式经典论文，其中只有两位学者各有两篇论文入选，霍尔就是其中之一（另一位是1972年图灵奖获得者狄克斯特拉）。霍尔入选的两篇论文分别是1969年10月的《计算机程序设计的公理基础》（An Axiomatic Basis for Computer Programming，这篇论文的要点我们前面已经介绍过了），以及1978年8月的《通信顺序进程》（Communicating Sequential Processes），该论文奠定了CSP语言的基础。
听到这里，大家可能会有这样的疑问，这么出名的科学家，我竟然只知道他读书的时候，搞的两个微不足道的东西，一个快速排序，一个Case语句。为什么会这样呢？其实呢，答案挺简单的，在网上，不是有很多人会骄傲的说：你还是多读点书吧。大部分说这句话的人，是不读书的，自己不读，反而要别人读。
但是，用在这个问题里，是相当的切合。为什么大部分人对霍尔，只知道快速排序，而不知道他研究的那么多问题呢？原因真的是因为读书太少。他研究的问题，都是博士生才能研究的，一般计算机本科毕业，搞个快速排序就已经快把CPU干烧了。
好了，这一期到这里了，他获得的奖实在是太多了，如果要一一列举，也讲不完。值得一提的是，老爷子现在还健康的活着，今年90岁了。