The Call Stack: Frames, Locals and Returns

Part I · Module 5 · Chapter 5.7 · The Call Stack: Frames, Locals and Returns

1. Three Questions You Can Already Ask

Nothing in this chapter requires a new construct. Everything it explains follows from calls you could already write.

Whose n is whose? If three functions each have a parameter called n, and all three calls are in progress at once, three objects named n exist simultaneously. Chapter 5.6 explained why the names do not collide. It did not explain where the three objects are.

Where does a return go back to? Chapter 5.2 said control resumes immediately after the call. A function can be called from several places, so immediately after the call is a different point each time. Something has to remember which one.

Why do locals not accumulate? A local declared inside a function is initialised every time the function runs. If the same function is called three times, there are three initialisations and no sign of the previous values.

One arrangement answers all three.

2. Watching It Happen

#include <stdio.h>

int innermost(int n)
{
    printf("      innermost begins, n = %d\n", n);
    int result = n * 2;
    printf("      innermost returns %d\n", result);
    return result;
}

int middle(int n)
{
    printf("   middle begins, n = %d\n", n);
    int result = innermost(n + 1);
    printf("   middle returns %d\n", result);
    return result;
}

int outer(int n)
{
    printf("outer begins, n = %d\n", n);
    int result = middle(n + 1);
    printf("outer returns %d\n", result);
    return result;
}

int main(void)
{
    printf("main begins\n");
    int answer = outer(1);
    printf("main has %d\n", answer);

    return 0;
}

Output:

main begins
outer begins, n = 1
   middle begins, n = 2
      innermost begins, n = 3
      innermost returns 6
   middle returns 6
outer returns 6
main has 6

The indentation is doing honest work here — it is the depth. Read the trace twice.

Going in, each function started and then stopped partway through, in the middle of evaluating an initialiser, to wait for the one it called. At the moment innermost began, three other calls were suspended, each holding its own n and each with an unfinished result.

Coming out, they resumed in exactly the reverse order. The last one entered was the first one finished, and main was the last to continue.

That ordering is not a coincidence of this program. It is forced: middle cannot finish before innermost does, because it is waiting for innermost's value. Last in, first out — every time, for every program.

3. The Model

Each call in progress has a frame: a region of storage holding that call's parameters, its local objects, and a record of where to resume when it returns. A call pushes a frame; a return pops it. Because calls finish in the reverse of the order they started, the frames behave as a stack.

Each frame is private to its call. outer's n and middle's n are different objects in different frames, which is the complete answer to §1's first question — and it is the same answer Chapter 5.3 gave from a different direction, since a parameter was always an object belonging to the call.

The record of where to resume answers the second question. A function does not need to know who called it; the frame carries that.

4. Why a Local Never Survives a Return

The third question has the most visible consequence.

#include <stdio.h>

int tally(int add)
{
    int running = 0;
    running = running + add;
    printf("  tally(%d) sees running = %d\n", add, running);

    return running;
}

int main(void)
{
    tally(5);
    tally(5);
    tally(5);

    return 0;
}

Output:

  tally(5) sees running = 5
  tally(5) sees running = 5
  tally(5) sees running = 5

Not 5, 10, 15. Each call gets a fresh frame, running is a new object each time, and the previous call's frame is gone. There is nothing for the values to accumulate in.

This is the behaviour you want almost always — it is exactly what makes a function checkable on its own, which was Chapter 5.1's argument. A function whose result depended on how many times it had been called before would be far harder to reason about.

When you genuinely need a value to persist across calls, C has a way to ask for it, and it is Chapter 9.3's subject. It is deliberately not something you get by accident.

5. What Else the Model Explains

Why calls cost something. Chapter 5.1 said a call is not free. Pushing a frame, arranging the arguments and recording where to resume is what the cost is made of — small, fixed per call, and often removed entirely when the implementation substitutes the body instead.

Why the depth is limited. The region set aside for frames is finite. Nesting calls deeply enough exhausts it. C does not define what happens then; on hosted systems the usual result is that the program is terminated by the operating system, and on an embedded target without that protection the consequences can be worse. Chapter 5.8 depends on this, because recursion is the easy way to reach the limit.

Why a returned value is a value. Chapter 5.4 said a function returns exactly one value. The frame holding the function's objects is gone by the time the caller continues, so what comes back cannot be one of those objects — only a value copied out before the frame went away. This becomes important in Module 7, where it is possible to hold on to something that identified an object in a frame that no longer exists.

6. What C Actually Says

Everything above is the arrangement real implementations use. It is worth being exact about its status, because this is one of the places where a useful picture is most often mistaken for a language rule.

The C standard does not mention a call stack. It does not require frames, does not say where objects are placed, and does not describe how a return finds its way back.

What C specifies instead is a lifetime rule: an object declared inside a block exists from when control enters the block until it leaves, and its lifetime ends at that point. That rule is what makes §4's output guaranteed, rather than the stack. Chapter 9.2 states it properly and gives it its name.

The difference is practical, not pedantic:

Keep the stack as a picture for reasoning about why and reach for the lifetime rule when you need to know what is guaranteed. Chapter 9.4 returns to the stack explicitly, as a mental model with named limits, once the lifetime rules are in place to anchor it.

7. What You Should Be Able to Say Now

1. Nested calls suspend: when the innermost begins, every caller above it is waiting partway through.
2. Calls complete in the reverse order they started — forced, because a caller waits for its callee.
3. Each call in progress has a frame holding its parameters, its locals and where to resume.
4. A call pushes a frame; a return pops it.
5. Separate frames are why three objects named n can exist at once.
6. A local never survives a return — the same function called three times printed 5 each time, not 5, 10, 15.
7. Persisting a value across calls requires asking for it, and that is Chapter 9.3's.
8. The model explains the cost of a call and the limit on depth.
9. C does not mention a stack. What it specifies is a lifetime rule, which Chapter 9.2 owns.
10. The stack is common implementation behaviour — a picture for reasoning, not a guarantee to rely on.

8. Exercises

Exercise 1 — predict the trace. Do not compile yet. Give the exact output, in order.

#include <stdio.h>

int c(int n) { printf("c in\n");  return n + 1; }
int b(int n) { printf("b in\n");  int r = c(n); printf("b out\n"); return r; }
int a(int n) { printf("a in\n");  int r = b(n); printf("a out\n"); return r; }

int main(void)
{
    printf("start %d\n", a(1));
    return 0;
}

Explain why b out appears before a out, in terms of which call is waiting for which.

Exercise 2 — draw the frames. For §2's program, draw the frames that exist at the moment innermost executes its first printf, and give the value held by each n. Then draw them again at the moment outer executes its last printf.

Exercise 3 — predict the counter. Give the exact output and explain which rule produces it.

#include <stdio.h>

int bump(void)
{
    int seen = 0;
    seen = seen + 1;
    return seen;
}

int main(void)
{
    printf("%d %d %d\n", bump(), bump(), bump());
    return 0;
}

Then say which earlier chapter tells you that the order of those three calls is not something C fixes, and why it does not change the answer here.

Exercise 4 — classify eight claims. For each, say whether it is an ISO C guarantee, common implementation behaviour, or an implementation detail.

• a parameter is a distinct object for each call
• parameters are stored in a stack frame
• a local object's lifetime ends when its block exits
• the stack grows downward in memory
• a function returns to the point just after its call
• recursion depth is limited to a few thousand frames
• the same function called twice gets two sets of locals
• reading an uninitialised local gives whatever the previous call left there

Exercise 5 — explain the mechanism without the rule. A colleague says "an uninitialised local holds garbage left by the last function that ran." Say what is right about that, what is wrong about it, and what you would tell them to do instead.

Exercise 6 — find the wrong model. A program calls tally(5) three times expecting 5, 10, 15. Say which belief about frames produced that expectation, what actually happens, and two different ways to get the accumulating behaviour — one available now, and one that is Chapter 9.3's.

Exercise 7 — reason about depth. Explain why a chain of 100,000 nested calls is a problem while a loop running 100,000 times is not, using the frame model. Then say precisely what C guarantees about what happens when the limit is reached.

Exercise 8 — connect it forward. Chapter 5.4 said a function returns exactly one value, and §5 gave a frame-based reason. Explain in two sentences why a function cannot usefully hand back something that identified one of its own locals, and name the module that makes this a practical hazard.

9. Summary

• Nested calls suspend their callers; completion is forced into reverse order.
• Each active call has a frame holding its parameters, locals, and resume point. Calls push; returns pop.
• Separate frames explain why identically named parameters do not interfere.
• A local never survives a return — three calls to the same function each start fresh.
• Persisting across calls is something you must ask for, in Chapter 9.3.
• The model explains both the small cost of a call and the finite depth available.
• C never mentions a stack. It specifies a lifetime rule, which Chapter 9.2 owns and Chapter 9.4 revisits.
• Use the stack to reason about why; use the lifetime rule to say what is guaranteed.

The model also makes one thing predictable that was not obvious before: if calls simply push frames, then a function that calls itself is not a special construct needing new machinery — it is an ordinary call whose frame happens to sit on top of another frame for the same function, with its own parameters and its own locals, exactly like any other. That turns out to be a genuinely useful way to express certain problems, and a genuinely easy way to exhaust the finite region §5 described. The next chapter covers both halves.