#structured stack allocations

Imagine this weird approach to writing code for a moment. I will use C as an example because C has the fewest implicit memory allocations and is conceptually pretty close to what a real computer is doing with memory as it executes, but you can map this concept pretty easily to other languages:

you are unable to declare any local variables in a function

instead, all local variable declarations go in a struct definition, and

each function receives a pointer to that "local variables" struct as a parameter.

What happens if we do this? Well, if a function call needs stack space, then:

I as the caller know exactly how much stack space it will use - it's whatever `sizeof` on that struct returns.

The easiest way for me to give a function the stack space it needs is for me to create a local variable of that struct type in my function - which of course now has to go in my "local variables" struct.

If I am going to call multiple functions one after the other, I can combine all their "local variables" structs into a union.

So any given function has an accurate account, available at compile time, of how much stack space any call it does will need - technically it can see the full tree of possible stack depths.

`main` starts with a full nested tree of unions of "local variable" structs for the whole program.

If you have been writing complex code for embedded microcontrollers that go in medical devices keeping people alive or in spacecraft trying to land, you immediately see something huge here. If you ever wanted to be robust against the Linux out-of-memory killer, or to just fail fast if there won't be enough stack memory, you may have noticed it too.

We've been treating "stack" memory as effectively free and big enough at the language level since before C, long before languages with automatic memory management started also treating "heap" memory as effectively free and big enough. And that's usually fine - for most code, most of the time, those details are irrelevant concerns, and the code is better for being decoupled from them.

But sometimes it isn't free, and sometimes it's very important to know if it's big enough. Sometimes the exact amount of stack space you use is part of your API, or ought to be.

Note how if we just add a "grow the stack if possible and allowed" API, then

the "local variable" union tree can hold the minimum needed to even run stack space, and

spots in the code that want to gracefully handle a lack of stack space can use that API.

Note also how regular dynamic memory allocation gives you the same big-picture semantics as stack memory allocation that can fail, so you can - today - play with the concept as described so far.

Finally note how callers can predict and control stack usage even better if the "grow the stack if possible and allowed" API is paired with an API to reduce the "allowed" limit for all functions that you call, and so on leafwards on the call tree.

A tougher challenge is situations where the needed "local variable" space can be, especially without whole-program optimizations, impossible to know until runtime:

functions that take pointers to other functions to call - need to add the local variable space needs of the function being called and the function being pointed to, and

recursion, both direct and indirect, needs a multiplication of stack space.

Ultimately I think in this paradigm you have to handle these with the "grow the stack if possible and allowed" API, and this is a good thing for code where space cost of each function matters, just as in fixed-size arrays versus dynamic allocation, it is good when code whose relevant costs are not predictable before execution have to look different.

Of course, the above was just sketching out the idea manually in C. In a mature implementation:

there is no need to reveal the struct contents up the call stack and across interface boundaries - just a simple size of the needed space would do;

for separately compiled linkable code objects, we would want each function's current stack size requirement to be stored along with the function's machine code in a way that the linker and other code can access;

the idea of manually gathering up all your local variables in a struct and explicitly passing pointers to the space was just a way to easily see the concept - any compiler already figures out how much stack space it will need when it builds the function, it just needs to expose that information;

this can be zero overhead and zero change for most machine code - once the sum of the minimum required stack size is known, startup code can check if it can get enough space, and code that never asks for more than its minimum can run as normal;

that "grow stack if possible and allowed" API can be optimized to an integer comparison against the remaining limit.