begin quoting Tracy R Reed as of Sat, Jun 23, 2007 at 02:05:30AM -0700: > Andrew Lentvorski wrote: [snip] > >Also, iteration is *by definition* O(1) in space. That is not true for > >generalized recursion; it is true only for tail recursion. > > Right. Fortunately most of the commonly used types of iteration can be > implemented in a tail recursive way.
That just means you need to warp your logic to handle tail recursion. This isn't hard... except that if J. Random Prorammer has a hard time with simple iteration, why would I expect 'em to understand tail recursion? > And it seems that anything can be > made tail recursive using CPS transform. But then you start using space > on the heap instead of the stack. A lot of computability theory involves transforms to non-efficient alternatives. You *can* do it, so... theorem proven! Whee! > It seems that it works out the same > (in that in those situations you use O(n) space no matter what) except > with a functional/recursive approach the programmer doesn't have as many > opportunities to mess up the state. And that is the whole point. That would be nice if bugs were randomly introduced, rather than being the result of carelessness or a conceptual misunderstanding... > Although you might as well just do normal recursion on the stack even if > it is not tail recursive since you are going to use space regardless but > at least if you do it on the stack you can free space by decrementing > the stack pointer instead of involving garbage collection which will tie > up lots of cpu cycles in this situation. Breathe, man, breathe! > And really, tail recursion is > iteration as far as the control flow of the machine language goes except > the compiler worries about the state so you don't have to. Again, that > would seem to be a good thing. You have other things to worry about. For simple iteration, sure, it's rote, but even then it's a mismatch -- you use tail recursion for simple iteration because that's the mechanism provided by the language, not because it matches the problem. Sometimes, wrestling an iterative problem into a tail-recursive-friendly form takes some contemplation. So "it prevents the programmer from making stupid mistakes" goals seem a little bogus ... you're just changing where the errors are going to occur. > >>But it usually results in less code and > >>fewer opportunities for bugs among other nice properties. > > > >I don't believe that. The main problem is that iteration is overloaded. > > I have transformed a few iterative processes into recursive processes > just for fun and watched them do the same in the videos and it usually > works out that way. The simple example of summing a list that I pasted > in my original mail was a little example to present the general idea of > why this is so. Doesn't that mean if you get a bunch of sequential & nested loops, you end up pollutiong your function space with loops-constructs, instead of hiding 'em away in one function? Or do you put your loops into a temporary or local namespace? > >One of the main uses for iteration in an imperative language is "do > >action X to every element of Y". This always winds up with fencepost > >and side effect errors. > > How can you end up with fencepost errors if you say "do action X to > every element of Y"? That sort of notation would seem to rule them out. > Much better than doing a for loop over n elements incrementing i each > time through to index through the array of elements and then messing up > your termination condition by using the wrong comparison. Um... that's his point. [snip] > I understand this is all tradeoffs and before anyone accuses me of being > dazzled by the shiny newness of functional programming let me say that > I'm just trying to broaden my horizons. Heh. Okay. Fair enough. -- Newness isn't shiny. Real shiny takes years of polishing. Stewart Stremler -- [email protected] http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
