Tail Recursion Elimination (2009) | Hacker News Reader

Tail Recursion Elimination (2009)

neopythonic.blogspot.com

19 pointsmpweiher27 comments

  ...the idea that TRE is merely an optimization, which each Python implementation
  can choose to implement or not, is wrong. Once tail recursion elimination
  exists, developers will start writing code that depends on it, and their code
  won't run on implementations that don't provide it.

Someone should tell this to the amateurs over at GCC: https://godbolt.org/z/97s5afhsq

and Clang: https://godbolt.org/z/v384noWjq

and Microsoft: https://godbolt.org/z/Wr5zrWT84

and Intel: https://godbolt.org/z/5E7Mavf7h

As we all know, because these widely-used compilers treat TCO as an optimization, C programmers have become problematically insistent on using tail recursion instead of loops.

> As we all know, because these widely-used compilers treat TCO as an optimization, C programmers have become problematically insistent on using tail recursion instead of loops.

I think you are misunderstanding. To put it another way: because, in C, the optimisation is not guaranteed, recursion is rarely used in practice. This is a shame as many problems do have a recursive structure and are best solved using recursion. It's probably the best decision for C, but not for a high-level language.

A counter-argument to the idea that TRE is merely an optimization: Why Object-Oriented Languages Need Tail Calls, by Guy Steele [1].

[1] https://web.archive.org/web/20091206042608/http://projectfor...

I’m sharing the “og” about tail recursion optimization, in case some haven’t seen it. It’s from 1977.

https://en.m.wikisource.org/wiki/Lambda:_The_Ultimate_GOTO

Guido is probably right that tail recursion is unpythonic but he seems oddly proud of this. In defending Python's design decisions, he makes a great case for the prosecution.

The first tenet of the Zen of Python:

“Beautiful is better than ugly.”

Tail recursion is beautiful in the right context. There are plenty of problems where it’s the clear, obvious, elegant way to write an algorithm. Sure, you can rewrite a tail recursive algorithm iteratively. However, not once have I seen a case where the result is easier to read, understand, and reason about than the original version.

It’s only unpythonic for the same reason multithreading is: because it’s traditionally sucked in Python. Therefore no one does it. Therefore there’s no perceived demand for it because no one’s doing it. Therefore it’s not changed to make it easier to work worth. Therefore no one does it. Lather, rinse, and repeat.

I love Python, but there are a few corner cases like this that drive me to drink.

There's a great (and readable) paper [1] that provides a really strong motivation for TCO in my opinion: the paper shows how to make a language for describing finite state machines with macros. The surface-syntax gets transformed by the macro system into tail-recursive function calls. Without TCO, there's a limit to the number of states you can walk between before your stack gets full. With TCO, you can naturally transition between states without any issue.

Can you build a FSM with, say, an object? Of course. Encoding a FSM with functions comes with benefits though. A big one is that it's harder to get a state encoding error: if you represent your state with an integer, string, or atom, then any value of the right type would suffice, and you could transition to a "state" that doesn't exist. (A good type system can mitigate this significantly.) With functions, however, you'd get a compile-time check that all your states exist.

It's nice having a choice between different ways of encoding FSMs and other constructs. This is probably my biggest beef with Python: a limitation that doesn't exist in other languages that changes how I have to write my code.

I have run into this stack limit in real code. I was building a little classical AI program (might have been negamax; might have been some other search algorithm) and I found a beautiful tail-recursive solution. It was pure and functional and easy to test. It worked on my little test cases, but blew up with a stack error when I ran it on the full-size problem. Had to refactor my code to use some ugly state. Booooo

[1]: Krishnamurthi, Shriram. Educational pearl: Automata via Macros. Journal of Functional Programming. 2006

https://cs.brown.edu/~sk/Publications/Papers/Published/sk-au...

> unfortunately Python's compiler cannot reliably determine whether any particular call is actually reference the current function, even if it appears to have the same name.

Interesting and unfortunate. Is this still the case in 2024?

Yes, I believe that this is due to how python lets you dynamically redefine functions even to violate lexical scoping. So in the author's example:

  def f(x):
      if x > 0:
          return f(x-1)
      return 0
  # Here is where a compiler might assume that f(x) is tail recursive, and so do TCE
  g = f
  def f(x):
     return x
  g(5)

So according to the python standard, g(5) returns 4, since it calls the original f, but then the first recursive call will go to the new f. If f was TCE'd, then it would return 0, as the actual recursion would be eliminated, so it wouldn't matter that you've reassigned f to a new function.

> dynamically redefine functions even to violate lexical scoping

When would someone want to do this?

Let's say you had a library function foo, which takes no arguments, does an expensive computation, and then prints a single result to the console. You need the function to instead return the value, so that you can do more computation on it. You could write a wrapper function that will call foo, but replace the print function with one that records the printed result.

For example:

  def foo():
      print('usually this value is inaccessible from "python land"')
  def extract_printed_values(bar):
      global print
      old_print, returnv = print, None
      def new_print(x):
          nonlocal returnv
          old_print(returnv := x)
      print = new_print
      bar()
      print = old_print
      return returnv
  fooval = extract_printed_values(foo)

fooval will then be equal to whatever value foo printed to the console, otherwise foo will behave exactly the same as normal (assuming it only printed a single value), and print will even behave normally afterwards

I find that argument very unpersuasive: the optimization is tail CALL elimination, not tail RECURSION elimination, and the call to f(x-1) is certainly a tail call. I see no reason you couldn't optimize away that stack frame. "Tail recursion" is a technique in functional programming, that depends crucially on tail call elimination, but the tail call itself absolutely does not have to be recursive (it just has to be in tail position), it's just that it happens to be so in a tail recursive algorithm.

Incidentally: I don't believe that is a violation of lexical scoping. f is scoped globally, inside itself f is not defined, so f(x-1) refers to the globally scoped f. When it's reassigned, you reassign the global f. Nothing here violates lexical scoping, since f is never scoped anywhere other than globally (note that the blog post never claims it is, either)

I don't disagree with Guido's larger point, though, Python probably shouldn't use TCO. The debugging/stack trace point is very true, and also it's just not Pythonic to write algorithms TCO style. You just don't need to, in Python.

Well I mean the reason you can't optimize away the stack frame is that at any point during runtime f can be redefined to be a different function. In the above example, do you agree that any tail call elimination would result in the wrong evaluation of `g(5) = 0` instead of the correct `g(5) = 4`?

And your understanding of why python doesn't permit TCE is because functions are globally scoped with indefinite extent?

> In the above example, do you agree that any tail call elimination would result in the wrong evaluation of `g(5) = 0` instead of the correct `g(5) = 4`?

No, I very much do not agree: it is still a tail call, and can use tail call optimization. When it calls f(x-1), regardless of whether f has been reassigned or not, you have to resolve what f is, because it COULD have been reassigned. The Python interpreter has to do this regardless, the fact that it's recursive is irrelevant.

You do that, and you get the function value you need to call (it could be the original value assigned to f, it could be the new value, it doesn't matter). At that point, nothing that is remaining on the stack frame except the arguments and return address is needed anymore, so you can reuse it for the the call to f(x-1). That is what tail call elimination is.

I'll grant that it's entirely possible that I've misunderstood this whole thing and that Guido is correct (he's a much smarter fella than me), but if so, I have no idea why I'm wrong.

> And your understanding of why python doesn't permit TCE is because functions are globally scoped with indefinite extent?

No, not at all, that was just a side note about why you were wrong to say it violated lexical scoping (it doesn't). My understanding of why Guido didn't do this is because he didn't think tail call elimination is a very useful feature for Python, and it destroys stack traces. Both of which I agree with. I just don't buy the other technical reason.

It’s somewhat unclear, but in this case Guido is responding directly to a particular - broken - attempt to add TCO to self-tail calls to CPython in the fashion described. I assume, having not read the linked article, that the author must have done that as a quick hack - because CPython’s bytecode must allow arbitrary jumping within a function body but doesn’t have the means to express a true tail call. I guess.

He goes on, later in the post, to describe how he’d go about adding tail calls - although this treatment is also confused.

What amuses me is that he goes on to explain how you'd retain the existing Python behavior and still do a tail call optimization. You have to retain the late binding by not converting the call-return into a jump but instead to a special new call_return which still performs the lookup (to satisfy late binding) and can reuse the stack frame instead of generating a new one.

This would work for every instance of call-return pairs except in try statements and similar (anything that that has whatever Python calls unwind-protect). Since, in those cases, the except/finally/else of a try is code that may be executed (or is always executed in the case of the finally) after the call but before the return.

So it really does come down to a desire to prevent the use of deep call stacks (auto-recursion is just one case that would have been optimized here) rather than a true technical limitation. This could even have been brought in incrementally over the years and provided as an option.

I feel like this part has little to do with TCO and TFA is overly focused on the recusion part of things. Even in the case of that example, there's still a function that directly returns the result of another function call. That's a tail call and can be optimized the same way it could if it were recusion optimized to reuse the current stack frame.

> The first observation is that you can't do it at compile time. I've seen at least one blog entry that used a bytecode hack to replace a CALL opcode immediately before a RETURN opcode with a jump to the top of the function body. This may be a nice demo, but unfortunately Python's compiler cannot reliably determine whether any particular call is actually reference the current function, even if it appears to have the same name.

Tail call elimination should handle mutual recursion too, so this is completely unnecessary to check, and any CALL in tail position should become a tail call. Ironically I found this post from https://news.ycombinator.com/item?id=40504141 which is all about using mutual recursion to encode automata.

Funny how Python has a reputation as a functional language when it intentionally doesn’t have the features required to write in that style.

Does it, though? This is the first time I'm hearing about this. In fact I'd say that Python is known for the complete opposite (e.g. wrt lambdas, map, filter etc)

It's probably the number types and the syntax that make Python interesting for all these cases usually dealt with by functional languages.

JS got big int just some time ago.

Large number of developers think that FP is simply lambdas, map, filter and reduce. From this false premise, they dismiss the need for true functional programming languages.

Fair enough. Though I don't understand how that relates to your original point. For what it's worth I can _kinda_ understand the point that Guido's making here.

Some prior discussions.

https://news.ycombinator.com/item?id=574566 - 48 points by mace on April 22, 2009 (13 comments)

https://news.ycombinator.com/item?id=16671987 - 13 points by tosh on March 25, 2018 (11 comments)

https://news.ycombinator.com/item?id=40471476 - 3 points by ibobev 3 days ago (2 comments)

we need more (not in Python) programming examples.

aka poorly thought-through dog's dinner of a language now presents all kinds of issues when trying to add modern features.

Reply on news.ycombinator.com