Abstract Heresies: 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

18 comments:

John CowanMarch 30, 2011 at 3:44 PM
This deserves to be written up somewhere in letters of gold. 14,907 of them, to be exact.
UnknownMarch 30, 2011 at 7:58 PM
Awesome post. Thank you.
Nilanjan RaychaudhuriMarch 30, 2011 at 8:07 PM
Sweet
!March 30, 2011 at 11:47 PM
best counter-argument ever, thank you
Manuel SimoniMarch 31, 2011 at 12:23 AM
Entertaining? Yes.

Convincing? As convincing as any strawman.
Mohamed SamyMarch 31, 2011 at 5:05 AM
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 ReesMarch 31, 2011 at 5:23 AM
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.
UnknownMarch 31, 2011 at 5:37 AM
@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.
UnknownMarch 31, 2011 at 5:39 AM
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 BickingMarch 31, 2011 at 10:12 AM
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.
voidlizardApril 1, 2011 at 5:59 AM
Great. Thanks.
John ClementsApril 4, 2011 at 1:13 PM
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 HughesApril 12, 2011 at 8:54 AM
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.
John CowanDecember 30, 2012 at 10:14 PM
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.
AnonymousFebruary 20, 2019 at 12:29 PM
A more detailed explanation of tail recursion can be found here https://www.byte-by-byte.com/recursion.
Pierre ThierryAugust 1, 2019 at 7:21 AM
I hope this was posted as a joke.

It's pretty sad to see how many people actually believe you cannot debug TCOed code.

First, that stack trace gives almost zero information more than a stack where frames would have been removed, because you have no arguments shown.

Second, decent development tools let you retain stacks in debug mode.
AnonymousSeptember 21, 2020 at 11:28 PM
Ever heard of grep?
AnonymousOctober 30, 2021 at 9:05 AM
"Recursion is a crutch for mathematicians who can't be bothered to learn how to program a real computer."

You're so right. Better just stick with BASIC.

Wednesday, March 30, 2011

Tail recursion and debugging

18 comments: