[为了设置背景，我正在学习Clojure，并且更广泛地开发Lisp。在通往Lisp的道路上，我目前正在研究“小”系列，以巩固函数式编程和基于递归的解决方案解决的基础。在“小计划者”中，我完成了许多练习，但是，我正在努力地将其中的一些转换为Clojure。更具体地说，我正在努力将它们转换为使用“递归”以启用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表达式列表，那么应该使用什么通用模式？对于它的价值，我已经看到了使用带懒惰序列技术的多方法（参考Halloway的“ Programming Clojure”的第151页）以“用懒惰替换递归”-但是我不确定如何应用该模式这个例子中，我不是试图建立一个列表，而是计算一个整数值。
在此先感谢您提供任何指导。
[首先，我必须建议您在通过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))))))))
A，这是错误的：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)
不是打电话给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（对返回类型有一些限制）。使用它，我们不需要专门的trampoline：
empty-kTrampolining当然是一种很酷的技术，但是对程序进行蹦床的前提是它必须仅包含尾部调用； CPS是这里真正的明星。它使您可以清晰自然地定义算法，并通过保留正确性的转换在任何具有单个循环和堆的主机上高效地表达它。
您无法使用固定的内存量执行此操作。您可以消耗堆栈或堆；那是您要做的决定。如果我使用Clojure编写此代码，则可以使用scratch.core=> (trampoline (occurs-cps-tramp 'foo nested (fn [v] v)))
1
和map来实现，而不必使用手动递归：
reduce请注意，如果使用(defn occurs [x coll]
(if (coll? coll)
(reduce + (map #(occurs x %) coll))
(if (= x coll)
1, 0)))
或tree-seq，则存在更短的解决方案，但是到那时，大多数问题都消失了，因此没有太多要学习的东西。
这里是一个不使用任何堆栈的版本，而是让其队列越来越大（耗尽堆）。
flatten