
Tony Hoare(托尼·霍尔,英国,1934 年生)在 并发程序的形式化验证与算法设计 领域的位置,很少有人能给出准确坐标。他把并发程序从「靠测」变成了「可证明」——而证明的代价,是一门需要二十年才被广泛接受的新逻辑。
一、Hoare 逻辑:一个不变量管住所有执行的验证思路
他受的是哲学训练而非工程训练——这解释了他后来为何总在追问「这个命题到底意味着什么」,而不是「这个程序跑得怎么样」。他在国王学院的老师是迪利·哈里(Diehls Harry),一个把编译器实践带进课堂的人,这让他在纯理论之外接触到了真实机器。他在牛津期间主修哲学,这段训练让他后来习惯于先厘清「什么是一个正确的问题」再动手写程序。他早期在编译器与汇编语言上的实践经历,让他对程序正确性的关注带有一种工程师式的具体。
牛津的哲学训练给了他一种习惯:任何命题都要先问清楚它到底断言了什么。他的核心提问是:能不能只写出程序的若干性质,就让机器自动检查出其余一切?Hoare 逻辑正是对这一提问的形式化回答。他的教学影响远超论文本身——牛津的编程方法课程把”先写不变量再写代码”变成一代程序员的默认习惯。
二、1934 年在伦敦出生:一个在牛津学哲学的少年
他把早期经历里的「编译器写多了」当成方法论来源:写程序的人最终会发现,代码的正确性不该只靠运行来发现。他在编译器课程上第一次意识到程序可以像数学命题一样被证明,这个转折点改变了他后来的研究方向。他在国王学院遇到的老师迪利·哈里把编译器带进课堂,这种把理论与工程结合的教法影响了他一生。迪利·哈里把编译器带进课堂的做法让他第一次看到理论与实现可以互相印证。他在国王学院与后来牛津的课堂上反复强调「先想清楚问题」这一方法论。他原本学的是哲学,这个背景解释了他为何总把编程问题当作逻辑推理问题来处理。他在牛津期间因为一台早期计算机的缺陷而接触到机器编程,这段经历让他意识到抽象与实现之间必须有可靠接口。
三、1958 年:Quicksort 与那个被自己发现的越界错误
他最初把 Quicksort 写在打字机上,纸带长度超过了当时的机器纸卷,于是他改用更简单的版本——这个「因打不上去而简化」的过程本身是算法史上的经典细节。他自己对 Quicksort 的评价带着工程师的谦逊:这不总是最快的,但在大多数情况下是最快的。Quicksort 最初是他在实现一个高效排序时顺手写出的,论文只占几页,却被引用了数十年。他曾为一本杂志写过回顾文章,把排序算法的历史串成一条线索,读者因此能看出设计思路的演进。
他曾为算法杂志撰写过多篇回顾文章,把不同方法的来龙去脉梳理成连贯的线索。这些文章至今仍是理解算法史的重要材料。Quicksort 的原始实现存在越界缺陷,他自己发现后公开修正,这段插曲常被用来讲测试与自我怀疑的价值。他提出的关键洞见是:这类错误的根源在设计而非实现,因此应当用一种能自动证明部分性质的方法来取代逐例调试。
四、1965 年:信号量与「等待」和「通知」这两个原语
信号量的原始形式由荷兰人 Dijkstra 提出,Hoare 的贡献是给出了更接近程序员的「等待与通知」版本,并证明其正确性。这成为计算机科学史上典型的「先做出来、后被接受」的路径:论文发表后近十年几乎无人引用,后来成为操作系统教科书的标配。他把并发问题归约到同步问题,这一抽象使后续的验证工作第一次具有可操作性。信号量与管程构成的两套方案,分别对应了「计数」与「互斥」的两种思路。信号量的提出解决的是两个基本问题:如何让一个进程等待、如何让一个进程通知,两者各自只需要两条原子操作。他用”哲学家进餐”这类具体场景说明死锁,而不是停留在抽象定义上。
五、1979 年:通信顺序进程与用通信取代共享内存
CSP 的关键创新是:程序被写成进程之间的对话,而不是命令的序列,这使得死锁分析变成了结构上的可读性判断。CSP 与 Unix 的管道、Go 的 goroutine 通道、Erlang 的邮箱机制在思想上是同源的。CSP 用对话而非命令来描述程序,这个视角让并发规范第一次可以像数学推导那样被审查。该论文在发表后相当长时间影响有限,直到智能体与并发编程兴起才被重新发现。CSP 把进程间的交互写成对话,这种记法让并发规范第一次可以用数学方法审查。
论文的完整轨迹被开源社区保存下来,多年后成为智能体设计的直接灵感来源。CSP 用通信而非共享内存来组织并发,这一取舍直接影响了后来 Go、Erlang 与 CSP 语言家族的设计。他在 1978 年获得图灵奖,评语特别提到他把并发问题转化为通信问题这一方法论贡献。
六、他对「过早优化」的批评与「先写对,再写快」的主张
他 1980 年因算法与程序设计方法获图灵奖,是最早因形式化工作获奖的学者之一。他在 2000 年获得「软件系统」年度影响奖时仍坚持同一句话:可靠的系统需要可机器检查的论证,而不只有测试。他的图灵奖主要表彰其在算法与程序设计方法上的贡献,而形式化方法只是其中一条线索。他晚年关心编程语言的可读性与教学价值,认为这是决定语言能否被广泛采用的关键。他晚年推动「先定义后使用」这类原则进入语言与教学,影响了此后数十年的程序设计教育。
他的核心主张是:程序设计首先是与人沟通,其次才是与机器沟通。他对行业的著名批评是过早优化,并强调应先保证程序结构正确,再依据测量结果处理性能。他推动的”验证与开发分离”思路在安全攸关领域影响尤大,被许多标准组织纳入过程要求。
参考来源
- 托尼·霍尔 的公开传记、论文与技术档案(可按其所属机构与年代检索)
- 相关领域的学术史与技术史综述文献