Tail Recursion and Debugging (2011)

http://funcall.blogspot.com/2011/03/tail-recursion-and-debugging.html

by lelf • 6 years ago

59 24 6 years ago

funcall.blogspot.com

rjmunro• 6 years ago

You don't get a stack trace from an ordinary loop, but somehow we manage. As long as it is clear that tail recursion happened, not having a complete stack trace doesn't seem like the end of the world.

ufo• 6 years ago

I think this might be what the author was trying to say with that inscrutable stack trace that they weaved between the various quotes. It would be reasonable to argue that all those FilterDefinition.doFilter are making it harder to debug the stack trace, not easier.

braythwayt2• 6 years ago

The equally interesting implication of your comment that "we don't get a stack trace from an ordinary loop" is that maybe we should have logging and introspection the behaviour of loops, and the fact that we have them for function invocation but not for loops is combination of a historical accident and a lack of interest in rethinking how languages are implemented.

pkaye• 6 years ago

What information should be logged? And if the loop iterates for a million times, should we log it every time?

vilhelm_s• 6 years ago

And indeed, in Scheme (the language that originally made tail recursion famous) you can get stack traces from loops too! Well, at least in one Scheme implementation, MIT Scheme.

The MIT Scheme debugger has a notion of "reductions and subproblems" [1], which basically correspond to tail calls and non-tail calls. You can step "backwards" to the previous reduction, or "upwards" to the previous subproblem. In terms of other programming languages, that corresponds to going back to the previous loop iteration, or going up to the previous call frame.

Behind the scenes, this is implemented using a "ring-buffer or ring-buffers" [2], which stores the values of local variables for, e.g., the last 10 iterations through a loop. So if you step back further than that you will lose history and jump back to the start of the function call.

(The second link goes to the same blog as OP, I guess he has been writing a lot on this topic!)

[1] https://www.gnu.org/software/mit-scheme/documentation/stable... [2] http://funcall.blogspot.com/2009/05/you-knew-id-say-somethin...

mannykannot• 6 years ago

Indeed; to debug either a loop or a recursive function (and whether the latter is using tail-call recursion optimization or not) you often need to see the data. Given a stack trace showing only calls without arguments, about the only extra datum you get with non-optimized recursion is how deep it went.

In terms of debugging, tail-call elimination is no worse than the optimizations typically applied to loops.

nradov• 6 years ago

Some platforms such as the JVM allow for recording debuggers which can keep a record of all opcodes executed. So developers can play back a recording and step forward and back in time to observe state changes.

agapon• 6 years ago

It's not the end of the world, of course, but sometimes it makes debugging much harder. Especially with higher optimization levels.

grantjpowell• 6 years ago

This is satire right? The author's point is that this stack trace isn't very helpful because it's repeating the same thing over and over?

mcguire• 6 years ago

The trace isn't repeating. Those are individual call stack records. It is just printing the trace as it is.

CyberDildonics• 6 years ago

They didn't say the trace was repeating.

pizlonator• 6 years ago

This is like some kind of artwork, and it’s a masterpiece.

Whether you want to see tail deleted frames or not depends a lot on how you code. I can appreciate both sides of the argument and haven’t ever really made up my own mind.

bachmeier• 6 years ago

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).

That has always been a strange argument. You can turn features on and off, so the "it's hard to debug" argument doesn't make sense. Scala added @tailrec and I don't think I've ever heard complaints about it. Clojure has recur. Both are JVM languages.

thewisenerd2• 6 years ago

oh;

I remember debugging something similar on maven due to a circular dependency somehow that only broke my team's project;

ran mvnDebug, connecting jdb; stacktrace crapped out; dumping variables, and adding the appropriate <exclusion> worked :D

that was the highlight of my sunday evening.

https://github.com/apache/maven-resolver/blob/d1d30018b990f7...

thewisenerd2• 6 years ago

it's funny how there's a framesInCommon removal for printing out stack traces; but something similar _could_ likely be added for x lines repeating y times continuously

(_could_ because I don't know how mathematically hard that is)

duckerude• 6 years ago

Here's one implementation: https://github.com/ipython/ipython/blob/be5c0545c3/IPython/c...

thamer• 6 years ago

For the JVM it's worth noting that Project Loom[1], while so far focused mainly on concurrency features like virtual threads and continuations also includes a proposal to implement better tail calls in the JVM:

it is also the goal of this project to add an even lighter-weight construct that will allow unwinding the stack to some point and then invoke a method with given arguments (basically, a generalization of efficient tail-calls). We will call that feature unwind-and-invoke, or UAI. It is not the goal of this project to add an automatic tail-call optimization to the JVM.

Since this paragraph is explicit about the feature not being "automatic", it'll be interesting to see what form this takes.

[1] https://cr.openjdk.java.net/~rpressler/loom/Loom-Proposal.ht...

nonbirithm• 6 years ago

I personally find it annoying that you can't create a full CPU benchmarking tree from function calls in LuaJIT because the debug information in tail calls is elided. That means you have to guess if a function return went up the stack multiple times and it doesn't always work. So now I'm trying to figure out other ways of profiling my code.

gumby• 6 years ago

There’s no reason a -g build couldn’t maintain a small stack of arg breadcrumbs which would go a long way to address this. Or simply don’t make a tail call for debugging builds (might be hard when you use tail call for large iterations though)

a1369209993• 6 years ago

  > 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)
  > (82 repetitions of 2 lines elided) [sic]
  > 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)

This is a tooling problem.

Tail Recursion and Debugging (2011)

Related Stories