Are there stackless or heapless implementation of C++?

Question

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?

Answer 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."

Answer 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++.

Answer 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.

Answer 4

Yes there are, mainly MCUs like Freescale and PIC

2. Stackless processors are being used now.

We don't look at cores the way assembly programmers do. We're happy with bare-bones programmer's models, so long as the required fundamentals are present. A stack is not one of them: we've run into several stackless cores recently, and have had no problems developing C compilers for them.

The eTPU is a 24-bit enhanced time processing unit, used in automotive and general aviation engine control, and process control. eTPU may be a co-processor, but it has a complete instruction set and a full CPU core, and it's stackless. It is a mid-volume processor: chances are you'll drive or fly home tonight courtesy of C on a stackless processor.

We have a C compiler for the eTPU based on C99 and ISO/IEC 18037. We run standard C test suites on this processor.

The Freescale RS08 is a more traditional MCU that is stackless. In the process of "reducing" the HC08/HCS08 core, Freescale removed the CPU stack. We consulted on the architecture of RS08, and we never felt the need to insist on a hardware stack.

To mention another co-processor we consulted on, the Freescale XGATE has a very friendly ISA and programmer's model, but it doesn't have a stack.

Then there are the "nearly stackless". Microchip PIC never had data stacking, with only an 8-entry (or 16-entry in the enhanced 14-bit core) call-return stack. Nobody doubts that C is available for PICs.

These parts, especially the eTPU, were designed to be compiler friendly and encourage machine-generated code.

There are other non-stack-based processors, some created recently, spanning a range of applications and enjoying their own C compilers. There are mid- to high-volume stackless parts. Performance is usually the primary reason that parts do not have a stack.

http://www.bytecraft.com/Stack_controversy

Answer 5

I dare to say there is no such C++ implementation, but simply because the stack and heap are very useful abstractions for which basically all processors on the market provide some HW support to make them very efficient.

Since C++ aims at efficiency, C++ implementations will make use of them. Additionally, C++ program don't typically operate in a vacuum. They must integrate into the platform ecosystem, which is defined by the platform's Application Binary Interface. The ABI - for the very same reasons - defines stack and other memory structures the C++ implementation will need to obey to.

However, let's assume your C++ program is targeted to a simple, small, resource constrained embedded platform with an exotic microcontroller and no Operating System (your application will be the OS!) and no threading or processes.

To start with, the platform may not provide dynamic memory at all. You will need to work with a pool of static memory defined at link time, and develop your own memory allocation manager (new). C++ allows it, and in some environments it is indeed used.

Additionally, the CPU may be such that stack abstraction is not that useful, and therefore not worth implementing. For instance, CPUs like SPARC define a sliding register window mechanism that - combined with a large amount of registers - makes use of the stack not efficient for function calls (if you look at it, the stack is already done in HW!).

Long story short, all C++ implementation use stack, most use the heap, but the reason is strongly correlated to the platform properties.