Tail Recursion and Debugging (2011) | Hacker News Reader

Tail Recursion and Debugging (2011)

funcall.blogspot.com

59 pointslelf24 comments

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.

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.

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.

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

It could be an option when debugging like adding a trace to your function calls. And the amount of tracing (how much is stored) could be configured.

Depending on the loop syntax, presumably you'd want to know (in the case of a for loop) what variables are initialized, what the test condition is and its result, and what is altered. But, in the case of C for loops as an example, this wouldn't be easy to automate since the user can always do something like:

  for(;;) {
    if(condition) break;
    // other logic
  }

In the best case (which would be the most data-ful case and hardest to use) you'd log all changes that occur within the loop. What you really want would be smaller, like detecting the break and the condition leading to it and watch that.

More realistically, you probably want to document your loop invariants with assertions which could be optionally recorded in your trace output.

This sounds like watchpoints which can be used both for loops and (tail-)recursive functions.

I guess you're suggesting that adding a million lines to a log is excessive. But in my math, you can count lines like this: 1, 2, 3, ..., the-number-of-lines-that-fit-in-a-window, many.

Once you have more lines than fit in a window, you've already got "many" and now it's time to talk about tooling like searching logs.

A million lines of log feels like an excessive waste intuitively, but that's only because I was brought up on 8-bit computers with 16K of RAM. Now my watch has more power than probably all of the computers I owned in the 20th century put together, and a single image it displays might have more bits than a million lines of a log file.

---

I know this stuff isn't free, but we should at least consider the possibility that what we really need are proper and comprehensive logs/traces, and a "stack trace" is nothing more than an abbreviated execution trace that just happens to be relatively cheap to collect when something goes wrong.

how hard is it to log a million messages?

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

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.

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.

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

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

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

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

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.

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?

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

They didn't say the trace was repeating.

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.

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)

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

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)

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

Reply on news.ycombinator.com