惰性求值、无穷流与发生的魔法

litjohn · 2025-08-09 11:14:31 · 算法·理论

前言：什么是魔法？

（注：这个前言可以跳过。它是最终成果展示。感到迷惑很正常，请先阅读正文。）

什么是魔法？

(define-syntax delay
  (syntax-rules ()
    ((delay x) (lambda () x))))

(define (lazy-variable thunk)
  (cons #f thunk))

(define (is-calculated? variable)
  (car variable))

(define (force variable)
  (if (is-calculated? variable)
    (cdr variable)
    (begin
      (set-car! variable #t)
      (set-cdr! variable ((cdr variable)))
      (cdr variable))))

(define-syntax stream-cons
  (syntax-rules ()
    ((stream-cons a b)
     (cons
       a
       (lazy-variable
         (delay b))))))

(define (stream-car x)
  (car x))

(define (stream-cdr x)
  (force (cdr x)))

(define (int-from n)
  (stream-cons
    n
    (int-from
      (+ n 1))))

(define nature-numbers (int-from 1))

真成四十行代码了。感兴趣的读者可以数一数，刚好 39 行。

然后下面还有一些有趣的小工具：

(define (get a pos)
  (if (= pos 0)
    (stream-car a)
    (get (stream-cdr a) (- pos 1))))

(define (take a len)
 (if (= len 0)
   '()
   (cons
     (stream-car a)
     (take (stream-cdr a) (- len 1)))))

这些有什么用呢？请见下文。

(define org '(1 2 3 4 5))

(define (twice a)
  (if (null? a)
    '()
    (stream-cons
      (* 2 (car a))
      (twice (cdr a)))))

(define new (twice org))

这里实现了类似于 C++ 20 std::views 库中的视窗的东西。具备类似的惰性求值特性。

更加抽象的范式。我们发现上面的具体的“将一个元素变成它的二倍”的操作其实是和整体框架的“构建一个流，每个元素是原始列表/流中对应元素经过一个变换后得到的”的语义无关的。

于是把框架提取出来，变成类似于列表的 map 的操作。

(define (transfer-to-stream operator a)
  (if (null? a)
    '()
    (stream-cons
      (operator (car a))
      (transfer-to-stream operator (cdr a)))))

(define (stream-map operator a)
  (if (null? a)
    '()
    (stream-cons
      (operator (stream-car a))
      (stream-map operator (stream-cdr a)))))

正文

好了好了炫技到此结束。如果看到这里你都能看懂的话就可以离开了，这篇文章大概不会对您这样的大佬产生什么帮助。

而如果你一头雾水也完全不要紧。正文从这里才刚刚开始。

目标 · 魔法

“一个存储着所有自然数的、无穷大的列表”。

在有着有限内存的计算机中，这是不可能达成的任务。然而，今天我们将亲手实现它。用非常少的代码。

惰性求值 · 魔法的机理

各位听说过“惰性求值”（lazy-evaluation）吗？大概的思想就是，一个变量我们不立刻算出它的值，而是把它背后的“计算”保存起来，直到要用的时候才算出它的值。以此避免不必要的计算。

举个例子：

myClass foo() {
    myClass res();
    // lots of work
    return res;
}

auto x = foo();

假设 C++ 是惰性求值的，这里程序就不会在 x 定义时立刻执行 foo() 并计算返回值。而是会到你真正使用 x 的值的时候再执行 foo() 并计算出 x 的真实值。

不过，我们熟悉的 C++ 和大多数主流语言都是严格求值/应用序求值的。并不（默认）支持这种特性。一个表达式被绑定到变量上，它立刻就被求值。函数调用时，也先对函数本身以及各个参数进行求值。比如这个函数：

int foo(int x) {
  return x * 2;
}

调用 foo(3 + 3) 时就会先求值 foo 发现它是一个函数。然后求值参数 x，发现它是 3 + 3，等于 6.函数体里面 x 的值直接就是 6.

但是某些语言是默认惰性求值的。一个著名的例子是 haskell。它们在这种地方会让 x 变成一个未完成的计算 3 + 3，直到使用了 x * 2 时才求出 x 的值是 6，并返回 6 * 2 = 12.

这是第一项前置知识。它是整个魔法的基础，我们能够创造出无穷大的列表，正是因为我们并没有创造出它！

我们只需要创造出那些我们需要使用的部分就可以了。比如说，如果我们的程序只访问了自然数列表的前十项，就只计算出这前十项。

手动实现惰性求值 · 魔法的材料

在一门严格求值的语言中，我们也是可以通过一些手法实现惰性求值机制的。

最经典的方法是利用 lambda。

我们知道，一个函数的函数体只有在调用时才会被求值。这个特性是容易理解的：函数需要知道参数以及引用的自由变量的值才能确定函数体的值。你不可能在函数定义时就准确地知道每次调用它产生的副作用和返回值。

这就产生了一个天然的惰性求值对象！我们可以用它来构建惰性求值系统。

具体地。我们知道这样的东西：

对于任意一个函数 g，定义

f:=\lambda x.(g\ x)

则有 f 和 g 等价。

从感性上，这是显然的。对于任意输入，f 和 g 的输出都一模一样。f 干的唯一一件事就是把输入扔给了 g 处理。它自己什么都没干。

在 lambda 演算的体系中，这是三条计算法则之一 η 变换。

那么，我们就可以用一层 lambda（lambda 本质上是匿名函数/函数字面量）来包裹住表达式！

这样，表达式就不会立即被求值了。而如果我们要获取表达式的值，只需要应用那个 lambda，就能得到表达式的求值结果。

lambda 的参数具体是什么不重要，因为我们只是想要创建一个延迟求值的计算或者得到被延迟的计算的值。所以，干脆就不要参数了！一个无参数的 lambda 能够最简洁清晰地达成我们的目的。

有一个术语用来描述这些：thunk。它指的是被延迟求值的计算。

下面不得不涉及到一些细节。用 C++ 来写本文的代码会非常痛苦，需要和类型系统搏斗，给代码加上大量的模板技巧……那会完全掩盖思想的优雅本质。所以本文的代码不采用 C++。

相反地，我们采用 scheme。scheme 是一门 lisp 方言，具有动态类型和函数式特性。也是一门严格求值的语言。

scheme 的代码是以“S 表达式”（符号表达式）的形式组织的。

快速了解一下 S-表达式：

核心是列表 (List)： S-表达式的基本形式是由圆括号 () 包围起来的列表。
结构：(操作符参数1 参数2 ...)： 列表中的第一个元素通常是操作符（即要应用的函数），其余元素则是传递给该操作符的参数。
原子 (Atom) 与嵌套： 列表中的元素可以是原子（如数字 123、符号 x、+），也可以是另一个 S-表达式。这种嵌套能力使得 S-表达式可以表示复杂的树状结构。

例如，表达式 (+ 1 (* 2 3)) 在 Scheme 中表示数学上的 1 + (2 * 3)。这里：

最外层的 (+ 1 (* 2 3)) 是一个 S-表达式。+ 是操作符，1 和 (* 2 3) 是它的参数。
(* 2 3) 本身也是一个 S-表达式。* 是操作符，2 和 3 是它的参数。执行它会得到 6。
所以整个表达式 (+ 1 6) 最终会计算得到 7。

你可以通过搜索、查阅文档或者询问 AI 得到 scheme 的更多信息。本文不过多赘述。

于是我们就可以理解前言的第一段，delay、force 以及 lazy-variable 是在干什么了。delay 接受一个表达式，把它用 lambda 包装起来变成一个 thunk。force 对一个惰性求值的变量求取值，得到它的真实值。

lazy-variable 是在干什么？它对 delay 给出的 thunk 进行了进一步的封装，加上了一个标志说明它是否已被求值。因为如果每次 force 取值都重新调用一遍 thunk，我们会不停地重复计算一模一样的东西，时间复杂度就寄了。

所以，我们需要记忆化。第一次对于一个惰性变量的取值会求值 thunk，之后它的值就被存储在一个普通变量里了，不需要重复计算。

force 如何区分一个惰性变量是否被求值过了？就是靠 lazy-variable 引入的那个标志位。

注意到 delay 是一个宏。因为 scheme 是应用序求值的。如果用一般的函数，参数会被先求值，就无法实现惰性求值了。

到这里，我们就在 scheme 这门严格求值的语言中手动实现了惰性求值系统。

流 · 魔法现身！

有了惰性的变量，我们自然可以定义惰性求值的数据结构！

“流”就是一个这样的惰性数据结构。具体的，它是一个列表。不过，它并不从一开始就存储着所有的数据，而是在访问时才生成真实的元素。（惰性求值特性）

流可以是无穷大的，因为它只有被访问的项才会被生成。这就是我们最开始提出的魔法。

我们如何实现一个流呢？我们发现，一个流的被计算完成的 cons 单元，它的数据域（car）就是一个普通的值。而指针域指向的，“下一项”却有可能是依然没有被生成的 thunk。

所以就有了前言中的这些：

(define-syntax stream-cons
  (syntax-rules ()
    ((stream-cons a b)
     (cons
       a
       (lazy-variable
         (delay b))))))

(define (stream-car x)
  (car x))

(define (stream-cdr x)
  (force (cdr x)))

有了这些，我们如何构造出一个具体的流呢？比如一个全部项都是 1 的无穷流？

你可能会想，一个全部都是 1 的无穷流，和它自己前面加上一个 1 是完全等价的。于是你可能会写出：

(define one
  (stream-cons 1 one))

然而这是错的。你会惊讶地发现，把上面代码中的 stream-cons 换成 cons，也能运行并且生成一个循环列表。这是 scheme 的一个特性。

所以，上面的代码并不是你想象中被延迟无穷递归的无穷流，而只是一个普通的循环列表，指针域被延迟求值了而已。

真正的实现利用的是函数被延迟的无穷递归。

(define (one)
  (stream-cons 1 (one)))

(define stream-of-one (one))

当你在这个流上遍历的时候，你会不断地触及到被延迟求值的 one 调用。而它返回 1 和另一个被延迟的 one 调用构成的 cons 单元，永无休止。这是一个无穷流。

以及，我们可以完成那个魔法了！自然数流，启动！

(define (int-from n)
  (stream-cons
    n
    (int-from
      (+ n 1))))

(define nature-numbers (int-from 1))

魔法现身之后的应用

我们需要一些操纵流的方法。我们已经有了 stream-car 和 stream-cdr 来访问它。不过还不够。

前言中的 take 和 get，一个用来取一个流的前若干项（项数不足就 RE），一个用来取一个流的第 i 项（0-base，流的第一项是第 0 项）

这些都很简单。不过下面的才是真正的重量级，也是流的实际应用。

(define (twice a)
  (if (null? a)
    '()
    (stream-cons
      (* 2 (car a))
      (twice (cdr a)))))

从一个列表创建一个流，流的每一项是原始列表对应项的两倍。

这里前言里面有介绍。

然后是 transfer-to-stream 和 stream-map。都是类似于普通列表的 map 的操作（将每个元素做给定变换，然后用变换后的元素创建并返回新的列表）。不过一个是从列表 map 到流，一个是流 map 到流。

操作的组合 · 管道

这里不得不提到另外一个概念：管道。

管道是一种高阶函数。它描述的是这样的一种东西：数据进入第一个函数，流出来变成返回值，然后继续进入第二个函数……就像水流过管道，数据流过一系列处理它的函数。

下面就是一个简单的管道实现：

(define combine
  (lambda (f g)
    (lambda x (g (apply f x)))))

(define tunnel
  (lambda list-of-params
    (let ((x (car list-of-params))
          (tmp (cdr list-of-params)))
      (if (null? tmp)
        x
        (let ((y (car tmp))
              (rest (cdr tmp)))
          (apply tunnel
            (cons
              (combine x y)
              rest)))))))

管道使得我们可以组合对一个流的不同操作，制造“数据的流水线”。

(define example
  (stream-map
    (tunnel
      (lambda (x) (* x x))
      (lambda (x) (+ x 3))
      (lambda (x) (log x 2)))
    nature-numbers))

魔法的代价：惰性与可变状态的冲突

scheme 中函数的闭包对作用域是默认按引用捕获的。也就是说，如果我包装的 thunk 在被计算之前，内部引用的自由变量被修改了或者生命周期结束，惰性求值的结果就会和严格求值不同。

一个问题发生的示例：

> (define x 10)
> (define my-lazy-value (lazy-variable (delay (* x 2))))  ; 值是 2x = 20
> (set! x 100)
> (force my-lazy-value)
200 ; something strange happened!

haskell 就没有这种问题。因为它是“纯”的，状态不会被莫名其妙地改掉。而我们上面的构建流的代码也是纯的，所以它们是安全的。

想要在可变状态中避免这种惨案的发生，我们需要一个“按值捕获”。

(define x 10)

; 使用 let 来“冻结”x 当前的值
(define my-safe-lazy-value
  (let ((frozen-x x)) ; frozen-x 是一个全新的绑定，其值为 10
    (lazy-variable
      (delay (* frozen-x 2)))))

(set! x 100)

(force my-safe-lazy-value)
; ==> 20

不过，需要注意的是，仅仅修改 delay 很难做到按值捕获。因为你无法预料哪些变量是自由的。或者你不可能先求值表达式再存储，那样惰性求值就不存在了。

我们只能手动按值捕获。

我们实现的 delay 机制，其默认行为是捕获变量的“绑定”而非“值”。这在处理可变状态时会带来非预期的结果。这并非 delay 实现的缺陷，而是 Scheme 语言设计哲学的一种体现。它要求我们，作为魔法的施法者，必须清楚地知道自己法术的边界。当需要“固化”状态时，我们必须亲手使用 let 咒语来创建一个不可变的副本，从而保证魔法效果的确定性。这种对控制权的明确要求，正是这门语言强大而迷人的一部分。

后记

到此，本文就结束了。我们成功使用惰性求值将“创建一个无穷大的列表”这样不可能的魔法化作了现实。

我们亲手实现了一种声明式的方法。流可以让我们声明并组合对于列表的种种操作，而无需手动管理中间临时列表。

代码即思想，我们描述的是“是什么”，而不是“怎么算”，将逻辑与控制分离。

（BTW，也许你会好奇用 C++ 如何作到这些。那么你可以看看这个：https://www.luogu.com.cn/article/jomps7w6，AI生成的代码，能够过编和运行，并且实现了和本文一样的功能。）