On Thu, Dec 30, 2010 at 5:34 AM, Mark Engelberg <mark.engelb...@gmail.com>wrote:
> On Wed, Dec 29, 2010 at 11:31 PM, David Nolen <dnolen.li...@gmail.com> > wrote: > > The original algorithm is simply wrong for very large inputs, it cannot > be > > TCO'ed. Pick a ridiculously large list size and the Scheme/Racket program > > will barf *immediately*. > > David > > Have you tried it? I tried this particular algorithm, in Racket, on > rather large lists. It runs seemingly forever (it is a quadratic > algorithm, of course), but I was unable to make Racket "barf > immediately". In my experience, Racket's more likely to fall over > from trying to create such a large input to begin with (simply because > there's not enough memory to hold a list that large) than it is to > barf from stack size while executing a non-TCO recursive function over > a list. My understanding is that Racket's key to handling non-TCO > recursion so gracefully is that it traps errors from stack overflows, > and swaps the stack out to memory to make room on the stack to > continue. So in essence, you get a stack that is bounded only by your > computer's memory (or whatever memory threshold you've enabled in the > settings). > > What size input is barfing for you? 2e6. Racket can easily create a list of that size. Calling sort on it however fails fast. David -- 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
