10 ms·

Tail Recursion and Debugging (2011)

59 points by lelf 6y ago

gumby 6y 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)
rjmunro 6y 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 6y 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.
- braythwayt 6y 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 6y ago
    What information should be logged? And if the loop iterates for a million times, should we log it every time?
    - Jtsummers 6y ago
      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.
      - remram 6y ago
        This sounds like watchpoints which can be used both for loops and (tail-)recursive functions.
    - braythwayt 6y ago
      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.
    - heavenlyblue 6y ago
      how hard is it to log a million messages?
  - vilhelm_s 6y 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/mit-scheme-user/Subproblems-and-Reductions.html#Subproblems-and-Reductions https://www.gnu.org/software/mit-scheme/documentation/stable... [2] http://funcall.blogspot.com/2009/05/you-knew-id-say-something-part-iv.html http://funcall.blogspot.com/2009/05/you-knew-id-say-somethin...
- mannykannot 6y 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 6y 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 6y ago
  It's not the end of the world, of course, but sometimes it makes debugging much harder. Especially with higher optimization levels.
grantjpowell 6y 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 6y ago
  The trace isn't repeating. Those are individual call stack records. It is just printing the trace as it is.
  - CyberDildonics 6y ago
    They didn't say the trace was repeating.
pizlonator 6y 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 6y 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.
thewisenerd 6y 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/d1d30018b990f76e8a7b463988b1abbdc3d6944f/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/transformer/NearestVersionSelector.java#L158 https://github.com/apache/maven-resolver/blob/d1d30018b990f7...
thewisenerd 6y 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 6y ago
  Here's one implementation: https://github.com/ipython/ipython/blob/be5c0545c3/IPython/core/ultratb.py#L444 https://github.com/ipython/ipython/blob/be5c0545c3/IPython/c...
thamer 6y 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.html https://cr.openjdk.java.net/~rpressler/loom/Loom-Proposal.ht...
nonbirithm 6y 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.
a1369209993 6y 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.

59 points by lelf 6y 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)

rjmunro 6y 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 6y 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.
braythwayt 6y 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 6y ago
  What information should be logged? And if the loop iterates for a million times, should we log it every time?
  - Jtsummers 6y ago
    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.
    - remram 6y ago
      This sounds like watchpoints which can be used both for loops and (tail-)recursive functions.
  - braythwayt 6y ago
    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.
  - heavenlyblue 6y ago
    how hard is it to log a million messages?
- vilhelm_s 6y 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/mit-scheme-user/Subproblems-and-Reductions.html#Subproblems-and-Reductions https://www.gnu.org/software/mit-scheme/documentation/stable... [2] http://funcall.blogspot.com/2009/05/you-knew-id-say-something-part-iv.html http://funcall.blogspot.com/2009/05/you-knew-id-say-somethin...
mannykannot 6y 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 6y 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 6y ago
It's not the end of the world, of course, but sometimes it makes debugging much harder. Especially with higher optimization levels.

grantjpowell 6y 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 6y ago
The trace isn't repeating. Those are individual call stack records. It is just printing the trace as it is.
- CyberDildonics 6y ago
  They didn't say the trace was repeating.

pizlonator 6y 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 6y 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.

thewisenerd 6y 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/d1d30018b990f76e8a7b463988b1abbdc3d6944f/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/transformer/NearestVersionSelector.java#L158 https://github.com/apache/maven-resolver/blob/d1d30018b990f7...

thewisenerd 6y 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 6y ago
Here's one implementation: https://github.com/ipython/ipython/blob/be5c0545c3/IPython/core/ultratb.py#L444 https://github.com/ipython/ipython/blob/be5c0545c3/IPython/c...

thamer 6y 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.html https://cr.openjdk.java.net/~rpressler/loom/Loom-Proposal.ht...

nonbirithm 6y 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.

a1369209993 6y 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.