Friday, March 16, 2012

Tail recursion in Python

[Python-Dev] Proper tail recursion

If tail-call elimination is an optimization, it is the kind of optimization that you have to keep your eye on: if you've been writing your code thinking it's there, it better really be there. Tail-call elimination can make or break a program. Run a tail-recursive loop that services requests indefinitely, and you'll see it's not just an optimization whether the stack grows with each call.

Still, tail recursion is not everybody's style. As Guido says:

I don't think it's a good idea to try to encourage a Scheme-ish "solve everything with recursion" programming style in Python.

And there's the truth: Python's goal is to restrict your programming style. Why are the following awkward (albeit possible) in Python?

  • Lazy evaluation

  • Sum-of-product types (as in Haskell)

  • Enforced private members / fix the set of fields for a class

  • Tail recursion

  • User-defined control structures (as in Scala or Ruby)

  • User-defined literals, syntax, pattern matching, or any extention to the basic building blocks of the language.

They are awkward because there was another way of doing it, and, when there's more than one way of doing it, Python makes a choice.

Now, I must be honest, if every language took it upon itself to enforce a particular style I would not find that exquisitely pleasant. I am grateful that languages like Scala and C++ and Ruby exist. But I am also glad that we have at least one language we can reach for when we need a homogeneous style.

Personally, I turn to a functional style when I can. And, yes, the awkwardness of functional programming in Python does occasionally irritate me ("Python: As much Lisp as a C programmer can (under)stand." -- Nathan Sanders). But, at the end of the day, when I go to push my changes, that irritation is more than offset by a tiny feeling of confidence in the code I just wrote that someone else will understand it.

No comments:

Post a Comment