[Haskell-cafe] Debunking tail recursion

[Juan Carlos Arevalo Baeza]

On Fri, 18 May 2007 01:52:11 -0700, Jules Bean <jules at jellybean.co.uk>  
wrote:

> A conversation on #haskell just showed that it's quite hard to explain  
> (at least it is for me) to people attached to tail recursion why that is  
> a red herring in Haskell.
>
> If someone has the energy and the clarity to explain this clearly and  
> make a wiki page about it, that would be great. If someone finds an  
> existing wiki page I'm too unperceptive to notice, even better!

    Here's an explanation that I put together a while ago for a friend (and  
forgive my pseudo-coding):

-------------------------------------------------
    I guess the thing with Haskell is that the complication is in the  
details and behavior of your program. It?s very easy to shoot yourself in  
the foot without even knowing.

    The basics of parsers are very easy to understand. For instance:

hello = char ?h? >> char ?e? >> char ?l? >> char ?l? >> char ?o?

    The ?do? notation is just syntactic sugar for that, which sometimes  
makes those more readable:

hello = do
     char ?h?
     char ?e?
     char ?l?
     char ?l?
     char ?o?

    Is a very simple parser that is easy to understand. I mean? any monad  
can be seen as just a way to enforce order of evaluation (so that in this  
case the letters are recognized in the proper order) and to hide some of  
the parameters to the functions (so that you don?t have to explicitly pass  
the input string in those parsers). That?s really all there is to it. Then  
there?s the concept of combinators: functions that take parsers as  
arguments, and generate a new parser. ?>>? is part of the monad  
definition, but it is also a combinator in its own right (take two parsers  
and generate a new parser which is the sequence of them). Also the  
alternative (call it ?<|>?) is a combinator:

many1hellos = hello >> (many1hellos <|> return ())

    ?return a? is also part of the definition of any monad. It is an  
operation that always succeeds and just returns the value, in this case  
the Haskell equivalent to ?void?. So if ?many1hellos? fails because the  
next ?hello? couldn?t be matched, then it calls it good anyway. That?s the  
backtracking you find in all these parsers.

    The ?<|>? combinator knows about the guts of the monad (about the  
internal state and the guts), of course, so it can do the very interesting  
things it does. It?s a primitive combinator. Something kinda like this  
(hope you?re already comfortable with the ?do? notation):

a <|> b = do
     oldState <- getCurrentParserState
     resultFromA <- try a
     if failed resultFromA then do
             -- Try the other one
             setCurrentparserState oldState
             b
         else do
             -- oldState gets forgotten ? it will be garbage-collected
             return (extractResultValue resultFromA)

    Once you have enough of those primitives, you can build your own  
combinators, which work in exactly the same way. That?s where things start  
to go south, though, and the foot-shooting begins. Take for instance:

many1 p = p >> (many1 p <|> return ())

    Combinator that takes any parser (just like for instance ?hello?) and  
parses one or more of them (it exists in the standard library). That  
works. So far so good. But then maybe we want one that matches zero or  
more:

many0 p = (p <|> return ()) >> (many0 p <|> return ())

    That?s a silly example that is totally wrong, obviously (let me know if  
you don?t see it). This parser will never finish parsing. It?s an infinite  
loop. All grammar languages have rough corners like this one, of course,  
but with Haskell they can be very hard to track down.

many0 p = (p >> (many0 p <|> return ())) <|> return ()

    This one is also an infinite loop, although it is harder to figure it  
out.

many0 p = (p >> (many1 p <|> return ())) <|> return ()
many0 p = many1 p <|> return ()

    Those two are both identical and correct, the last one is just more  
concise. But their behavior is poor. I mean, if you try to parse a 1 GB  
file full of ?X?, using ?many0 (char ?X?)? the ?many1 p? part will take a  
long time to parse, and in the meantime the ?oldState? variable that I  
showed you above in the definition of ?<|>?, which is required in some  
form in order to do the backtracking, is fully alive (cannot be  
garbage-collected) even though after the first ?X? is parsed _we_ know it  
can never fail.

    That is a bad thing, but much worse is the behavior of ?many1?. In this  
case, the recursion is not good for tail-recursion, so you?ll end up  
running out of stack. Basically, you end up with a nested sequence of  
?<|>? calls.

    That sort of problem is endemic to backtracking parsers, and all  
monadic parsers I know are backtracking parsers. The solution in this case  
is to never put anything expensive on the left side of a ?<|>? combinator.  
We can do that like so:

many0 p = do
     result <- try p
     if failed result
         then return ()
         else many0 p

    This way, there is no backtracking, and many1 can be efficiently  
defined as so:

many1 p = p >> many0 p

    That is all somewhat similar to the issues you?d find in a  
recursive-descent parser written in any imperative language. But then  
again ? monads are very much like somewhat-restricted imperative programs.

    The point where it all gets really tricky is that you can find similar  
sorts of problems in non-monadic code, and those are really hard to find.  
For instance, take the following function from the standard library (I  
hope you?re somewhat acquainted with Haskell lists):

replicate 0 v = []
replicate n v = v : replicate (n-1) v

    That?s a neat little function which builds a list by repeating the ?v?  
element ?n? times. Very simple. But it is not tail-recusive! The  
imperative way of thinking about it is that, after calling ?replicate  
(n-1) v?, it gets the result and appends it to ?v?. Clearly, that prevents  
the tail-recursion from happening.

    A fully tail-recursive version is this:

replicate n v = replicateHelper n v []

replicateHelper 0 v result = result
replicateHelper n v result = replicateHelper (n-1) (v : result)

    To the imperative eye, that looks much better.

    The problem here is that the tail-recursive version is less efficient  
in Haskell. This is because of the laziness inherent in the language. In  
the first version, the expression ?replicate (n-1) v? is a very compact  
thing. It?ll be evaluated some day, but until then it occupies very little  
space. But, in the tail-recursive version, the recursion _must_ happen all  
the way to the end before you can do anything with the list. As soon as  
you try to do anything with the list (like compare it with ?[]? to see if  
it?s empty), it will evaluate all the calls to ?replicateHelper?. It won?t  
evaluate all the ?:? operations, for instance, but still it will create an  
expression tree such as ?v : (v : (v : (v : ?)))? which is arbitrarily  
large. It has no choice, as the outermost ?v : ?? node of the expression  
tree is generated by the innermost call to ?replicateHelper?.

    So in the first case, the comparison ?replicate 1000000 ?X? == []?  
returns ?False? immediately. But in the second case it probably will blow  
due to lack of memory. The proper ?Haskell? way to read that function (or  
any other function) is? ?how quickly can you get to the outermost node of  
the actual expression generated by this function?? That will tell you how  
efficient it is, much better than anything else.
-------------------------------------------------

    The morale is... tail recursion is a strict code optimization only.  
Lazy code will do best to stay as far away from it as possible.

    Hope there aren't too many typos, and also hope that helps someone.

JCAB