Clojure

提升 Clojure 的惰性

(注意:此页面描述了序列最后一次重大更新中所做的更改,当时 Rich 也在探索名为流的替代方案。将此页面视为这些设计决策的有用历史记录,而不是参考文档。)

在开发流的过程中,一些事情变得很明显

  • 流代码很丑陋且命令式

    • 即使变得安全,仍然很丑陋,有状态

  • 流支持完全惰性

    • 这最终变得非常好

  • 透明地集成流(即没有 map 和 map-stream 两种)需要进行更改,以放松核心序列函数(map、filter 等)的契约

    • 如果我要这样做,我能否在保持 Clojure 优美的递归风格的同时实现相同的完全惰性?

      • 同时与现有代码基本兼容

      • 是的!

        • 但是 - 最好更改一些名称

当前的 seq 模型

  • 最初建模于 Common Lisp 的 cons

  • 要么你有一个 seq,带有一个有效的 first,要么什么也没有 (nil)

  • 一个 seq 就像一个逻辑游标

  • rest 从根本上说是及时的

    • 返回另一个 seq 或 nil

    • 需要确定是否还有更多才能确定返回值是否为 nil

    • lazy-cons 可以延迟 first/rest 的计算,但不能延迟是否还有 rest 的确定

      • 确定这一点通常需要“拉动”内部 seq,降低了有效的惰性

  • 序列函数目前返回一个 seq 或 nil

rest 的及时性意味着序列函数不是完全惰性的,它们至少需要确定是否存在 first。

增强 seq 模型 - 对 seq 的第三种操作 - 'next'

  • 更改: (rest aseq) - 返回一个可能为空的 seq,绝不为 nil

    • 如果参数不是 seq,则调用 seq

    • 返回的 seq 可能为空

      • 将打印 (),但不是单个哨兵对象

    • 从不返回 nil

      • 目前在第三方 seq 上未强制执行

    • 一条(可能)延迟的路径,通往剩余的项目(如果有)

  • 更改:seq 可以为空

    • 始终为 ISeq

  • 更改seq 函数 - 不再是 ISeq 的恒等函数

    • 仍然返回 seq 或 nil

    • (seq aseq) → 不再是恒等函数,如果 aseq 为空则返回 nil

    • 仍然适用于 nil

  • first 函数没有改变

    • 如果参数不是 seq,则调用 seq

    • 返回第一个项目

    • 仍然适用于 nil

  • 新增: next 函数执行 rest 过去执行的操作

    • 返回下一个 seq(如果有),否则返回 nil

    • 如果参数不是 seq,则调用 seq

    • (next aseq) === (seq (rest aseq))

    • 适用于 nil

  • 更改:seq?

    • (seq? ()) → true

  • 更改: 序列函数 (map、filter 等) 返回 seq,但不返回 nil

    • 你需要在其返回值上调用 seq 以获得 seq/nil

      • seq 也充当结束测试,这已经是惯用法了

        (when (seq coll)
          ...)
    • 允许完全惰性

    • 不支持 nil 双关

      • 因为序列函数不再返回 seq/nil

方案 - 如何在新模型中编写惰性序列函数

  • 再见 lazy-cons,你好 lazy-seq

    • lazy-cons 消失了

    • 新的惰性宏 - lazy-seq

      • 接受一个产生 seq、nil 或任何可 seq 化内容的主体

      • 返回一个逻辑集合,通过调用主体来实现 seq

        • 仅在第一次在它上面调用 seq 时才会调用主体,并缓存结果

        • 如果主体返回值不是 seq 或 nil,则将调用 seq

    • 最终效果是创建一个虚拟集合,在调用 seq 之前不做任何工作 - 完全延迟

    • 支持所有集合操作

    • 可以为空 - 例如,在它上面调用 seq 可以返回 nil

      • 为空时将打印为 ()

  • lazy-seq 位于惰性序列函数的顶层

    • 而不是嵌套的 lazy-cons

  • 在内部,使用普通的 cons 调用

    • 在需要之前不会创建

  • 如果消费另一个 seq,请使用 rest 而不是 next

旧方法

(defn map
  ([f coll]
   (when (seq coll)
     (lazy-cons (f (first coll)) (map f (rest coll)))))
...

新方法

(defn map
  ([f coll]
   (lazy-seq
    (when-let [s (seq coll)]
      (cons (f (first s)) (map f (rest s))))))
...

注意 when-let 的使用,它获取一次 seq,以便后续在 first 和 rest 中使用,即使 first/rest 在其参数上调用 seq。在新模型中,这具有性能优势。

牺牲品 - nil 双关

CL 的 cons 使用 nil 表示列表末尾的一件好事是,当与 nil 在条件语句中的可测试性结合时,返回 cons 的函数可以用作谓词。现在只有 seqnext 可以这样使用 - map、filter 等不行。请注意,seq/nil 二元组的大部分经济性仍然适用,例如上面 map 中 when 的使用。

扩展 ISeqs

如果你正在扩展 ISeq,你需要支持 ISeq.more()(rest 的基础)。幸运的是,大多数 ISeq 扩展器都源自 ASeq,ASeq 根据 next 定义了 more()。如果你的 seq 从 ASeq 派生,不要定义 more(),使用 ASeq 提供的版本。只需将你的 rest() 方法重命名为 next()。

方案 - 移植

要迁移到新模型,你需要按照以下步骤进行操作,顺序如下

  • 将所有对 rest 的调用重命名为调用 next

  • 如果你正在定义自己的惰性序列函数,使用 lazy-cons,请使用上面的方案将它们切换到 lazy-seq。确保在递归调用中调用 rest 而不是 next

  • 审核你的代码以查找 nil 双关。惰性分支支持在调试模式下进行编译,如果尝试在条件语句中测试惰性序列的真值,则会断言,如果这样做,则会抛出异常。只需像这样构建 clojure

    • ant -Dclojure.assert-if-lazy-seq=true

    • 然后,以下 nil 双关将抛出异常

      • (when (filter neg? [1 2]) :all-pos)

      • (not (concat))

      • (if (rest (seq [])) 1 2)

    • 在所有情况下,你都可以通过用 seq 调用包装序列来修复 nil 双关

      (when (seq (filter neg? [1 2])) :all-pos)
      -> nil
    • 完成后,在不使用该标志的情况下重新构建,因为它会降低速度。

别灰心

递归定义的惰性序列函数优雅且易于理解。它们可以非常节省内存,允许你使用可能不适合内存的数据源,因为只需要当前使用的部分数据结构在内存中。有时确定哪些部分当前正在使用可能很棘手,因为它们可能仍然被局部变量引用。Clojure 在尾调用上执行局部变量清除以确保堆栈上没有残留引用,但有一个剩余的情况 - 封闭的局部变量,这很难控制,尤其是在使用像 lazy-seq 这样的宏时,它会代表你创建一个闭包。

考虑 filter 的原始、不完全惰性的定义

(defn filter
  "Returns a lazy seq of the items in coll for which
  (pred item) returns true. pred must be free of side-effects."
  [pred coll]
    (when (seq coll)
      (if (pred (first coll))
        (lazy-cons (first coll) (filter pred (rest coll)))
        (recur pred (rest coll)))))

通过递归调用自身,它有效地擦除了每次迭代的 coll 参数,因此看起来它在跳过不匹配谓词的元素时不会保留 coll。问题在于,有时对 filter 的调用位于 lazy-cons 中,它扩展为一个闭包,该闭包会闭包 coll,从而在循环发生时保留它,并且被调用函数对此无能为力。这意味着像

(filter #(= % 20) (map inc (range 10000000)))

这样的表达式可能会导致内存不足异常。避免它的唯一方法是使用变异重写 filter。太糟糕了。

新的 filter 看起来像这样

(defn filter
  "Returns a lazy sequence of the items in coll for which
  (pred item) returns true. pred must be free of side-effects."
  [pred coll]
  (let [step (fn [p c]
                 (when-let [s (seq c)]
                   (if (p (first s))
                     (cons (first s) (filter p (rest s)))
                     (recur p (rest s)))))]
    (lazy-seq (step pred coll))))

旧 filter 的主体已放入一个辅助函数中,lazy-cons 已替换为 cons,然后整个调用被包装在一个 lazy-seq 中,按照上面的方案进行操作。但是 lazy-seq 也创建了一个闭包,该闭包会闭包 coll。如果没有一些增强,这个 filter 虽然更惰性,但将与旧的具有相同的内存占用空间。新的惰性分支为此类场景包含一个编译器增强。lazy-seqdelay 都在其主体的尾调用上执行闭包的局部变量清除,确保当尾调用执行时,闭包本身中不会保留任何引用。它们可以做到这一点,因为它们会缓存结果,因此知道闭包只会调用一次。因此,惰性分支对上面的 filter 表达式没有问题,你可以使用类似的技术来控制你自己的惰性函数中的内存使用情况。