玻尔百科在编程世界中，一个简单的决定——何时计算一个值——对效率、正确性和表达能力有着深远的影响。大多数常见语言都遵循“急切”原则，立即对函数参数求值，这可能导致不必要的计算，并且无法处理某些问题，如处理无限数据。本文探讨了一种更为优雅的替代方案：传需调用，一种体现了“非绝对必要不工作”原则的“惰性”求值策略。我们将分两大部分来解析这个强大的概念。首先，在“原理与机制”中，我们将深入探讨惰性的机制，探索传需调用如何避免不必要的工作，通过记忆化共享结果，并实现对无限数据结构的使用。随后，“应用与跨学科联系”将揭示这个看似简单的思想如何在编译器优化、算法设计、大规模数据系统乃至区块链技术等领域找到强大的应用。让我们从探索计算拖延的艺术开始吧。
想象你是一位正在准备盛大宴会的厨师。你有两个选择。你可以做一个“急切”的厨師，在开始烹饪之前，为菜单上每道可能的菜肴 meticulous 准备好每一种食材。或者，你可以做一个“惰性”的厨师，只在你当前步骤需要时，才去切洋葱或取香料。急切的厨师预先做了大量工作，如果某道菜最终没有被点单，其中一些工作可能就浪费了。惰性厨师则在每一刻都只做最少量的必要工作。在计算世界里，这种在急切与惰性之间的简单选择带来了深刻而美妙的结果。这就是传需调用（call-by-need）的故事，它是编程语言求值策略中那位聪明而惰性的厨师。
任何编程语言的核心都是一种求值策略——一条规定何时以及如何计算表达式值的规则。最常见的策略是传值调用（call-by-value），见于 C++、Java 和 Python 等语言中。它就是那位急切的厨师。在函数开始工作之前，传值调用坚持要求其所有参数都必须被完全求值，得到它们的最终值。
让我们通过一个思想实验来看看这意味着什么。假设我们有一个特殊的函数，称之为 const42，它接受一个参数 x 但直接忽略它，总是返回数字 42。在 λ 演算的形式语言中，我们写作 。现在，假设我们给这个函数传入一个真正可怕的参数：一个永不停止的计算。我们称这个计算黑洞为 。一个典型的例子是一个无限调用自身的函数，写作 。
当我们要求计算机对 const42(Ω) 求值时，会发生什么？
一个传值调用求值器，由于其无法救药的急切性，会说：“等等！在我运行 const42 之前，我必须先算出它的参数 的值。” 然后它一头扎进那个黑洞，开始无限计算。它永远不会返回。整个程序都被困住了，尽管该函数甚至不需要这个参数来产生它的答案。
这正是惰性求值，特别是传需调用（call-by-need），提供了一条更优雅路径的地方。传需调用求值器是终极的拖延者。它会说：“除非我绝对必须，否则我不会去计算那个参数。” 当它看到 const42(Ω) 时，它不去求值 。相反，它直接开始执行 const42 函数。该函数的指令很简单：“返回 42。” 由于参数 x 从未被提及，求值器永远不需要查看 x 绑定的是什么。那个黑洞 从未被触及。求值器愉快地返回 42，程序终止。
这个简单的例子揭示了一个深刻的真理：通过延迟计算，惰性求值可以避免不必要的工作。而有时，那些“不必要的工作”可能是无限量的工作。它将传递参数的行为与計算參數的行为分离开来。
延迟工作是个好的开始，但这还不是全部。一个真正“聪明”的惰性策略不应只是惰性，还应避免重复自己。这就是精巧的传需调用与其更简单但更“笨”的近亲——传名调用（call-by-name）的区别所在。
传名调用是惰性的，但却是健忘的。每次需要一个参数的值时，它都从头重新计算。让我们想象一个函数 add_three_times(x)，它计算 ，我们用一个中等耗费的参数来调用它，比如 E = (1+1) + (1+1)。
一个传名调用求值器会有效地将程序重写为 ((1+1) + (1+1)) + ((1+1) + (1+1)) + ((1+1) + (1+1))。可怜的机器不得不将 E 的计算执行三次。
传需调用既惰性又聰明。它采用了一种名为 thunk 的优美机制。thunk 就像一张值的“期票”。当你向函数传递参数时，你传递的不是最终值，也不是原始表达式。你传递的是一个 thunk——一个整洁的包，其中包含了配方（待计算的表达式）和一个指示其是否已被计算的标志。
函数第一次需要 x 的值时，它会“强制”（force）这个 thunk。这会触发计算。值被计算出来。但神奇之处在于：thunk 随后会更新自身，用计算出的值替换掉配方。期票被兑换成了真金白银。这个过程被称为记忆化（memoization）。下一次函数需要 x 时，它发现值已经在那儿了。无需重新计算。它是即时可用的。对于我们的例子 add_three_times(E)，表达式 E 只被计算一次。x 的所有三次使用都共享那一次计算的结果。
这种差异不仅仅是一个小优化。它可能是一个程序在几秒内完成与运行到宇宙末日之间的区别。考虑一个函数 G(x) 计算 。如果我们嵌套这个函数，创建一个像 这样的项，传名调用策略将表现出指数级的计算增长，其成本与 成正比。相比之下，传需调用通过在每一层共享结果，将成本降低到线性级别，仅与 成正比。这是一个巨大的收益，通过“计算一次，处处共享”这一简单而优雅的原则实现。
当我们考虑一个看似不可能的任务时，传需调用的真正力量和优雅就显现出来了：在一台有限的机器上表示一个无限的数据结构。你怎么可能存储所有斐波那契数或所有素数的列表呢？
使用严格的传值调用求值，你做不到。你必须在开始使用之前就计算出所有这些数，这是一个永远不会结束的无限任务。
但有了惰性求值，无限变得可控。一个惰性列表，或称流（stream），不是一个装满预计算值的巨大容器。它是一个单一的数据单元，包含两样东西：一个值（列表的“头”）和一个 thunk（对“尾”或列表其余部分的承诺）。为了定义斐波那契数的无限流 ，我们可以使用一个奇妙的自引用定义：
F = 0 : 1 : zipWith(+) F tail(F)
这可以翻译为：“斐波那契流以 0 开始，接着是 1，然后是一个通过将 与其自身的尾部逐元素相加而创建的流。”
对一个严格求值器来说，这是一个毫无意义的悖论。要定义 ，你需要 ！但惰性求值器看不出任何问题。zipWith(+) 部分只是一个 thunk，一个未来计算的配方。它不会立即执行。
现在，如果你请求 的前五个元素，take(5, F)，求值过程会优美地展开：
0 是现成的。1。zipWith thunk 被首次强制求值。它需要计算 。但等等——多亏了共享， 结构就是我们开始时的那个！ 和 的值已经实现。它们被即时检索，求和计算完成，第三个元素就产生了。生活在一个惰性的世界里，需要我们对程序性能的思考方式进行微妙的转变。时间复杂度不再仅仅是总输入大小（比如 ）的函数。它变成了实际被需要（demanded）的输入量（我们称之为 ）的函数。如果你有一个包含十亿个数字的列表，但只请求前十个，那么所做的工作量与 10 成正比，而不是十亿。这使得一种奇妙的组合式编程风格成为可能，你可以将大型、甚至可能是無限的處理管道粘合在一起，並確信不會做任何不必要的工作。
然而，天下没有免费的午餐。惰性有时会导致一个令人惊讶的问题，称为空间泄漏（space leak）。当程序忙于“不计算”某些东西时，它必须记住它所做出的所有承诺。这些未求值的 thunk 会占用内存。如果一个程序构建了一个非常长的延迟操作链——例如，通过一个惰性的 foldl 函数对列表求和，该函数创建了一个像 (...((0 + h(1)) + h(2)) + ... + h(m)) 这样的结构——它可能会消耗大量内存来持有这些嵌套的 thunk，等待一个最终命令来对整个事物求值。这意味着，虽然惰性编程者从思考控制流中解放出来，但他们必须更加关注数据流和未求值表达式的内存占用。
到目前为止，我们一直生活在纯函数的纯净、数学领域中——这些函数，就像 2+2 一样，对于相同的输入总是给出相同的输出，并且除了返回值之外，对世界没有其他可观察的影响。当我们的优雅惰性模型与充满副作用（如打印到屏幕、写入文件或更改变量值）的混乱现实世界碰撞时，会发生什么？
答案是：事情变得复杂了。考虑表达式 print("A") + print("B")。+ 运算符是严格的；它需要两个操作数的数值才能继续。在惰性环境中，求值器有两个 thunk 需要强制求值：一个用于 print("A")，另一个用于 print("B")。它应该先强制哪一个？如果顺序没有指定，输出可能是 "AB" 或 "BA"。这种不确定性对于编写可靠的软件来说是一场噩梦。
更糟糕的是，当延迟的计算依赖于一个可以改变的值时，记忆化本身变得“不健全”（unsound）。如果我们记忆化像 s + 1 这样表达式的结果，其中 s 是一个可变变量，然后程序的其他部分改变了 s，我们记忆化的值现在就过时了。这种聪明的共享优化破坏了我们程序的正确性。
这导致了拥抱惰性的语言的一个基本原则：它们必须强制执行一个纯洁性契约（purity pact）。传需调用的惊人好处——对未使用参数的终止保证、避免重复计算以及启用无限数据结构——只有在被延迟的计算是纯粹（pure）的情况下才是安全和可预测的。
像 Haskell 这样的现实世界惰性函数式语言通过在代码的纯粹部分和不纯部分之间建立一堵墙来解决这个问题。副作用不是被禁止的，而是被隔離起來。像 I/O 这样的不纯操作被封装到特殊的数据类型中，通常称为 monads，它们充当与现实世界进行一系列交互的配方。在这个 monadic 世界内部，操作的顺序被严格执行，确保如果我们希望的话，“A”总是在“B”之前打印。在此之外，在广阔的纯代码世界中，传需调用至高无上，发挥其效率和表达优雅的全部力量。这种分离让程序员可以享受两全其美：一种有原则的方式来推理副作用，和一个用于纯计算的强大惰性引擎。
我们已经花了一些时间来理解传需调用求值机制——这个将计算延迟到最后一刻的聪明想法。你可能会认为这只是程序员的一个小技巧，是编译器编写者的一些秘闻。但事实远非如此。传需调用不仅仅是一种优化；它是一条基本原则，一种计算效率和优雅的哲学，其回响可以在各种令人惊异的领域中找到。它体现了两条非常实用的规则：非到万不得已不做工，永不做重复工。
让我们踏上一段旅程，看看这个简单的想法能带我们走多远。我们将看到它如何驯服无穷级数，使数据处理管道变得奇迹般地高效，并为庞大的、遍布全球的信息系统提供支柱。
见证惰性力量最直观的地方是在算法世界。考虑著名的斐波那契数列，其中每个数都是前两个数之和。一个计算第 个数的朴素程序可能会一遍又一遍地重新计算相同的早期值，这是一种计算上的浪费。但如果我们用惰性的方法来处理它呢？我们可以想象一个“无限”的斐波那契数流，随时供我们检查。当我们请求第 10 个数时，系统只计算到达那里所必需的内容。如果我们接着请求第 5 个数，它已经被计算过并且会立即返回。如果我们请求第 50 个数，系统会从它离开的地方继续，刚好扩展其知识以满足我们的请求。每个斐波那契数最多只计算一次。我们构建了一个潜在的无限对象，但我们只为我们实际接触到的部分付费。
这个原则延伸到更复杂的结构。想象一个优先队列，一种总是将最重要的项保持在最前面的数据结构。在许多现实世界的系统中，一个项的优先级不是一个固定的数字，而是从几个属性派生出来的——这个计算可能很昂贵。如果一个项的属性被更新，它的优先级就会改变。一个朴素的、“急切”的系统会立即重新计算优先级并重新排序队列，即使该项离队首很远。一个惰性优先队列则做得更聪明。当一个项被更新时，它只是将其旧优先级标记为“过时”并且什么也不做。计算成本被延迟了。只有当我们请求查看或移除顶部项（peek 或 pop）时，系统才费心去检查当前的领先者是否过时。如果是，它将被丢弃，其真实优先级被计算出来，然后重新插入队列，找到它的新位置。这种惰性重求值确保了工作只在可能影响可观察结果时才被执行。
惰性求值原则是许多现代函数式编程语言的基石，它促成了一种既富于表现力又异常高效的编程风格。最美的结果之一是“流融合”（stream fusion）或“去森林化”（deforestation）。假设你有一个庞大的数据集——比如说，来自一个实验的传感器读数——并且你想执行一系列转换：首先，缩放所有值（map），然后只保留那些超过某个阈值的值（filter）。急切的方法会在 map 之后创建一个全新的、巨大的列表，然后再次遍历它以创建第三个列表用于 filter 的结果。这在内存使用上非常低效。
一个惰性语言会施展一种魔法。因为在需要之前什么都不会计算，所以 filter 可以一次只向 map 请求一个项。map 产生一个缩放后的值，将其传递给 filter，filter 检查它是否满足条件。如果满足，它就被传递给最终的消费者。中间的列表从未完全形成；它们只作为一种短暂的值流存在。编译器可以将这个管道“融合”成一次单一的遍历，这在内存上是惊人地高效，允许程序员组合优雅的操作链，即使在概念上无限的数据流上也能工作。
惰性对于正确性也至关重要，特别是当计算对外部世界有影响时。想象一个“惰性日志记录”系统，其中详细的诊断消息只应在发生错误时生成。我们可以将消息生成代码打包成一个 thunk。如果没有错误发生，该 thunk 永远不会被强制求值，构建消息的成本也永远不会付出。但如果错误确实发生了，并且消息需要发送到两个地方，比如一个控制台和一个文件呢？如果我们使用简单的传名调用策略，thunk 会被强制求值两次，其中的任何副作用（比如递增一个计数器）都会发生两次，这是不正确的。传需调用及其记忆化是完美的解决方案。第一次需要消息时，thunk 被强制求值，消息被生成，结果被缓存。第二次需要时，缓存的结果被即时使用，保证了计算及其副作用最多只发生一次。
“只为你使用的付费”这一哲学在处理非终止计算时有着深远的影响。如果一个函数被传递了一个会将程序带入无限循环的参数，但函数的逻辑恰好没有使用那个参数，那么一个惰性系统将永远不会强制求值该参数的 thunk。程序成功终止，幸福地不知道它被递过一颗它从未需要拆除的计算炸弹。
当我们将其从代码行扩展到大型系统时，传需调用的真正奇迹就显现出来了。想一想数字地图应用，比如地理信息系统（GIS）。世界地图是一个巨大的数据集。一个试图一次性加载整个地球所有数据的急切方法是不可想象的。相反，这些系统从根本上是惰性的。世界是一个由瓦片组成的网格，每个瓦片都是一个 thunk——一个从服务器加载数据的承诺。当你查看地图的某个区域时，只有可见瓦片的 thunk 被强制求值。当你平移或缩放时，新的 thunk 被强制求值，它们的数据被获取和渲染。此外，如果你有多个图层（道路、卫星图像、交通），它们都可以引用同一个底层的原始瓦片 thunk。多亏了记忆化，瓦片数据从网络上只加载一次，然后被共享，即使它被用来渲染十个不同的图层。
同样模型直接适用于现代科学和数据分析工作流。一个复杂的模拟可以看作一个有向无环图（DAG），其中节点是计算阶段，边是依赖关系。一个急切的系统可能会计算所有可能的输出。然而，一个惰性的工作流引擎将每个阶段视为一个 thunk。当你请求一个最终指标时，引擎会向后追溯依赖关系，并只强制求值产生该特定结果所需的子图中的 thunk。如果你稍后请求另一个共享某些中间计算的指标，传需调用确保那些共享的阶段不会被重新运行；它们的记忆化结果被简单地重用。这在数据科学和高性能计算中节省了大量的时间和资源。
惰性求值的应用甚至超出了纯粹的性能优化，影响了计算系统的根本逻辑。在一个交互式证明助手中，数学家和计算机科学家在这里构建正确性的形式化证明，每个引理都可以表示为一个 thunk。验证一个顶层定理会强制求值它所依赖的引理的 thunk，这些 thunk 又会强制求值它们的依赖项。惰性求值过程本身就变成了对逻辑依赖图的一次遍历。更深刻的是，这种机制可以用来检测推理中的错误。如果检查引理 A 需要引理 B，而引理 B 需要引理 C，而 C 又需要引理 A，惰性求值引擎将检测到这种试图强制一个已经“正在进行中”的 thunk 的行为，并报告一个循环依赖——这是对循环逻辑的形式化检测。
也许最现代的应用之一是在区块链和分布式账本的世界里。验证区块链的状态可能极其昂贵，可能需要访问大量的历史数据。通过将交易和状态数据请求建模为 thunk，验证引擎可以惰性地操作。为了确认一个特定的事实，它只强制求值代表最小交易集合的 thunk，并获取该确认所需的最小加密证明集（如 Merkle 证明）。庞大的、全球分布的账本上的所有其他交易和状态都保持为未触及的承诺。这种惰性方法是构建可扩展和高效工具以与这些复杂的去中心化系统交互的关键。
从一个简单的斐波那契数列到全球金融账本的验证，传需调用的原则展示了一种美妙的统一性。它是一个简单、优雅的概念，一旦应用，就能产生不仅更快，而且往往更智能、更健壯、更具可扩展性的系统。它教给我们一个强有力的教训：在计算中，如同在生活中一样，不去做今天可以推迟到明天的事是极具智慧的——尤其是如果明天永远不会到来。