path: root/content/article/compute-infinity.md

+++
title = '计算无穷'
subtitle = 'Clojure 中的惰性序列'
slug = 'compute-infinity'
tags = ['Lisp','Clojure','编程']
categories = '代码炼金术'
date = 2026-03-18 00:22:11
draft = false
toc = true
toot = 'https://akk.eltr.ac/objects/c6ff1636-d71d-4077-94c5-499b5282a388'
+++

由于计算机算法的特性之一是有穷性，一切能被计算机计算的东西都必须是能够在有限步骤内完成的，所以，计算机不能够应对无穷长的数据。

真的是这样吗？<!--more-->

## 穿针引线

在正式介绍 Clojure 这门语言如何操作无穷之前，我想先介绍两个非常好用的宏，`->` 和 `->>`，因为我会在接下来的演示代码中非常频繁地使用它们。这两个宏的名字分别叫作 thread-first 和 thread-last。它们是用来做什么的呢？

首先，在任何编程语言中（哪怕不是 Lisp），都有可能遇到连续对数据进行计算的情况，一段计算完成之后，需要把结果传递给下一段代码继续操作，一般来说需要嵌套函数。假设我们需要解析一段 Markdown 文本，而我们采取的策略是，使用一个函数解析所有的标题，使用另一个函数解析块引用，再使用一个函数解析列表，以此类推，我们可能会这样写：

```go
func parseMarkdown(raw string) string {
    return parseLists(parseBlockquotes(parseHeadings(raw)))
}
```

显然，这种代码可读性很差。大多数时候，我们可能会将某一段计算的结果存放在变量里，再把变量的值传递给下一个函数，以此提升可读性。

```go
func parseMarkdown(raw string) string {
    result1 := parseHeadings(raw)
    result2 := parseBlockquotes(result1)
    result3 := parseLists(result2)
    return result3
}
```

上面这段代码可读性就高很多了。你可能觉得这样很蠢，怎么会有人这样写解析器？没关系，就算不是解析器，也可能会出现类似结构的代码，比如一开始传入一个文件路径，读取这个路径下文件的内容，再把文件内容（假设是 JSON 字符串）解析为数据对象，再提取数据中的某个值。

这种做法看起来并不少见，所以能否简化呢？有没有办法让我们不需要把数据放进变量里，再取出来，再传给下一个参数，而是能够直接把所有的操作都串起来呢？

而且，我们知道，Lisp 语言一般遵从函数式编程范式，这种范式一般要求变量是不可变的，对赋值有着极为苛刻的要求，在 Lisp 语言里用这么多变量是不现实的，尽管能够用不太优雅的方式做到。

用 thread-first 和 thread-last 这两个宏就能解决上述问题。

```clojure
(defn parseMarkdown [raw]
  (-> raw
      parseHeadings
      parseBlockquotes
      prseLists))
```

视觉上，这很像类 Unix 系统上常用的管道（Pipes），即 `|` 符号。在输入命令行的时候，可以用 `|` 把两个命令串联起来，使 `|` 之前的命令的结果传递给之后的命令。假设你需要读取 `foo.txt` 这个文件的内容，并查找其中包含 `bar` 的行，就可以这样写。

```sh
cat foo.txt | grep bar
```

使用 `->` 可以让代码变得简洁。假如你想要读取一个 JSON 文件的内容，这个文件不大，你想直接加载到内存里并直接转换为 Clojure 的数据结构，就可以这样写：`(-> filename slurp json/read-string)`。

thread-first 和 thread-last 的区别是什么呢？刚刚我们演示的函数都只接受一个参数，而 first 或 last 指的是把上一个函数运算的结果传给下一个函数的第一个参数或最后一个参数，所以并没有体现出区别。

假设我们要操作的数据是列表，而操作这类数据的函数往往在最后一个参数的位置接收列表（比如 `(map f coll)` 的作用是对 `coll` 中的每一个元素执行 `f` 操作，然后返回一个惰性序列，`coll` 就是最后一个参数）。如果使用 thread-first，也就是 `->` 宏，列表就会作为第一个参数传入，也就是被当成函数 `f` 而非 `coll`。

箭头宏还有另外的版本，`cond->` 和 `cond->>`，这里的 `cond` 是 condition（条件），你可以根据条件判断要不要执行这条流水线里的某一环。

```clojure
(cond-> filename
        true    slurp ;; 由于条件为 true，所以总是会被执行
        json?   json/read-string ;; 如果是 json，才会被解析
        json?   :body ;; 如果是 json，才会尝试获取 body
        true    println)
```

箭头宏的用处很多，最常见的场景之一是用来处理列表，毕竟，Lisp 就是列表处理语言（List Processing）啊！

假设我们有一个装满了狗狗的向量，我们要从所有的狗狗中找出听话的好狗狗，并给好狗狗每只狗一块零食吃。[^1]

```clojure
(defn treat-good-dogs [dogs]
  (->> dogs
       (filter :good)
       (map give-treat)
       doall))
```

如果对上面的代码进行宏展开，就会得到：

```clojure
(defn treat-good-dogs [dogs]
    (doall (map give-treat (filter :good dogs))))
```

不过，为什么在最后加上 `doall` 呢？这是做什么的？

## 惰性的魔力

假设我们有无穷只狗狗，但我们的零食数量是有限的，要怎么办呢？我们当然没办法满足所有的好狗狗，在零食发放完之后就不能继续操作了。这要怎么写呢？你可能会想，需要一个整数型的变量来表示零食的数量，每发出去一块零食就减 `1`，当变量值为 `0`，就停下，终止操作。

用不着这么麻烦，我们可以直接对无穷进行操作，直接在无穷的狗狗里筛选好狗狗，再取出前 `n` 个好狗狗（`n` 为零食的数量），给他们零食就好了。

假设 `dogs` 是一个无穷的序列，也就是说用无穷无尽的狗狗们在等待着发放零食（天哪，光是写下来就觉得可爱爆了）。那么，下面这段代码会陷入无限循环吗？

```clojure
(->> dogs
     (filter :good)
     (map give-treat))
```

不会，因为 `filter` 和 `map` 返回的是惰性序列（Lazy sequence）。

简单来说，只要我们不主动读取惰性序列中的数据，相关的操作就永远不会被计算。比如 `(filter :good dogs)` 这一步，虽然写法很优雅，可以直接读作「filter good dogs」（筛选好狗狗），但 Clojure 实际上并没有真的去筛选好狗狗，而是承诺：*下次，下次一定，之后我就把这件事情办了。*

下一步 `(map give-treat ...)` 也是一样，Clojure 还没有「给每一只好狗狗一块零食」，而是做出了「我之后就会给每只好狗狗一块零食」的承诺。

这就是为什么之前我们要用到 `doall`，这个函数的效果是执行惰性序列中的所有效果。如果没有这个函数，我们就只是做出了承诺，而没有真的去执行。

当然，现在的情况是，我们得到的惰性序列是无穷长的（无穷的狗狗中好狗狗的数量自然也是无穷），当然不能 `doall`，因为这样做资源会很快被消耗光，我们没有那么多零食。在计算机系统的视角下，我们也没有那么多的内存和处理器资源可以分配。

假设我们有 `n` 个零食，我们可以这样写：

```clojure
(->> dogs
     (filter :good)
     (map give-treat)
     (take n)
     doall)
```

上面这段代码的意思是：

1. 我们有无穷的狗狗
2. 承诺之后会筛选出其中的好狗狗
3. 承诺之后会给筛选出的好狗狗零食吃
4. 取出前 n 个承诺
5. 执行这些承诺

## 实践惰性

你可能会以为，`dogs` 为无穷长的序列只是个假设，如果真的有无穷长的序列，Clojure 也是处理不了的。

实际上 Clojure 真的可以生成无穷长的惰性序列。[range](https://clojuredocs.org/clojure.core/range) 函数一般接收一到两个参数，生成一段由连续整数组成的惰性序列，例如执行 `(range 3)` 会得到 `(0 1 2)`，执行 `(range 1 3)` 会得到 `(1 2)`。如果不传入任何参数，也就是不限定边界，就会得到一个无穷长的惰性序列。

读《Living Clojure》的时候，读到作者写了这样一句话：

> 不要运算它，否则会使你的 REPL[^2] 崩溃

于是我就这么做了。

![](https://img.eltr.ac/geedeapro/article/compute-infinity/range-in-repl.png "在 REPL 里运行 `(range)` 的后果")

Clojure 显然是陷入了每个程序员都遇到过的无限循环，这是怎么发生的？首先，我输入了 `(range)`，构造了一个无穷的惰性序列，然后 REPL 读取了这个惰性序列，并想立刻求出这个惰性序列的值，于是惰性序列中的元素就被运算了，运算之后被打印了出来，就造就了图中的局面。

我们可以优雅地从无穷里取出有限个元素，来避免无限循环。

```clojure
(take 5 (range))
;; => (0 1 2 3 4)
```

显然，我们并不会遇到规模为无穷的问题，否则就算有能力处理无穷长的惰性序列，在实际运算这个惰性序列时，也会因为陷入无限循环而无法继续执行程序。

不过，这不妨碍我们利用惰性序列优雅地处理大规模的问题。

假设有一个几万行的 JSONL 文件，也就是说有好几万条 JSON 数据被存储在这个文件里，每一行都是有效的 JSON 对象。我们知道 I/O 操作开销很大，把这么大的数据整个读取到内存里也极其消耗资源，更别提还要把 JSON 字符串解析为可以直接操作的数据结构，为了保证程序不会太低效，必须采取一些手段。

惰性序列就是很好的解决方案。

```clojure
(with-open [rdr (io/reader "very-large-file.jsonl")]
  (let [lines (line-seq rdr)] ;; line-seq 返回包含所有行的惰性序列
                              ;; 它接收的数据类型是 java.io.BufferedReader
    (count lines))) ;; 返回文件行数，但没有真的读取文件内容
```

你也可以用 `filter`、`map` 和 `reduce` 等函数直接操作惰性序列，它们接收惰性序列，返回的也是惰性序列，只要不执行 `doall` 或 `dorun`，或者用其他函数读取其中的值，它们就永远不会被计算。

如果你打算遍历这个文件的所有行，只有被遍历到的行才会被读取，余下的行仍然是惰性的。换句话说，如果你在惰性序列里寻找一个符合特定条件的元素，比如包含特定字符串的行，而符合条件的元素恰好就是第一个元素，那么整个遍历操作实际上只会读取文件的第一行。

如此优雅的操作，只需要三行代码！

这就是把一切都变成列表的好处。除了用于筛选的 `filter`、用于创建映射的 `map` 和用于累计计算所有元素的 `reduce`，还有许多可以用来操作列表的工具，比如 `remove` 可以移除列表中符合条件的元素，`flatten` 可以打平任意嵌套的列表，`into` 可以把一个列表的元素全部放进另一个列表，`partition` 可以把一个列表分割成相等长度的多个列表。

你可能还发现上面的许多函数都还涉及判断列表元素是否符合某个条件，在其他语言里你可能见过类似的做法，比如给排序函数传入一个函数作为参数，用来比较谁应该放在前、谁应该放在后，这种函数一般叫谓词函数（predicate）。

Clojure 里有很多好用的谓词函数。比如 `nil?` 可以判断一个值是 `nil` 还是不是，如果要移除列表里所有的 `nil`，就可以这样写 `(remove nil? coll)`。我也很喜欢 `complement` 谓词，它的意思是「补集」，比如 `nil?` 的补集 `(complement nil?)` 就是判断一个值不是 `nil` 的谓词，如果不是 `nil` 就返回 `true`。刚才写的 `(remove nil? coll)` 也可以写作 `(filter (complement nil?) coll)`。

你也可以用匿名函数作为谓词，写法是 `(fn [] ...)`，简便写法是 `#(...)`，在简便写法中可以使用 `%` 来表示参数，如果有多个参数，就写作  `%1` `%2`...... 上面写的用来在列表中移除 `nil` 值的函数，还可以这样写：`(filter #(not (nil? %)) coll)`。

利用好这些谓词函数和操作列表的函数来操作惰性序列，在最后才读取惰性序列中的值，就能用最简短的方式写出高性能的代码，~~虽然跑在 JVM 上性能也高不到哪里去就是了。~~

## 最后

本文是学习 Clojure 约莫一个月时间，在一个月内连连感到大脑被击穿，在人脑代码解析器过载和好奇心被狠狠满足之间反复横跳后产生的东西。

到目前为止，对 Clojure 唯一的不满就是：我写出来的东西只能编译成 `.jar` 文件，用 Java 运行环境来执行，因为这是一门运行在 Java 虚拟机上的语言。虽然能偷 Java 的库来用，但也不可避免地继承了 Java 的臃肿，比如 [weepinbell](https://codeberg.org/eltrac/weepinbell) 编译之后竟然有 170+ MB 大小，实在是太让人不爽了。

唉，美味中拌了点垃圾也将就吃吧。

![](https://img.eltr.ac/geedeapro/article/compute-infinity/racoon-philosophy.jpeg "死亡很近。吃垃圾。自由生活。")

[^1]: 假设「好狗狗」的数据结构长这样 `{:good true}`，这是 Clojure 中映射的写法，可以用关键词作为操作取出其映射的值，比如 `(:good {:good true})` 就会返回 `true`。

[^2]: REPL：Read Eval Print Loop（读取-求值-打印-循环），是与 Clojure 交互的最简单方式，基本上就是一个接收代码然后运算，再把结果打印出来的程序。