延续传递风格似乎对Clojure没什么影响 [英] Continuation-passing-style does not seem to make a difference in Clojure

问题描述

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

I have been experimenting with continuation-passing style, as I may need to deal with some non tail-recursive functions soon. Good technique to know, in any case! I wrote a test function, both in Lua and in Clojure; ran the Lua one on my little Android handheld.

Lua版本似乎运行良好，Lua的堆栈深度已经达到300000，但是使用CPS，我当时很容易能够在系统崩溃之前进行超过7000000次迭代，这可能是由于内存不足，而不是CPS / Lua组合没有任何限制。

The Lua version seems to have worked fine, Lua's stack already has a depth of about 300000, but with CPS, I was easily able to do over 7000000 iterations before the system blew up, probably out of lack of memory, rather than any limitation of the CPS/Lua combination.

Clojure尝试失败了不太好。在进行1000次以上迭代时，它抱怨堆栈过大，仅使用普通迭代（它的堆栈大约为1600，iirc）就可以做得更好。

The Clojure attempt fared less well. With little over 1000 iterations it was complaining of blown stack, it can do better just with plain iteration, which has a stack of about 1600, iirc.

任何想法都可能是问题吗？ JVM固有的某些功能，还是一些愚蠢的noob错误？ （哦，顺便说一句，选择了测试函数sigma（log）是因为它增长缓慢，而Lua在Android上不支持bignums）。

Any ideas what might be the problem? Something inherent to the JVM, perhaps, or just some silly noob error? (Oh, BTW, the test function, sigma(log) was chosen because it grows slowly, and Lua does not support bignums on Android)

所有想法，提示和建议

Clojure代码：

The Clojure code:

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。经过一些试验之后，我尝试了在第三条注释中提到的代码，

PS. After experimenting a bit, I tried the code I mention in my third comment, below

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

按照命令，这显然更好，但是我仍然认为它太低了。从技术上讲，它应该仅受内存限制，是吗？

That's obviously better, by an order, however I still think it's way too low. Technically it should be limited only by memory, yes?

我的意思是玩具Lua系统在玩具Android平板电脑上的性能超过700万...

I mean the toy Lua system, on a toy Android tablet did over 7000000...

推荐答案

Clojure具有 蹦床 函数可以消除很多与此问题相关的令人困惑的管道：

Clojure has the trampoline function that can remove a lot of the confusing plumbing involved in this problem:

(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

传递给蹦床的函数可以返回一个新函数（在这种情况下，蹦床继续弹跳），也可以返回一个非函数值，即最终值。此示例不涉及相互递归函数，但也可以使用蹦床来实现。

The function you pass to trampoline can either return a new function, in which case the trampoline continues "bouncing", or a non-function value which would be a "final" value. This example doesn't involve mutually recursive functions, but those are also doable with trampoline.

这篇关于延续传递风格似乎对Clojure没什么影响的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！