TITLE: Recursion, Trampolines, and Software Development Process AUTHOR: Eugene Wallingford DATE: September 10, 2010 2:22 PM DESC: ----- BODY: Yesterday I read an old article on tail calls and trampolining in Scala by Rich Dougherty, which summarizes nicely the problem of recursive programming on the JVM. Scala is a functional language, which lends itself to recursive and mutually recursive programs. Compiling those programs to run on the JVM presents problems because (1) the JVM's control stack is shallow and (2) the JVM doesn't support tail-call optimization. Fortunately, Scala supports first-class functions, which enables the programmer to implement a "trampoline" that avoids the growing the stack. The resulting code is harder to understand and so to maintain, but it runs without growing the control stack. This is a nice little essay. Dougherty's conclusion about trampoline code being harder to understand reminded me of a response by reader Edward Coffin to my July entry on CS faculty sending bad signals about recursion. He agreed that recursion usually is not a problem from a technical standpoint but pointed out a social problem (paraphrased):

I have one comment about the use of recursion in safety-critical code, though: it is potentially brittle with respect to changes made by someone not familiar with that piece of code, and brittle in a way that makes breaking the code difficult to detect. I'm thinking of two cases here: (1) a maintainer unwittingly modifies the code in a way that prevents the compiler from making the formerly possible tail-call optimization and (2) the organization moves to a compiler that doesn't support tail-call optimization from one that did.

Edward then explained how hard it is to warn the programmers that they have just made changes to the code that invalidate essential preconditions. This seems like a good place to comment the code, but we can't rely on programmers paying attention to such comments, even that the comments will accompany the code forever. The compiler may not warn us, and it may be hard to write test cases that reliably fail when the optimization is missed. Scala's @tailrec annotation is a great tool to have in this situation! "Ideally," he writes, "these problems would be things a good organization could deal with." Unfortunately, I'm guessing that most enterprise computing shops are probably not well equipped to handle them gracefully, either by personnel or process. Coffin closes with a pragmatic insight (again, paraphrased):

... it is quite possible that [such organizations] are making the right judgement by forbidding it, considering their own skill levels. However, they may be using the wrong rationale -- "We won't do this because it is generally a bad idea." -- instead of the more accurate "We won't do this because we aren't capable of doing it properly."

Good point. I don't suppose it's reasonable for me or anyone to expect people in software shops to say that. Maybe the rise of languages such and Scala and Clojure will help both industry and academia improve the level of developers' ability to work with functional programming issues. That might allow more organizations to use a good technical solution when it is suitable. That's one of the reasons I still believe that CS educators should take care to give students a balanced view of recursive programming. Industry is beginning to demand it. Besides, you never know when a young person will get excited about a problem whose solution feels so right as a recursion and set off to write a program to grow his excitement. We also want our graduates to be able to create solutions to hard problems that leverage the power of recursion. We need for students to grok the Big Idea of recursion as a means for decomposing problems and composing systems. The founding of Google offers an instructive example of using inductive definition recursion, as discussed in this Scientific American article on web science:

[Page and Brin's] big insight was that the importance of a page -- how relevant it is -- was best understood in terms of the number and importance of the pages linking to it. The difficulty was that part of this definition is recursive: the importance of a page is determined by the importance of the pages linking to it, whose importance is determined by the importance of the pages linking to them. [They] figured out an elegant mathematical way to represent that property and developed an algorithm they called PageRank to exploit the recursiveness, thus returning pages ranked from most relevant to least.

Much like my Elo ratings program that used successive approximation, PageRank may be implemented in some other way, but it began as a recursive idea. Students aren't likely to have big recursive ideas if we spend years giving them the impression it is an esoteric technique best reserved for their theory courses. So, yea! for Scala, Clojure, and all the other languages that are making recursion respectable in practice. -----