Been thinking about tail recursion lately. I think compilers should automatically make function definitions like this tail recursive:
fac 0 = 1
fac n | n > 0 = n * fac (n-1)They can do this by noting, each time they recur, that the only thing to do after returning from this recursion is to multiply, or on the second recursion, to multiply twice. On the second recursion, these two multiplications can be simplified into one, right then and there. Like this:
fac 4: (fac 4 = 4 * fac 3) =>
(4*) (fac 3 = 3 * fac 2) =>
(4*) . (3*) (fac 2 = 2 * fac 1) =>
(12*) (fac 2 = 2 * fac 1) =>
(12*) . (2*) (fac 1 = 1 * fac 0) =>
(24*) (fac 1 = 1 * fac 0) =>
(24*) . (1*) (fac 0 = 1) => 24This can compute factorials of arbitrarily large n while using constant stack space. The big deal here is that the compiler has to know when it's able to simplify two composed functions into one; in this case, it has to know that a*(b*c) = (a*b)*c, i.e. * is associative. Comments?
Damn, I was trying to keep that short so it would all fit on the index page. I guess there's a penalty line for each code block.
Nobody uses recursion and compilers at the same time, so the idea is fairly meaningless!
>>3 is utter nonsense.
>>3
Maybe I didn't provide enough context. I suppose recursion is not used very much in languages like C, C++, ... I had in mind functional languages, more like Lisp and Scheme, and particularly Haskell, which my example code is designed to look like.
Often in these languages, a routine like factorial will be optimized by adding an accumulator, like this:
facAcc a 0 = a
facAcc a n = facAcc (n*a) (a-1)
fac = facAcc 1This allows the use of tail recursion, which is like "goto with arguments", so that it doesn't eat up stack space. But I don't think adding an accumulator is in the spirit of declarative programming, since it tells how, rather than what, to compute. Hence, the proposal in >>1.
But as I said, nobody compiles Lisp or Scheme.
Also, nobody uses Haskell.
Right, and I'm pretty sure nobody uses the first two.
I guess there's one person out there who uses Haskell, though!
Also I meant to say >>7, but didn't because I can't count any further than three! Sorry!
I think >>6 was joking.
Proper tail recursion, including mutual tail recursion is quite simple when you have continuations. Perl6's VM, 'parrot' is based mostly on continuations.
Continauations make tail recursion optimisations, exception handling, and co-routines quite easy to implement, and as such, perl6 will have tail recusion optimisation. :)
Why I care? I dunno. Tail recursion is stupid, recursion is stupid, the stack is a precious resource, not something to throw away willy nilly.
What are your thoughts of recursion on Itanium then? Not only does it have multiple huge stacks, but it has a metric assload of registers to use instead of the stack space for args.
Pretty much no matter what you do, replacing a loop with recursion will make your memory usage go from O(1) to O(N). As >>1 shows, in special cases you can apply optimizations to *get back to the same performance as a loop.
It's incredibly wasteful and silly.
Ok, you do your octree traversals iteratively then. I'll write them in 8 lines recursively.
I don't know about you, but I write for loops a hell of a lot more often than I write octree traversals. And you know what? I can still do my octree traversals recursively even if I do all my for loops iteratively!
"Best tool for the job", maybe? Possibly?
>>15 ahahah you mean people would actually use logic instead of blindly following rhetoric? Oh how naive you are.
I was responding to "recursion is stupid" and "the stack is a previous resource"
I think you missed the part where recursion is still stupid in the vast majority of cases, and an esoteric example like traversing an octree every once in a blue moon is not really a refutation.
What was being attacked was not recursion in general, but functional programming languages' insistance that recursion is the only construct one should ever use.
>>17
Functional programming languages don't insist that. Common Lisp has its loop macro, Scheme has iterative "do" syntax, and in Haskell the way you'd define factorial in practice is
fac n = product [1..n]although you can do it iteratively too, if you must:
fac n = result (for init next done)
where init = (0,1)
next (i,m) = (i+1, m * (i+1))
done (i,_) = i==n
result (_,m) = m
for i n d = until d n iIteration is available in all these languages. It's just not the best tool for the job as often as you'd think.
>>18
that's got to be the clumsiest code I've ever seen. is haskell usually like that, or does it just look insane there because you're doing something the "wrong" way?
Functional languages fit naturally with recursion, not iteration, so of course it'd look ugly.
There most certainly are benefits to using a functional language, it's just that most people don't need them (yet). These benefits wouldn't exist if iteration was a normal feature.
He presents two ways, the first way 1 line. The second way is the clumsy non-haskellish way of doing it.
>>21
Yeah I know. And I'm talking about the second, clumsy way, since the first example is one line (and one line is never any kind of indication of what a language looks like). And I'm asking if Haskell normally looks that nasty, or if it's only because he's doing something the language clearly wasn't intended to do frequently. Or, for that matter, if he's intentionally making it more complicated than normal to "prove" how clean its recursion is.
I ripped off that code from "The Evolution of a Haskell Programmer" (http://www.willamette.edu/~fruehr/haskell/evolution.html). It's an example of what someone thinking in Pascal might write.
The one-line version actually does give a pretty good indication of Haskell. Lots of things can be done in one or two lines, like finding the minimum element of a list:
minlist = foldl1 minDon't take my word for it though, try it.
`
y f = f (y f)
fac = y (\f n -> if (n==0) then 1 else n * f (n-1))
`
i like this
So basically, if there is a built-in special-case construct ("product"), that will look a whole lot tidier than doing it by hand. This is hardly an argument for or against recursion, loops, functional programming, or imperative programming.
I can do the same thing in C, by using the imaginary library libproduct:
int factorial(int n) { return product(sequence(1,n)); }Now, the actual subject of this discussion is cases where you do have to write your own loops or recursions, for large amounts of data. Not special cases where you can use syntactic sugar, nor cases where you only have to interate or recurse a handful of times. This is a very common situation in real-world code, and my claim, at least, is that iterative langauge are ill suited for it.
product = foldr (*) 1And for those who don't quite get it yet:
fac n = product [1..n]
is the same as:
fac n = foldr (*) 1 [1..n]
Where 'foldr' is as essential to writing a haskell program as 'while' is to C.
So foldr (the hell is up with that name?) is syntactic sugar for a certain kind of recursive loop, and hopefully implemented without recursion internally by the language?
This is the implementation of foldl and foldr:
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xsfoldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)You'll note that the type signatures are slightly different, but if you don't know how to read haskell type signatures, that'll mean very little to you.
If you're especially quick, you'll notice that it is implemented using recursion.
And this is the difference:
foldl (+) 0 [1,2,3,4,5] means (((((0+1)+2)+3)+4)+5)
foldr (+) 0 [1,2,3,4,5] means (1+(2+(3+(4+(5+0)))))i.e. one is to the 'left' and one is to the 'right'.
in python, foldr is spelt reduce()
But is it actually implemented like that, or is it implemented internally with a normal imperative loop? Because if you do implement it like that, it uses O(N) memory for something as simple as multiplying an array, which is ridiculous.
The definition of foldl is tail recursive. I don't know about foldr, but GHC and Hugs seem to optimize those sorts of things in some way. Both compute fac faster and with less memory than facAcc. I have no idea how it works.
Uh, that's the implementation. Right there. I copied it out of the standard file 'Prelude.hs'. No trickery. That's the exact implementation.
Iterative languages aren't the only ones with optimizing compilers (or sane interpreters). The people writing these things aren't idiots.
s/iterative/imperative/
So it does use O(N) memory for something that could be done in O(1) with an imperative loop?
I suppose it might be able to optimize something that simple, but what about a slightly more complex recursion? You'll end up having to pray that the compiler will optimize it properly even though you wrote a horribly ineffecient algorithm. Of course, you always have to trust the compiler to some extent to optimize properly, but forcing you to write badly performing code on the algorithmic level, and praying the compiler fixes it, doesn't seem very wise.
These statements about trusting the compiler and using efficient algorithms are misguided. Fast code requires profiling to see where the time is actually spent, and theoretically inefficient algorithms are often better in practice (example: quicksort beats radix sort on most real-world inputs).
But you're right to some degree in this case, and I do wonder how those Haskell implementations manage to optimize that.
Wait a minute.
foldl is iterative in haskell. foldr is recursive.
Can anyone show me a way to do foldr iteratively?
Well, exactly, the way to get fast code is to do proper testing to see what works best, working from your knowledge of algorithms and optimization, which is why you definitely don't want to intentionally write a horrible algorithm because the langauge is designed to only use horrible algorithms, and then hope the compiler will clean up your mess for you.
foldr f z ls = foldl (flip f) z (reverse ls)For reference, flip and reverse are defined as:
flip f x y = f y x
reverse = foldl (flip (:)) []Both foldl and foldr in the Prelude is O(N) time. foldl is O(1) space; foldr is O(N) space.
>>39
You reversed a list, which takes O(N) time and space. Then did foldl on it which takes O(N) time, O(1) space.
The foldr in the Prelude goes forward in the list, creating a huge function, which is O(N) time and space. Then it goes backwards to simplify the function, which takes O(N) time.
Your foldr is basically the same as the one in the Prelude. The difference is that yours has two list and it traverses through the both lists once. The Prelude's has one list and a huge function. It traverses through the list and simplifies the function. I don't know what goes on in the compiler.
> you definitely don't want to intentionally write a horrible algorithm because the langauge is designed to only use horrible algorithms
This is leaving the realm of the reasonable, and entering the realm of religion. Recursion does not imply horrible algorithm. In fact, iteration is (provably) just one case of recursion.
Those problems that are iterable are also easy to optimize in functional languages using a tail recursion. No active frame is created on the stack for either, unless the language implementation is braindead.
> In fact, iteration is (provably) just one case of recursion.
Does this proof take into account the memory usage of stack frames in recursion?
> Those problems that are iterable are also easy to optimize in functional languages using a tail recursion.
This statement might or might not be true, but it is not trivially obvious that it should be. Please back up this claim.
> Does this proof take into account the memory usage of stack frames in recursion?
Provably the same means that they are identical. If you can optimize out the use of stacks in iteration, you can do the same for the same case in recursion since it's the same thing.
> Please back up this claim.
For once I think "go google it" is apt. If you're going to argue a point, at least research it a little. Here's the first three links returned in a google for "tail recursion", all which include examples:
First link: http://en.wikipedia.org/wiki/Tail_recursion
In computer science, tail recursion is a special case of recursion that can be easily transformed into an iteration. It is used in functional programming languages where the declarative approach and explicit handling of state emphasize recursive functions that rapidly fill the stack. Replacing recursion with iteration, either manually or automatically, drastically decreases the amount of stack space used and improves efficiency.
Second link: http://www.cis.ksu.edu/VirtualHelp/Info/develop/cmu-user.info.Tail_Recursion.html
Tail recursion is interesting because it is form of recursion that can be implemented much more efficiently than general recursion. In general, a recursive call requires the compiler to allocate storage on the stack at run-time for every call that has not yet returned. This memory consumption makes recursion unacceptably inefficient for representing repetitive algorithms having large or unbounded size. Tail recursion is the special case of recursion that is semantically equivalent to the iteration constructs normally used to represent repetition in programs. Because tail recursion is equivalent to iteration, tail-recursive programs can be compiled as efficiently as iterative programs.
Third link: http://www.nist.gov/dads/HTML/tailrecursn.html
Some examples in C. The others all have examples too, but this one is in a language you're probably familiar with.
This is pretty stupid. fyi. Tail recursion is basically the same as a while loop if the compiler does it right. In functional languages (they usually don't have while loops), tail recursion is called iteration (ex: foldl) and different from actual recursion (ex: foldr).
Yes, tail recursion can be optimized. But tail recursion is a very limited subset of all possible recursions, and it is also a very limited subset of things that can be implemented in O(1) memory with an iterative loop. It's not obvious that all the things you can do with an iterative loop can be transformed into tail recursion in O(1) memory.
This very thread contains this example: >>37,39,40. I don't see a resolution for how to do foldr with tail recursion. With a loop, I can trivially change the order I traverse the elements in, including some pretty non-trivial orderings like taking the odd elements first and the evens second.
What I asked for is some proof that all this, and not just a subset, can be transformed into tail recursion in O(1) memory and O(n) time.
> But tail recursion is a very limited subset of all possible recursions
Yes.
> and it is also a very limited subset of things that can be implemented in O(1) memory with an iterative loop.
No. Please read the links I provided.
I did read them, if not all that thoroughly, but I didn't see a general proof of this. For instance, how do I, with recursion, do:
Maybe I am getting ahead of myself since these are mostly built around array indexing, but that's pretty much what iterative loops are all about anyway.
There is no way to do foldr in O(1) space and O(N) time.