Are there stackless or heapless implementation of C++?

C++ standard does not mention anything about the stack or the heap, they are implementation specific, which is true.

Even though they are not part of the C++ standard, we end up using them anyway, so much that it's like they are part of the language itself and have to be taken into consideration for memory or performance purpose.

Hence my question are there implementations of C++ that doesn't use stacks and heaps?

Solution 1:

Others have already given good answers about the heap, so I'll leave that alone.

Some implementations (e.g., on IBM mainframes) don't use a stack as most people would think of it, for the simple reason that the hardware doesn't support it. Instead, when you call a function, an activation record (i.e., space for the locals, arguments, and return address) is allocated from (their version of) the heap. These activation records are built into a linked list.

From a purely abstract viewpoint, this is certainly a stack -- it supports last-in, first-out semantics, just like any other stack. You do have to look at it pretty abstractly to call it a stack though. If you showed people a diagram of the memory blocks linked together, I think it's safe to guess most programmers would describe it as a linked list. If you pushed them, I think most would judge it something like "yeah, you can use it in a stack-like manner, but it's still a linked list."

Solution 2:

C++ standard does not mention anything about the stack or the heap

It actually does -- just not in those words, and without specifying how the stacks & heaps are implemented.

In C++03 there are three kinds of variables:

1. Those with static storage duration (3.7.1). These are "in-scope" for the duration of the program.
2. Those with automatic storage duration (3.7.2). These are in scope only in the context in which they are declared. Once they fall out of scope, the variable is destroyed & deallocated.
3. Those with dynamic storage duration (3.7.3). These are created with a new expression, and are destroyed with a delete. the objects themselves are scopeless, in the sense that their lifetime is not bound to the context in which they were newed. Immediate Pointers to these object are, of course, scoped. The pointers are of automatic or, rarely (and usually wrongly) static storage duration.

"Stack" and "Heap" are really just where later second two types of objects live. They are platform-dependant implementation details which realize language requirements.

So, technically you're right. The Standard doesn't say anything about heaps & stacks. But it does say quite a bit about different flavors of storage duration which requires some kind of implementation on a real platform. On most modern PC-type hardware, this is implemented as heaps & stacks. Could the different types of storage duration be implemented on a platform without using heaps or stacks? Anything is possible -- I suppose that it could. But whatever that implementation ended up being, it would probably have characteristics similar to at least one of the two.

In addition to all this, there is the consideration that both automatic and dynamic storage duration are required by the Standard. Any language implementation that didn't meet both of these requirements wouldn't be C++. It might be close, but it wouldn't really be C++.

Solution 3:

For small programming environments, for example the arduino platform which was based on an 8K Atmel microprocessor (now it has 32K or more), a heap is not implemented and there is no new operator defined by the library. All objects are created statically or on the stack. You lose the advantages of the standard library, but gain being able to use an object-oriented language to program a very small platform - for example,creating classes to represent pins configured as particular output modes or serial ports, create an object of that class giving it the pin number and then calling functions on that object rather than having to pass the pin number around to your routines.

If you use new on an arduino, your program compiles but does not link - the compiler is g++ targeting the avr instruction set, so is a true C++ compiler. If you chose to provide your own implementation, you could do so, but the cost of providing an implementation on so small a footprint is not worth the gain in most cases.

Solution 4:

This is essentially echo'ing Mr. TA's answer (+1 BTW). Stack and heap are abstract concepts.

The new and delete operators (and malloc and free functions) are really just an interface to the abstraction called a heap. So, when you ask for a C++ implementation to be "heapless", you are really asking for the implementation to not allow you to use these interfaces. I don't think there is anything preventing an implementation from always failing these interfaces.

Calling functions and resuming the current execution after the call returns (and optionally retrieving a return value) are interfaces to a stack abstraction. When you are asking for the C++ implementation to be "stackless", you are asking for the C++ implementation to disallow the program from performing these actions. I can't think of a conforming way for the compiler to impose this condition. The language dictates the source code be allowed to define functions, and to define code to call functions.

So my answer in terms of what is possible: "stackless" no, "heapless" yes.