13

The first time a teacher had introduced me to C++, one of the first definitions was about "stack based languages" like Java, C and C++.

Now i read about this in a reply and I'm honestly confused.

C++ is a stack based language but doesn't requires a stack ?

Community
  • 1
  • 1
user1797612
  • 812
  • 6
  • 22
  • 4
    C++ is not a stack based language. That is your misconception. It can use a stack (and most implementations do). But this is not a requirement but more a property of the hardware that you are using. – Martin York Dec 14 '12 at 03:15
  • @LokiAstari can you offer examples where C++ is not based on the stack ? – user1797612 Dec 14 '12 at 03:17
  • 5
    Read the C/C++ specs. There is no mention of a stack. There is nothing in the language that requires a stack for it to work. An easy example. The "Manchester dataflow machine" is a dataflow architecture and thus has no concept of a stack. Yet it has a C (and limited C++) compiler. – Martin York Dec 14 '12 at 03:21
  • I'm really curious about reading some source code that runs on that machine, 2 possible scenario: or that machine got a lot of CPU cache and it's incredibly expensive or I can't think about an useful application for that machine. – user1797612 Dec 14 '12 at 03:43
  • 3
    The "Manchester dataflow architecture" has no concept of cache because it has no concept of memory. It does not even have a concept of an instruction pointer or registers as the whole program is executed simultaneously based only on the availability of data. It has a concept of data and a destination instruction the data is flowing too. A dataflow instruction is an instruction with with one or two destinations (for the data to flow in-to). When all input data is available for an instruction the instruction will fire and generate the output data with a destination. – Martin York Dec 14 '12 at 03:52
  • 2
    The C source for "dataflow architecture" is exactly the same as for "von-neuman architecture". Which is the point of the specification. – Martin York Dec 14 '12 at 03:55
  • @LokiAstari i mean the code as what the program is supposed to do, the von-neuman architecture is well known in the general computing world, i don't know this dataflow machine but i suppose that is not that flexible, I'm curious about specific application of this machine and related code. – user1797612 Dec 14 '12 at 03:57
  • "Dataflow architecture" is a general purpose processing architecture just like "Von-Neumann". It is just different. Its not the only alternative either just the one I am familiar with. – Martin York Dec 14 '12 at 04:02

4 Answers4

9

When I hear "stack based language" I usually think of languages like FORTH where everything is done on a stack, ie no variables. I'm guessing when your teacher said Java they meant the JVM which is stack based.

Now, the C++ standard has absolutely no concept of a stack or heap, only things like automatic and dynamic storage. C++ is specified in terms of more abstract ideas which allows it to theoretically work on many different implementations and hardware. Of course, it turns out that these ideas map directly onto the idea of a stack, so every implementation ends up using one.

Pubby
  • 51,882
  • 13
  • 139
  • 180
  • "no concept of a stack or heap", ok, now what about a keyword like `new` usually used to allocate things on the heap according to the reason why everybody uses `new` to avoid unwanted copies between the internal construction of the object and the stack ? If there is no stack what `new` is for ? – user1797612 Dec 14 '12 at 03:16
  • 5
    @user1797612 Stacks and heaps are *where* and *how* memory gets allocated. Automatic and Dynamic describe the *semantics* of the memory's *lifetime*. C++ only cares about the semantics, not the location. – Pubby Dec 14 '12 at 03:21
  • 1
    @user1797612: new is used to create objects of "dynamic storage duration". There are also "automatic/static/thread storage duration" types for objects. Nothing is defined in terms of a stack. see: http://stackoverflow.com/a/11712472/14065 – Martin York Dec 14 '12 at 03:25
  • 1
    @LokiAstari automatic storage with registers only ? I would go in Stack Overflow with just using few Kb with most of the machines on the market today. – user1797612 Dec 14 '12 at 03:30
  • 2
    @user1797612: It has nothing to do with registers or stacks. The lifespan of automatic storage duration object is the scope it is defined within. Nothing else. It has nothing to do with implementation details. You are trying to define the language in terms of the hardware you are most used to. Sure you can use a stack. But that is not a requirement. You need to think beyond your current experience (that is why the C++ language is designed like this, so that it can be implemented on other architectures or even new architectures that have not been though off). – Martin York Dec 14 '12 at 03:32
  • @LokiAstari i get that, but consider the ages, when C++ was out, around the 90's, there were machines with a very small amount of Kb for the RAM, the CPU registers were even smaller, my point is that I found really strange to not make this kind of requirement in the standard at the point that i can't image a programmer making an useful program with only a very minimum amount of Kb from the registers. – user1797612 Dec 14 '12 at 03:39
  • @user1797612: What has registers got to do with anything. The standard imposes no requirements. You seem to be trying to say that we need implement it this way to work. That's just exactly the opposite of what the spec says. Its says we don't care how you implement it just make it work. Think about it this way. The Russions did not think of a stack (until they stole the concept from America). Their language compilers generated code as sophisticated (even more sophisticated actually) as the western code but there programs did not have a concept of a stack (or need it). – Martin York Dec 14 '12 at 03:47
  • Can you imagine riding in the Soyuz module knowing it was running some sophisticated self modifying code. – Martin York Dec 14 '12 at 03:48
  • @LokiAstari i guess that it's just the fact that i haven't seen a real application of this or a machine that acts without a stack, i still can't imagine what is point of a machine acting without a stack. No problem to accept that, I still can't imagine the alternative. – user1797612 Dec 14 '12 at 03:49
  • @user1797612: That is not that surprising. It takes a huge conceptual leap from "Von-Neuman" to nearly anything else (mainly because this is what you have been indoctrinated with since birth). Most other architectures have been found to have flaws that we can not **currently** overcome technologically. Dataflow for example generates an explosion in parallelism beyond that is nearly impossible to control we have not been able to solve this problem as a result it is not popular (it is sitting on a shelf until our technology caches up with the concepts). – Martin York Dec 14 '12 at 04:08
  • How about "Transaction Architecture". This one is still just of reach but closer to realization than dataflow technology for this is nearly doable. It is also closer to the "Von Neuman" apart from processors have a hardware rollback concept. – Martin York Dec 14 '12 at 04:09
  • And some teachers are even paid ... :D I will read the ISO paper about C++ one and for all, thanks for everything. – user1797612 Dec 14 '12 at 04:14
4

C++ (like C, Java, and most other block-structured languages) requires a "stack" in the sense of some sort of last-in, first-out data structure to hold the activation records for function calls. That is, a function can call itself recursively to some arbitrary depth, and as it does so, the parameters/local variables for each call must be independent of those for previous calls. As those function calls return, the parameters/local variables for each must be destroyed.

That does not, however, require execution on a CPU that directly supports a stack in hardware. It's entirely possible to execute C++ (and the other block-structured languages, as mentioned above) without direct hardware support for a stack.

Just for example, early Crays and (even current) IBM mainframes do not support stacks. Despite this, they can and do support C++. At least in most cases, the LIFO data structure used for activation records is allocated dynamically, and build into a linked list. As each function is called, its activation record is allocated and added to the linked list. When the function returns, that activation record is removed from the list and the memory released.

So, if you're looking at things from a somewhat abstract viewpoint, thinking of a stack as the essence of the basic operations it provides, then yes, C++ requires a stack. If you look at "stack" less abstractly, and think in terms of something like a CPU with a stack pointer register (or anything on that order) then no, C++ definitely does not need a stack (and the same goes for C, Java, etc.)

Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111
3

A non-"stack based language" is not simply a language that does not requires a stack.

Java's bytecode language is a stack-based language because its operations do not operate on registers, they operate on a stack. On the other hand, the Intel microprocessor's ASM language uses registers, and this may be reflected in languages designed to be compiled to that architecture.

C and C++ may or may be not stack based. That is entirely up to the compiler and to the target OS/microprocessor. You can't assume that it is or that it is not. In practice however, it is largely implemented as register-based.

Even if the language operates entirely with registers, you still have a stack for function calls and local variables that does not fit the registers. The presence of this stack does not makes the language stack-based, is the absence of the registers that does.

Edit: Nitpick as suggested by the user mikera: Java's bytecode language is stack-based, but in order to run it in most architectures that are register-based, you will need something translating the stack-based bytecode language in the register-based architecture. This work may be done by the interpreter in the JVM or by a JIT or non-JIT bytecode-to-native compiler.

MrTheWalrus
  • 9,670
  • 2
  • 42
  • 66
Victor Stafusa - BozoNaCadeia
  • 13,995
  • 13
  • 56
  • 72
  • Nitpick: Java absolutely does use registers. It's just that the language does not have facilities that allow you to directly use them. It still gets compiled down (via the JIT) to native code that uses registers. – mikera Dec 14 '12 at 03:13
  • @mikera: Nitpick. Java does not use registers. But the JVM implementation (and the JIT) may as part of the running of an application. I think what Victor is getting at is the that the java byte code is explicitly designed around a stack (no consideration of registers). But this does not prevent an implementation that runs the byte code from using registers. – Martin York Dec 14 '12 at 03:17
  • @mikera: Folowing your reasoning, then everything does use registers. That is not the point. The bytecode instructions does not use registers. If there is a JIT compiler translating these stack-based instructions into register-based ones from another language is a completely different thing. – Victor Stafusa - BozoNaCadeia Dec 14 '12 at 03:17
  • I still don't get the meaning of this, for example the `new` keyword as discussed in a previous comment here http://stackoverflow.com/questions/13872066/c-doesnt-require-a-stack#comment19104546_13872110 – user1797612 Dec 14 '12 at 03:19
  • @user1797612: new allocates in the heap. The heap is a different area of the memory for dynamic allocations that are not bound to the function call stack. In C, you will get something in the heap if you use malloc. In C++ and java, you will get something from the heap if you use `new`. – Victor Stafusa - BozoNaCadeia Dec 14 '12 at 03:22
  • so `new` stands for "dynamic allocation" and not for "the heap" ? There is some word to correct here ?! – user1797612 Dec 14 '12 at 03:36
  • "dynamic allocation" is the type of allocation that is done, as opposed to "static allocation". The dynamic allocated memory is allocated from the "heap", which is an area of the memory reserved for uses that are not bound to the stack. – Victor Stafusa - BozoNaCadeia Dec 14 '12 at 03:39
  • so heap it's not a word from the C++ dictionary, it's **only** about the machine ? – user1797612 Dec 14 '12 at 03:40
  • @Victor: I'm just suggesting improvements to your answer. You described Java as "stack based". Java *bytecode* is stack based (though it isn't the processor stack, it's a virtual stack); but Java itself is no more stack based than C or C++. You also said Java is "stacked based because it ... does not operate on registers". The second part is misleading (for the reason I gave earlier) and the overall conclusion is debatable (why should not operating on registers mean that you are stack based? surely there are other possibilities?). – mikera Dec 14 '12 at 03:41
  • @user1797612: See this: http://en.wikipedia.org/wiki/Memory_management#Dynamic_memory_allocation – Victor Stafusa - BozoNaCadeia Dec 14 '12 at 03:47
1

It is semantics.

Think about a car. A car is described in terms of radio, speed, power seats, CD player, number of cup holders, paint color, etc. The feature list does not talk about where the power comes from to run all this stuff. Almost all cars use gas going to an internal combustion engine and the engine turns the wheels and runs a generator to make electric power to run all the accessories. An engine is not required, but most cars have one.

The language spec talks about the lifetime of data. It does not say how the lifetime is implemented. It turns out 99% of C++ compilers use global data, a stack and a heap to meet the requirements for the lifetime of data the language spec wants.

brian beuning
  • 2,836
  • 18
  • 22