ARTICLE DETAIL

资讯详情

深耕网站建设与运营推广的一线实战洞察。

托尼·霍尔逝世:从快速排序到“十亿美元错误”null的前世今生

托尼·霍尔逝世:从快速排序到“十亿美元错误”null的前世今生 又一位计算机界的大师离开了我们。2025年1月11日托尼·霍尔Tony Hoare去世享年90岁。如果你平时主要写业务代码可能对这个名字有点陌生但你手头任何一个Java、C#、C项目几乎每天都在和他的某个“发明”打交道——就是那个在日志里出现过千百遍的NullPointerException。没错null引用就是他提出的。他后来在一场知名演讲里公开道歉管这叫“十亿美元的错误”。干我们这行的谁没被这玩意儿坑过所以这篇不是正经讣告而是一个普通程序员借这个机会聊聊我眼中的托尼·霍尔聊聊null的前世今生也顺手整理一下这些年踩过和见过的null的坑。1. 托尼·霍尔其人从古典学转向代码世界1.1 文科起步半路出家做编程托尼·霍尔1934年出生年轻时读的是古典学主修拉丁语和希腊语。按照今天的说法他是个不折不扣的“文科生”。那个年代学古典学的人毕业后大多去教书、做研究跟计算机八竿子打不着。但他后来因为机缘巧合转向了统计学在进修期间第一次见到了计算机从此一头扎进编程和程序设计语言的研究中。这段经历挺有意思。古典学的训练让他对“精确表达”有近乎苛刻的追求拉丁语和希腊语的语法复杂、逻辑严密一句话里动词变位、名词变格都得严丝合缝。这种训练直接影响了他后来做编程语言设计的风格——语言要语义干净、要能推理、要尽量简单。后来他设计CSP、提出霍尔逻辑、坚持用断言验证程序本质上都是在追求“用严谨的符号系统描述真实行为”。他转行的路径也印证了计算机科学的一个特点很多奠基人根本不是科班出身。图灵是数学出身迪杰斯特拉是理论物理出身霍尔是古典学出身。这个领域的门槛从来不是专业名头而是你有没有能力把一个抽象问题想透彻。1.2 快速排序一个递归的顿悟托尼·霍尔最广为人知的算法贡献是快速排序Quicksort。1960年代初他在做程序翻译相关的工作被一个用ALGOL写成、逻辑绕来绕去的程序折磨得头疼由此开始痴迷于递归的思想。有一天他意识到如果让数组自己递归地把元素分成“小于基准”和“大于基准”两部分排序就可以非常优雅地完成。这就是Quicksort的雏形。快速排序的思路其实不复杂。每轮先挑一个基准值把所有比它小的放左边、比它大的放右边然后对左右两个子数组继续做同样的事直到整个数组有序。平均时间复杂度是O(n log n)最坏情况下退化成O(n²)但实际运行时表现得相当好至今仍是许多标准库排序引擎的默认选择。我上大学第一次看到这段算法时最大的感受是“这也太简单了为什么我没想到”。但这种简单恰恰是天才的体现。Hoare后来自己也说快速排序是他在做机器翻译时为了处理词典里大量单词而临时想出来的方法没想到一用就是六十多年。今天随便一个电商系统的商品列表排序、搜索引擎的结果排序底层都可能有快速排序的影子。1.3 图灵奖和爵士头衔1980年他因为对编程语言定义与设计、数据结构、算法分析方面的基础性贡献获得了图灵奖。后来又在2000年被授予爵士头衔。图灵奖常被称为“计算机界的诺贝尔奖”托尼·霍尔拿到它的时候职业生涯还远没结束。他后来的研究重心转向并发计算、程序验证、分布式系统这些领域的教科书里他的名字反复出现。2. null的诞生一次“十亿美元的错误”2.1 1965年为什么偏偏要发明nullnull是霍尔在1965年设计ALGOL W语言时引入的。当时他需要设计一套类型系统用来管理内存中的“引用”。引用本质上是一个指向对象的指针但世界上的逻辑并不总是“引用一定要指向某个对象”。有的变量还没赋值有的查询没有结果有的对象确实不存在。为了让编译器能统一处理这些情况他加了一个特殊值让任何引用类型都能表示“不指向任何东西”的状态。这个值就是null。在1960年代这个设计不算奇怪。当时C语言的用户都还在为野指针发愁内存管理全靠程序员自觉。null至少给了一个统一的出口如果你访问了一个为null的引用程序崩溃但你至少知道是自己忘了检查。关键是从理论上看它在类型系统里开了一个后门——所有引用类型都默认可以是null编译器没法阻止你“对null做解引用”。2009年霍尔在一场QCon技术会议上公开承认他把自己发明null并允许在任何地方自由使用这件事称为“十亿美元的错误”因为从1965年到现在无数系统因为空引用崩溃、被攻破、产生逻辑漏洞直接或间接造成的损失难以估算。他当时还幽默地说光是把“空引用”这个概念从所有语言里抹掉省下来的钱就能建一座大桥。2.2 “十亿美元的错误”到底错在哪很多人不理解null无非就是一个“空”的哨兵值怎么就到了“十亿美元错误”的地步我个人的理解是它的核心问题不在“允许空值”而在于“所有引用类型都被默认允许为空但类型系统对此毫无约束”。这句话换个说法想象一栋楼的门上写着“每扇门都可能没有门”但你敲门前系统完全不提醒你。你必须亲手去推每一扇门发现推不开才知道这扇门不存在。代码世界里的每个对象引用都可能是null但你编译时看不到任何提示只能在运行时被NPE砸一脸。更麻烦的是null在工程中被赋予了太多含义。它可能表示“尚未初始化”也可能表示“查询无结果”还可能表示“异常被吞掉了什么都没有”。语义模糊带来的后果是你在排查问题时根本不知道这个null是从哪里冒出来的更不知道业务上应该怎么处理它。我见过太多代码getX()返回null时上层直接转发给下游下游再转发给另一个服务最后所有人在一场连环空指针事故里互相甩锅。2.3 null也不是全无可取之处说到这里也别急着把null一棒子打死。它至少有两个优点一是省内存一个null引用通常就是一个机器字二是表示“缺失”非常方便尤其在业务系统里我就是要区分“没填手机号”和“手机号为空字符串”null提供了语义上的区分能力。现代语言并没有真的“消灭null”而是把它“关进笼子里”。要么把它变成显式的类型让编译器强制你处理要么提供语法糖让你在代码里声明哪些地方允许为空、哪些地方不允许。后面这一节我展开讲讲目前最主流的几种“关null”方案顺便聊聊一个经常被忽视的角落数据库排序里的NULL。3. 现代语言怎么“填坑”从Optional到Result3.1 Optional和Maybe让“有可能没有”变成类型的一部分Java 8引入了OptionalHaskell有MaybeScala有Option。这些类型的思想是一致的用一个容器把“可能有值”和“没有值”包起来你没法绕过这个容器直接操作内部的值必须先用map、flatMap、orElse之类的方法处理“空”的情况。举个Java的例子。以前我们经常写这样的代码User user userRepository.findById(id); String name user.getName(); // 如果user是null这里就炸了用Optional改一下OptionalUser user userRepository.findById(id); String name user.map(User::getName) .orElse(unknown);你发现关键变化了吗userRepository.findById(id)返回的是一个Optional调用方没法直接“拿到内部的User”。你必须先告诉程序如果里面有值怎么取name如果没值用什么兜底。这种设计把NULL检查从“程序员自觉”变成了“编译器强制”。我在团队里推广Optional时踩过不少坑。最大的问题是很多人把Optional仓库返回以后还是习惯先isPresent()再get()写出来的代码又臭又长还被同事吐槽“Optional嵌套地狱”。后来我定的规矩是方法返回值要不要用Optional在团队规范里明确连续两个isPresent()嵌套就说明设计有问题该用Mapper或者流式API化解。3.2 Kotlin、Swift和Rust对空值的不同管理方式Kotlin做得更彻底。它把“可空”和“非空”直接在类型系统里区分开来变量类型后面带问号表示这个变量允许为null不带问号编译器就保证它不可能为null。这类代码能过编译基本说明你在类型层面把空值问题处理干净了。var nickname: String? null val length nickname?.length ?: 0Swift的设计也很像Optional本质上是一个枚举有.some和.none两种状态语法上写成String?用guard let和if let解包。Rust更狠一点干脆没有null这个关键字用Option 表示可有可无用ResultT,E表示可能出错然后用运算符在函数间传递错误或缺失。Rust社区有一句话“Null消失了但Option无处不在。”这其实就是把“空值”从碰运气的坑变成了逻辑中必须处理的分支。我自己的体会是强制性的空值处理一开始会觉得繁琐但代码维护久了就明白那一点点繁琐换来的是一整条调用链的确定性。3.3 数据库排序里的NULLasc和desc背后有讲究聊完了编程语言再说一个日常开发里经常被忽略的坑SQL排序结果里的NULL位置。很多程序员写ORDER BY时根本没想过NULL应该排在前还是后结果不同数据库的默认行为不同线上环境换了个数据库排序结果就变样了。MySQL的默认行为是NULL按“最小值”处理所以升序排序时NULL排在最前面降序排序时NULL排在最后面。PostgreSQL的默认行为是NULL值比所有普通值都大升序排序时NULL排在最后降序时NULL排在最前。Oracle和PostgreSQL类似但不同版本也略有差异。如果业务上对NULL位置有明确要求建议不要依赖数据库默认行为而是显式声明。PostgreSQL支持NULLS FIRST和NULLS LAST可以这样写SELECT * FROM products ORDER BY price ASC NULLS LAST; SELECT * FROM products ORDER BY price DESC NULLS FIRST;MySQL不支持NULLS FIRST这种语法得用IS NULL配合排序键模拟。写SQL时把这段写好能省去很多后续排查“为什么排序不对”的麻烦。4. 应对null的实战清单那些年我踩过的坑4.1 最常见的崩溃NPE和NullReferenceException我最开始写Java时几乎每天都要在日志里看到NullPointerException。最常见的原因有三类第一类是方法返回了null调用方没检查就继续调方法。比如查字典发现没有这个用户getUser()直接返回null然后你紧接着去调user.getOrders()。第二类是集合操作比如Map里get一个不存在的key返回null然后代码直接对它做一堆操作。第三类是Java 8之前的流式写法退化成for循环后从集合里取出的元素可能是null。排查NPE有个小技巧先看异常堆栈里最上面那行确定是哪一行代码触发了异常再看这一行的对象引用是从哪来的逐层往前推。这个“从异常点反向追源码”的过程新手可能觉得枯燥但经验多了以后你一眼就能看出NPE高发的“毒区”通常集中在链式调用里。4.2 框架注入为nullRedis、过滤器这些老朋友Spring Boot项目里有个经典问题在Servlet Filter过滤器或者Spring的HandlerInterceptor里直接Autowired一个RedisTemplate结果运行的时候发现它是null。原因很简单Servlet Filter的生命周期由Servlet容器管理不在Spring容器的管辖范围内。Filter被实例化时Spring的依赖注入还没执行你注入的bean自然拿不到。我当时的解决办法是在Filter的init()方法里手动从Spring容器拿Bean或者在配置类里把Filter声明成Bean交给Spring管理。如果你用的是Spring Boot更推荐的方法是注入ApplicationContext然后在业务代码里按类型或名字取出Bean。另外一个和null强弱相关的框架坑是报错信息里直接写“error adding module to project: null”。这个问题在若依这类基于Maven的项目里比较常见通常不是真正的“null”错误而是Maven在解析模块依赖时抛出的异常信息被工具层格式化成了null。排查思路是先看完整maven日志确认具体是哪个依赖下载失败再检查parent版本、仓库配置和settings.xml里的镜像源。当年我被这个报错坑了半个下午最后发现是本地Maven仓库里一个jar包损坏了删掉重下就好了。4.3 JSON里的null和API返回的nullJava项目里用Jackson处理JSON时有一个长期存在的分歧序列化时字段值为null到底是要输出还是要省略Jackson默认输出null字段但返回给前端的JSON里如果包含大量null接口文档写得又不清楚前端就很痛苦。我见过一个后端接口正常返回长这样{ code: 5, message: login required, data: null }如果不看文档第一次接的人很容易直接data.list走人前端就白屏。后来我们在团队里统一了接口规范data字段只在有数据时是有意义对象列表无数据返回空数组而不是null单个对象不存在时可以用null但要告诉前端。处理JSON反序列化时也要小心有些字段在JSON里是null直接用模型类接收后它会覆盖掉对象里原本的默认值。如果这个字段被用来做一些全局配置一个null就能让逻辑走向完全不同的分支。我建议在服务端使用DTO时明确区分“字段缺失”和“字段显式传了null”这个区分看起来很细但线上事故往往就出在这种细节上。4.4 小程序和网关报错里的“null”信号还有一个玄学场景报错信息里全是null但真正的锅根本不在null只是个信号。比如微信小程序里做WebSocket连接时偶尔会报“handshake failed due to invalid upgrade header: null”。这个名字看起来是“头为null”其实是WebSocket握手时客户端没收到正确的Upgrade响应头可能是nginx反向代理没有配置Upgrade和Connection。解决方法是把这两行配置补上。密码学和字符串转换场景也有类似问题。举个例子某些地方用EC参数的时候直接调用参数表去取SM2曲线的P256参数如果返回了null大概率不是“数据为空”而是这个曲线实例没有被注册进来或者名称拼写大小写不对。遇到这种null第一时间应该去看API文档里支持哪些参数名而不是在业务代码里疯狂判空。null经常只是一个“表象”真正的线索在“为什么它是null”。4.5 空值常见问题速查表我把日常开发里常见的null问题整理了一个速查表方便直接对照排查问题场景常见原因建议处理方式Java NPE方法返回null后继续调用接口返回Optional或使用Nullable注解尽早fail-fastFilter注入Bean为nullFilter生命周期不在Spring容器中通过ApplicationContext手动获取BeanMaven error null依赖解析失败或本地仓库损坏查看完整日志重下依赖或清仓库JSON中data为null接口未约定空值语义明确接口规范列表用空数组对象缺省用nullSQL排序结果不对数据库对NULL默认位置不同显式使用NULLS FIRST/LASTWebSocket握手失败提醒nullnginx未传Upgrade头配置proxy_set_header Upgrade/ConnectionPHP数组访问null元素查询结果为空后直接下标访问先判空再访问或用??运算符密码学API返回null曲线或算法名称不被支持校验参数拼写打印支持的参数列表这张表不一定覆盖所有场景但每次遇到空指针异常先不要急着加if(x ! null)而是停下来问一句这个空值是合理业务状态还是系统异常这两种情况的处理方式完全不同。合理业务状态要设计默认值系统异常要尽早抛出让排查的人能一眼看到。5. 除了null我们还要记住他什么5.1 霍尔逻辑用断言证明程序如果说快速排序是算法的明珠霍尔逻辑就是程序验证的基石。他提出用三元组来描述程序行为{P} C {Q}P是前置条件C是一段程序Q是后置条件。它表达的意思是如果程序执行前满足P并且C能正常终止那么执行后一定满足Q。这个看起来简单的表达式把“程序正确性”从玄学变成了数学证明的一部分。举个例子你写了一个求绝对值的函数{ x是整数 } abs(x) { 结果 0 }前置条件是“入参是整数”后置条件是“返回值大于等于0”。如果代码实现和这两个条件完全吻合就能证明这个函数的正确性。现代很多高质量库的开发和验证底层都离不开这套思想。虽然我们日常业务代码不可能每一步都做形式化验证但霍尔逻辑教我最重要的一个习惯是写函数之前先想清楚它的前置条件和后置条件。这个习惯能大大减少“传入null、返回null、中途炸掉”的概率。5.2 CSP并发编程理论的地基托尼·霍尔在1978年发表了《Communicating Sequential Processes》论文这套并发模型把系统看成若干独立运行的进程进程之间通过通信进行协作而不是通过共享内存。这个概念在当年的计算机界非常超前后来直接影响了Go语言中goroutine和channel的设计也影响了Erlang的Actor模型甚至微服务架构中的很多设计思想都能看到CSP的影子。我做服务端开发时对一条原则深有体会并发系统里最危险的不是进程本身出问题而是多个进程对同一份数据做操作时互相干扰。CSP倡导的“通信代替共享”其实就是从源头降低这种风险。你今天写Go的时候用channel传递数据可能没意识到这个优雅模型已经发展了四十多年。霍尔当年的贡献早就嵌在我们的日常工作方式里了。5.3 文科生的技术远见托尼·霍尔的故事让我印象最深的其实不是图灵奖也不是快速排序而是他从古典学转到计算机的那条路。那个年代没有“转码培训班”他靠的是对逻辑本身的兴趣。古典学的严谨训练让他格外在意“一个概念不能有歧义”这一点直接影响了他的语言设计哲学。今天的编程语言还在朝这个方向演进让类型系统更严格、让空值更显式、让并发更可控。从这个角度讲我们每个人每次写代码时某种程度上都在延续他留下的思考方式。与其说我们在纪念一个发明了null的人不如说我们在纪念一位反复提醒程序员“要对自己的代码负责”的先行者。结尾对我而言这更是一个做事方式的提醒我花了很长时间才理解null真正令人头疼的地方不是“为空”而是“不可预期”。如果你写代码时清晰地声明了每个变量、每个参数、每个返回值到底允不允许为空null并不会造成那么多灾难。托尼·霍尔发明null不是因为他觉得空值安全而是当时的语言设计者根本没想到类型系统的约束能力会被后来的技术挑战得这么严重。每次我遇到一个NullPointerException现在做的第一件事不是骂框架、骂调用方而是想这个null是从哪个入口漏进来的我有没有在类型或接口定义上给够约束如果大部分空指针问题都能被扼杀在“设计阶段”那我想这就是对霍尔最好的纪念。他留下的遗产不止是快速排序、霍尔逻辑和CSP更是一种“代码要精确、行为要可预期”的信念。老爷子一路走好。
返回列表