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?

Langley

Questions that ask "where do I start" are typically too broad and are not a good fit for this site. People have their own method for approaching the problem and because of this there cannot be a correct answer. Give a good read over Where to Start, then address your post. – Circumsolar

Possible duplicate – Fruma

Without a stack, where should variables with local (function) scope be allocated? Without a heap, no dynamic memory allocation is possible. On micro controllers, this is often unwanted anyway, all data then is held in global variables. So (partial) yes, you can do without heap. – Foulard

Your question will be Ok if you delete the second paragraph and also the last line of the first paragraph. Please edit your question so that it will meet SO's standards. – Urinalysis

@CoolGuy but i really want to ask that question in the last line of the first paragraph, how can i change it to meed the standards – Langley

But that's too broad for one question. You're asking about answers for multiple programming languages at once. I suggest you remove that. – Urinalysis

Voting to reopen as the OP has now edited the question – Urinalysis

All you need to implement a stack or a heap is random access memory, so even if your CPU does not "natively" support stacks or heaps, you can still implement them as part of your C runtime library. – Nodule

To a large degree whether the machine provides a "stack" and a "heap" is nomenclature semantics. While not mentioned in the standard, the terms "stack" and "heap" are ingrained in programming beginning with the 'SP' Register. Without a "stack" (or the concept thereof) that register would likely have a different acronym, For a good historical review, see how prevalent the concept of a stack is within the Processor register. – Croteau

How does a stackless language work?, Are there stackless or heapless implementation of C++? – Nonnah

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.

Opposable

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.

Metalepsis

Interesting research... too bad I cannot upvote more than once and everybody seems to have gone away for the week-end (or perhaps watches the Tour de France arrival) – Kidskin

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.

Blau

I beg to disagree: the word stack is not even present in the C Standard. Some mechanism is needed to implement automatic storage and keep track of function call return points, but it does not have to be a CPU stack. – Kidskin

@Kidskin That is a a true interesting point. I will edit my answer. But I suspect that in practice all C implementations use a stack. Do you know of any that do not? – Blau

No, I do not know of any, but A C interpreter could use a doubly linked list of frames. Many processors do not have a built-in stack: for example many RISC architectures do not have a call/ret mechanism with an implicit stack, but instead use a link register that can be saved in various ways by appropriately generated code. – Kidskin

IBM System Z uses dynamic allocation to implement automatic storage. I knew there was at least one not totally obscure system / C implementation that worked that way, but had to google what it was. (Which brought me to this Q&A, specifically Paxdiablo's answer, and this answer which slightly overstates things by saying "invariably".) – Assumed

There are some 8-bit micros that don't have full-width pointer registers, like 6502 and 8080 / Z80. As discussed in Why do C to Z80 compilers produce poor code?, it's possible but very clunky to support recursion / reentrancy in a C implementation. Not helped by compilers for those systems being old and needing to run on cramped systems, limiting their ability to find peephole optimizations when the full general case slow version wouldn't be needed, but some things are just hard on those machines. – Assumed