Are there stackless or heapless implementation of

问题:

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?

回答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."

回答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++.

回答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.

回答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.

回答5:

There can't be a stack-less and heap-less implementation since C++ defines constructs such as functions and the new operator. Calling a function requires a stack, and "new"ing up an instance requires a heap. How those are implemented can be different between platforms, but the idea will be the same. There will always need to be a memory area for instance objects, and another memory area to track the execution point and call hierarchy.

Since x86 (and x64) have convenient facilities for these things (ie. the ESP register), the compiler uses that. Other platforms might be different, but the end result is logically equivalent.

回答6:

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.

回答7:

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