4 ms·

- The vararg function doesn't even know exactly how many args it's been passed, it only knows a lower bound (the non-variable declared args). - The trampoline i

• deleted 2mo ago
  [deleted]
• cryptonector 2mo ago
  The trampoline must indeed be a closure, but let's say you have a chain of main() calling f() tail-calling g() tail-calling... in all cases needing a trampoline, and some being [mutually, even] recursive, and even variadic: there is only ever one live closure: the return to the main() call site to f(), so there is no unbounded stack growth due to tail-call recursion. The trampoline would replace the {main retaddr, main fp} closure with {trampoline addr, [stack byte count to pop], main retaddr, main fp} and would pop some number of bytes, either hard-coded into the the trampoline function (so you get a bunch of them) or is part of the closure.
  • kazinator 2mo ago
    We have to avoid the situation whereby we have a tail calling loop, in the course of which a growing chain of these fixup thunks is accumulating, such that when we return to the original caller, a cascade of these goes off. That will clearly cause accumulation of something on the stack. Maybe we just need one global thunk. When a function sees that its return address points to the tail fixup thunk, it avoids installing another one, but instead updates some word at a well-known frame offset location to inform that thunk that more words need to be cleaned up. All of this obviously does relate to trampoline-based tail calling.
    • cryptonector 2mo ago
      Yes, of course, the tail-calling function must recognize that its continuation is a trampoline closure, pop it, then push either a new trampoline or the original closure (if no trampoline would be needed for the particular tail-call being performed). Do it right and there should only ever be one trampoline closure on the stack for any chain of tail calls, making the scheme O(1) in space. So the whole protocol is that when the compiler recognizes that a call is a tail call, and one that can be turned into a jump instead of call, then the compiler must emit code to a) pop the current continuation (which will either be the original or a trampoline that embeds the original, and from which the original can be recovered), b) pop all the previous arguments and push all the new ones (possibly some are the same, so there is room for optimization here), and c) push a new continuation that is either the same as the previous current continuation or else a new continuation closure that is the correct trampoline corresponding to -and embedding- the original continuation, where the original is recovered from (a). The trampoline recovers the original continuation, fixes the stack depth to what the caller expects, and executes a return to the original continuation. For variadic functions it has to be the case that they have used `va_start()`, consumed all variadic arguments with `va_arg()`, then called `va_end()`, leaving no active copy of the `va_list`, then the compiler can arrange to keep a hidden local variable count of stack words used by the variadic arguments that it can use to implement the above protocol correctly.