延续传递风格似乎在Clojure中没有任何区别

Question

我一直在尝试继续传递样式,因为我可能需要尽快处理一些非尾递归函数.无论如何,要知道好的技术!我在Lua和Clojure中编写了一个测试函数; 在我的小型Android掌上电脑上运行Lua.

Lua版本似乎运行良好,Lua的堆栈已经有大约300000的深度,但是使用CPS,我很容易在系统爆炸之前完成超过7000000次迭代,可能是因为缺乏内存,而不是任何限制CPS/Lua组合.

Clojure的尝试表现不太好.只有1000多次迭代,它就是抱怨堆栈爆炸,只需使用普通迭代就可以做得更好,它的堆栈大约为1600,iirc.

任何想法可能是什么问题？JVM固有的东西,或者只是一些愚蠢的noob错误？(哦,BTW,测试功能,sigma(日志)被选中,因为它增长缓慢,Lua不支持Android上的bignums)

所有的想法,提示,建议都非常受欢迎.

Clojure代码:

user=> (defn cps2 [op]
  #_=>   (fn [a b k] (k (op a b))))
#'user/cps2

user=> (defn cps-sigma [n k]
  #_=>  ((cps2 =) n 1 (fn [b]
  #_=>           (if b                    ; growing continuation
  #_=>               (k 0)                ; in the recursive call
  #_=>               ((cps2 -) n 1 (fn [nm1]
  #_=>                        (cps-sigma nm1 (fn [f]
  #_=>                                          ((cps2 +) (Math/log n) f k)))))))))
#'user/cps-sigma

user=> (cps-sigma 1000 identity)
5912.128178488171

user=> (cps-sigma 1500 identity)

StackOverflowError   clojure.lang.Numbers.equal (Numbers.java:216)
user=> 

===================

PS.经过一番实验,我尝试了我在下面第三条评论中提到的代码

(defn mk-cps [accept? end-value kend kont]
  (fn [n]
  ((fn [n k]
    (let [cont (fn [v] (k (kont v n)))]
      (if (accept? n)
        (k end-value)
        (recur (dec n) cont))))
    n kend)))

(def sigmaln-cps (mk-cps zero? 0 identity #(+  %1 (Math/log %2)))) 

user=> (sigmaln-cps 11819) ;; #11819 iterations first try

StackOverflowError   clojure.lang.RT.doubleCast (RT.java:1312)

通过订单,这显然更好,但我仍然认为它太低了.从技术上讲,它应该仅限于记忆,是吗？

我的意思是玩具Lua系统,在玩具Android平板电脑上做了700多万...

Answer 1

Clojure具有trampoline可以消除此问题中涉及的许多令人困惑的管道的功能:

(defn sigma [n]
  (letfn [(sig [curr n]
            (if (<= n 1)
              curr
              #(sig (+ curr (Math/log n)) (dec n))))]
    (trampoline sig 0 n)))

(sigma 1000)
=> 5912.128178488164
(sigma 1500)
=> 9474.406184917756
(sigma 1e7) ;; might take a few seconds
=> 1.511809654875759E8

你传递给函数trampoline可以返回一个新的功能,在这种情况下,蹦床继续"反弹",或者这将是"最终"值非函数值.此示例不涉及相互递归的函数,但这些函数也可以使用trampoline.