Stack-based machine depends on a register-based machine?

Question

Normal CPUs (for example, Android devices) are register-based machines. The Java virtual Machine is a stack based machine. But does a stack-based machine depend on a register-based machine to work? Can't stack-based machines run lonely, because it is not a OS? Are there any stack-based machine examples except the JVM? Some are saying 1 operand, 2 operand; why do you need this?

Answer 1

The JVM does not mention the existence of registers anywhere. From its perspective, memory exists in only a few places, such as the per-thread stack, the method area, runtime constant pools, etc. That said, if you wanted to actually implement a physical device that adhered to the JVM, you'd almost certainly need registers to hold some of the temporary values generated when executing certain bytecodes, or to maintain some extra scratch information on the side. For example, try looking up the multianewarray instruction and see if you could implement it without registers. :-)

One parallel you can find in real CPUs these days is that while there are dedicated set of registers available to programmers, most CPUs have substantially more registers that are used internally for various purposes. For example, most MIPS chips have a huge number of registers used for pipelining. They hold things like the control bits from previous instructions. I would be blown away if x86 was any different.

The thing to remember is that it's not registers that really define how a register-based machine versus a stack-based machine work. In most architectures, you have O(1) registers that are dedicated for internal use. Even the JVM has these - each method has a "local variables array" that originally hold the function's parameters, but can also be used as scratch space if need be. The more important part about stack machines that differentiates them from other machines is how the extensible memory works. In most computers, memory is random-access and you can read from any location you want at any time. That is, with n memory locations, you have O(n) memory readable at any time. In stack-based machines, you only have access to the top few spots of the stack, so you only have O(1) memory locations readable at any one time.

In theory, because the JVM is supposed to represent a full virtual machine, you could have a computer that booted up and just ran a JVM without any OS (or rather, the JVM would be the OS, and your "programs" would just be Java bytecodes and class files).

There are a few other stack-based languages, of which the first that jumps to mind is Forth. I mention Forth because it's explicitly a stack-based language; everything you do is phrased in terms of manipulating an operand stack. What's cool about this with regards to your original question is that Forth used to be extremely popular among hobbyists because you could really easily port it to embedded devices. To get a full Forth interpreter working you don't need a really powerful OS - you just need the command interpreter. Forth isn't as popular these days, but it's still a really cool language.

Another stack-based language that's in wide use is PostScript, which has lost a lot of ground to PDF but is still used extensively in environments where you need to render scalable graphics on a variety of platforms. It technically is a Turing-complete programming language, though few people use it that way.

Answer 2

I know you've already selected your answer, but I'd like to address the whole "stack machine" thing.

While most physical CPUs are, in fact, register machines, there have been stack machines as physical CPUs. Burroughs' B5000- and B6000-series machines, for example, or the RTX2000-series chips used in space flight (originally implemented by Chuck Moore in gate array logic and later commercialized). The UCSD Pascal p-Machine was implemented straight up in hardware as well by a variety of implementers.

In terms of computational strength, register and stack machines are roughly equivalent. (It depends, of course, on which precise models of register or stack machines you're dealing with.) Stack machines have the advantage of simplicity, small size and expandability. Register machines tend to be faster. Register machines can emulate stack machines (that's what the BP and SP registers in the x86 architecture are for, after all!) and stack machines can themselves imitate register machines if need be.

---

edited to add

I'd almost forgotten to point you to a book that discusses stack computers in depth. Koopman is a bit of a fanboi for stack computers and his prediction that they were "the new wave" was woefully wrong, but it's an interesting read.