递归 Clojure 中的 s 表达式列表

Question

为了说明一些背景，我正在学习 Clojure，更广泛地说是 Lisp 开发。在我的 Lisp 之路上，我目前正在学习“Little”系列，以巩固函数式编程和基于递归的解决方案的基础。在“The Little Schemer”中，我已经完成了许多练习，但是，我正在努力将其中一些练习转换为 Clojure。更具体地说，我正在努力将它们转换为使用“recur”以启用 TCO。例如，这是一个基于 Clojure 的“occurs*”函数实现(来自 Little Schemer)，它计算一个原子在 S 表达式列表中出现的次数:

(defn atom? [l]
  (not (list? l)))

(defn occurs [a lst]
  (cond
   (empty? lst) 0
   (atom? (first lst))
    (cond
     (= a (first lst)) (inc (occurs a (rest lst)))
     true (occurs a (rest lst)))
   true (+ (occurs a (first lst))
           (occurs a (rest lst)))))

基本上，(occurs 'abc '(abc (def abc) (abc (abc def) (def (((((abc))))))))) 将计算为 5 . 明显的问题是这个定义会消耗堆栈帧，如果给定的 S 表达式列表太深，将会炸毁堆栈。

现在，我理解了重构递归函数以使用累加器参数来启用将递归调用置于尾部位置(以允许 TCO)的选项，但如果此选项甚至适用于诸如此类的情况，我正在努力这个。

如果我尝试使用“recur”以及使用累加器参数来重构它，我会得到多远:

(defn recur-occurs [a lst]
  (letfn [(myoccurs [a lst count]
            (cond
             (empty? lst) 0
             (atom? (first lst))
             (cond
              (= a (first lst)) (recur a (rest lst) (inc count))
              true (recur a (rest lst) count))
             true (+ (recur a (first lst) count)
                     (recur a (rest lst) count))))]
    (myoccurs a lst 0)))

所以，我觉得我快到了，但还不完全是。明显的问题是我的“else”子句，其中列表的头部不是原子。从概念上讲，我想将列表中第一个元素的重复结果与列表其余元素的重复结果相加。我正在思考如何重构它，以便可以将重复项移到尾部位置。

“累加器”模式是否有额外的技术来实现将递归调用放入我应该在这里应用的尾部位置，或者，这个问题只是更“基本”并且没有一个干净的 Clojure基于 JVM 的解决方案缺乏 TCO？如果是后者，一般来说，Clojure 程序使用需要在 S 表达式列表上重复出现的一般模式应该是什么？对于它的值(value)，我已经看到使用了带有惰性序列技术的多方法(Halloway 的“Programming Clojure”第 151 页以供引用)以“用惰性替换递归”——但我不确定如何应用该模式对于这个示例，我不是在尝试构建列表，而是在计算单个整数值。

提前感谢您对此的任何指导。

Answer 1

首先，我必须建议您在学习 The Little Schemer 时不要太担心堆栈溢出等实现障碍。愤怒编程时，注意尾调用优化不足等问题固然好，但本书的重点是教你递归思考。转换示例累加器传递样式当然是很好的做法，但它本质上是放弃递归以支持迭代。

但是，我必须以剧透警告作为开头，有一种方法可以保持相同的递归算法，而不会受到 JVM 堆栈突发奇想的影响。我们可以使用连续传递样式以额外的匿名函数参数 k:

的形式创建我们自己的堆栈

(defn occurs-cps [a lst k]
  (cond
   (empty? lst) (k 0) 
   (atom? (first lst))
   (cond
    (= a (first lst)) (occurs-cps a (rest lst)
                                  (fn [v] (k (inc v))))
    :else (occurs-cps a (rest lst) k))
   :else (occurs-cps a (first lst)
                     (fn [fst]
                       (occurs-cps a (rest lst)
                                   (fn [rst] (k (+ fst rst))))))))

我们不是通过非尾函数调用隐式创建堆栈，而是在每次调用 occurs 后打包“剩下要做的事情”，并将其作为下一个延续 k。当我们调用它时，我们从一个 k 开始，它代表无事可做，身份函数:

scratch.core=> (occurs-cps 'abc 
                           '(abc (def abc) (abc (abc def) (def (((((abc)))))))) 
                           (fn [v] v))
5

我不会进一步详细介绍如何执行 CPS，因为那是 TLS 后面的章节。但是，我会注意到这当然还不能完全起作用:

scratch.core=> (def ls (repeat 20000 'foo))          
#'scratch.core/ls
scratch.core=> (occurs-cps 'foo ls (fn [v] v))       
java.lang.StackOverflowError (NO_SOURCE_FILE:0)

CPS 允许我们将所有重要的、构建堆栈的调用移动到尾部位置，但在 Clojure 中，我们需要采取额外的步骤将它们替换为 recur:

(defn occurs-cps-recur [a lst k]
  (cond
   (empty? lst) (k 0)
   (atom? (first lst))
   (cond
    (= a (first lst)) (recur a (rest lst)
                             (fn [v] (k (inc v))))
    :else (recur a (rest lst) k))
   :else (recur a (first lst)
                (fn [fst]
                  (recur a (rest lst) ;; Problem
                         (fn [rst] (k (+ fst rst))))))))

唉，这是错误的:java.lang.IllegalArgumentException:重复出现的参数计数不匹配，预期:1 个参数，得到:3 (core.clj:39)。最后一个 recur 实际上指的是它上面的 fn，我们用它来表示我们的延续!大多数时候，我们可以通过将 recur 更改为调用 occurs-cps-recur 来获得良好的行为，但病态嵌套的输入仍会溢出堆栈:

scratch.core=> (occurs-cps-recur 'foo ls (fn [v] v))
20000
scratch.core=> (def nested (reduce (fn [onion _] (list onion)) 
                                   'foo (range 20000)))
#'scratch.core/nested
scratch.core=> (occurs-cps-recur 'foo nested (fn [v] v))
Java.lang.StackOverflowError (NO_SOURCE_FILE:0)

与其调用 occurs-* 并期待它返回一个答案，我们可以让它立即返回一个 thunk。当我们调用那个 thunk 时，它会关闭并立即做一些工作，直到它执行递归调用，这又会返回另一个 thunk。这是蹦床风格，“弹跳”我们的声音的功能是 trampoline。每次我们进行递归调用时返回一个 thunk 将我们的堆栈大小限制为一次一个调用，所以我们唯一的限制是堆:

(defn occurs-cps-tramp [a lst k]
  (fn [] 
    (cond
     (empty? lst) (k 0) 
     (atom? (first lst))
     (cond
      (= a (first lst)) (occurs-cps-tramp a (rest lst)
                                          (fn [v] (k (inc v))))
      :else (occurs-cps-tramp a (rest lst) k))
     :else (occurs-cps-tramp a (first lst)
                             (fn [fst]
                               (occurs-cps-tramp a (rest lst)
                                                 (fn [rst] (k (+ fst rst)))))))))

(declare done answer)

(defn my-trampoline [th]
  (if done
    answer
    (recur (th))))

(defn empty-k [v]
  (set! answer v)
  (set! done true))

(defn run []
  (binding [done false answer 'whocares]
    (my-trampoline (occurs-cps-tramp 'foo nested empty-k))))

;; scratch.core=> (run)                             
;; 1

请注意，Clojure 有一个内置的 trampoline (对返回类型有一些限制)。使用它，我们不需要专门的 empty-k:

scratch.core=> (trampoline (occurs-cps-tramp 'foo nested (fn [v] v)))
1

蹦床当然是一项很酷的技术，但是蹦床程序的前提是它必须只包含尾调用； CPS 是这里真正的明星。它使您能够以自然递归的清晰度定义您的算法，并通过保持正确性的转换，在具有单个循环和堆的任何主机上高效地表达它。