6 ms·

Worth reading why python doesn’t have it either http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html http://neopythonic.blogspot.com/2009/04

by leoh 4y ago

Worth reading why python doesn’t have it either http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html http://neopythonic.blogspot.com/2009/04/tail-recursion-elimi...

duxup 4y ago
> Python's default is and should always be to be maximally helpful for debugging. I can’t say I understand the whole topic but when someone who knows more than me says that…. It is a pretty compelling argument to me.
- ynniv 4y ago
  It's kind of a weird argument though. How do you expect a for loop to be represented in a stack trace?
  - foldr 4y ago
    The problem that’s hard to get around is this: https://github.com/elixir-lang/elixir/issues/6357 https://github.com/elixir-lang/elixir/issues/6357 Tail calls don’t have to be recursive. See also this old thread: https://news.ycombinator.com/item?id=5376924 https://news.ycombinator.com/item?id=5376924
    - ynniv 4y ago
      Good point, but surely there's a compromise somewhere. Keep the first TCO'd frame for reference maybe? Perfect stack traces aren't required.
      - foldr 4y ago
        Yeah, that could work in principle. However, if it's a language that’s using recursion for looping, then you'll loose that history every time you have a loop with more than n iterations (which could be quite often). Given that recursion can be indirect, you can't entirely eliminate that problem just by special casing direct recursion. It might still be better than nothing, though, I agree.
- pmelendez 4y ago
  I would opt for balance, there is a reason why some languages compile in debug and release mode, because of the tradeoffs. Having code that is optimal in performance often implies a tradeoff in debuggability. If debugging helpfulness is the major design decision of a programming language, that designer is trading off performance.
  - duxup 4y ago
    It certainly can be a trade-off. I think that's what they're saying for Python, maximizing helpful debugging > that feature.
  - layer8 4y ago
    Tail calls fundamentally isn’t (just) about performance, it’s about language capability. Tail calls allow you to recurse indefinitely (because required stack space remains constant), which is not possible without tail calls (stack grows indefinitely). For example, tail calls make it okay to recurse on variable-length user input, which would be ill-advised in languages not supporting tail calls.
    - Jtsummers 4y ago
      And not just direct recursion as is often considered. Mutual recursion is also handled neatly by this permitting you to write very clear state machines via functions and mutual recursion, if the tail calls get optimized. Very handy for parsing and similar tasks.
- crdrost 4y ago
  So the whole topic is not terribly hard to understand. When you see return f(x', y', z') in some function g, then g's stack frame just describes a forwarding proxy, “let me take the value returned by f and hand it to whoever called me.” And like with all forwarding proxies you can just delete the middleman and it works fine. You would do this because it gives you an alternate, debatably simpler, model for looping. In other loops you either have to return out midloop, or have to explicitly marshal your inputs and outputs of each step into mutable variables, see. So here is the same loop written two ways, the second is probably less familiar to you: function fib(n) { let curr=0, last=1; for (let i = 0, i < n; i++) { [ curr, last ] = [curr + last, curr]; } return curr; } function fib(n, i=0, curr=0, last=1) { if (n == i) return curr; return fib(n, i + 1, curr + last, curr); } These are only different styles for the same thing if you can trust that the call stack does not overflow in the second, which it doesn't have to because it returns a call to a function. So the problem is, if you have too many forwarding proxies in a chain, the language gives up on you. Guido gives four reasons, you are quoting the first. The counterpoint there is, tail calls are just rewrites for looping constructs, as Guido admits in point 3. Should we ban loops as not “maximally helpful for debugging” because not every iteration appears on error stack frames? Perish the thought! So at the end of the day that one just turns out to be, I am a lazy developer and don't want to figure out how to track this looping info in a way that makes sense outside of the call stack, the call stack exists and works, let's just keep it. And like, that's respectable! The other 3 reasons are better? Reason 2 is correct, Python has multiple implementations and they'd all have to play, cf. the OP where JS implementations didn't. Reason 3 is correct but unimaginative, there's no reason you can't write a loop in this style and use Python's data structures, for that matter you can write in this style and not use any data structures, like the example above! Because the technical objection isn't really there, again, this boils down to just, Guido wants to read Python code and he finds recursion hard to read, and wants the language to make it deliberately slow so that he never has to read it. That one is valid, but it sounds almost borderline unethical? And I will admit that reason 4 fooled me at first! This appears to be a damning problem but in fact it's just smoke and mirrors, right? “I might not know who the forwarding proxy is forwarding in advance.” Yes that's true but we can agree that the forwarding proxy is unnecessary no matter what it is forwarding. Sure, your language sucks at referential transparency, but if you are conflating these two things you are confusing the issue, no? Okay, so I started out this comment wanting to defend Guido and here I am at the end disagreeing with him...
MrBuddyCasino 4y ago
Pretty good arguments in there: - TCO only addresses recursion that can easily be replaced by a loop - loosing stack frames makes debugging harder - its not just an optimization, as soon as code depends on it to not blow the stack its a required feature for all implementations - functional languages with no side effects need recursion, everyone else really doesn't Personally, I think TCO is bad in a similar way as async functions. It is an exception from the general mental model of how function calls work, makes tooling much more complex and the alternative is just writing a loop, which I know is beneath the average Lambda The Ultimate subscriber, but its just how some people earn their money.
- vgatherps 4y ago
  Being able to guarantee tail calls is a useful optimization in far more cases than code replaceable by loops. I’ve used it myself where dispatch targets themselves are dynamic (so can’t be trivially made into a loop) for significant performance gains. Some other folks who’ve done the same thing (and can post publicly) for code that’s not just “must recurse because loops are for lowly imperative serfs”: * https://blog.reverberate.org/2021/04/21/musttail-efficient-interpreters.html https://blog.reverberate.org/2021/04/21/musttail-efficient-i... * http://lua-users.org/lists/lua-l/2011-02/msg00742.html http://lua-users.org/lists/lua-l/2011-02/msg00742.html * https://cantortrading.fi/rust_decimal_str/ https://cantortrading.fi/rust_decimal_str/ Now does JavaScript really need/care about any of this? Probably not.
  - MrBuddyCasino 4y ago
    Interesting use case, didn't occur to me that tail calls can also just be a performance optimisation technique to help out the compiler and branch predictor. I assumed hot loops could be implemented just as well using GOTOs, but maybe not?
    - vgatherps 4y ago
      Tail calls are basically GOTOs, yeah. The bring a HUGE benefit of very clearly defining state flow between gotos which makes the compiler's job super easy.
nabla9 4y ago
Also. Final Words on Tail Calls http://neopythonic.blogspot.com/2009/04/final-words-on-tail-calls.html http://neopythonic.blogspot.com/2009/04/final-words-on-tail-... Outside pure functional languages, I think the best way to implement them is to have explicit tail call declaration for functions and/and tail positions and ability to disable them for debugging (or have debugger aware of them). This way you can actually use them to implement useful stuff and rely on them. You get a compiler error if tail call can't be implemented.
- dmitriid 4y ago
  > Outside pure functional languages Erlang isn't pure, and has tail calls without an explicit syntax.
cerved 4y ago
I'm guessing it's the same reason it doesn't have a reduce function, Guido loves loops
- __alexs 4y ago
  You what? https://docs.python.org/3/library/functools.html?highlight=reduce#functools.reduce https://docs.python.org/3/library/functools.html?highlight=r...
  - phyrex 4y ago
    No, he's right. It got 'demoted' from a core function to a footnote in a module. See also https://blog.finxter.com/about-guidos-fate-of-reduce-in-python-3000/ https://blog.finxter.com/about-guidos-fate-of-reduce-in-pyth...
    - __alexs 4y ago
      No he's wrong. Python the language and Python the standard library are not separate things.
      - cerved 4y ago
        no I'm right > So in my mind, the applicability of reduce() is pretty much limited to associative operators, and in all other cases it's better to write out the accumulation loop explicitly. https://www.artima.com/weblogs/viewpost.jsp?thread=98196 https://www.artima.com/weblogs/viewpost.jsp?thread=98196
  - coldtea 4y ago
    Grantparent is right. What you pointed to is in functools, a "functional" utility package in the stdlib, which has even more exotic stuff. But Python doesn't have a reduce function as a primitive, and Guido and co discourage such uses. So much so, that Python 2 did have, and it was explicitly removed.
patrec 4y ago
Worth reading only if "because ignorance" is useful knowledge to you. In any case, you'd be better off starting at http://funcall.blogspot.com/2009/04/you-knew-id-say-something.html http://funcall.blogspot.com/2009/04/you-knew-id-say-somethin..., which tries to clear up some of the misconceptions Guido was laboring under at the time.

by leoh 4y ago

Worth reading why python doesn’t have it either http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html http://neopythonic.blogspot.com/2009/04/tail-recursion-elimi...

duxup 4y ago

> Python's default is and should always be to be maximally helpful for debugging. I can’t say I understand the whole topic but when someone who knows more than me says that…. It is a pretty compelling argument to me.

ynniv 4y ago
It's kind of a weird argument though. How do you expect a for loop to be represented in a stack trace?
- foldr 4y ago
  The problem that’s hard to get around is this: https://github.com/elixir-lang/elixir/issues/6357 https://github.com/elixir-lang/elixir/issues/6357 Tail calls don’t have to be recursive. See also this old thread: https://news.ycombinator.com/item?id=5376924 https://news.ycombinator.com/item?id=5376924
  - ynniv 4y ago
    Good point, but surely there's a compromise somewhere. Keep the first TCO'd frame for reference maybe? Perfect stack traces aren't required.
    - foldr 4y ago
      Yeah, that could work in principle. However, if it's a language that’s using recursion for looping, then you'll loose that history every time you have a loop with more than n iterations (which could be quite often). Given that recursion can be indirect, you can't entirely eliminate that problem just by special casing direct recursion. It might still be better than nothing, though, I agree.
pmelendez 4y ago
I would opt for balance, there is a reason why some languages compile in debug and release mode, because of the tradeoffs. Having code that is optimal in performance often implies a tradeoff in debuggability. If debugging helpfulness is the major design decision of a programming language, that designer is trading off performance.
- duxup 4y ago
  It certainly can be a trade-off. I think that's what they're saying for Python, maximizing helpful debugging > that feature.
- layer8 4y ago
  Tail calls fundamentally isn’t (just) about performance, it’s about language capability. Tail calls allow you to recurse indefinitely (because required stack space remains constant), which is not possible without tail calls (stack grows indefinitely). For example, tail calls make it okay to recurse on variable-length user input, which would be ill-advised in languages not supporting tail calls.
  - Jtsummers 4y ago
    And not just direct recursion as is often considered. Mutual recursion is also handled neatly by this permitting you to write very clear state machines via functions and mutual recursion, if the tail calls get optimized. Very handy for parsing and similar tasks.
crdrost 4y ago
So the whole topic is not terribly hard to understand. When you see return f(x', y', z') in some function g, then g's stack frame just describes a forwarding proxy, “let me take the value returned by f and hand it to whoever called me.” And like with all forwarding proxies you can just delete the middleman and it works fine. You would do this because it gives you an alternate, debatably simpler, model for looping. In other loops you either have to return out midloop, or have to explicitly marshal your inputs and outputs of each step into mutable variables, see. So here is the same loop written two ways, the second is probably less familiar to you: function fib(n) { let curr=0, last=1; for (let i = 0, i < n; i++) { [ curr, last ] = [curr + last, curr]; } return curr; } function fib(n, i=0, curr=0, last=1) { if (n == i) return curr; return fib(n, i + 1, curr + last, curr); } These are only different styles for the same thing if you can trust that the call stack does not overflow in the second, which it doesn't have to because it returns a call to a function. So the problem is, if you have too many forwarding proxies in a chain, the language gives up on you. Guido gives four reasons, you are quoting the first. The counterpoint there is, tail calls are just rewrites for looping constructs, as Guido admits in point 3. Should we ban loops as not “maximally helpful for debugging” because not every iteration appears on error stack frames? Perish the thought! So at the end of the day that one just turns out to be, I am a lazy developer and don't want to figure out how to track this looping info in a way that makes sense outside of the call stack, the call stack exists and works, let's just keep it. And like, that's respectable! The other 3 reasons are better? Reason 2 is correct, Python has multiple implementations and they'd all have to play, cf. the OP where JS implementations didn't. Reason 3 is correct but unimaginative, there's no reason you can't write a loop in this style and use Python's data structures, for that matter you can write in this style and not use any data structures, like the example above! Because the technical objection isn't really there, again, this boils down to just, Guido wants to read Python code and he finds recursion hard to read, and wants the language to make it deliberately slow so that he never has to read it. That one is valid, but it sounds almost borderline unethical? And I will admit that reason 4 fooled me at first! This appears to be a damning problem but in fact it's just smoke and mirrors, right? “I might not know who the forwarding proxy is forwarding in advance.” Yes that's true but we can agree that the forwarding proxy is unnecessary no matter what it is forwarding. Sure, your language sucks at referential transparency, but if you are conflating these two things you are confusing the issue, no? Okay, so I started out this comment wanting to defend Guido and here I am at the end disagreeing with him...

MrBuddyCasino 4y ago

Pretty good arguments in there: - TCO only addresses recursion that can easily be replaced by a loop - loosing stack frames makes debugging harder - its not just an optimization, as soon as code depends on it to not blow the stack its a required feature for all implementations - functional languages with no side effects need recursion, everyone else really doesn't Personally, I think TCO is bad in a similar way as async functions. It is an exception from the general mental model of how function calls work, makes tooling much more complex and the alternative is just writing a loop, which I know is beneath the average Lambda The Ultimate subscriber, but its just how some people earn their money.

vgatherps 4y ago
Being able to guarantee tail calls is a useful optimization in far more cases than code replaceable by loops. I’ve used it myself where dispatch targets themselves are dynamic (so can’t be trivially made into a loop) for significant performance gains. Some other folks who’ve done the same thing (and can post publicly) for code that’s not just “must recurse because loops are for lowly imperative serfs”: * https://blog.reverberate.org/2021/04/21/musttail-efficient-interpreters.html https://blog.reverberate.org/2021/04/21/musttail-efficient-i... * http://lua-users.org/lists/lua-l/2011-02/msg00742.html http://lua-users.org/lists/lua-l/2011-02/msg00742.html * https://cantortrading.fi/rust_decimal_str/ https://cantortrading.fi/rust_decimal_str/ Now does JavaScript really need/care about any of this? Probably not.
- MrBuddyCasino 4y ago
  Interesting use case, didn't occur to me that tail calls can also just be a performance optimisation technique to help out the compiler and branch predictor. I assumed hot loops could be implemented just as well using GOTOs, but maybe not?
  - vgatherps 4y ago
    Tail calls are basically GOTOs, yeah. The bring a HUGE benefit of very clearly defining state flow between gotos which makes the compiler's job super easy.

nabla9 4y ago

Also. Final Words on Tail Calls http://neopythonic.blogspot.com/2009/04/final-words-on-tail-calls.html http://neopythonic.blogspot.com/2009/04/final-words-on-tail-... Outside pure functional languages, I think the best way to implement them is to have explicit tail call declaration for functions and/and tail positions and ability to disable them for debugging (or have debugger aware of them). This way you can actually use them to implement useful stuff and rely on them. You get a compiler error if tail call can't be implemented.

dmitriid 4y ago
> Outside pure functional languages Erlang isn't pure, and has tail calls without an explicit syntax.

cerved 4y ago

I'm guessing it's the same reason it doesn't have a reduce function, Guido loves loops

__alexs 4y ago
You what? https://docs.python.org/3/library/functools.html?highlight=reduce#functools.reduce https://docs.python.org/3/library/functools.html?highlight=r...
- phyrex 4y ago
  No, he's right. It got 'demoted' from a core function to a footnote in a module. See also https://blog.finxter.com/about-guidos-fate-of-reduce-in-python-3000/ https://blog.finxter.com/about-guidos-fate-of-reduce-in-pyth...
  - __alexs 4y ago
    No he's wrong. Python the language and Python the standard library are not separate things.
    - cerved 4y ago
      no I'm right > So in my mind, the applicability of reduce() is pretty much limited to associative operators, and in all other cases it's better to write out the accumulation loop explicitly. https://www.artima.com/weblogs/viewpost.jsp?thread=98196 https://www.artima.com/weblogs/viewpost.jsp?thread=98196
- coldtea 4y ago
  Grantparent is right. What you pointed to is in functools, a "functional" utility package in the stdlib, which has even more exotic stuff. But Python doesn't have a reduce function as a primitive, and Guido and co discourage such uses. So much so, that Python 2 did have, and it was explicitly removed.

patrec 4y ago

Worth reading only if "because ignorance" is useful knowledge to you. In any case, you'd be better off starting at http://funcall.blogspot.com/2009/04/you-knew-id-say-something.html http://funcall.blogspot.com/2009/04/you-knew-id-say-somethin..., which tries to clear up some of the misconceptions Guido was laboring under at the time.