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

    • 如果 arg 不是 seq,則對其呼叫 seq

    • 傳回的 seq 可能為空

      • 將列印 (),但不會列印單一哨兵物件

    • 絕不會傳回 nil

      • 目前未在第三方 seq 上執行

    • 一條(可能)延遲的路徑,通往剩餘的項目(如果有)

  • 已變更:seq 可以為空

    • 永遠是 ISeq

  • 已變更seq 函數 - 不再是 ISeq 的身分

    • 仍然回傳 seq 或 nil

    • (seq aseq) → 不再是同一性,如果 aseq 為空則回傳 nil

    • 仍然對 nil 有效

  • first 函式不變

    • 如果 arg 不是 seq,則對其呼叫 seq

    • 回傳第一個項目

    • 仍然對 nil 有效

  • 新增: next 函式執行 rest 過去執行的動作

    • 回傳下一個 seq(如果有),否則回傳 nil

    • 如果 arg 不是 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,它使用 next 定義 more()。如果您從 ASeq 衍生您的 seq,請勿定義 more(),請使用 ASeq 提供的版本。只要將您的 rest() 方法重新命名為 next() 即可。

食譜 - 移植

要轉移到新模型,您需要按以下順序執行下列步驟

  • 將您對 rest 的所有呼叫重新命名為呼叫 next

  • 如果您使用 lazy-cons 定義自己的延遲序列函數,請使用上述食譜將它們切換到 lazy-seq。請務必在您的遞迴呼叫中呼叫 rest,而不是 next

  • 稽核您的程式碼是否有 nil-punning。延遲分支支援在偵錯模式下編譯,如果嘗試在條件式中測試延遲序列的真值,它會聲明,並且如果執行此操作,它會擲回例外。只要像這樣建置 Clojure

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

    • 然後,像以下這樣的 nil puns 會擲回例外

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

      • (not (concat))

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

    • 在所有情況下,您都可以透過使用 seq 呼叫包裝序列來修正 nil pun

      (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)))))

透過遞迴到 fn 本身,它會在每次反覆運算中有效地清除 coll 參數,因此看起來在跳過與謂詞不匹配的元素時,它不會保留 coll。問題在於,有時對 filter 的呼叫在 lazy-cons 中,它會擴充為封閉在 coll 上的封閉,因此在迴圈發生時保留它,而且被呼叫的函數對此無能為力。這表示像這樣的表示式

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

可能會導致記憶體不足的例外狀況。避免這種狀況的唯一方法是使用突變重寫篩選器。真討厭。

新的篩選器如下所示

(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))))

舊篩選器的本體已放入輔助函數中,並將 lazy-cons 替換為 cons,然後將整個呼叫包裝在 lazy-seq 中,遵循上述配方。但是 lazy-seq 也會建立一個封閉在 coll 上的封閉函數。在沒有任何增強的情況下,這個篩選器雖然較為惰性,但記憶體使用量與舊篩選器相同。新的惰性分支包含針對此類場景的編譯器增強。lazy-seqdelay 都會在主體的尾端呼叫上執行封閉的局部清除,確保當執行尾端呼叫時,封閉函數本身中不會有任何參照。它們可以執行此操作,因為它們會快取結果,因此知道封閉函數只會被呼叫一次。因此,惰性分支對於上述篩選器表達式沒有問題,而且您可以使用類似的技術來控制您自己的惰性函數中的記憶體使用量。