Quoth john.holland on Sweetmorn, the 44th of The Aftermath: > It seems to me that as general solutions to stack overflow, > trampoline and recur are very valuable. I had gotten the mistaken > idea that Scheme was somehow immune to the problem.
Trampoline and recur are a poor man's tail-call-optimization; and, if by "the problem," you mean that a call-stack grows linearly with its recursive depth: yeah, even Scheme is susceptible to stack-growth if your calls aren't "properly tail-recursive." See R5RS s. 3.5 [1], "Proper tail recursion": A tail call is a procedure call that occurs in a tail context; e.g. the last expression within the body of a lambda expression. William Clinger wrote a paper that formalizes proper tail recursion in more depth [2]. Suffice to say, the naïve recursive implementation of quick sort contains at least one non-tail-call; and, just for kicks, here's an implementation of quicksort in Joy (a so-called concatenative language): [small] [] [uncons [>] split] [swapd cons concat] binrec Joy, too, implements recursion (through `binrec') without growing the call-stack. Footnotes: [1] http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-6.html#%_sec_3.5 [2] ftp://ftp.ccs.neu.edu/pub/people/will/tail.pdf -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
