Tail Call Optimization

Guido van Rossum, the benevolent dictator for life of the Python language, recently posted that he does not believe Python needs to support tail call optimization (TCO). However, he demonstrates his ignorance of TCO, as do many of these comments on Reddit. What is TCO? Whenever you make a function call, the language saves your state on the stack and creates a new frame for the next function. If you make a huge number of calls, then you could potentially run out of stack space. The obvious answer, therefore, is not to write programs that make lots of recursive calls. This is acceptable for every mainstream language, none of which support TCO.

So why is TCO useful? It allows you to create complex recursive programs that behave like loops. The most common example is the least compelling:

   1: int sumList (Node n, int sum) {

   2:   if (n != null)

   3:     return sumList (n.next, sum+n.val) ;

   4:   else

   5:     return sum ;

   6: }

For very large lists, the recursive call to sumList will run out of stack space and raise an exception. TCO will adjust the recursive call to reuse the same stack frame; therefore, this recursion will work on very large lists without using any extra space. The reason this example is lame is because it can easily be rewritten to use a while loop. A better example is to use recursion for stream-based programming (just a sketch in C#-ish code):

   1: abstract class Plugin {

   2:   Plugin nextStep ;

   3:   public int Process (int input) {

   4:     return nextStep.Process (DoWork(int)) ;

   5:   }

   6:  

   7:   public abstract int DoWork (int x) ;

   8: }

   9:  

  10: stream = new ReadData (new Plugin1 (new Plugin2 (new Plugin3 ()))) ;

  11: stream.endPoint = stream ;

  12: stream.readFile (file) ;

The idea here is you can glue together any set of Plugins to build a pipeline that processes a stream of data in a big recursive circle of calls. Normally this would blow the stack, but TCO turns this into a loop that doesn’t use any extra stack space. You could rewrite this to avoid recursion, but you end up implementing a weak form of TCO yourself. When you don’t have to worry about it, you can write more complex code and trust the compiler to optimize it for you. As an analogy, you can write programs in languages that don’t have GC, but it’s annoying to manage memory manually.

Guido lists three points against the inclusion of TCO: (1) TCO doesn’t give you nice stack traces when things fail because it drops all the intermediate stack frames; (2) Once you add TCO, every implementation must support it;  (3) He doesn’t “believe in recursion as the basis of all programming”. #1 & #2 are true, but #3 is an exaggeration. Recursion is a nice feature that makes programming easier in some respects, but not the basis of everything. Instead, I think #2 is a strong argument against TCO for Python because it would be inefficient in some implementations, and very few Python programmers would understand it anyway. I just hope the next scripting fad will have this feature.

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s