I interrupt this exposition to jump to the meat. I want to use jargon that would confuse that development. When a compiler contemplates stack layout for a new routine that it is compiling, the simple idea is that every variable declared in the body of the routine definition gets its own stack space. Sometimes however the exceptions to this pattern overwhelm the pattern. We consider some exceptions here. The original and simple idea of a variable which is local to the routine, meaning that it is declared in the text of the body of the routine, is that the storage is needed only after the routine begins and before the routine ends. The heap was invented for storage not conforming to that discipline. With the advent of pointers is was possible to remember the location of a heap location. Pascal forbad taking the address of a variable on the stack.

The status of functions slowly grew in popular computer languages. Nested function definitions became possible in Algol 60. In Algol 60 if function Y is defined within the body of function X then a function value arising from Y during some evaluation of X will differ from values for Y on another evaluation of X, just as “x+y” does not always evaluate to the same number. .... This may happen if X is recursive. Such values for Y become invalid when the corresponding evaluation of X finished. for some compilers this rule is enforced at compile time and in others the results are undefined.


Clang complains of but compiles this valid silly program “int * s(){int y; return &y;}”. Here is an invalid useful program whose analogs in other languages are valid, efficient, useful and popular:


For terminology we call our routine X and assume that there is a routine Y defined textually within X and also a variable B defined in X but not Y, and referenced both in X and Y.
We might be able to compute the offset of B from the stack pointer while Y is running.

The only references to Y must appear as routine invocations in X. Otherwise the relative offsets between the two stack frames are unknown. This precludes passing Y as an argument in a call site within X. It also precludes X returning Y as a result. Were the returned value to be invoked the storage for B would be gone. If Y is passed as an argument to other routines running while the current frame lives on, then the stack pointer, having moved, will not suffice for the code compiled for Y to find B. A classic solution to this problem is fat pointers to denote function calls: two pointers are included: one for the code and one for the frame that locates B. A routine body may include reference to variables at several levels out. If each frame includes the address of the frame of its caller, then this chain can be followed by the compiled code for the inner function. The compiler knows exactly how many intervening frames there are; it is the level of routine nesting. There are subtle issues that will vex a language lawyer here whose outcome depends on seldom read parts of the language definition and often parts that were never written.