7 ms·

There's a funny interaction between TCO and memory management. If you have scoped destructors (C++, Rust) then you might accidentally defeat TCO by simply decla

There's a funny interaction between TCO and memory management. If you have scoped destructors (C++, Rust) then you might accidentally defeat TCO by simply declaring a variable. GCs solve this problem by deferring collection to allocation points, but now TCO requires GC. What's the modern view here? I think it's bimodal: either TCO is a defining feature of the language, or a best-effort optimization that nobody should rely on.

Andys 6y ago
Yep. Matz disabled TCO in Ruby because it was incompatible with some alternative implementations like JRuby.
- pmontra 6y ago
  Disabled by default but it can be enabled at runtime https://ruby-doc.org/core-3.0.0/RubyVM/InstructionSequence.html#method-c-compile_option-3D https://ruby-doc.org/core-3.0.0/RubyVM/InstructionSequence.h...
haberman 6y ago
> either TCO is a defining feature of the language, or a best-effort optimization that nobody should rely on. I think a third option is that tail calls are only guaranteed if you add a special attribute (eg. [[musttail]]) and that attribute fails to compile if your code is written in such a way that a true tail call cannot be guaranteed. The LLVM backend supports a "musttail" marker on function calls (https://llvm.org/docs/LangRef.html#call-instruction https://llvm.org/docs/LangRef.html#call-instruction), but it specifies a set of constraints that must be met for "musttail" to be valid. I have been experimenting with a Clang change that would plumb a C++ [[musttail]] attribute through the C++ frontend to LLVM, but it requires some care to make sure we satisfy LLVM's constraints.
- im3w1l 6y ago
  I nominate the syntax goto function(parameter1, parameter2); Also, may I suggest that it runs destructors prior to the jump rather than throwing up it's hands and saying you can't TCO because you have destructors?
  - kccqzy 6y ago
    What about the destructors for the temporaries used in the computation or the function call parameters, or the parameters themselves?
    - im3w1l 6y ago
      Handle it the same way as a return I think. Evaluate the temporaries, move / copy into the right place, run destructors, jump? Copy elision might be hard to pull off I suppose. Edit: Hmm there is an issue in handling the stack space I suppose, because there are live old parameter objects already in the place you want to put your new parameters. An ugly but possibly workable way of handling it is to have two areas for parameters. One used for odd recursion depths and another used for even ones.
      - yakubin 6y ago
        Then you changed the semantics of the code. Now a program that e.g. prints a message in its destructor, which gives this output: Message 1 Message 2 Message 3 Will give this output: Message 3 Message 2 Message 1 Your odd/even fix also won't work, because a function may push an argument to a list, and pass the list in another argument, making the original temporary accessible from any recursion level. A call to a destructor is a normal call. If you need to call destructors, then it means your tail call is a call to a destructor and not what you're seeing in the code. It's a fundamental semantical problem. You can't have "make the last call in this function be an implicit call to some function" and "make the last call be the explicit call to this other function" at the same time.
        syrrim 6y ago
        If it's a different syntax, then you can expect people to know that it's semantically different. That's the whole point of using a different syntax, I think.
        yakubin 6y ago
- _flux 6y ago
  This is what OCaml does: you can annotate function calls with [@tailcall] to result in compiler diagnostics if the call in fact isn't in tail call position.
  - kodablah 6y ago
    Scala too with @tailrec
    - johncolanduoni 6y ago
      tailrec is more restricted: it only supports simple tail recursion (i.e. calling the same function in tail position) that can trivially be rewritten into a loop. Scala isn’t really in a position to optimize mutual tail calls, since those don’t in general collapse to loops.
- KMag 6y ago
  Speaking of TCO constraints, all of the common C/C++ calling conventions[0] have a fixed size stack cleanup. Some are caller-cleanup and some are callee-cleanup, but they all have amounts of stack cleanup that are constant (cdecl,stdcall,thiscal, etc.) or at least fixed at call time (varargs). This means that TCO can't be done across calls where the amount of stack space used for arguments in the callee is larger than that of the caller. (In cases where the stack space used by the callee is less than the caller, the caller just needs to leave "wasted" stack space as if amount of stack space used by arguments were the same.) It wouldn't be much of a point on architectures where the cdecl calling convention passes enough arguments in registers to cover the majority of functions, except that some of these ABIs (notably Windows x64 calling convetion, but not Linux x64_64 SysV ABI) require the caller to allocate shadow space on the stack for all register-passed arguments. (Edit: I was wrong, the Windows shadow space on the stack is a fixed 32 bytes, regardless of the number of register-passed arguments.) This motivates a couple of ABI questions: 1. Why does the Windows x64 ABI require the caller to pre-allocate "shadow space" to potentially spill register-passed arguments? It's wasteful if it's not needed (especially in ABIs with a redzone), and it reduces opportunities for TCO. (Edit: ahh, unlike Linux, the Windows x64 calling convention has no redzone. I guess this then becomes "Why doesn't Windows x64 provide a redzone?") 2. Why not define a calling convention that is callee-cleanup where the post-cleanup stack pointer is passed in a designated register (or at the top of the stack) to the callee? I understand that it might not make sense to pay the cost (fewer arguments passed in registers, and often an extra stack spill) for the majority of functions, but it seems an oversight that there's not a calling convention that (in the absence of destructors) always allows tail calls to be optimized. I guess the answer to both questions is that most TCO opportunities are within a single DLL, so the compiler is free to create non-exported versions of functions with custom calling conventions. Is this right? [0] https://en.wikipedia.org/wiki/X86_calling_conventions https://en.wikipedia.org/wiki/X86_calling_conventions plus their variants on other architectures
  - johncolanduoni 6y ago
    > I guess the answer to both questions is that most TCO opportunities are within a single DLL, so the compiler is free to create non-exported versions of functions with custom calling conventions. Is this right? LLVM mostly follows this path: it allows full TCO only when using the “fastcc” (i.e. “whatever LLVM feels like generating”) and some calling conventions from functional languages (like GHC) that have a specific carve out for it.
- DarkWiiPlayer 6y ago
  Alternatively, compilers could generate warnings when they find something like `return some_func(args...)`, and can't eliminate the tail-call because of something that happens elsewhere in the code.
yakubin 6y ago
It's not that it requires GC, but that it is disabled by implicit calls at the end of scope. Scoped destructors aren't only for memory management. They are also widely used for e.g. closing files or sockets, basically anything that you may think of as a resource. Go has the defer statement, which would also disable TCO, even though Go has a GC. You can call just about any function in a defer statement. You can have TCO in a language that has scoped constructors/defer statement and doesn't have a GC. It's just that the things that at first look like tail calls often aren't. But the same thing can be said about operator overloading. TCO will still be in this language, but it will only be applied to tail calls, not calls which the programmer mistakenly believed were tail calls.
noctune 6y ago
You could change the drop semantics to drop as soon as a variable is no longer used/borrowed (as opposed to now when it goes out of scope). But IMO that does not seem like it's worth it considering how less predictable it would make drop.
deleted 6y ago
[deleted]
tomp 6y ago
I don't see how that's an issue, at least for Rust. If a variable is captured by the tail-called function (i.e. the function receives the unique or borrowed pointer) then you can do TCO with an extra argument (said variable, owned/unique) and clean up at the end of the "loop". If the variable isn't captured by the tail-called function, then it's unobservable (except through side effects) if it's deallocated before the tail call.

Andys 6y ago

Yep. Matz disabled TCO in Ruby because it was incompatible with some alternative implementations like JRuby.

pmontra 6y ago
Disabled by default but it can be enabled at runtime https://ruby-doc.org/core-3.0.0/RubyVM/InstructionSequence.html#method-c-compile_option-3D https://ruby-doc.org/core-3.0.0/RubyVM/InstructionSequence.h...

haberman 6y ago

> either TCO is a defining feature of the language, or a best-effort optimization that nobody should rely on. I think a third option is that tail calls are only guaranteed if you add a special attribute (eg. [[musttail]]) and that attribute fails to compile if your code is written in such a way that a true tail call cannot be guaranteed. The LLVM backend supports a "musttail" marker on function calls (https://llvm.org/docs/LangRef.html#call-instruction https://llvm.org/docs/LangRef.html#call-instruction), but it specifies a set of constraints that must be met for "musttail" to be valid. I have been experimenting with a Clang change that would plumb a C++ [[musttail]] attribute through the C++ frontend to LLVM, but it requires some care to make sure we satisfy LLVM's constraints.

im3w1l 6y ago
I nominate the syntax goto function(parameter1, parameter2); Also, may I suggest that it runs destructors prior to the jump rather than throwing up it's hands and saying you can't TCO because you have destructors?
- kccqzy 6y ago
  What about the destructors for the temporaries used in the computation or the function call parameters, or the parameters themselves?
  - im3w1l 6y ago
    Handle it the same way as a return I think. Evaluate the temporaries, move / copy into the right place, run destructors, jump? Copy elision might be hard to pull off I suppose. Edit: Hmm there is an issue in handling the stack space I suppose, because there are live old parameter objects already in the place you want to put your new parameters. An ugly but possibly workable way of handling it is to have two areas for parameters. One used for odd recursion depths and another used for even ones.
    - yakubin 6y ago
      Then you changed the semantics of the code. Now a program that e.g. prints a message in its destructor, which gives this output: Message 1 Message 2 Message 3 Will give this output: Message 3 Message 2 Message 1 Your odd/even fix also won't work, because a function may push an argument to a list, and pass the list in another argument, making the original temporary accessible from any recursion level. A call to a destructor is a normal call. If you need to call destructors, then it means your tail call is a call to a destructor and not what you're seeing in the code. It's a fundamental semantical problem. You can't have "make the last call in this function be an implicit call to some function" and "make the last call be the explicit call to this other function" at the same time.
      - syrrim 6y ago
        If it's a different syntax, then you can expect people to know that it's semantically different. That's the whole point of using a different syntax, I think.
        yakubin 6y ago
_flux 6y ago
This is what OCaml does: you can annotate function calls with [@tailcall] to result in compiler diagnostics if the call in fact isn't in tail call position.
- kodablah 6y ago
  Scala too with @tailrec
  - johncolanduoni 6y ago
    tailrec is more restricted: it only supports simple tail recursion (i.e. calling the same function in tail position) that can trivially be rewritten into a loop. Scala isn’t really in a position to optimize mutual tail calls, since those don’t in general collapse to loops.
KMag 6y ago
Speaking of TCO constraints, all of the common C/C++ calling conventions[0] have a fixed size stack cleanup. Some are caller-cleanup and some are callee-cleanup, but they all have amounts of stack cleanup that are constant (cdecl,stdcall,thiscal, etc.) or at least fixed at call time (varargs). This means that TCO can't be done across calls where the amount of stack space used for arguments in the callee is larger than that of the caller. (In cases where the stack space used by the callee is less than the caller, the caller just needs to leave "wasted" stack space as if amount of stack space used by arguments were the same.) It wouldn't be much of a point on architectures where the cdecl calling convention passes enough arguments in registers to cover the majority of functions, except that some of these ABIs (notably Windows x64 calling convetion, but not Linux x64_64 SysV ABI) require the caller to allocate shadow space on the stack for all register-passed arguments. (Edit: I was wrong, the Windows shadow space on the stack is a fixed 32 bytes, regardless of the number of register-passed arguments.) This motivates a couple of ABI questions: 1. Why does the Windows x64 ABI require the caller to pre-allocate "shadow space" to potentially spill register-passed arguments? It's wasteful if it's not needed (especially in ABIs with a redzone), and it reduces opportunities for TCO. (Edit: ahh, unlike Linux, the Windows x64 calling convention has no redzone. I guess this then becomes "Why doesn't Windows x64 provide a redzone?") 2. Why not define a calling convention that is callee-cleanup where the post-cleanup stack pointer is passed in a designated register (or at the top of the stack) to the callee? I understand that it might not make sense to pay the cost (fewer arguments passed in registers, and often an extra stack spill) for the majority of functions, but it seems an oversight that there's not a calling convention that (in the absence of destructors) always allows tail calls to be optimized. I guess the answer to both questions is that most TCO opportunities are within a single DLL, so the compiler is free to create non-exported versions of functions with custom calling conventions. Is this right? [0] https://en.wikipedia.org/wiki/X86_calling_conventions https://en.wikipedia.org/wiki/X86_calling_conventions plus their variants on other architectures
- johncolanduoni 6y ago
  > I guess the answer to both questions is that most TCO opportunities are within a single DLL, so the compiler is free to create non-exported versions of functions with custom calling conventions. Is this right? LLVM mostly follows this path: it allows full TCO only when using the “fastcc” (i.e. “whatever LLVM feels like generating”) and some calling conventions from functional languages (like GHC) that have a specific carve out for it.
DarkWiiPlayer 6y ago
Alternatively, compilers could generate warnings when they find something like `return some_func(args...)`, and can't eliminate the tail-call because of something that happens elsewhere in the code.

yakubin 6y ago

It's not that it requires GC, but that it is disabled by implicit calls at the end of scope. Scoped destructors aren't only for memory management. They are also widely used for e.g. closing files or sockets, basically anything that you may think of as a resource. Go has the defer statement, which would also disable TCO, even though Go has a GC. You can call just about any function in a defer statement. You can have TCO in a language that has scoped constructors/defer statement and doesn't have a GC. It's just that the things that at first look like tail calls often aren't. But the same thing can be said about operator overloading. TCO will still be in this language, but it will only be applied to tail calls, not calls which the programmer mistakenly believed were tail calls.

noctune 6y ago

You could change the drop semantics to drop as soon as a variable is no longer used/borrowed (as opposed to now when it goes out of scope). But IMO that does not seem like it's worth it considering how less predictable it would make drop.

deleted 6y ago

[deleted]

tomp 6y ago

I don't see how that's an issue, at least for Rust. If a variable is captured by the tail-called function (i.e. the function receives the unique or borrowed pointer) then you can do TCO with an extra argument (said variable, owned/unique) and clean up at the end of the "loop". If the variable isn't captured by the tail-called function, then it's unobservable (except through side effects) if it's deallocated before the tail call.