Edsger W. Dijkstra：用结构化编程让复杂性有序退场

图灵奖第七届（1972）| Edsger W. Dijkstra：用结构化编程让复杂性有序退场

一句话概括：他教会程序员”先思考，再编码”，让软件工程从”黑魔法”变成了”可证明的科学”

🏆 获奖简介

Edsger Wybe Dijkstra（艾兹赫尔·戴克斯特拉）是结构化编程的奠基人、并发理论的先驱、算法大师。

• 出生时间：1930年5月11日
• 出生地点：荷兰 鹿特丹
• 获奖年份：1972年
• 获奖原因：在程序设计语言、编译器、操作系统设计以及形式化验证方面的基础性贡献

为什么他是第七位？ 因为他是继Alan Perlis、Maurice Wilkes、Richard Hamming、Marvin Minsky、James Wilkinson、John McCarthy之后，第七位获得图灵奖的计算机科学家。他让编程从”艺术”变成了”工程”。

🚀 他的重大贡献

1. 结构化编程：终结”意大利面代码”的革命

简单理解：结构化编程就像给代码定规矩——只用顺序、选择、循环三种结构，不允许乱跳。

Dijkstra的贡献：

• 背景：1960年代，程序员写代码就像在迷宫里乱跑，到处是goto语句，代码像意大利面一样纠缠不清。
• 1968年的炸弹：Dijkstra在《Communications of the ACM》发表了那篇著名的《Go To Statement Considered Harmful》（Go To语句有害论），引发了编程界的大地震。
• 核心思想：任何程序都可以只用三种控制结构表达——顺序（sequence）、选择（selection）、循环（iteration）。
• 革命性影响：这篇短文改变了整个编程语言的设计方向，影响了从Pascal到Python的所有现代语言。

为什么重要？ 在结构化编程之前，维护大型程序简直是噩梦。一个goto可能从程序的任何地方跳到任何地方，调试就像大海捞针。结构化编程让代码变得可读、可维护、可证明。

实际影响：

• 语言设计：Pascal、C、Java、Python等所有现代语言都采纳了结构化编程原则
• 代码审查：今天的代码规范几乎都禁止或严格限制goto的使用
• 编程教育：所有编程教材都从顺序、选择、循环开始教起
• 软件工程：结构化设计、模块化思想都源于此

打个比方：如果说传统编程像在一个没有规则的城市开车，想去哪就去哪，结果经常迷路；那么结构化编程就像建立了交通规则——只能沿着规定的道路（顺序、选择、循环）行驶，虽然看似受限，但整个城市的交通反而更流畅了。

2. 最短路径算法：每个程序员都会用到的经典

简单理解：Dijkstra算法就像导航软件，帮你找到从A点到B点的最短路径。

Dijkstra的贡献：

• 提出时间：1956年，当时Dijkstra才26岁
• 灵感来源：在阿姆斯特丹咖啡馆喝咖啡时，思考如何找到两个城市之间的最短路径
• 核心思想：从起点开始，逐步扩展到最近的未访问节点，保证每次都选择当前最优的路径
• 时间复杂度：使用优先队列优化后可以达到O(E + V log V)，其中E是边数，V是顶点数

为什么重要？ 这个算法简单、优雅、高效，成为图论算法的基石。今天几乎所有的路径规划问题都要用到它或它的变体。

实际应用：

• 地图导航：Google Maps、百度地图、高德地图的核心算法
• 网络路由：互联网路由协议（如OSPF）的基础
• 游戏AI：角色寻路的标准算法
• 社交网络：推荐”你可能认识的人”
• 物流优化：快递路线规划

有趣的细节：Dijkstra后来说，他之所以能想出这个算法，部分原因是当时没有纸笔，只能在脑子里思考，这迫使他想出最简洁的方案。他还说：“算法必须简单到可以在没有纸笔的情况下理解，否则它就太复杂了。“

3. 信号量与并发控制：多线程编程的”红绿灯”

简单理解：信号量就像交通红绿灯，控制多个线程（车辆）对共享资源（路口）的访问。

Dijkstra的贡献：

• 提出时间：1965年
• 核心概念：信号量（Semaphore）——一个整数变量，只能通过两个原子操作访问：
  • P操作（等待/减）：如果信号量大于0，减1并继续；否则等待
  • V操作（信号/加）：信号量加1，如果有等待的线程，唤醒一个
• 命名由来：P和V来自荷兰语proberen（测试）和verhogen（增加）

为什么重要？ 在多核CPU成为主流的今天，并发编程无处不在。信号量是最基础的同步原语，几乎所有现代操作系统都实现了它。

实际应用：

• 互斥锁（Mutex）：用信号量值为1的二元信号量实现
• 生产者-消费者问题：经典的并发编程教学案例
• 数据库连接池：限制同时访问数据库的连接数
• 限流器：限制API的并发访问量

经典问题：哲学家就餐问题 Dijkstra提出了这个著名的思想实验：5个哲学家围坐在圆桌旁，每人面前有一盘面条，但只有5根筷子（每两个人之间一根）。哲学家要么思考，要么用左右两根筷子吃饭。问题是：如何设计规则，让大家都能吃到饭，又不会发生死锁？

这个问题优雅地展示了并发编程的核心挑战：资源竞争、死锁、饥饿。今天它仍然是操作系统课程的必讲案例。

4. 银行家算法：死锁预防的经典方案

简单理解：银行家算法就像银行管理现金——确保无论客户怎么取钱，银行都不会”破产”（系统不会死锁）。

Dijkstra的贡献：

• 提出背景：为了解决操作系统的资源分配问题
• 核心思想：在分配资源前，先检查分配后系统是否还处于”安全状态”——即存在一个资源分配序列，让所有进程都能完成
• 命名由来：就像谨慎的银行家不会把所有现金都贷出去，而要保留足够的储备

为什么重要？ 死锁是并发系统最头疼的问题之一。银行家算法提供了一个理论上完美的预防方案，虽然实际应用中有性能开销，但它的思想影响了无数资源管理策略。

实际影响：

• 操作系统教学：几乎每本操作系统教材都讲这个算法
• 资源调度器：启发了云计算、容器编排中的资源分配策略
• 数据库事务：事务管理中的锁策略受其启发

5. THE操作系统：分层架构的开创性实践

简单理解：THE操作系统就像盖房子——从地基到屋顶，一层层严格分开，下层为上层服务。

Dijkstra的贡献：

• 开发时间：1960年代后期，在荷兰埃因霍温理工大学
• 命名：THE是Technische Hogeschool Eindhoven（埃因霍温理工大学）的缩写
• 革命性设计：首次系统性地使用分层架构（Layered Architecture）
• 六层结构：
  • 第0层：处理器分配与多道程序
  • 第1层：内存管理与虚拟内存
  • 第2层：进程间通信
  • 第3层：I/O管理
  • 第4层：用户程序
  • 第5层：操作员控制台

为什么重要？ 分层架构成为现代软件设计的基本原则。从操作系统到网络协议（TCP/IP七层模型），从企业应用到微服务，处处可见分层思想的影子。

核心原则：

• 单向依赖：上层可以调用下层，下层不能调用上层
• 信息隐藏：每层只暴露必要的接口，隐藏实现细节
• 独立验证：每层可以独立测试和验证正确性

6. 形式化验证与程序正确性

简单理解：形式化验证就像数学证明——用数学方法证明程序”一定正确”，而不是”测试没发现问题”。

Dijkstra的贡献：

• 核心理念：“测试可以发现bug的存在，但永远无法证明bug的不存在”
• 与Tony Hoare合作：推动Hoare逻辑（前条件-后条件证明）的发展
• 提出”卫式命令”（Guarded Commands）：一种更容易形式化推理的编程范式
• 倡导”正确构造”：程序应该在设计时就保证正确，而不是写完再调试

为什么重要？ 虽然形式化验证在工业界应用有限（成本高、难度大），但它的思想深刻影响了软件工程：

• 设计先行：先想清楚再动手写代码
• 断言与契约：在代码中明确前置条件、后置条件和不变式
• 类型系统：现代语言的类型系统本质上是轻量级的形式化验证
• 关键系统：航空、医疗、金融等领域的关键软件越来越多地采用形式化方法

7. EWD手稿：思想的原始记录

独特的工作方式：

• EWD编号系统：Dijkstra的所有技术笔记都有编号，从EWD1到EWD1318
• 手写原稿：坚持用钢笔手写，认为这能让思维更清晰
• 公开传播：复印后寄给全世界的同行，形成了独特的学术交流方式
• 思想宝库：这些手稿记录了无数洞见，从算法到哲学，从技术到教育

经典语录：这些手稿中诞生了许多名言，比如：

• “简洁是可靠性的前提”
• “计算机科学与天文学一样，与望远镜关系不大”
• “提出正确的问题，比回答错误的问题重要得多”

🌍 对世界的深远影响

改变了编程语言的设计

从Pascal（Niklaus Wirth深受Dijkstra影响）到现代语言，结构化编程原则成为语言设计的基本准则。今天我们觉得理所当然的if-else、while、for，都是结构化编程革命的成果。

奠定了软件工程的理论基础

Dijkstra强调”程序正确性”和”形式化推理”，让软件开发从”手工艺”变成了”工程学科”。他的思想影响了软件工程的方方面面：需求分析、设计、实现、测试、维护。

塑造了操作系统设计

THE操作系统的分层架构、信号量的并发控制，成为所有现代操作系统的标配。Unix、Linux、Windows在设计上都能看到Dijkstra思想的影子。

让算法成为独立学科

Dijkstra最短路径算法不仅本身重要，更重要的是他对算法设计的系统性思考。他证明了算法不仅要”能跑”，还要优雅、高效、可证明。

影响了计算机科学教育

今天全世界的计算机课程——从数据结构、算法到操作系统、软件工程——都深受Dijkstra思想的影响。他的严谨性和优雅性成为学科标准。

🏆 获奖理由

ACM官方表彰：“表彰他在ALGOL等高级编程语言的开发、编译器设计、操作系统原理（特别是THE系统）、并发程序设计以及程序设计方法论方面的基础性贡献。”

更通俗的理解：他让程序员从”调试高手”变成了”设计大师”，让软件开发从”碰运气”变成了”有保障”。

历史意义：作为第七位图灵奖得主，Dijkstra完美体现了理论与实践的结合——既有深刻的数学洞察（算法、形式化），又有重要的工程贡献（THE系统、信号量）。

👤 个人生平与传奇经历

生平时间线

• 1930年5月11日：出生于荷兰鹿特丹
• 1948年：进入莱顿大学学习数学和物理
• 1951年：参加剑桥大学的计算机课程，第一次接触编程
• 1952年：在阿姆斯特丹数学中心开始编程工作
• 1956年：提出最短路径算法（在咖啡馆用20分钟想出）
• 1957年：与Maria Debets结婚（婚姻登记员一度拒绝承认”程序员”是合法职业）
• 1959年：获得阿姆斯特丹大学博士学位
• 1962年：成为埃因霍温理工大学教授，荷兰第一位计算机科学教授
• 1965年：提出信号量概念
• 1968年：发表《Go To Statement Considered Harmful》
• 1972年：获得图灵奖
• 1984年：从埃因霍温退休，移居美国德克萨斯州奥斯汀
• 1984-2002年：在德克萨斯大学奥斯汀分校任Schlumberger百周年纪念主席教授
• 2002年8月6日：在荷兰纽嫩去世，享年72岁

性格特点与趣闻

完美主义者：

• 坚持用钢笔手写所有技术笔记，从不涂改，写错了就重新写一遍
• 认为使用计算机反而会限制思维，更喜欢在纸上思考
• 对代码质量要求极高，宁可不写也不写烂代码

坦率的批评者：

• 公开批评BASIC语言会”永久性地损害学生的编程能力”
• 批评”软件工程”这个词，认为它暗示编程是体力劳动
• 对面向对象编程也有保留意见，认为很多OOP实践违背了简洁性原则

教育理念独特：

• 不喜欢学生在课堂上使用电脑，认为应该先在纸上设计
• 强调思考比编码重要：“编程是一项脑力活动”
• 倡导”关注点分离”：每次只思考一个问题

生活轶事：

• 1957年结婚时，婚姻登记员拒绝在职业栏填写”程序员”，说荷兰法律没有这个职业。最后只好填”理论物理学家”。
• 他拒绝使用电子邮件，认为会打断思考。一直坚持手写信件。
• 晚年仍然坚持每天散步思考问题，许多重要想法都是在散步时产生的。

经典语录

“简洁是可靠性的前提。“（Simplicity is prerequisite for reliability.）

“提出问题比解决问题更重要。如果你在解决错误的问题，解决得再好也没用。”

“计算机科学与计算机的关系，就像天文学与望远镜的关系。“（Computer Science is no more about computers than astronomy is about telescopes.）

“测试可以证明bug的存在，但永远无法证明bug的不存在。“（Testing shows the presence, not the absence of bugs.）

“优雅并非可有可无的奢侈品，而是决定成功与失败的因素。“（Elegance is not a dispensable luxury but a factor that decides between success and failure.）

💡 核心思想深度解析

结构化编程的三大支柱

1. 顺序结构（Sequence） 最简单直接的控制流：语句按顺序执行。这听起来理所当然，但在goto横行的年代，能保证”代码从上到下执行”本身就是进步。

2. 选择结构（Selection） 使用if-then-else做分支判断，而不是用goto跳来跳去。关键在于：每个分支都有明确的入口和出口，执行完后回到主流程。

3. 循环结构（Iteration） 使用while、for等循环，而不是用goto构造循环。循环有明确的进入条件和退出条件，不会出现”不知道从哪跳进来”的情况。

为什么这三个够用？ Dijkstra和其他计算机科学家证明了：任何可计算的算法都可以用这三种结构的组合来表达。这叫”结构化程序定理”（Structured Program Theorem）。

关注点分离（Separation of Concerns）

这是Dijkstra思想的核心：

• 一次只想一件事：设计程序时，把不同的关注点分开处理
• 模块化：每个模块只负责一个明确的功能
• 抽象：隐藏实现细节，只暴露必要的接口

实际应用：

• THE操作系统的分层就是关注点分离的体现
• MVC架构（模型-视图-控制器）也是这个思想
• 微服务架构更是把分离做到了极致

程序正确性的层次

Dijkstra区分了几个层次的”正确”：

1. 语法正确：编译能通过 2. 部分正确：如果程序停机，结果是对的 3. 完全正确：程序一定会停机，且结果是对的 4. 形式化验证：用数学方法证明程序满足规格说明

他认为测试只能达到第2层，真正的可靠性需要第4层。虽然在实践中很难做到，但这个理念影响了软件质量保证的所有工作。

并发编程的本质困难

Dijkstra深刻理解并发的困难：

1. 不确定性：多个线程的执行顺序是不确定的 2. 竞态条件：结果依赖于时序的微小差异 3. 死锁：多个线程互相等待，都无法继续 4. 饥饿：某个线程永远得不到资源

信号量是他对这些问题的优雅回答：用一个简单的抽象（P和V操作）就能构建各种复杂的同步模式。

🔍 经典算法详解

Dijkstra最短路径算法的直观理解

核心思想：从起点开始，像”波浪”一样向外扩散，每次都选择”最近的未访问节点”。

步骤说明：

1. 初始化：起点距离为0，其他所有点距离为无穷大
2. 选择：从未访问的节点中选择距离最小的节点
3. 更新：检查通过该节点能否让其他节点的距离变小
4. 重复：重复步骤2-3，直到所有节点都被访问

为什么正确？ 关键的贪心性质：每次选择的”当前最近”节点，它的最短路径已经确定。因为如果有更短的路径，一定会经过一个更近的中间节点，但那个节点应该在更早的步骤就被选中了——矛盾。

优化技巧：

• 使用优先队列（堆）来快速找到最小距离节点
• 对于稀疏图，斐波那契堆可以进一步优化
• 双向搜索：从起点和终点同时搜索，可以快很多

信号量的典型应用模式

1. 互斥锁（Mutex） 用信号量值为1的二元信号量实现临界区保护。

2. 资源计数 用信号量的值表示可用资源的数量，比如数据库连接池。

3. 事件通知 一个线程等待（P操作），另一个线程发信号（V操作），实现线程间通信。

4. 栅栏（Barrier） 让多个线程在某个点同步，都到达后才一起继续。

银行家算法的安全性检查

核心问题：给定当前资源分配情况，判断系统是否处于安全状态。

安全状态定义：存在一个进程序列P1, P2, …, Pn，使得每个Pi都能：

• 用当前可用资源 + 已分配给P1到Pi-1的资源完成任务
• 完成后释放资源，供后续进程使用

算法思路：

1. 假设某个进程完成，回收它的资源
2. 看能否满足另一个进程的需求
3. 重复这个过程，看能否让所有进程都完成

如果能找到这样的序列，系统是安全的；否则可能会死锁。

🏛️ 思想遗产与现代启示

对现代编程语言的影响

Go语言的简洁性： Go的设计哲学”少即是多”直接继承了Dijkstra的思想。故意限制特性数量，强制程序员写简洁的代码。

Rust的所有权系统： Rust的所有权和借用检查器本质上是”编译时的形式化验证”——在编译阶段就证明程序没有内存安全问题。

函数式编程的复兴： Haskell、Scala等语言强调不可变性和纯函数，部分原因是这样的代码更容易推理和验证——正是Dijkstra倡导的方向。

对软件工程实践的启示

1. 设计优先于编码 现代的敏捷开发虽然强调迭代，但优秀的实践者仍然会先做设计——这正是Dijkstra”先思考后编码”的体现。

2. 代码审查的价值 为什么要做代码审查？因为”测试无法证明没有bug”，需要人来检查设计和逻辑——这是Dijkstra教给我们的。

3. 技术债务的代价 Dijkstra会说：写烂代码很容易，但维护烂代码的代价是指数级增长的。今天”技术债务”的概念本质上就是在说这个道理。

4. 抽象与模块化 微服务、领域驱动设计、清晰架构……这些现代方法论都在践行Dijkstra的”关注点分离”。

对并发编程的持续影响

从锁到无锁： 虽然现代并发编程越来越多地使用无锁数据结构（Lock-Free），但它们的正确性分析仍然需要Dijkstra式的严格推理。

分布式系统的共识： Paxos、Raft等分布式共识算法，在精神上延续了Dijkstra对并发正确性的追求。

并发bug的调试： 为什么并发bug难调试？因为Dijkstra告诉我们，并发的本质是不确定性。现代的工具（如ThreadSanitizer）本质上是在尝试系统性地探索这种不确定性。

对算法教育的影响

算法竞赛的兴起： 今天的ACM-ICPC、LeetCode等算法竞赛和练习平台，都在训练程序员设计优雅、高效的算法——这正是Dijkstra推崇的技能。

可视化的重要性： 为什么算法课要用动画演示？因为Dijkstra说过：“我们必须让程序员看到算法的本质，而不是被实现细节淹没。”

证明的价值： 好的算法课不仅教”怎么做”，还教”为什么对”——这是Dijkstra形式化思想的教育学延伸。

🎯 实践建议：如何应用Dijkstra的思想

对初学者

1. 先在纸上设计，再写代码 在动手写代码前，先画流程图或写伪代码。强迫自己把思路理清楚。

2. 小步前进，频繁验证 不要一次写一大堆代码。写一小段，测试一下，确认正确后再继续。

3. 追求简洁 同样的功能，选择更短、更清晰的实现。记住：“简洁是可靠性的前提”。

4. 学会阅读代码 读优秀的开源项目，看看别人是如何组织代码的。好代码应该”读起来像散文”。

对专业程序员

1. 关注点分离 设计系统时，明确每个模块的职责，避免”大泥球”架构。

2. 不变式与契约 在关键函数前后写注释，说明前置条件、后置条件和不变式。这是轻量级的形式化验证。

3. 并发要谨慎 能不用并发就不用。必须用时，优先考虑高级抽象（如Actor模型、CSP），而不是直接用锁。

4. 测试是必要的，但不充分 写测试，但不要以为测试通过就万事大吉。还要做代码审查、静态分析、形式化验证（关键代码）。

对架构师

1. 分层架构 学习THE操作系统的经验，设计清晰的分层结构。下层提供基础服务，上层实现业务逻辑。

2. 接口设计 接口要简洁、正交、难以误用。好的接口让用户”掉进成功的陷阱”。

3. 可证明的设计 关键系统（支付、安全）要能推理正确性。如果做不到形式化验证，至少要做到”专家审查能看出错误”。

4. 技术选型 优先选择简单、成熟、有理论支撑的技术。避免”因为新而选择”，要”因为合适而选择”。

🧪 思考题与实践练习

基础练习

1. 重构意大利面代码 找一段充满goto或深度嵌套if-else的代码，用结构化编程原则重构它。

2. 实现Dijkstra算法 不看参考实现，自己从头实现最短路径算法。然后对比教科书的实现，看看差异在哪。

3. 生产者-消费者 用信号量实现经典的生产者-消费者模式，然后故意制造死锁，再修复它。

进阶挑战

4. 哲学家就餐问题 实现至少三种不同的解决方案，对比它们的优缺点。

5. 银行家算法模拟 实现一个资源管理系统，使用银行家算法避免死锁。

6. 形式化验证入门 选一个简单函数（如二分查找），尝试用Hoare逻辑证明它的正确性。

高级探索

7. THE系统研究 阅读THE操作系统的论文，理解它的分层设计。尝试用现代语言实现一个简化版。

8. 并发正确性分析 写一个多线程程序，用模型检查工具（如Spin）验证它的正确性。

9. 算法优雅性评估 选择一个你常用的算法，评估它的”优雅性”：是否简洁？是否易于证明？是否难以误用？

📚 推荐阅读与延伸学习

Dijkstra的经典著作

《A Discipline of Programming》（程序设计的纪律） 系统阐述了形式化程序设计的方法，包括卫式命令和最弱前条件演算。

《Selected Writings on Computing: A Personal Perspective》（计算论文选集） 精选了Dijkstra最重要的技术论文和随笔。

《Go To Statement Considered Harmful》（Go To语句有害论） 虽然只有几页，但改变了编程历史的短文。

EWD手稿集

可以在德克萨斯大学奥斯汀分校的网站上找到所有EWD手稿的扫描版。推荐几篇：

• EWD316：关于”goto有害”的完整论述
• EWD498：关于如何做研究的建议
• EWD1036：对面向对象编程的批评

相关经典教材

《算法导论》（CLRS） 第24章详细讲解了Dijkstra算法及其变体。

《操作系统概念》（恐龙书） 第5-7章讲解进程同步、死锁，大量使用Dijkstra的概念。

《程序设计语言：实践之路》 第6章讨论控制流，解释为什么结构化编程是好的。

在线资源

Dijkstra’s Writings 搜索”E.W. Dijkstra Archive”可以找到他所有手稿的数字化版本。

算法可视化 VisuAlgo等网站有Dijkstra算法的动画演示，帮助理解算法执行过程。

并发编程教程 《The Little Book of Semaphores》免费在线书籍，全面讲解信号量的各种应用。

🎓 Dijkstra的教育哲学

反对过早使用计算机

Dijkstra有一个备受争议的观点：初学者不应该过早接触计算机。

他的理由：

• 计算机会让学生养成”试错”的坏习惯，而不是先思考
• 调试器会让人忽视设计的重要性
• 编译器的错误信息会误导学生关注语法而非逻辑

争议与讨论： 这个观点在今天看来有些极端，但核心思想有价值：思考比动手重要。优秀的程序员应该能在脑子里”运行”程序，而不是依赖计算机告诉他对不对。

数学训练的重要性

Dijkstra坚信：好的程序员需要扎实的数学基础。

为什么？

• 算法分析需要数学（复杂度、正确性证明）
• 并发和分布式系统需要逻辑推理
• 数据结构的设计需要离散数学
• 形式化验证本身就是应用数学

对今天的启示： 虽然现代开发工具降低了编程门槛，但要成为顶尖程序员，数学思维仍然不可或缺。

“优雅”的标准

Dijkstra对”优雅”有明确的定义：

1. 简洁性：用最少的概念解决问题 2. 对称性：设计应该和谐、没有”特殊情况” 3. 可证明性：逻辑链条清晰，易于推理 4. 通用性：解决一类问题，而不仅仅是一个实例

实例： 为什么Dijkstra算法优雅？因为它用一个简单的贪心策略，解决了看似复杂的问题，并且可以数学证明其正确性。

🌟 Dijkstra对后世的影响

影响的程序员

Donald Knuth（高德纳，《计算机程序设计艺术》作者） 深受Dijkstra结构化编程思想影响，在《TAOCP》中大量使用形式化分析。

Niklaus Wirth（尼克劳斯·维尔特，Pascal语言设计者） Pascal语言的设计直接体现了结构化编程原则，Wirth本人多次表示受Dijkstra启发。

Tony Hoare（霍尔，快速排序发明者） 与Dijkstra合作推动Hoare逻辑，共同开创程序验证领域。

Leslie Lamport（兰波特，分布式系统专家） 在分布式算法的形式化验证方面延续了Dijkstra的传统。

学术遗产

结构化编程运动 1960-1970年代的编程革命，彻底改变了软件开发方式。

程序验证学科 虽然工业应用有限，但在关键系统（航空、医疗、核能）中越来越重要。

算法工程 把算法从”数学游戏”变成”工程工具”，Dijkstra功不可没。

并发理论 从信号量到进程代数，Dijkstra开创的并发理论仍在发展。

文化影响

“Considered Harmful”短语 Dijkstra的《Go To Statement Considered Harmful》开创了一种论文标题风格，后来出现了无数”XX Considered Harmful”的文章。

完美主义文化 Dijkstra对代码质量的极致追求，影响了整个程序员文化。虽然有时被批评过于理想化，但提高了行业标准。

手写的艺术 虽然EWD手稿的形式在数字时代看起来过时，但它们提醒我们：慢下来、深度思考、精心打磨思想。

🔮 如果Dijkstra看到今天的软件世界

他会赞赏什么

静态类型的复兴 TypeScript、Rust、Kotlin等语言的流行说明行业在重视类型安全——这是轻量级的形式化验证。

函数式编程的主流化 不可变性、纯函数、高阶函数——这些让程序更容易推理的特性正在被广泛采纳。

代码审查文化 GitHub的Pull Request、代码审查工具的普及——说明行业认识到”测试不够”。

形式化方法在关键领域的应用 AWS用TLA+验证分布式算法，航空软件用形式化方法——Dijkstra会欣慰地看到他的理念在关键系统中开花结果。

他会批评什么

JavaScript的混乱 动态类型、隐式转换、各种奇怪的行为——Dijkstra大概会写一篇”JavaScript Considered Harmful”。

过度的抽象层 现代软件栈层层叠叠（框架套框架），很多程序员不理解底层——这违背了”理解你所用的工具”的原则。

“快速迭代”的过度解读 如果”快速迭代”变成”草率编码+频繁修bug”，Dijkstra会说这是在浪费时间。

技术债务的常态化 “先上线再重构”如果成为常态而非例外，软件质量会螺旋下降。

他会好奇什么

大规模分布式系统 数百万台机器协同工作——并发复杂性达到了Dijkstra时代难以想象的规模。他会好奇如何保证正确性。

机器学习的”黑盒” 深度学习系统无法像传统程序那样推理——这对Dijkstra的形式化世界观是个挑战。他会问：如何验证AI系统的正确性？

开源运动 全世界程序员协作开发复杂软件——这种大规模协作在他的时代是不可想象的。

💬 虚构的Dijkstra访谈

问：您如何看待现代程序员对框架的依赖？

答：框架本身不是问题，问题是程序员不理解框架做了什么。如果你用了一个框架，但不知道它的抽象边界在哪里、失败模式是什么，那你就不是在工程，而是在碰运气。好的程序员应该知道何时使用框架，何时从头构建。

问：您怎么看敏捷开发？

答：如果”敏捷”意味着频繁交付价值、快速响应变化，我赞成。但如果它变成”不做设计、边写边改”的借口，那就是灾难。好的设计不是一次完成的，但这不意味着可以不做设计。迭代应该是”设计-实现-反馈-改进设计”的循环，而不是”写烂代码-修bug”的循环。

问：如何平衡”完美设计”和”按时交付”？

答：这是个假问题。真正好的设计往往更快，因为它避免了返工。当然，有时你需要做权衡，但要明确这是权衡，而不是说”没时间做好”。如果你总是”没时间做好”，说明你的流程有问题。

问：您对年轻程序员有什么建议？

答：第一，学好数学。第二，阅读经典代码和论文，站在巨人的肩膀上。第三，追求优雅，不要满足于”能跑”。第四，思考比编码重要——如果你发现自己一整天都在写代码而没有思考，停下来，重新审视你在做什么。

🎯 总结：Dijkstra留给我们的遗产

Edsger W. Dijkstra不仅仅是一位杰出的计算机科学家，更是一位深刻的思想家。他用数学的严谨、哲学的深度和工程的务实，重塑了软件开发的范式。

技术遗产

• 结构化编程：让代码从”迷宫”变成了”花园”
• 经典算法：从最短路径到银行家算法，经久不衰
• 并发理论：信号量和PV原语成为操作系统基石
• 形式化方法：虽然未能普及，但在关键领域不可或缺

思想遗产

• 简洁性原则：少即是多，优雅即是力量
• 关注点分离：复杂性管理的核心策略
• 正确性优先：测试不够，需要推理和证明
• 思考先于行动：编程是脑力活动，不是体力劳动

对今天的意义

在快节奏的现代软件开发中，Dijkstra的思想提醒我们：

• 慢下来思考比快速试错更高效
• 简洁的设计比复杂的实现更可靠
• 理解原理比记住语法更重要
• 追求优雅不是奢侈，而是必需

最后一句话：Dijkstra教会我们，编程不仅是让计算机做事，更是一种智力活动的艺术。真正的程序员不是”代码工人”，而是”思想工程师”。

---

附记：本文力求全面展现Dijkstra的贡献与思想，但篇幅所限，仍有许多细节未能涵盖。建议读者查阅EWD手稿原文，那里有更多宝藏等待发掘。正如Dijkstra所说：“我们应该像数学家一样思考，像工程师一样行动，像艺术家一样创造。”

❓ 常见问题解答

Q1: Dijkstra算法能处理负权边吗？

答：不能。这是Dijkstra算法的一个重要限制。

原因：算法的核心假设是”一旦确定了到某个节点的最短路径，就不会再更新”。但如果存在负权边，可能通过一个”更远”的节点和负权边，得到更短的路径。

解决方案：

• 如果有负权边但没有负权环，使用Bellman-Ford算法
• 如果需要所有节点对之间的最短路径，使用Floyd-Warshall算法

Q2: 结构化编程是否意味着完全不能用goto？

答：不是绝对的，而是原则性的。

Dijkstra的真实观点：他反对的是”任意使用goto”，而不是”在所有情况下都禁止goto”。在某些底层代码、错误处理、性能关键代码中，goto可能是最清晰的选择。

关键是：

• goto应该是例外，不是常态
• 如果用goto，应该只向前跳转（不回跳）
• goto的目标应该靠近使用点，不要跨越大范围
• 现代语言提供的break、continue、return往往可以替代goto

Q3: 信号量、互斥锁、条件变量有什么区别？

答：它们是不同层次的抽象。

信号量（Semaphore）：

• 最基础的同步原语
• 可以用来实现互斥锁和条件变量
• 计数信号量可以管理多个资源

互斥锁（Mutex）：

• 二元信号量的特化
• 专门用于保护临界区
• 通常有”所有权”概念（谁加锁谁解锁）

条件变量（Condition Variable）：

• 用于线程间等待某个条件
• 必须配合互斥锁使用
• 提供wait和signal/broadcast操作

实践建议：优先使用高级抽象（互斥锁、条件变量），只在需要特殊语义时才直接使用信号量。

Q4: 如何判断一段代码是否”优雅”？

答：Dijkstra给出的标准可以归纳为：

1. 简洁性测试

• 能否用更少的行数表达同样的逻辑？
• 是否有重复的代码可以提取？
• 是否引入了不必要的概念？

2. 对称性测试

• 设计是否和谐？有没有太多”特殊情况”？
• 各部分的复杂度是否平衡？

3. 可读性测试

• 不看注释能否理解代码意图？
• 变量和函数名是否表意清晰？
• 控制流是否容易追踪？

4. 可证明性测试

• 能否在脑子里”执行”代码？
• 边界条件是否明确？
• 不变式是否清晰？

实用技巧：如果你需要写很长的注释来解释代码，通常说明代码本身不够清晰。好的代码应该”自解释”。

Q5: THE操作系统的分层思想在现代有什么应用？

答：分层思想无处不在，几个例子：

网络协议栈：

• 物理层、数据链路层、网络层、传输层、应用层
• 每层只关心自己的职责
• 下层为上层提供服务

现代操作系统：

• 硬件抽象层（HAL）
• 内核层
• 系统服务层
• 应用层

企业应用架构：

• 数据访问层
• 业务逻辑层
• 表示层
• 前端层

微服务架构：

• 基础设施层（容器、网络）
• 平台服务层（服务发现、配置管理）
• 业务服务层
• API网关层

核心原则始终是：下层不依赖上层，每层职责单一，接口清晰。

Q6: 形式化验证真的有实用价值吗？

答：在关键系统中，价值巨大。

成功案例：

航空航天：

• 空客A380的飞控软件部分使用形式化方法验证
• NASA的航天器控制系统越来越多地采用形式化验证

操作系统：

• seL4微内核——世界上第一个经过完全形式化验证的操作系统内核

分布式系统：

• AWS使用TLA+验证S3、DynamoDB等系统的关键算法
• 发现了多个难以通过测试发现的bug

编译器：

• CompCert——经过形式化验证的C编译器
• 保证编译不会引入bug

为什么不普及：

• 成本高：需要专业知识和大量时间
• 工具不成熟：易用性还不够好
• ROI不明显：对普通应用，测试够用了

趋势：随着工具改进和关键系统增多，形式化方法的应用会逐渐扩大。

Q7: 如何在敏捷开发中应用Dijkstra的思想？

答：关键是理解”敏捷”和”严谨”不矛盾。

设计优先：

• 每个sprint开始前，做充分的设计讨论
• 用白板、图表把设计想清楚再动手
• 这不违背敏捷，反而让开发更快

增量式严谨：

• 第一个版本可以简单，但要”正确”
• 每次迭代都要保持代码质量，不积累技术债
• 重构应该是日常工作，不是”以后再说”

自动化验证：

• 单元测试、集成测试、静态分析
• CI/CD流水线自动检查代码质量
• 用工具辅助人的推理

代码审查：

• 每个PR都要有人审查
• 审查不仅看功能，还看设计
• 养成”解释你的设计决策”的习惯

记住：Dijkstra反对的是”草率编码”，不是”快速迭代”。好的设计让迭代更快，而不是更慢。

Q8: 为什么Dijkstra反对面向对象编程？

答：他并非反对OOP本身，而是反对某些实践。

他的批评主要针对：

过度的复杂性：

• 深层次的继承树难以理解和维护
• “万物皆对象”导致不必要的抽象

封装的滥用：

• 把简单的数据结构包装成复杂的类
• getter/setter方法泛滥，没有实质性封装

命名问题：

• 类名、方法名过于冗长
• 为了”看起来像现实世界”牺牲简洁性

他会赞成的OOP实践：

• 使用接口定义契约
• 多态来实现关注点分离
• 组合优于继承
• 不可变对象

现代的共识：函数式编程和简洁的OOP结合，往往是最好的选择。Rust、Kotlin、Swift等语言正是这样设计的。

Q9: 如何培养”先思考再编码”的习惯？

答：这需要刻意练习。

具体方法：

1. 纸上设计 每次写代码前，花10分钟在纸上画出：

• 数据结构的图示
• 算法的流程图
• 主要函数的签名和职责

2. 橡皮鸭调试的反向应用 在写代码前，向橡皮鸭（或同事）解释你打算怎么做。如果解释得磕磕巴巴，说明还没想清楚。

3. 写伪代码 用接近自然语言的伪代码先把逻辑写出来，确认逻辑正确后再翻译成真实代码。

4. 限制编码时间 给自己设定”思考时间”和”编码时间”。比如：思考20分钟，编码40分钟。强迫自己在思考时间不碰键盘。

5. 代码审查前的自我审查 提交PR前，自己先完整读一遍代码。问自己：这是我能写出的最简洁的版本吗？

6. 学习数学证明 做一些数学证明题（不一定很难），培养”逻辑推导”的思维习惯。

长期效果：几个月后，你会发现写代码更快了（因为返工少了），bug更少了，代码更清晰了。

Q10: Dijkstra对当代大学计算机教育有什么启示？

答：他的教育理念在今天仍然适用。

核心课程的重要性：

• 数据结构与算法：不仅要会用，还要会分析
• 离散数学：逻辑、集合、图论是基础
• 操作系统：理解并发、资源管理的本质
• 编译原理：理解语言的抽象层次

动手与思考的平衡：

• 不能只看PPT，要写代码
• 但也不能只写代码，要理解原理
• 最好是”先想后做，边做边思考”

形式化思维的培养：

• 要求学生写出算法的不变式
• 分析算法的时间和空间复杂度
• 证明简单算法的正确性

代码质量的强调：

• 作业不仅看”能不能跑”，还要看”写得好不好”
• 引入代码审查环节
• 教学生欣赏”优雅的代码”

长远视角：

• 不仅教当前流行的技术，更要教”不变的原理”
• 算法、数据结构、并发、抽象——这些十年后仍然重要
• 特定的框架会过时，但思维方式不会

Dijkstra会说：好的计算机教育应该让学生”学会学习”，而不仅是”学会特定技术”。

🎁 彩蛋：Dijkstra的”珍珠”语录

“优雅并非可有可无的奢侈品，而是决定成功与失败的因素。”

这句话适用于代码、设计、论文、演讲——任何需要与人沟通的智力产物。

“问题的困难程度往往与解决方案的复杂度成反比。”

最难的问题往往有最简洁的解决方案，就像E=mc²一样。

“如果调试是消除bug的过程，那么编程就是引入bug的过程。”

这是一句幽默的讽刺，提醒我们要在设计阶段就避免bug，而不是依赖调试。

“简化的艺术，就是知道忽略什么。”

抽象的本质是忽略不重要的细节，强调重要的本质。

“我们能做的工作量远少于我们想象，因此选择做什么比如何做更重要。”

这是关于优先级的深刻洞察——与其把所有事做到60分，不如把重要的事做到100分。

“计算机是一种极其愚蠢的机器，但编程让我们假装它很聪明。”

这句话提醒我们，所有的”智能”都来自程序员的设计，而不是机器本身。

“我不喜欢’软件工程’这个词，因为它暗示编程是体力劳动。”

Dijkstra坚持认为编程首先是智力活动，其次才是工程实践。

“好的程序员会问’我能让这个多简单’，而不是’我能让这个多复杂’。”

复杂性是敌人，简洁性是朋友。任何人都能把事情搞复杂，只有大师能把复杂的事情简化。

🏁 结语：继承Dijkstra的衣钵

Edsger W. Dijkstra留给我们的不仅是具体的算法和理论，更是一种思维方式和价值观：

追求优雅：不满足于”能用”，要追求”美”。
重视思考：编程是脑力劳动，不是体力劳动。
强调简洁：复杂性是敌人，简洁性是力量。
坚持严谨：测试不够，要能推理正确性。

在这个快节奏、充满诱惑的软件世界中，Dijkstra的思想就像一座灯塔，提醒我们什么是真正重要的。我们不需要成为Dijkstra那样的完美主义者，但可以学习他的精神：在追求速度的同时，不忘记质量；在拥抱新技术的同时，不忘记基本原理。

最后的最后：下次当你准备直接开始写代码时，停下来，问自己一个问题——“Dijkstra会怎么做？“也许答案就是：先在纸上想清楚，再让手指碰键盘。

愿我们都能写出Dijkstra会点头赞许的代码。