Does C need a stack and a heap in order to run?

Question

People talk about what the stack and heap are and the differences between them. But I am curious to know that if a CPU does not support stack and heap structure, then can C run properly without a stack and a heap?

Answer 1

No, it does not. Let's cover the heap first, that's easy.

An implementation that does not provide a heap of any sort just needs to return NULL whenever you try to call malloc (or any other memory allocation function). That's perfectly acceptable behaviour according to the standard.

---

In terms of the stack, it also doesn't need to provide one. ISO C11 mentions the word "stack" exactly zero times.

What an implementation does need to do is simply be a correct "virtual machine" for all the things specified in the standard. Granted that will be very difficult without a stack but it's not impossible. As an extreme case, there's nothing that says you can't simply inline every single function call recursively. That would use rather a large amount of code and function-specific data space, but it's certainly doable.

However, it's probably something that would convince me to move to another architecture, one that did have a stack (and heap, for that matter).

---

Having said that, even if an architecture provides neither a heap nor a stack, both of those can be built out of basic memory I/O operations. In fact, one of the earliest computers I ever had as a teen sported an RCA 1802 CPU which had no dedicated stack. It didn't even have a call or ret instruction.

Yet it could handle subroutines and a stack quite well (for some definition of the word "well") using its SCRT (standard call and return technique). See here for some more detail on how this thing of beauty (or monstrosity, depending on your viewpoint) worked, along with some other unusual architectures.

---

The IBM Z (a.k.a. System z, zSeries, whatever they're calling it this week) actually has a heap (of sorts, in that you can allocate memory from the OS) but no stack. It actually implements a linked-list stack by using this heap memory along with certain registers (similar to the RCA chip referenced in the above link), meaning that a function prolog allocates local function memory using STORAGE OBTAIN and the epilog releases it with STORAGE RELEASE.

Needless to say that puts quite a bit of extra code into the prolog and epilog for each function.

Answer 2

Neither stack nor heap are required by the C11 standard (see n1570), as explained by other answers. But, in practice, both are useful.

Regarding the call stack it is very common, but it might be "avoided":

• some optimizing compilers might be clever enough (notably with whole-program optimization, or link-time optimization) to detect the case where an entire program don't need any (a simple such case would be a whole program without function pointers and without recursion: in that case every "call frame" could be allocated statically at compile time). And many optimizing compilers are inlining some calls (effectively removing the need of a call stack for these calls), even for functions which are not marked inline.

• many today's processors (x86 or x86-64, AVR, SPARC, ColdFire i.e. mc68K...) have a hardware call stack (e.g. some "stack pointer" register, known to function calls). On those that don't have such a hardware stack pointer (e.g. IBM Z series mainframes, PowerPC, MIPS, RISC-V, or perhaps ARM), the calling convention (or the ABI) might conventionally dedicate some register to play the role of a stack pointer. BTW, C could even be implemented theoretically for random-access machines (which don't have any register or stack pointer).

• one could imagine a compiler using continuation-passing style to avoid a call stack (effectively, "allocating" some "call frames" in the -or in some- heap, perhaps with the help of some garbage collector). Appel's old book Compiling with Continuations explains this idea in detail. I cannot name any C compiler doing this, but the standard permits such an approach. And if you coded some compiler from C to SML (or to some Lisp), you could have such a compiler.

Regarding the C heap, the malloc function could always fail and that is still standard compliant. I claim that such a malloc is useless, but probably the fastest. Also, the C standard permits freestanding implementations to not have any malloc at all.

If you seek for a feature nearly required by C, I would investigate binary representations. I tend to believe that implementing a C11 compiler for decimal computers (like the old IBM 1620) or for ternary computers (like Setun) would be very impractical (but in principle it is possible, since you could "emulate" a binary computer on a ternary or decimal one; all are Turing-complete). However, you'll find such old (late 1950s, early 1960s) computers only in museums, and they disappeared before the invention of C.

BTW, call stacks and heaps existed in ALGOL and Lisp (and IPL-V) implementations, dozens of years before C.

Answer 3

The C language requires (as chqrlie, points out) some mechanism to implement automatic storage and keep track of function call return points. In practice this is almost invariably a stack. But it does not require a heap.

A heap is only normally required if you use library functions like malloc; not by the C language itself. There is actually nothing magic about a heap - you can write malloc and free in pure C. It just has a big block of static memory and has an algorithm to allocate space from the block.

You ask what about "if a CPU does not support stack and heap structure"? Well, stacks and heaps are just built of memory and pointers. I don't think you will find an example of any processor that can be regarded as a "CPU" that does not have this ability.