艾兹格·迪科斯彻

1968 年，《ACM 通讯》刊发了一封只有三段话的短信，标题是《Go To 语句被认为是有害的》（Go To Statement Considered Harmful）。发信人是荷兰计算机科学家艾兹格·威贝·迪科斯彻（Edsger Wybe Dijkstra）。这封信引发的争论延续了数十年——但它改变了整整一代程序员理解"好代码"的方式。

破除误解：他不是一个算法发明家#

提到迪科斯彻，多数人首先想到的是"Dijkstra 算法"——寻找图中最短路径的经典算法。这是真实的贡献，但如果仅凭此记住他，就错过了更重要的东西。

迪科斯彻真正关心的是：程序员如何思考程序。他的一生都在追问一个问题：什么是"正确的程序"，以及人类的头脑如何能够系统地构造出正确的程序，而不是凭运气碰到正确的结果。他是"程序正确性"这一研究议程的最重要推动者之一。

现场：从物理到计算机——职业选择的纠结#

迪科斯彻 1930 年 5 月 11 日生于荷兰鹿特丹。父亲是化学家，母亲在头脑中做数学计算的能力令他印象深刻。他起初打算学物理，1948 年进入莱顿大学。但在莱顿他遇到了编程，并在 1951 年参加剑桥的一个课程后开始使用 EDSAC（最早的实用存储程序计算机之一）。

他向老板提出想以"程序员"为职业，老板回答说，没有任何大学把程序设计当成一门学科，他不能宣称自己是"程序员"。迪科斯彻后来回忆，这个问题促使他思考：计算机编程应该成为什么？——一门科学，还是只是一种技艺。

他 1959 年获得阿姆斯特丹大学数学博士学位，1972 年获得图灵奖，2002 年 8 月 6 日在荷兰努埃嫩（Nuenen）去世，享年 72 岁。

核心一：Dijkstra 算法（1959）#

1959 年，迪科斯彻在一篇仅 3 页的论文中发表了寻找图中单源最短路径的算法。

算法的核心思想是贪心+确定性扩展：从起点出发，每次从"尚未确定最短距离"的节点中选出当前距离最小的那个，将它纳入"已确定"集合，并更新它的邻居的距离估计。重复这个步骤，直到目标节点被纳入。

算法的时间复杂度（使用最小堆）为 $O((V + E) \log V)$，其中 $V$ 是节点数，$E$ 是边数。

迪科斯彻后来说，他在阿姆斯特丹与未婚妻购物时，累了坐在一家咖啡馆露台上喝咖啡，用了大约 20 分钟想出了这个算法的主要思路，当时他甚至没有铅笔和纸（他认为正是这一点逼他把算法设计得足够简洁）。这个算法今天仍然是 GPS 导航、网络路由协议（OSPF）、游戏地图寻路的基础。

核心二：结构化编程与"goto 有害论"#

1960 年代，程序普遍依赖 goto（无条件跳转）语句。代码像一团乱麻，执行路径很难追踪，更难证明其正确性。

迪科斯彻论证：一段程序的静态文本（你看到的代码）和动态执行（程序运行时做的事）之间的关系，应当可以被人的头脑所掌握。goto 把这种关系切碎，使得理性分析变得不可能。

他与 C. A. R. Hoare、Ole-Johan Dahl 合著的《结构化编程》（Structured Programming，1972）提出：任何程序都可以只用三种控制结构表达——顺序（sequence）、选择（selection，if/else）、迭代（iteration，while/for）。这就是今天所有高级语言的骨架。

这场争论不只是技术之争，更是关于什么是可理解的程序的哲学之争。

核心三：信号量与并发#

1960 年代初，迪科斯彻主持了 THE 操作系统的设计（Technische Hogeschool Eindhoven）。在处理多个并发进程协作时，他发明了信号量（semaphore）：一种用于协调并发进程访问共享资源的抽象机制，通过 P（等待/减少）和 V（释放/增加）两个原语操作来实现互斥与同步。

他同时定义了哲学家进餐问题（Dining Philosophers Problem）作为并发死锁的经典演示：五位哲学家围坐一桌，每人需要两只叉子才能进餐，而只有五只叉子。如果每人同时拿起左边的叉子等右边的叉子，就会陷入死锁。这个模型至今仍是操作系统和并发编程教科书的核心案例。

代价与争议#

迪科斯彻的风格以直率——有时被认为是傲慢——著称。他写了数千页未正式发表的手写备忘录（EWD 系列），对自认为糟糕的编程实践毫不留情。他对 FORTRAN、PL/I、COBOL、后来的 Java 都发出过尖锐批评。

他关于"goto 有害"的影响是深远的，但批评者指出：在某些低级系统编程场景下，合理使用跳转比强行套用结构化范式更清晰。这场争论随着语言演化逐渐平息，但争论本身推动了语言设计的进步。

形式方法：程序正确性的数学追求#

结构化编程只是迪科斯彻更宏大愿景的一部分。他真正的目标是形式方法（Formal Methods）：用数学方法严格证明程序满足其规格说明。

他发展了"最弱前置条件"（wp，weakest precondition）演算：对于任何程序语句 $S$ 和期望的后置条件 $Q$（程序终止后应该满足的性质），$wp(S, Q)$ 是使 $S$ 在终止后能满足 $Q$ 的最弱初始条件。通过组合这些计算，可以对整个程序进行正确性证明。

这套方法被纳入他的经典著作《程序设计学科》（A Discipline of Programming，1976），至今仍是形式方法教学的核心参考。它的实用继承者包括 Hoare 逻辑（C. A. R. Hoare，1969）和后来的程序验证工具（如 Dafny、Frama-C）。

计算机科学的身份认同争论#

迪科斯彻对一个问题有强烈的看法：计算机科学是数学学科还是工程学科？他毫不含糊地站在数学一边。

有一句流传甚广的话——"计算机科学之于计算机，不比天文学之于望远镜"——常被归到他名下，但其溯源其实存疑：它最早见于 Michael R. Fellows 1990 年的文章，并无证据表明出自迪科斯彻（庞大的 EWD 档案中并无此句）。不过这句话确实精准概括了他的立场：计算机只是工具，计算机科学研究的是抽象的计算结构，而非具体机器。这个立场让他与强调工程实践的阵营长期处于张力之中。

他对"软件工程"这个术语的态度相当怀疑，认为它掩盖了人们不愿意面对的事实：写出正确程序需要数学严格性，而不只是工程经验。这场争论至今未有定论，但它帮助塑造了计算机科学作为一门独立学科的自我认知。

EWD 备忘录：一位科学家的私人日志#

迪科斯彻以"EWD"开头（他名字缩写）的手写备忘录著称。他从 1960 年代开始写这些备忘录，内容涵盖研究思考、旅行见闻、对技术报告的评论，以及对自认为糟糕的计算机科学实践的直接批评。

这些备忘录以手工复印的形式在研究者之间流传——在互联网出现之前，这是一种影响力惊人的"前博客时代的博客"。据统计，他共写了 1300 余份 EWD 备忘录，已由得克萨斯大学奥斯汀分校数字化存档，公开可访问。

它们的语言风格极为清晰，偶尔辛辣——读迪科斯彻的 EWD，比读任何教科书都更能感受到他思考问题的方式。

跨域连接#

• 认知心理学：跳转让执行历史无法从文本位置推出，读者必须在头脑里同时保存多条可能路径。顺序、选择、迭代之所以够用，是因为每一种都能被折叠成一个输入到输出的关系，于是阅读可以逐块进行而不必展开全部路径。这条论证的落脚点不是优雅，而是人类工作记忆容量的硬上限。
• 证明：最弱前置条件演算把证明方向倒过来走——从期望的结果倒推所需的初始条件。好处是每一步都由语法结构唯一决定，因此可以机械化；代价是循环处必须由人提供不变量，机器至今无法一般地猜出它。这条界线解释了为什么验证工具能自动化大半，却总卡在循环与递归上。
• 动力系统：自稳定要求合法状态集合是全局吸引子——从任意初始状态出发都会收敛进去，既不假设故障类型，也不假设初始状态正确。这比一般容错强得多：只要系统还在按规则运行，它就能自我修复。代价同样明确：收敛时间没有一般上界，系统可能长时间停在不合法但会自行退出的状态里。
• 一语习得：他断言早年接触简陋语言会"污染"思维，这等于把编程当作第一语言习得来处理——存在关键期，早期表征难以改写。这条类比在自然语言里有证据（音系尤其明显），在编程语言里却没有：大量优秀程序员正是从他所鄙夷的语言入门。类比不能替代证据，这里是个干净的反例。
• 并发：信号量的贡献不在机制本身，而在把互斥从临时约定升级成可被推理的原语：P 与 V 是原子的，于是关于共享资源的论证可以只在原语层面进行。哲学家进餐则给出死锁的最小模型——几个条件同时成立就必然卡住，缺一不可，这才使破解有处下手。

生平年表#

最短路径算法的现代应用与变体#

1959 年的原始 Dijkstra 算法，在此后几十年经历了多个方向的发展和优化：

A\* 算法（1968）：由 Peter Hart、Nils Nilsson、Bertram Raphael 提出，在 Dijkstra 的基础上引入启发式函数（heuristic function）$h(v)$——对从节点 $v$ 到目标的距离的估计——使搜索能优先探索更有希望的方向。当启发函数满足"可采纳性"条件（不高估实际距离），A\ 保证找到最短路径，同时通常比 Dijkstra 快得多。A\ 是游戏 AI 寻路、机器人路径规划的标准算法。

双向搜索（Bidirectional Dijkstra）：从起点和终点同时向中间搜索，两个搜索波前相遇时终止。理论上可以把搜索空间减小到原来的一半。Google Maps 等地图服务在大规模路网上使用了更复杂的变体（如 Contraction Hierarchies，收缩层次结构）来处理数亿节点的全球路网查询。

Bellman-Ford 算法（1958）：处理 Dijkstra 不能处理的情况——允许负权边。代价是时间复杂度从 $O((V+E)\log V)$ 上升到 $O(VE)$。在金融套利检测（负权环意味着无风险套利机会）等场景中有直接应用。

迪科斯彻对教育的批判#

迪科斯彻对计算机科学教育的现状持强烈批评态度，多份 EWD 备忘录专门讨论教学问题：

他认为，在学生接触任何具体机器或语言之前，应该先让他们接触形式化的程序推理——就像学物理的学生应该先掌握数学，而不是直接动手拨弄设备。他担心学生通过"反复试错"学会编程，会形成根深蒂固的错误直觉：认为调试就是"瞎猜然后试试看"，而不是通过逻辑推理找出错误所在。

他对 BASIC 语言的批评最为激烈：他认为，早年接触 BASIC 的人脑子已经被"污染"，以后很难真正学会优雅的编程思维。这个说法在当时和后来都引发了强烈反弹——许多出色的程序员都从 BASIC 入门，并不认为这损害了他们的思维。

迪科斯彻的教育观极端而严格，但也揭示了一个真实的张力：入门编程教学应该优先可达性还是优先正确性？这个问题至今没有共识答案。

分布式算法的先驱工作#

迪科斯彻晚年的研究重心转向分布式系统——多台计算机如何在缺乏全局同步时协调工作。

1974 年，他提出了自稳定系统（Self-Stabilizing Systems）的概念：一个分布式系统，无论从哪种任意初始状态出发，只要所有进程遵循算法规则，最终都会收敛到合法状态。这提供了一种不依赖于初始状态正确性的容错保证——只要系统能最终运行，它就能自我修复。

自稳定理论在后来的分布式系统、传感器网络、区块链协议设计中都有直接应用，是迪科斯彻晚期工作中最具前瞻性的部分。

他的分布式算法研究，与他的结构化编程哲学一脉相承：总是在问"系统处于合法状态意味着什么"，以及"如何在数学上证明这一点"。

参考文献#

• Dijkstra, E. W. A Note on Two Problems in Connexion with Graphs. Numerische Mathematik 1 (1959): 269–271. （最短路径算法原始论文）
• Dijkstra, E. W. Go To Statement Considered Harmful. Communications of the ACM 11 (1968): 147–148.
• Dahl, O. J., Dijkstra, E. W., & Hoare, C. A. R. Structured Programming. Academic Press (1972).
• Dijkstra, E. W. A Discipline of Programming. Prentice-Hall (1976).
• EWD 档案（迪科斯彻手写备忘录）：University of Texas at Austin，已数字化，可在线访问。