Tail Recursion Elimination (Guido van Rossum, 2009) | Hacker News Reader

Tail Recursion Elimination (Guido van Rossum, 2009)

neopythonic.blogspot.com

13 pointstosh11 comments

> Is it really such a big deal to rewrite your function to use a loop? (After all TRE only addresses recursion that can easily be replaced by a loop. :-)

Sure. Recursion is iteration. But the beauty of recursion is that it lends itself to mathematical/algorithmic/etc thinking and is far more elegant and readable in many situations. Try writing something basic as fib as a recursive function and then in a loop. One is elegant and the other is kludgy.

Lots of things aren't a "big deal" but it's nice to have. It's why we have so much syntactic sugar in languages and it's also why so much of functional concepts are moving to OO space.

> Try writing something basic as fib as a recursive function and then in a loop. One is elegant and the other is kludgy.

At the same time, one is slow as hell, because recalculates the very same value multiple times (unless you return a tuple, in which case it loses its elegance). You've chosen a bad example.

Also, remember that the opinion comes from a guy who mistakes tuples for lists with some unrelated property (being immutable), even though he had a few opportunities to fix his initial misunderstanding. Anything coming from van Rossum about functional programming should be taken with a grain of salt.

> At the same time, [recursive fib] is slow as hell, because recalculates the very same value multiple times...

That depends on the language and choice of evaluation strategy. For example, in Haskell this recursive form is both elegant and fast:

    fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

There is this curious divergence between what people writing in Haskell consider elegant and what virtually everybody else considers elegant. I can't make heads or tails of your example, even though I'm versed enough in functional and imperative programming and I know what the code should do.

But yes, in languages that cache the call results by default the original formula will be fast.

Apart from non-strict evaluation, the example doesn't use any primitives which are not extremely common in any functional programming language:

    -- list constructor
    1 : 2 : 3 : [] == [1,2,3]

    -- remove first item from a list
    tail [1,2,3] == [2,3]

    -- combine two lists "pointwise"
    zipWith (+) [1,2] [3,4] == [1+3,2+4]

If you line up the Fibonacci numbers starting from the first element and the Fibonacci numbers starting from the second element, and add the corresponding elements, you get the remaining elements of the Fibonacci sequence. Visually:

      1,  1, (2, 3,  5,  8, 13, ...)  -- fibs
      1, (2,  3, 5,  8, 13, ...)      -- tail fibs
    + ==========================
      (2, 3,  5, 8, 13, ...)          -- zipWith (+)

This declaration:

    fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

is merely the previous recurrence diagram translated into code. That is why I consider it an elegant definition.

One simple reason to not have tail-call elimination is the "nice stack traces" that are so useful in Python.

This one reason is somewhat OK, but note that these "nice stack traces" are not really that useful in functional languages (Erlang being a prominent example). It's a self-inflicted thing that full stack traces are that useful in Python.

Stack traces are not a very good argument. As a general rule, you should write your programs to be flawless. Only if you are unsure about a particular piece of code, then can you manually add debugging information, at your own expense.

Not a very good example. The n-th term of the Fibonacci sequence can be computed straightforwardly with an imperative loop:

    def mul(a,b,c,d):
        x = a*c + a*d + b*c
        y = a*c + b*d
        return x,y
    
    def fib(n):
        a,b,c,d = 0,1,1,0
        while n:
            while n % 2 == 0:
                c,d = mul(c,d,c,d)
                n //= 2
            a,b = mul(a,b,c,d)
            n -= 1
        return a

IMO a better example is a loop where a producer and a consumer interact in the following way:

(0) Get an element from the producer. If the producer is depleted, exit the loop.

(1) Put the element into the consumer. If the consumer is saturated, exit the loop.

With mutual recursion, you can do something like:

    (*  Standard ML syntax. This can be easily adapted to other languages.
     *  
     *  Naming convention:
     *  
     *    is: input stream
     *    os: output stream
     *    il: input leftovers
     *    ol: output leftovers
     *  
     *  Input/output are as in C++'s input/output iterators. In fact, this
     *  code is essentially C++'s std::transform, except not retarded.
     *)
    
    structure I : INPUT_STREAM = ...
    structure O : OUTPUT_STREAM = ...
    
    datatype result = Depleted of I.leftovers * O.stream
                    | Saturated of I.stream * O.leftovers
    
    fun first (is, os) =
      case I.fetch is of
          I.Cont (x, is) => second (x, is, os)
        | I.Done il => Depleted (il, os)
    
    and second (x, is, os) =
      case O.store (x, os) of
          O.Cont os => first (is, os)
        | O.Done ol => Saturated (is, ol)

Note how either `first` or `second` can break the loop by simply not calling the other. With an imperative loop, you have three choices, none of them pleasant:

(0) Assume that input streams cannot be depleted.

(1) Assume that output streams cannot be saturated. This is what C++'s `std::transform` does.

(2) Use an ugly “break” in the middle of the loop.

Let me copypaste a part of a previous comment I made:

When compiling/transpiling/whatever between languages, I have found that relying on regular procedure calls and TCO is generally a lot simpler than having to force the looping facility of one language into the semantics of another language.

I have written a guile scheme macro that more or less copies racket's for loops, and there are a lot of subtle things that would make using something else than tail recursive functions hard to use since I would have to work around the implicit behaviour of whatever looping facility I am trying to use.

+10

TCO is indispensable, when a language is used as the target language for a compiler.

Reply on news.ycombinator.com