1

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.

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.

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.

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)

All ideas, hints, suggestions most welcome.

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. 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?

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

Improve this question
4
  • 1
    Clojure isn't tail-call optimized. I think you will need recur or loop and recur. More info here: clojuredocs.org/clojure.core/recur Commented Jun 20, 2018 at 16:46
  • Good point. Bit of a moment there. I thought that since I'm looking to set this up to work on the "heap" (whatever that means in JVM), that the normal rules applying to Clojure and humans would not be in effect. I'll look to rewrite it using 'recur'. Stuff like CPS and y-combinator (which I was looking at previously) do weird things to your mind. All for the good in the end, I'm sure. Somehow it never occurred to me that the TCO mechanism would be employed to allow a mechanism for non-recursive calls to be implemented without using the stack. Thanks for the reminder! Commented Jun 20, 2018 at 16:56
  • Meantime if anyone has any version of the above written in canonical Clojure, or any hints, tips, etc. that would be great. Funnily enough, the algorithm I used worked OK in Lua. Lua is tail recursive, but I don't think the algorithm is, as far as I can tell. Do correct me if I'm wrong. Commented Jun 20, 2018 at 16:58
  • 1
    I found a very good set of tutorial slides here: slideshare.net/borgesleonardo/… Basically it has covered most of my questions. Recommended for anyone looking into this. Commented Jun 20, 2018 at 18:38

1 Answer 1

Reset to default
6

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

user=> (sigma 100000000) 1.7420680845246599E9 in 20-odd seconds on my ancient rickety desktop. That's more like it, I knew it was doable. I'll have to get the forensics in now, to see what's wrong with the rest of them. Thanks again, Taylor!

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.