4 ms·

Do you mean Tail Call Elimination? If so, are you thinking of all tail calls, or are you more focusing on the conversion of recursive calls to iteration?

lmm 3y ago
Yes, tail call elimination. Conversion of recursion to iteration is the most common case, I don't really understand what you're asking by distinguishing between "all tail calls" and "the conversion of recursive calls to iteration". The point is it's a similar case where a seemingly innocuous refactor can break your program because the implicit TCE stops working.
- throwaway17_17 3y ago
  Regarding the distinguishing between recursive tail calls and other tail calls: The conversion of tail calls to direct jumps seems to me a simpler conversion, where refactoring would be less likely to introduce errors. The conversion of recursive calls to iteration is different, I can see how the implicit conversion could lead to much more sensitive preconditions that refactoring could cause to not be satisfied. My initial (and rather lazily considered) reaction to the potential for breakage could be wrong, I doubt it would be worth an exhaustive testing effort to validate. I find TCE to be a conversion that is worth the potential downsides in heavily functional paradigms, but I certainly sympathize with becoming more skeptical of implicit alterations to code as written.
  - lmm 3y ago
    > The conversion of tail calls to direct jumps seems to me a simpler conversion, where refactoring would be less likely to introduce errors. The conversion of recursive calls to iteration is different, I can see how the implicit conversion could lead to much more sensitive preconditions that refactoring could cause to not be satisfied. Isn't it the same thing? If you convert a tail call to a jump, if the place you jumped to leads back to the same line (directly or indirectly) then you've converted recursion to iteration. Iteration is ultimately implemented as jumps too. > I doubt it would be worth an exhaustive testing effort to validate. I find TCE to be a conversion that is worth the potential downsides in heavily functional paradigms, but I certainly sympathize with becoming more skeptical of implicit alterations to code as written. I've been bitten by it often enough to be wary. I swear I once saw a language that had an explicit keyword for tail calls (not just an annotation to error out if TCO wasn't performed, but a keyword to make a tail call and no implicit optimization), which sounded like the best solution, but I can't find it now.
    - throwaway17_17 3y ago
      Interestingly, after a relatively quick check, it seems that the tail recursive conversion is actually simpler and more predictable than in the non-recursive case. For recursive calls the stack size is always the same between the caller and callee so refactoring of the recursive function is less likely to produce errors. In the general case, where caller/callee stacks are different sizes the algorithm requires more effort and analysis to ensure the proper stack adjustments are made, and such algorithms are seemingly going to more finicky with regards to changes in either function. This certainly seems to be one of those times when my gut instinct was just absolutely backwards, so thanks for the response which prompted me to actual check my assumptions.
    - mst 3y ago
      I have a feeling it doesn't build on recent versions, but somebody implemented https://p3rl.org/Sub::Call::Tail https://p3rl.org/Sub::Call::Tail for perl and I'll presumably resurrect that next time I need it. I think for some forms of unrolling clojure's loop/recur is a neat version of a limited explicit form. Of course, I'm difficult so what -I- really want is an explicit tail-call-modulo-cons but that would be a much more involved comment than my current caffeination levels really enable.

lmm 3y ago

Yes, tail call elimination. Conversion of recursion to iteration is the most common case, I don't really understand what you're asking by distinguishing between "all tail calls" and "the conversion of recursive calls to iteration". The point is it's a similar case where a seemingly innocuous refactor can break your program because the implicit TCE stops working.

throwaway17_17 3y ago
Regarding the distinguishing between recursive tail calls and other tail calls: The conversion of tail calls to direct jumps seems to me a simpler conversion, where refactoring would be less likely to introduce errors. The conversion of recursive calls to iteration is different, I can see how the implicit conversion could lead to much more sensitive preconditions that refactoring could cause to not be satisfied. My initial (and rather lazily considered) reaction to the potential for breakage could be wrong, I doubt it would be worth an exhaustive testing effort to validate. I find TCE to be a conversion that is worth the potential downsides in heavily functional paradigms, but I certainly sympathize with becoming more skeptical of implicit alterations to code as written.
- lmm 3y ago
  > The conversion of tail calls to direct jumps seems to me a simpler conversion, where refactoring would be less likely to introduce errors. The conversion of recursive calls to iteration is different, I can see how the implicit conversion could lead to much more sensitive preconditions that refactoring could cause to not be satisfied. Isn't it the same thing? If you convert a tail call to a jump, if the place you jumped to leads back to the same line (directly or indirectly) then you've converted recursion to iteration. Iteration is ultimately implemented as jumps too. > I doubt it would be worth an exhaustive testing effort to validate. I find TCE to be a conversion that is worth the potential downsides in heavily functional paradigms, but I certainly sympathize with becoming more skeptical of implicit alterations to code as written. I've been bitten by it often enough to be wary. I swear I once saw a language that had an explicit keyword for tail calls (not just an annotation to error out if TCO wasn't performed, but a keyword to make a tail call and no implicit optimization), which sounded like the best solution, but I can't find it now.
  - throwaway17_17 3y ago
    Interestingly, after a relatively quick check, it seems that the tail recursive conversion is actually simpler and more predictable than in the non-recursive case. For recursive calls the stack size is always the same between the caller and callee so refactoring of the recursive function is less likely to produce errors. In the general case, where caller/callee stacks are different sizes the algorithm requires more effort and analysis to ensure the proper stack adjustments are made, and such algorithms are seemingly going to more finicky with regards to changes in either function. This certainly seems to be one of those times when my gut instinct was just absolutely backwards, so thanks for the response which prompted me to actual check my assumptions.
  - mst 3y ago
    I have a feeling it doesn't build on recent versions, but somebody implemented https://p3rl.org/Sub::Call::Tail https://p3rl.org/Sub::Call::Tail for perl and I'll presumably resurrect that next time I need it. I think for some forms of unrolling clojure's loop/recur is a neat version of a limited explicit form. Of course, I'm difficult so what -I- really want is an explicit tail-call-modulo-cons but that would be a much more involved comment than my current caffeination levels really enable.