0

I've just accidentally came across this answer about inlined functions and I'd like to know how this affects call stack. But I can't add comments because I don't have enough rep so I decided to ask this question. Also recently I discovered Tail Call Optimization (TCO) and now I want to learn more about this topic. And since TCO is also related to call stack, I actually have 2 question.

  1. AFAIK every function call adds a new stack frame into a call stack. But what about functions inlined by a compiler? As this IBM article says:

An inline function is one for which the compiler copies the code from the function definition directly into the code of the calling function

It makes me think that in this case we don't really use a function at all. We use it's inner code but an actual function call doesn't happen. So does it mean that a new stack frame isn't created for such function? Hence "every function call creates a new stack frame" is a false claim?

  1. TCO allows a runtime to use the same stack frame for multiple recursive function calls. New stack frames are not added into a call stack. Instead the runtime just swap data inside the same stack frame - data that was necessary for the previous recursive call is replaced with data that is necessary for the next recursive call. Does it mean that in this case we can intentionally create an infinite recursion and we won't have a stack overflow since we always have a fixed amount of stack frames in a call stack?

Those 2 question are not language specific. And since different languages have different compilers, and every language can have multiple compilers that work differently, I'd like to get answers about any language and any compiler you used and know about.

1
  • TCO is Tail Call Optimization in this case
    – b3rry
    Commented Sep 28, 2023 at 21:50

1 Answer 1

2

AFAIK every function call adds a new stack frame into a call stack.

This is true for some functions, but not for all functions.  On some processors, simple functions, called leaf functions (functions that may do work but simply do not call other functions), usually operate without a stack frame.  On x86, the "stack frame" (if you can even call it one) for a leaf function may be as small as one word, for holding the return address; whereas on RISC machines, may be a small as zero words.


Inlining is a feature of some translators, when the compiler can see the internal implementation of a called function (the callee) at the point(s) where it is translating the caller.

Inlining is usually performed at a fairly high level in the translater, such as at the AST.  The optimization substitutes the function invocation in the caller with a copy of the callee's function body.  In use, the caller behaves the same as if it had actually called the callee, as with most languages there's no mechanism within the language that allows us to observe whether inlining was done or not.

Inlining enables numerous other options as the callee's body is placed within the context of the caller's code — loop optimizations, common sub expressions, constant propagation, direct use of variables provided by the caller instead of formal parameters in the callee, etc..

Since with inlining there is no actual low-level function invocation, the call stack is not (necessarily) enlarged by the execution of the copy of the callee's function body.  However, the caller's call frame my be enlarged to accommodate the new code and its variables.

Inlining has limitations, and if there's recursion, inlining has to be artificially limited to some number of levels.  Since inlining makes copies of the callee's function body, the generated code may get larger (but it may also get smaller).


TCO allows a runtime to use the same stack frame for multiple recursive function calls.

Tail Call Optimization applies to any function invocation that is the last operation of a function before returning to its caller.  It is very helpful in recursive code, but no recursion is required.  It applies when the last thing a function does, dynamically, is a function call, meaning that multiple return points allow for multiple TCO opportunities within the same function.

Because a tail call is specifically the last operation of an invoked function, it is the last thing it does before it returns to its caller, the caller no longer needs their own stack frame — the caller has nothing left to do (i.e. no computation or changing of state) to return to its caller — except actually return.  Thus, the TCO sets up the stack frame such that the callee returns, not to the caller, but rather directly to the caller's caller.  This removes the need for the intermediate (the caller's) stack frame, and in properly written recursive code (i.e. written for TCO) many levels of stack frames might be elided with TCO, and in addition, the caller's stack frame itself may be simpler (more like a leaf function's).

Does it mean that in this case we can intentionally create an infinite recursion and we won't have a stack overflow since we always have a fixed amount of stack frames in a call stack?

Yes, TCO can eliminate stack overflow that might have occurred without it.

11
  • wow! Thanks for such a detailed answer! But I have a few more questions. 1) In case of recursion every recursively called function needs a stack frame of the same size. But you mentioned that recursion is not required for TCO. But there's a very small chance that a function called at the very end of a caller would need a stack frame of a size the caller needed. How does re-using the same stack frame works in this case? 2) With TCO, if (for some reason) a recursive function does not have a base case it doesn't necessarily mean that a stack overflow would occur, right?
    – b3rry
    Commented Sep 27, 2023 at 10:08
  • 3) Where can I get more information about all those things you mentioned in your answer? Books, courses, youtube videos? I'm really interested in what happens under the hood when I run my program. And I want to learn more about such things. Low-level concepts are not often discussed so I discover them only when I acidentally come across them on the internet (like the post about function inlining I mentioned in my question). Maybe I should take a look at some low-level programming languages? And is the Dragon Book a good source?
    – b3rry
    Commented Sep 27, 2023 at 10:16
  • The principle of TCO is that, when A calls B, and B calls C, which returns to B, which returns to A, that B erases itself and transfers to C — instead of calling C. C then returns directly to A instead, since B has been effectively erased. With TCO, it is possible that B didn't even need a stack frame in the first place (but it would have needed one without TCO).
    – Erik Eidt
    Commented Sep 27, 2023 at 11:28
  • In the case of recursion, B and C are the same function. Further optimizations may be possible knowing that, for example, if B/C needs a stack frame, then it might skip setting up the frame and tearing it down, transferring control not to the beginning of B/C but just past setup of a frame, since part of that has already been done by the outer invocation.
    – Erik Eidt
    Commented Sep 27, 2023 at 11:30
  • Wikipedia is a good resource, for example, en.wikipedia.org/wiki/Tail_call. In some cases, what one needs to do is learn terminology to more effectively search for articles and videos on Wikipedia and beyond. At the very end of that Wikipedia page, there is a box labeled "Categories:" , which allows navigation to other similar content. For example, the first item is en.wikipedia.org/wiki/…
    – Erik Eidt
    Commented Sep 27, 2023 at 11:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.