8 ms·

TCO is an optimization. When it’s a semantic language feature like in Scheme, it should be called “Tail Call Elimination” because lack of it changes program se

TCO is an optimization. When it’s a semantic language feature like in Scheme, it should be called “Tail Call Elimination” because lack of it changes program semantics (thus not merely optimization)

kazinator 6y ago
In Scheme jargon, it has come to be that a "tail call" is in fact the name of the goto-like control transfer which replaces the regular subroutine call. Tail calls are not eliminated; rather it is ensured that a function call in tail position is a tail call. This is a useful view/terminology. Without the code transformation that implements tail calls, there is nothing special about a function call in tail position; it proceeds exactly like a call not in a tail position. Therefore, it is not a different kind of call. It becomes one after the code transformation: it becomes a tail call.
- beagle3 6y ago
  I don’t like that it has no special mention. In a factorial function, fac(n-1) would be a tail call, but 0+fac(n-1) would not. It would be nice if one could annotate (and thus make the compiler verify) tail calls.
  - crististm 6y ago
    Exactly. The tail function in the second case is '+' not 'fac' so you can't replace the recursion with iteration
  - deleted 6y ago
    [deleted]
  - eru 6y ago
    > It would be nice if one could annotate (and thus make the compiler verify) tail calls. This always comes up, but honestly, I've never really run into the problem where I mistook a non-tail call for a tail call. (And I've programmed the majority of my career in languages like Haskell, OCaml and Erlang.) Of course, I'm always in favour of the compiler verifying more stuff. It just doesn't seem very pressing.
    - beagle3 6y ago
      It might be easier in those languages, but C (and C++), Scheme, Lisp and Nim have macros that could obscure a tail call's missing elimination. It was never a problem for me because I never trust the compiler to do TCE and structure my code to be independent of it. But it IS a problem.
      - zelphirkalt 6y ago
        I've not yet heavily used macros in my project, but surely have used macros others wrote, sometimes perhaps even without knowing, aside from the Scheme implementations standard forms. However, I have yet to hit a case, where I thought something was a tail call, but in the end was not. It just does not seem to come up for me and has never been a problem. Perhaps I have only used "good macros" or something, which do not make seemingly tail calls into non-tail calls?
        beagle3 6y ago
        is it possible you actually did get a non tail call where you thought it would be one, but just didn't go deep enough to blow up the stack so you weren't aware? It could be possible the call recursed "only" 10,000 times and didn't blow up any stack. Or perhaps you've only used good macros. But it is incredibly easy for a macro to end up with (+ 0 x) where you think it will end up with "x". It's also possible that you have used a macro that ended with (+ 0 x), the optimizer turned it into "x" and you got the tail call eliminated but were not guaranteed to get that, and it may blow up on another Scheme implementation. That's what I don't like about it; The compiler definitely knows if it did TCE or cannot, and it does change program semantics if it did or didn't. So why can't I just annotate the code saying "well, I intend this to TCE, please complain if you can't?"
        zelphirkalt 6y ago
        I see your point about being explicit. I think ideally the specification would be precise enough for the user to conclude: "If this is a specification conforming Scheme implementation, then this must be a tail call." I was under the impression, that this is the case with the Scheme specification, but I might be wrong, as I am not very knowledgeable in terms of the specification. If it is not so specific about what exactly becomes a tail call, then I would say, that it would be great to have an explicit way to tell the interpreter or compiler, that you want something to definitely be a tail call.
  - deleted 6y ago
    [deleted]
- DarkWiiPlayer 6y ago
  A tail call is just any call that's at the tail of a function. It might be used to refer to TCE specifically, but that's a colloquialism and would be wrong in a more technical context.
  - eru 6y ago
    Scheme 'optimizes' any tail call. Whether that's a recursive call or something else.
  - kazinator 6y ago
    If we have no plan to treat any ordinary calls as tail calls, there is no point in identifying which are in the tail position, or using any terminology related to tail calling. The conversion of a regular call to a tail call could easily be applied to non-tail positions (e.g. it could be requested by some "please make this a tail call" annotation). The tail position is where that can be done without changing the meaning (of programs that meet certain restrictions, at least). The semantics of not being able to return, and not acquiring any stack-like space is what makes the call a tail call, whether or not it is in a tail position. If we make a call that doesn't return, that call is then the last action the function performs, which puts it at the tail of its activities. The terminology also gives us nice ways to talk about vaguely related things, also, like: "execvp is a kind of big tail call in Unix; it calls a new program, such that it's impossible to return to the original, which is entirely replaced (not just the stack frame of the caller of execvp)". "A boot-loader branching into firmware is a kind of tail call."
- quietbritishjim 6y ago
  > ... goto-like control transfer which replaces the regular subroutine call. That very much sounds like a [regular subroutine] call has been eliminated. > Tail calls are not eliminated This sounds like rather delicate semantics. A call has been eliminated. It was in the tail position. It was replaced by something else, which you call the "tail call". Maybe you'd prefer RSCITLEIOTC (regular subroutine call in tail location elimination in favour of tail call)? I think tail call elimination is good enough to communicate the concept, whereas (when it's not purely an optimisation) tail call optimisation is not good enough, because calling it an "optimisation" is such a dangerous trap.
dreamcompiler 6y ago
It only changes semantics of Scheme programs that are recursive in appearance. In non-recursive Scheme functions (those that don't loop and are not mutually recursive), it's merely an optimization, just as it is in C. Edit: Added mutual recursion explicitly.
- eru 6y ago
  Well, any program that neither loops nor is recursive (the same thing in Scheme), only has a very finite runtime. So those are not very interesting Scheme programs, I guess?
- pjmlp 6y ago
  Except unlike C, it is a required feature.
OskarS 6y ago
How does it change the semantics of Scheme? It avoids blowing the stack for sure, but the stack size isn’t part of the semantics of Scheme. If you imagine a computer with arbitrary amounts of memory, then the language behaves identically with or without tail call elimination, right? The only difference is performance and memory usage, but the meaning of programs is still the same.
- rcxdude 6y ago
  it changes it from 'all functions can recurse only up to some limit' to 'functions with tail calls can recurse indefinitely' (i.e. you can write an infinite loop recursively). It's not just a performance improvement but a change in capability.
  - bachmeier 6y ago
    Aren't you adding some assumptions about the implementation in your comment? Common Lisp doesn't require TCO, but it doesn't forbid it either, and SBCL chooses to do it. Your first sentence would be incorrect for a Common Lisp program someone executes with SBCL.
    - masklinn 6y ago
      > Aren't you adding some assumptions about the implementation in your comment? You'd have a point if they were talking about implementation semantics, but they're talking about language semantics. A Scheme program can assume TCE, a CL program can not, an SBCL program can.
      - bachmeier 6y ago
        It's not clear to me that the person I replied to was talking about language semantics. The phrasing of that comment would have taken the form "may not" or "can't assume", but instead asserted that you can write some code that's guaranteed to run differently, which is implementation semantics.
tomp 6y ago
It can't not change the semantics of a language. It's basically automatic recursion-to-loop transformation (whether you call it "optimisation" or not is just a semantic issue). So obviously will turn "infinite recursion but not really because it blows the stack" into "infinite loop". But then many languages are quite loose with stack size requirement anyways, as well as stack traces (e.g. JVM's can include details about the internal implementation and/or automatic compiler transforms, e.g. concerning lambdas, methodhanles, invokedynamic etc).
- beagle3 6y ago
  If you need an infinite loop (or very large iteration count), and rely on TCE but it is not available, the semantics of your program will change. In the "best" case, you'll get a stack overflow exception. In worse cases, your exception/condition system will kick in at a time which is essentially non-deterministic (it's usually deterministic but depends on a lost of things you may have no visibility into). But if TCE is available, you might even have no allocations after some startup. That's different semantics which are part of the language (e.g. in the case of Scheme) and thus not an "optimization".
mcguire 6y ago
There are only two hard things in computer science: cache invalidation and naming things.
- JadeNB 6y ago
  > There are only two hard things in computer science: cache invalidation and naming things. There are only two hard things in computer science: off-by-one errors, cache invalidation, and naming things.

kazinator 6y ago

In Scheme jargon, it has come to be that a "tail call" is in fact the name of the goto-like control transfer which replaces the regular subroutine call. Tail calls are not eliminated; rather it is ensured that a function call in tail position is a tail call. This is a useful view/terminology. Without the code transformation that implements tail calls, there is nothing special about a function call in tail position; it proceeds exactly like a call not in a tail position. Therefore, it is not a different kind of call. It becomes one after the code transformation: it becomes a tail call.

beagle3 6y ago
I don’t like that it has no special mention. In a factorial function, fac(n-1) would be a tail call, but 0+fac(n-1) would not. It would be nice if one could annotate (and thus make the compiler verify) tail calls.
- crististm 6y ago
  Exactly. The tail function in the second case is '+' not 'fac' so you can't replace the recursion with iteration
- deleted 6y ago
  [deleted]
- eru 6y ago
  > It would be nice if one could annotate (and thus make the compiler verify) tail calls. This always comes up, but honestly, I've never really run into the problem where I mistook a non-tail call for a tail call. (And I've programmed the majority of my career in languages like Haskell, OCaml and Erlang.) Of course, I'm always in favour of the compiler verifying more stuff. It just doesn't seem very pressing.
  - beagle3 6y ago
    It might be easier in those languages, but C (and C++), Scheme, Lisp and Nim have macros that could obscure a tail call's missing elimination. It was never a problem for me because I never trust the compiler to do TCE and structure my code to be independent of it. But it IS a problem.
    - zelphirkalt 6y ago
      I've not yet heavily used macros in my project, but surely have used macros others wrote, sometimes perhaps even without knowing, aside from the Scheme implementations standard forms. However, I have yet to hit a case, where I thought something was a tail call, but in the end was not. It just does not seem to come up for me and has never been a problem. Perhaps I have only used "good macros" or something, which do not make seemingly tail calls into non-tail calls?
      - beagle3 6y ago
        is it possible you actually did get a non tail call where you thought it would be one, but just didn't go deep enough to blow up the stack so you weren't aware? It could be possible the call recursed "only" 10,000 times and didn't blow up any stack. Or perhaps you've only used good macros. But it is incredibly easy for a macro to end up with (+ 0 x) where you think it will end up with "x". It's also possible that you have used a macro that ended with (+ 0 x), the optimizer turned it into "x" and you got the tail call eliminated but were not guaranteed to get that, and it may blow up on another Scheme implementation. That's what I don't like about it; The compiler definitely knows if it did TCE or cannot, and it does change program semantics if it did or didn't. So why can't I just annotate the code saying "well, I intend this to TCE, please complain if you can't?"
        zelphirkalt 6y ago
        I see your point about being explicit. I think ideally the specification would be precise enough for the user to conclude: "If this is a specification conforming Scheme implementation, then this must be a tail call." I was under the impression, that this is the case with the Scheme specification, but I might be wrong, as I am not very knowledgeable in terms of the specification. If it is not so specific about what exactly becomes a tail call, then I would say, that it would be great to have an explicit way to tell the interpreter or compiler, that you want something to definitely be a tail call.
- deleted 6y ago
  [deleted]
DarkWiiPlayer 6y ago
A tail call is just any call that's at the tail of a function. It might be used to refer to TCE specifically, but that's a colloquialism and would be wrong in a more technical context.
- eru 6y ago
  Scheme 'optimizes' any tail call. Whether that's a recursive call or something else.
- kazinator 6y ago
  If we have no plan to treat any ordinary calls as tail calls, there is no point in identifying which are in the tail position, or using any terminology related to tail calling. The conversion of a regular call to a tail call could easily be applied to non-tail positions (e.g. it could be requested by some "please make this a tail call" annotation). The tail position is where that can be done without changing the meaning (of programs that meet certain restrictions, at least). The semantics of not being able to return, and not acquiring any stack-like space is what makes the call a tail call, whether or not it is in a tail position. If we make a call that doesn't return, that call is then the last action the function performs, which puts it at the tail of its activities. The terminology also gives us nice ways to talk about vaguely related things, also, like: "execvp is a kind of big tail call in Unix; it calls a new program, such that it's impossible to return to the original, which is entirely replaced (not just the stack frame of the caller of execvp)". "A boot-loader branching into firmware is a kind of tail call."
quietbritishjim 6y ago
> ... goto-like control transfer which replaces the regular subroutine call. That very much sounds like a [regular subroutine] call has been eliminated. > Tail calls are not eliminated This sounds like rather delicate semantics. A call has been eliminated. It was in the tail position. It was replaced by something else, which you call the "tail call". Maybe you'd prefer RSCITLEIOTC (regular subroutine call in tail location elimination in favour of tail call)? I think tail call elimination is good enough to communicate the concept, whereas (when it's not purely an optimisation) tail call optimisation is not good enough, because calling it an "optimisation" is such a dangerous trap.

dreamcompiler 6y ago

It only changes semantics of Scheme programs that are recursive in appearance. In non-recursive Scheme functions (those that don't loop and are not mutually recursive), it's merely an optimization, just as it is in C. Edit: Added mutual recursion explicitly.

eru 6y ago
Well, any program that neither loops nor is recursive (the same thing in Scheme), only has a very finite runtime. So those are not very interesting Scheme programs, I guess?
pjmlp 6y ago
Except unlike C, it is a required feature.

OskarS 6y ago

How does it change the semantics of Scheme? It avoids blowing the stack for sure, but the stack size isn’t part of the semantics of Scheme. If you imagine a computer with arbitrary amounts of memory, then the language behaves identically with or without tail call elimination, right? The only difference is performance and memory usage, but the meaning of programs is still the same.

rcxdude 6y ago
it changes it from 'all functions can recurse only up to some limit' to 'functions with tail calls can recurse indefinitely' (i.e. you can write an infinite loop recursively). It's not just a performance improvement but a change in capability.
- bachmeier 6y ago
  Aren't you adding some assumptions about the implementation in your comment? Common Lisp doesn't require TCO, but it doesn't forbid it either, and SBCL chooses to do it. Your first sentence would be incorrect for a Common Lisp program someone executes with SBCL.
  - masklinn 6y ago
    > Aren't you adding some assumptions about the implementation in your comment? You'd have a point if they were talking about implementation semantics, but they're talking about language semantics. A Scheme program can assume TCE, a CL program can not, an SBCL program can.
    - bachmeier 6y ago
      It's not clear to me that the person I replied to was talking about language semantics. The phrasing of that comment would have taken the form "may not" or "can't assume", but instead asserted that you can write some code that's guaranteed to run differently, which is implementation semantics.

tomp 6y ago

It can't not change the semantics of a language. It's basically automatic recursion-to-loop transformation (whether you call it "optimisation" or not is just a semantic issue). So obviously will turn "infinite recursion but not really because it blows the stack" into "infinite loop". But then many languages are quite loose with stack size requirement anyways, as well as stack traces (e.g. JVM's can include details about the internal implementation and/or automatic compiler transforms, e.g. concerning lambdas, methodhanles, invokedynamic etc).

beagle3 6y ago
If you need an infinite loop (or very large iteration count), and rely on TCE but it is not available, the semantics of your program will change. In the "best" case, you'll get a stack overflow exception. In worse cases, your exception/condition system will kick in at a time which is essentially non-deterministic (it's usually deterministic but depends on a lost of things you may have no visibility into). But if TCE is available, you might even have no allocations after some startup. That's different semantics which are part of the language (e.g. in the case of Scheme) and thus not an "optimization".

mcguire 6y ago

There are only two hard things in computer science: cache invalidation and naming things.

JadeNB 6y ago
> There are only two hard things in computer science: cache invalidation and naming things. There are only two hard things in computer science: off-by-one errors, cache invalidation, and naming things.