Wednesday, March 30, 2011

Tail recursion and debugging

java.lang.NullPointerException
        at java.io.FilterInputStream.close(FilterInputStream.java:172)
        at sun.net.www.protocol.jar.JarURLConnection$JarURLInputStream.close(JarURLConnection.java:108)
        at com.alba.vware.ResourceServlet.doGet(ResourceServlet.java:396)
        at javax.servlet.http.HttpServlet.service(HttpServlet.java:617)
        at javax.servlet.http.HttpServlet.service(HttpServlet.java:717)
        at com.alba.vware.ServletDefinition.doService(ServletDefinition.java:261)
        at com.alba.vware.ServletDefinition.service(ServletDefinition.java:175)
        at com.alba.vware.ManagedServletPipeline.service(ManagedServletPipeline.java:91)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:62)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
[Continued on next page]
When a tail recursion is eliminated, there's no stack frame left to use to print a traceback when something goes wrong later.
— Guido van Rossum
[Continued from previous page]
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
[Continued on next page]
The elimination of stack frames doesn't do anything for the algorithmic complexity of the code, but it does make debugging harder.
— Guido van Rossum
[Continued from previous page]
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
[Continued on next page]
My issue with this optimization is that you lose debugging information.
— Ian Bicking
[Continued from previous page]
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
[Continued on next page]
Tail recursion can be easily inlined, however it is my understanding that the Java creators specifically chose not to implement this, as it makes resultant code hard to debug (if not impossible).
— Andrew Monkhouse
[Continued from previous page]
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
[Continued on next page]
This will confuse users who inadvertently wrote something recursive (the recursion isn't obvious in the stack trace printed), and makes debugging hard.
— Guido van Rossum
[Continued from previous page]
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
[Continued on next page]
I am a big fan of being able to get stack backtraces when I have a problem to debug. But tail call recursion silently throws away stack frames. You get great performance benefits from doing so, but I'd like an option when debugging to get at the information that has been thrown away.
— btilly
[Continued from previous page]
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
[Continued on next page]
I'm uninterested in optimizing tail recursion.
— Guido van Rossum
[Continued from previous page]
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.ManagedFilterPipeline.dispatch(ManagedFilterPipeline.java:118)
        at com.alba.vware.Filter.doFilter(Filter.java:113)
        at com.alba.vware.FilteredServlet$Chain.doFilter(FilteredServlet.java:176)
        at com.alba.vware.FilteredServlet.service(FilteredServlet.java:145)
        at com.alba.vware.HttpConnection.runServletFromWithinSpan(HttpConnection.java:933)
        at com.alba.vware.HttpConnection.access$000(HttpConnection.java:71)
        at com.alba.vware.HttpConnection$1.runServletFromWithinSpan(HttpConnection.java:854)
        at com.alba.vware.TraceHelper$TraceableServletRunnable$2.run(TraceHelper.java:467)
        at com.alba.vware.LocalTraceSpanRunnable.run(LocalTraceSpanRunnable.java:56)
        at com.alba.vware.LocalTraceSpanBuilder.run(LocalTraceSpanBuilder.java:518)
        at com.alba.vware.TraceHelper$TraceableServletRunnable.beginNewTrace(TraceHelper.java:411)
        at com.alba.vware.TraceHelper$TraceableServletRunnable.runWithTracingEnabled(TraceHelper.java:377)
        at com.alba.vware.TraceHelper$TraceableServletRunnable.run(TraceHelper.java:339)
        at com.alba.vware.HttpConnection.runServlet(HttpConnection.java:850)
        at com.alba.vware.HttpConnection.run(HttpConnection.java:815)
        at com.alba.vware.DispatchQueue$WorkerThread.run(DispatchQueue.java:379)
The default value for thread stack size is 128K for 32-bit server and 256K for 64-bit server.
— Java manual

15 comments:

John Cowan said...

This deserves to be written up somewhere in letters of gold. 14,907 of them, to be exact.

ob said...

Awesome post. Thank you.

Nilanjan Raychaudhuri said...

Sweet

! said...

best counter-argument ever, thank you

Manuel Simoni said...

Entertaining? Yes.

Convincing? As convincing as any strawman.

Mohamed Samy said...

I've been thinking about a possible best-of-both-worlds solution which I think would be quite useful if correct; but I'm not so sure about its correctness (because if it were correct and useful, then why have I never heard about anyone using it?).

Assume that the program is running on a virtual machine, and this VM has two modes for debugging and deployment.

In 'deploy' mode tail call elimination works normally, and performance is good.

In 'debug' mode, however, we don't want to show *all* calls because that would change the asymptotic space complexity of the program, instead we want to show enough information to be useful but keep the complexity...how so? The trick is based on the idea that the space complexity will change only of there is a cycle in a sequence of tail calls. The VM would monitor such cycles and 'clean up' or 'compress' the stack once it found one.

So to try it on the classic odd/even example:

even(n)
{
if(n = 0)
return true
else
return odd(n-1)
}

odd(n)
{
if(n = 0)
return false
else
return even(n-1)
}

main()
{
even(5)
}

Now suppose odd(n) threw an exception at n=0, the stack trace in debug mode would look like this:

[ odd n = 0]
[ even n = 5 -> even n=1; cycle]
[ main ]

So in summary:
* For 'deploy' mode, TCE works normally.
* For debug mode, all calls (tails or otherwise) are shown in the stack trace as long as there are no cycles.
* In the case of a cycle of tail calls fa(), fb(), ....fa() all the inner tails calls will be eliminated, leaving a special 'frame' representing an unknown sequence of calls starting and ending with fa(). This preserve's the space complexity requirement but still gives a hint of what was happening during program execution.
-----------------------------
Now I'm waiting for someone to point out the (probably obvious) mistake in this...

Gareth Rees said...

When an ordinary loop returns to the start, there's no stack frame left to use to print a traceback either. And yet somehow we've managed all these years without loop tracebacks.

Mihai Maruseac said...

@Mohamed Samy
They have tried to implement something like this for Haskell (lazy and TCO) and it is not widely used. At least, it is not recognized as solving the Haskell's lack of stack traces.

@Gareth Rees
The problem is that people understand loops but recursion is harder. Even more hard would be to reason about combinators like in Haskell or similar other programming language.

Mihai Maruseac said...

Also, there always should be a clear separation of when to use recursion calls in the stack trace and when to omit them. This should be always configurable in the debugger.

Ian Bicking said...

Mostly this looks like a demonstrating of a UI issue with the formatting of tracebacks ;)

There are other likely cases where that same overflow exception will catch unintended infinite recursion and tail call elimination would not. And it's not actually demonstrated tail call elimination would work here -- deliberately invoking tail call elimination is difficult and fragile, and involves low-level details of the languages execution model -- it's not simply syntactic (though dangerously it appears to be).

If you need deep nesting there are other ways to attain it without successive function invocations, and though it requires rearranging your program that would still be just as true if you were to make use of tail call elimination.

voidlizard said...

Great. Thanks.

John Clements said...

In case it's not obvious: for those of you who want to have your cake and eat it too, proper-tail calling is not incompatible with a system that retains the last 'n' tail calls for a fixed value of 'n'. I learned of this trick from Matthias Blume, though it may not originally be his.

Mark Hughes said...

You're using a Java servlet stack trace to argue with a strawman that Python should have TCE?

Not only wrong target, but that's a design flaw of the servlet spec, it should be an array of filters to loop over, not a chain.

The best way to eliminate tail calls is by eliminating recursion. Recursion is a crutch for mathematicians who can't be bothered to learn how to program a real computer.

rocky said...

I like the idea of improving stack tracebacks to detect recursion and giving a number of times the entry repeats. I'll put it on my list of things to do for the trepanning debuggers
(e.g. http://rubygems.org/search?query=trepanning)

John Cowan said...

John Clements: Indeed, Chicken works like this: you get a traceback of the last N calls whether tail-recursive or not. At the C level, it is a stack traceback, because Chicken implements all calls and as non-tail-recursive C calls and then kills the C stack every so often.