;; Does anyone know what the hell is going on here ? (clojureversion) "1.5.1" ;; I mean, this is bad enough: ;; Here's a function to sum up all the numbers from 1..n (def gaussrecurse (fn [n] (if (< n 1) 0 (+ n (gaussrecurse (dec n)))))) (gaussrecurse 3500) ;> 6126750 (gaussrecurse 4000) ;> StackOverflowError clojure.lang.Numbers$LongOps.combine (Numbers.java:394) ;; A maximum stack depth of 3500 or so is completely rubbish, but it's been like that for a while. ;; But I don't remember this: (def gaussmemoized (memoize (fn [n] (if (< n 1) 0 (+ n (gaussmemoized (dec n))))))) (gaussmemoized 160) ;> StackOverflowError clojure.lang.RT.boundedLength (RT.java:1654) (gaussmemoized 100) ;> 5050 I could probably do this in my head. At least it's the right answer. ;; Why would memoization affect the stack depth anyway? ;; Please please let this be a bug, or some idiocy on my part. ;; Please don't let my favourite language have decided that I can't ;; memoize a recursive function for any nontrivial problem. ;; And if any smartarse is thinking: 'You could use' (reduce + (range 1 5001)) ;> 12502500 (* 5000 5001 1/2) ;> 12502500N ;; or (defn gausstail ([n] (gausstail n 0)) ([n acc] (if (zero? n) acc (recur (dec n) (+ n acc))))) (gausstail 5000) ;> 12502500 ;; etc, etc, etc, then I already know, ok. That's not the point. So fuck off. ;; Unless you're about to give me a general macro which will transform ;; any collection of mutually recursive functions into an efficient ;; stackless implementation which avoids repeated solutions of the ;; same problem. In which case I will be most interested. ;; How on earth do you program without recursion ? ;; And why would you want to?
Blog Archive

▼
2013
(53)

▼
September
(12)
 Efficiency and Progress III : How Close Can We Get...
 Efficiency and Progress II : Behold, C
 Efficiency and Progress : My God, Clojure is Slow!...
 How on earth do you program without *recursion*?
 Algorithms II
 Putting it all together : Using UnionFind in Krus...
 Implementing a Data Structure : UnionFind version...
 Implementing a Data Structure: UnionFind
 Kruskal's Algorithm for Minimal Spanning Trees
 The Knapsack Problem : Another Classic Puzzle from...
 Optimal Scheduling : A Classic Puzzle from Compute...
 SVG Graphics in a Clojure Web Application

▼
September
(12)
Sunday, September 22, 2013
How on earth do you program without *recursion*?
Subscribe to:
Post Comments (Atom)
You mean, like this? http://clojuredocs.org/clojure_core/clojure.core/trampoline
ReplyDelete:)
We've got recursion, just no TCO, so no real corecursion.
ReplyDeleteAnd regarding that rage inducing part of your post  well memoize[1] gives you your fn wrapped in a LUT accessing fn, so on memo miss you call two fns for every original call. Also first run from 160 down does not utilize cache (all checks miss), because you're going down from 160 without entries in LUT. So you just exhaust your stack faster. Using memoize[1] for recursion is a hack and is not algorithm opaque (=requires hacking around populating the memo map from ground up). As Craig said  use trampoline[2].
[1] http://clojuredocs.org/clojure_core/clojure.core/memoize
[2] http://clojuredocs.org/clojure_core/clojure.core/trampoline
Here's a macro for transforming to tail calls. Not complete though.
ReplyDeletehttps://github.com/cjfrisz/clojuretco