玻尔百科在编程世界里，计算机如何以及何时执行其工作，是一个会产生深远影响的基础性选择。大多数语言都是“及早”的（eager），会立即执行代码并计算值，就像厨师在开始烹饪前会备好所有食材一样。但有没有一种更高效的方式？如果程序能够智能地“拖延”，只在最后一刻才执行工作呢？这便是惰性求值（lazy evaluation）背后的核心思想。它不是一种迟缓的策略，而是一种对资源极其明智的运用方式。
本文将探索计算领域中的“惰性”。它将探讨总是预先计算所有东西所固有的低效，并引入一种能优雅处理“无限”等概念的范式。在接下来的章节中，你将对这种变革性的方法有深入的理解。第一章“原理与机制”将剖析其核心概念，从 lambda 演算中的理论基础到 thunk 和记忆化（memoization）的实践魔法。随后，“应用与跨学科联系”将展示惰性求值如何从理论走向实践，为从高效算法和无限数据结构到我们日常使用的响应式用户界面的方方面面提供动力。
想象你在厨房里，正照着食谱做菜。一个典型的、直接的厨师——我们称之为严格（strict）厨师——会从一丝不苟地准备每一种食材开始。他会切好所有蔬菜，量好所有香料，并为整顿饭准备好所有酱汁，然后才打开炉灶。这是一个安全、可预测的过程。现在，想象另一种厨师，一个惰性（lazy）的厨师。这位厨师读到食谱的第一步——“炒一个切好的洋葱”——然后他才去拿一个洋葱和一把刀。他只在工作被要求的最后一刻才动手。这便是惰性求值的精髓。
你可能熟悉的大多数编程语言都像那个严格的厨师。它们遵循一种叫做严格求值（strict evaluation）（或更正式地称为传值调用，call-by-value）的原则。当你调用一个函数时，语言首先会勤勉地将每个参数都求值到其最终值，然后才用这些值执行函数代码。
惰性求值则颠覆了这一点。它遵循一个简单而强大的规则：非到万不得已，不进行任何计算。这无关乎迟缓，而在于极致的效率。
让我们来做一个植根于编程数学核心——lambda 演算——的思想实验。假设我们有一个函数，无论输入什么，它总是返回数字 42：。现在，我们给它一个代表永不结束的计算的参数——一个我们可以称之为 的计算黑洞。完整的表达式是 。
一个严格的求值器看到这个表达式，首先会尝试计算参数 。它卡住了。它会永远运行下去，陷入一个无限循环，永远也到不了函数本身。程序发散了。而一个惰性的求值器则会先看函数。它看到函数体只是 ，变量 甚至从未被使用。“啊哈！”它想，“我根本不需要这个参数！”于是，它完全忽略了 ，并立即返回 。这就是惰性的魔力：能够绕过并完全避免不必要的工作。
计算机是如何实现这种智能的“拖延”的呢？它使用一个名为thunk的巧妙装置。当一门惰性语言看到一个它暂时不需要求值的表达式——比如一个函数的参数——它不只是忘记它。它将表达式包裹在一个小包里，一个“承诺”在需要时再计算它。这个包，即 thunk，包含了表达式本身以及它运行时所需的上下文（变量环境）。
你甚至可以在一门严格求值的语言中模拟这个想法。如果你有一个高代价的计算，与其写 expensive()，你可以写一个函数，当被调用时才执行该计算：() => expensive()。通过传递这个函数，你就延迟了工作。这是 thunk 核心思想的体现。
但惰性求值还有另一个同样重要的诀窍：记忆化（memoization）。如果你不止一次需要同一个值，会发生什么？我们的惰性厨师切好一个洋葱后，下一步就不需要再切一个新的了。他记得切好的洋葱在哪里。惰性求值器也是如此。
让我们看一个像 (\lambda x. x + x)\ \text{expensive_computation} 这样的表达式。当程序第一次需要 的值（用于 的左侧）时，它会“强制”求值包含 expensive_computation 的 thunk。计算运行，产生一个结果，然后是关键的一步：该结果在内存中替换该 thunk。之后，当程序再次需要 的值（用于 的右侧）时，它会发现计算好的值已在那里等待。高代价的工作只执行了一次。这种将延迟计算与 thunk 和记忆化结果相结合的策略，被称为传需求调用（call-by-need），它是现代惰性语言的核心。
我们可以用一种引人入胜的方式将这个过程可视化。与其把程序看作一系列线性的命令，不如把它想象成一个依赖关系图，一种流程图，其中一些节点是操作，另一些是决策。数据边连接着节点，显示了哪些计算依赖于其他计算的结果。
在严格的世界里，执行是从输入向前推进的。我们遵循控制流箭头，运行我们遇到的每一个操作。在惰性的世界里，流程是反向的；它是一个需求驱动（demand-driven）的系统。程序是从最终输出被拉动的。当一个决策节点（比如一个 if 语句）需要一个值来做出选择时，它会沿着数据边向后发送一个“需求信号”给产生该值的操作节点。只有在那时，该节点才会执行。一旦完成，它会记忆化其结果，为未来的任何需求做好准备。计算仅在需要时，由输出的需求驱动而展开。
这一切似乎是优化程序的一种绝妙方式，但当我们敢于谈论无限时，它真正变革性的力量才得以显现。
你能写一个程序来容纳所有自然数的列表吗？或者所有素数的列表？在严格求值的语言中，这是荒谬的。计算机会试图预先生成整个无限列表，耗尽所有内存和时间，永不停止。
有了惰性求值，这不仅可能，而且优雅自然。我们可以用一个简单的递归思想来定义无限的自然数列表：自然数列表是 1 后面跟着（cons）每个元素都加了 1 的自然数列表。在代码中，这可能看起来像 naturals = cons(1, map(+1, naturals))。
这看起来像一个悖论，一条衔尾蛇！但对于惰性求值器来说，这是一个完全合理的蓝图。变量 naturals 最初只是一个 thunk。当你请求第一个元素时，机器仅对 thunk 求值到足以看到它是一个 cons 单元的程度。它给你 1，并将列表的其余部分——表达式 map(+1, naturals)——作为另一个未求值的 thunk 留下。当你请求第二个元素时，它强制求值这个新的 thunk，计算 1+1 得到 2，并为余下的部分留下又一个 thunk。
在纸面上看起来像一个深度递归的过程，在机器里变成了一个简单的迭代过程。它以恒定的栈空间运行，仅在你请求时才生成元素。“无限”列表从不一次性完全存在于内存中；它只是一个有限的、已实现的部分，后面跟着一个计算其余部分的单一承诺。这是视角上的一次深刻转变。惰性求值让我们能够直接描述无限的过程和数据结构，而机器则自行解决如何以有限的方式、按需处理它们。
这种强大的机制对语言的设计产生了深远而美妙的影响。
模式匹配：当你分析一个惰性数据结构时，你会求值多少？这要看情况。一个“严格”的模式匹配，如 case x of (a,b) -> ...，必须检查 x 是否真的是一个序对，因此它会强制 x 求值到其最外层形式。但一个“惰性”模式，如 case x of ~(a,b) -> ...，则不作此要求；它乐观地假设匹配会成功，为 a 和 b 创建 thunk，这些 thunk 只有在它们自身稍后被强制求值时才会强制 x 求值。惰性不是一个肤浅的特性；它渗透到语言的语义深处。
内存与效率：惰性求值是死代码消除的终极形式。如果你写 let x = expensive_computation in 1，会为 x 创建一个 thunk，但它永远不会被强制求值，因为它的值对于产生最终结果 1 是不必要的。当 let 表达式的作用域结束时，未被强制求值的 thunk 就变成了垃圾，被内存管理器清除。高代价的计算根本就没被执行过。
代数之美：因为惰性将求值与观察如此直接地联系起来，它允许了优美的高层推理。例如，表达式 map id xs（将恒等函数映射到列表上）在观测上与 xs 本身是等价的。对于你对输出提出的任何需求（例如，“给我头部元素”，“给我第三个元素”），两个表达式都会对输入列表 xs 提出完全相同的需求序列。这使得程序员和编译器能够以数学般的确定性来推理和转换程序。
就像物理学或计算机科学中的任何强大思想一样，惰性求值也有其自身的权衡和微妙之处。要掌握它，就要理解它的边界。
副作用的混乱：如果我们拖延的计算对外部世界有影响，比如在屏幕上打印信息，会发生什么？考虑 print("A") + print("B")。+ 操作符需要其两个参数的值。一个惰性求值器，可以自由选择其内部求值顺序，可能会先强制求值左边的 thunk，打印出 "A"，然后再强制右边的 thunk，打印出 "B"。或者它也可能反过来做。结果可能是 "AB" 或 "BA"。副作用的顺序变得非确定性！这对于可靠的程序是不可接受的。现代惰性语言开创的解决方案是明确地将纯计算与有副作用的计算分开。副作用被封装在特殊的类型中，通常称为 monad，它们作为一种框架，对与世界交互的动作强制施加一个特定的、可预测的序列，同时允许代码的其余部分保持纯粹的惰性。
空间泄漏的幽灵：一个从不清理工作空间的惰性厨师最终会被半成品淹没。同样，一个惰性程序可能会在堆上累积大量未求值的 thunk。如果一个程序持有一个指向一个长惰性计算起点的引用，它可能会阻止垃圾回收器回收一长串的 thunk，即使这些 thunk 永远不会被用来产生最终输出。这被称为空间泄漏（space leak）。程序的内存使用会意外增长，不是因为它在存储有用的数据，而是因为它存储了太多未兑现的承诺。学会推理这些 thunk 的生命周期，是惰性程序员的一项关键技能。这是为驾驭无限这一概念力量所付出的实际代价。
在遍历了惰性求值的原理与机制之后，人们可能会好奇：这种优雅的“拖延”仅仅是一种理论上的奇观，一个局限于函数式编程深奥世界的聪明技巧吗？答案是响亮的“不”。惰性求值不仅是一种不同的计算方式，它是一种从根本上不同的思考计算的方式。它的影响渗透到计算机科学的广阔领域，从创建看似不可能的数据结构，到设计我们日常使用的响应迅速、数据丰富的应用程序。它是一条统一的线索，将看似无关的领域编织在一起，揭示了软件艺术中更深层次的连贯性。
现在，让我们开始一次应用之旅，看看这个简单的想法——“非到万不得已，不去做”——如何绽放成一个强大的工具，用于构建更优雅、高效和富有表现力的程序。
惰性求值最令人脑洞大开却又立竿见影的应用之一，是它定义和操作无限数据结构的能力。一台有限的机器如何能容纳一个无限的列表？它并不能。它容纳的是一个承诺——一个按需逐个生成列表的配方。
思考著名的斐波那契序列，其中每个数是前两个数的和：。在严格的、及早求值的语言中，如果你想要前一百万个斐波那契数，你必须分配一个列表并预先计算所有一百万个数。但如果你不知道需要多少个呢？
通过惰性求值，我们可以定义一个潜在无限的 fibonacci_stream。当你请求第10个数时，数据流仅计算足以满足你请求的部分。如果你之后请求第100个数，它会从上次离开的地方继续，只计算所需的新值。得益于记忆化，它已经计算过的值，比如第10个数，会直接从内存中检索，绝不会重新计算。这赋予了我们将无限序列视为具体对象的能力，可以按需从中提取值，而永远不会耗尽内存或时间。
这个想法可以达到一种深刻的优雅。我们可以用斐波那契序列本身来定义它自己，这是一种优美的受卫递归（guarded recursion），在严格求值的语言中会导致致命的无限循环。我们可以声明序列 fibStream 就是数字 ，后面跟着数字 ，再后面跟着 fibStream 与其自身的尾部（tail fibStream）相加的结果。在惰性的世界里，这个定义不是一个悖论；它是一个完全有效的蓝图。自引用被隐藏在一个“thunk”内部，一个直到需要值时才会被打破的承诺。当我们请求第三个元素时，机器查看定义：它是 fibStream 第一个元素（即 ）和 tail fibStream 第一个元素（即 ）的和。就这样，序列自我展开，用它自己的开端来创造它的未来。
惰性不仅关乎优雅，也关乎实实在在的效率。想象一下工厂的流水线。严格求值的方法就像让每个工位处理完所有批次的产品后，再把它们传给下一个工位。工位1处理1000个物品，产生一个巨大的中间库存。然后工位2处理那1000个物品，以此类推。
另一方面，惰性求值就像一个单件流系统。一个物品被送到生产线上。它经过工位1，然后立即到工位2，再到工位3，然后出厂。只有这时，下一个物品才开始它的旅程。这避免了创建庞大的中间库存。在编程中，这种技术被称为循环融合（loop fusion）或森林砍伐（deforestation）。
当你将像 map（转换每个元素）和 filter（移除某些元素）这样的操作链接在一个列表上时，一个惰性编译器可以自动将它们融合成单次遍历。它在处理下一个元素之前，会让一个元素完整地通过整个转换和决策链。这完全消除了创建中间列表的需要，节省了大量的内存和时间，尤其是在处理大型数据集时。
这种延迟工作的原则从数据结构延伸到算法设计本身。考虑判断一个非常大的数是否为素数的任务。有些测试很廉价（它是否为偶数？），而另一些则极其昂贵（比如米勒-拉宾测试，Miller-Rabin test）。惰性方法构建了一个测试管道。这个数首先面对廉价的过滤器。如果它未能通过其中任何一个——如果它能被2或3整除，或者是一个完全平方数——我们立即得到答案（合数），而昂贵的测试甚至都不会运行。昂贵的计算被包裹在一个 thunk 中，一个只有在该数通过所有初步挑战后才会被兑现的承诺。这种“惰性”的控制流确保我们永远不会在已变得不必要的工作上浪费宝贵的计算周期。
我们讨论的这些原则不仅仅隐藏在编译器中；它们是我们日常许多流畅交互体验背后的无形引擎。
你是否曾毫不费力地滚动浏览拥有数千个帖子的社交媒体信息流，或浏览一个有无数图片的相册？如果你的浏览器必须在向你展示任何东西之前加载并渲染每一项内容，那等待将是无法忍受的。相反，这些系统使用了惰性求值。应用程序创建了一个承诺列表，即 thunk 列表，每个组件对应一个 thunk。只有当一个组件即将滚动到视口中时，系统才会“强制”求值相应的 thunk，及时地渲染该组件。当它滚动出视图时，它甚至可以被垃圾回收器回收。视口充当了驱动计算的需求源，从一个潜在庞大的数据集中创造出流畅的体验。
也许最直观的例子是地理信息系统（GIS），就像我们用于导航的在线地图。当你在看世界地图时，你的设备并没有下载太字节（terabytes）的卫星图像。它只下载填充你当前屏幕所需的少数几个图块。当你平移或缩放时，它会惰性地请求你需要的新图块。这就是传需求调用（call-by-need）的实际应用。地图是一个巨大的 thunk 网格，而你的视口只强制求值了其中的一小部分。这使得在手持设备上探索行星尺度的数据集成为可能。这个例子也完美地说明了传需求调用的优越性：一个严格的系统会试图加载整个世界（然后失败），而一个传名调用（call-by-name）的系统则会浪费地在每次被不同的地图层（例如，地形、交通、标签）需要时都重新加载一个图块。传需求调用，凭借其记忆化，做得恰到好处：按需加载，仅此一次。
当然，无论是在物理学还是在计算中，都没有免费的午餐。虽然惰性是一个强大的工具，但它的天真应用可能导致一个微妙但严重的问题，即空间泄漏（space leak）。
因为一个 thunk 持有一个值的承诺，它也必须持有计算该值所需的一切。在一个惰性列表中，每个节点都持有对列表其余部分的 thunk 的引用。如果你持有一个指向一个长惰性列表最开始节点的引用——即使你已经处理了其中的数百万个元素——垃圾回收器也无法回收它的任何部分。头节点对下一个 thunk 的引用，后者又引用下一个，如此下去，形成了一条链，使整个结构都存活在内存中。
这就是拖延的代价：通过保留承诺，你可能也保留了它的整个上下文。一个在 thunk 被强制求值后会小心清除这些引用的实现可以减轻这种泄漏，用惰性模型的纯粹性换取务实的内存管理。最节省空间的办法，一个简单的迭代循环，使用恒定的内存，但失去了惰性组合的表达能力。理解这种在声明式的优雅和资源管理之间的权衡，是掌握惰性求值的关键。
一个基本原则的真正美妙之处在于，当它在意想不到的地方浮现时，能在不相连的领域之间架起桥梁。惰性求值就是这样一个原则。
其共享的、按需计算的模型非常适合复杂的依赖图。在一个自动化的证明助手（proof assistant）中，引理和定理可以表示为 thunk。检查一个顶层定理只会强制求值它直接或间接依赖的引理的 thunk。系统惰性地遍历依赖图，任何不属于该证明路径的引理都不会被浪费地检查。
这种共享计算的思想在一个简单场景中得到了生动的说明：两个代理人沿着一个表示为惰性列表的规划路线行进。第一个代理人，A代理，支付了强制求值 thunk 并具象化路径段的“计算成本”。当第二个代理人，B代理，沿着同一路径行进时，它发现工作已经完成。得益于记忆化，B代理“搭了便车”，无需额外努力即可消耗已计算好的路段。这种惰性生成、共享和垃圾回收的动态相互作用，具体地描绘了这些抽象机制是如何协同工作的 [@problem-id:3649708]。
最后，我们来到了最深刻的联系。在垃圾回收（garbage collection）的世界里，一个被称为三色标记不变量（tri-color marking invariant）的核心原则确保了回收器可以增量工作而不会丢失对活动对象的跟踪。它本质上是说，一个“已完成”（黑色）对象绝不能指向一个“未见过”（白色）对象。如果即将创建这样一个指针，一个“写屏障（write barrier）”会被触发，它将白色对象涂成灰色（“待处理”），以维持不变量。
现在，考虑一个完全不同的领域：链接器（linker），这个工具将编译后的代码片段组合成最终的可执行文件。一个现代的、惰性的链接器希望按需解析符号地址。在这里，我们可以直接映射状态：一个 finalized（已完成）的符号是黑色的，一个 in-progress（处理中）的符号是灰色的，而一个 unresolved（未解析）的符号是白色的。链接器面临着与垃圾回收器完全相同的问题：一个已完成（黑色）的符号不能被允许包含一个指向未解析（白色）符号的引用，因为这会破坏输出文件的一致性。解决方案是什么？正是相同的三色不变量。当一个黑色符号需要引用一个白色符号时，一个“解析屏障（resolution barrier）”——在原则上与垃圾回收器的写屏障相同——会将白色符号涂成灰色，并将其排入队列等待解析。确保内存安全的同一抽象规则，为正确、增量的代码生成提供了蓝图。
这是一个真正深刻思想的标志。从构建无限列表到优化算法，从渲染用户界面到链接程序，惰性求值的原则证明了它自己不仅仅是一种编程技术，而是一种基本的思维模式——这是对支撑计算科学的统一之美的证明。