13

为了设置一些上下文，我正在学习 Clojure，以及更普遍的 Lisp 开发。在通往 Lisp 的道路上，我目前正在研究“小”系列，以巩固函数式编程和基于递归的解决方案解决方案的基础。在“The Little Schemer”中，我完成了许多练习，但是，我在将其中一些练习转换为 Clojure 时遇到了一些困难。更具体地说，我正在努力将它们转换为使用“recur”以启用 TCO。例如，下面是“occurs*”函数（来自 Little Schemer）的基于 Clojure 的实现，它计算出现在 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 表达式列表上递归的一般模式应该是什么？对于它的价值，我已经看到使用了多方法 w/lazy-seq 技术（Halloway 的“Programming Clojure”的第 151 页供参考）“Replace Recursion with Laziness”——但我不确定如何应用该模式在这个例子中，我不是试图建立一个列表，而是计算一个整数值。

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

4

2 回答 2

11

首先，我必须建议您在浏览 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，并将其作为下一个 continuation 传递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: Mismatched argument count to recur, expected: 1 args, got: 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)

我们可以让它立即返回一个 thunk，而不是调用occurs-*并期望它返回一个答案。当我们调用那个 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 是这里真正的明星。它允许您以自然递归的清晰度定义您的算法，并通过保持正确性的转换，在任何具有单个循环和堆的主机上有效地表达它。

于 2011-11-08T06:32:23.000 回答
7

您无法使用固定数量的内存来执行此操作。您可以使用堆栈或堆；这就是你要做的决定。如果我在 Clojure 中编写此代码，我会使用手动递归map而reduce不是手动递归：

(defn occurs [x coll]
  (if (coll? coll)
    (reduce + (map #(occurs x %) coll))
    (if (= x coll)
      1, 0)))

tree-seq请注意，如果您使用or ，则存在较短的解决方案flatten，但此时大部分问题都已解决，因此无需学习太多。

编辑

这是一个不使用任何堆栈的版本，而是让它的队列变得越来越大（使用堆）。

(defn heap-occurs [item coll]
  (loop [count 0, queue coll]
    (if-let [[x & xs] (seq queue)]
      (if (coll? x)
        (recur count (concat x xs))
        (recur (+ (if (= item x) 1, 0)
                  count)
               xs))
      count)))
于 2011-11-08T04:25:27.597 回答