0

Lately I've been asking a lot of questions here about VMs. Here's another one:

I understand that often stack based VMs use only one stack - the call stack - for everything. E.g. it is also used for evaluation of arithmetic expressions.

What I don't understand is, how doesn't this complicate things a whole lot? I'll demonstrate what I mean with an example.

Please consider the following psuedocode program:

func main:
    funcA()

func funcA:
    2 + 4 * 8

This would compile to the following bytecode:

main:
call funcA
end
funcA:
push 2
push 4
push 8
mult
add
end

(In this bytecode, the program starts at main:. call pushes the program counter onto the stack and jumps to the specified label. When an end is reached, the top of the stack - assumed to be a line number - is popped and we jump there.)

So let's see what happens here:

In call funcA, we push the program counter (i.e. next line number) onto the stack. Then we jump to funcA.

In funcA some computation is made. After the computation, the number 34 is left at the top of the stack.

When we reach end, we pop the top of the stack, assuming it's the line number we should return to But it isn't, the line number to return to is buried underneath. How should end know about this?

To avoid all this mess, we can just have a separate data stack and call stack, and not mix the two.

So my question is: why do some VMs (such as the JVM) use one stack for everything, and when the do: how do they handle situations such as the one described above?

  • 2
    Do you know how this is done on physical machines? I can't tell you the specifics from any VM, but on a physical machine your end instruction would also have to do something to tear down the stack frame. You always maintain a pointer to the start of your functions little bit of stack. The return address is just above that, not at the very end. – Phoshi Aug 1 '14 at 9:35
  • @Phosi So when end is reached, anything on the stack above the pointer to the start of the stack frame (the stack pointer?) is lost? – Aviv Cohn Aug 1 '14 at 9:48
  • 1
    Yes, exactly. That's why we only really use the stack for local variables, and anything that needs to go "up" the stack frame is typically heap allocated. – Phoshi Aug 1 '14 at 12:56
4

When we reach end, we pop the top of the stack, assuming it's the line number we should return to But it isn't, the line number to return to is buried underneath. How should end know about this?

You compiled the source to the wrong opcodes. There are two ways to solve this:

  1. Put a swap before each end. Because the return address sits immediately underneath the return value, this will put the return address onto the top. After end has performed the return, the return value will be the top value.

  2. Define an operation return which pops two values off the stack. The second value is the return address, the first value is the return value. After updating the instruction pointer to point to the return address, the return value is pushed back onto the stack. Then use this sane return instead of end.

The compiler is responsible for emitting correct instructions.


It is possible to write a VM using only one stack. However, this vastly restricts the expressiveness. When using multiple stacks, it becomes far more easy to implement more advanced control flow such as coroutines, continuations, error handlers. In a multi-stack architecture, there would typically be a value stack, and a separate call stack which stores not only the return address but possibly also debugging data, or cleanup actions to perform when the current scope is left. If you're already using multiple stacks, it also becomes easier to use segmented stacks, which are a technique to avoid stack overflows. Essentially, the stack is actually a linked lists of smaller stacks. If one segment is full and would overflow, then another segment is allocated and added to the list.

For a well-studied multi-stack VM look at the SECD machine, essentially a lambda calculus interpreter.

| improve this answer | |
  • Since it's easier and more flexible to have a separate call stack and data stack, why do VMs such as the JVM use only one stack? – Aviv Cohn Aug 1 '14 at 10:30
  • 2
    To be clear, when you write "multiple stacks" you mean something more general (and harder to implement efficiently) than OP. Just having one data and one call stack doesn't give rise to coroutines and continuations, you are probably thinking of a spaghetti stack. Segmented stacks are orthogonal, they work just fine with a single stack for everything (LLVM implements this and Rust, which never had call/cc or even limited coroutines, used it). – user7043 Aug 1 '14 at 10:31
  • @prog - because it isn't really easier. Having a separate return instruction if you want to return a value is a trivial thing for the compiler to implement, and is probably sensible in any case for the code's clarity's sake. A single stack is less work to keep track of, and is entirely adequate if you don't want the extra features you can get from multiple stacks. And I don't think the JVM specification actually specifies which model to use, in any case, so I'm not sure this discussion really applies to it: you could implement it either way, or JIT compile it and not use a stack at all at RT – Jules Aug 1 '14 at 14:58
2

Why: Because it's simple & efficient.

When you have only one stack, you don't have to do anything for your stack memory management. All the things you have to do is allocate one big chunk of memory before the execution. it's as same as native codes works. you can not make it simpler than that.

Second reason is efficiency of execution. Because your stack is just another big chunk of memory, it may reside in cpu cache most of times. It's good thing 'cause it's super fast. Furthermore because of the nature of stack data structure, memory access pattern would be consistent. So it's super cpu firendly. Most of cpu doesn't like random access so you can expect your vm runs much faster than the other architecture. And you only need two integer variable (probably on the cpu regsiter) to track the use of your stack.

How: "When we reach end, we pop the top of the stack, assuming it's the line number we should return to But it isn't, the line number to return to is buried underneath. How should end know about this?"

In a first place, there is no line number in assembly. It's memory address of code section of your program. before call funcA, usually argument pushed on to the stack. Then, it save the register called "base pointer register". Then, return address of funcA is pushed on to stack to save where to execute when the control returned from the function. call instruction usually do this (save ebp) and jump to the address of funcA.

What's happening at the end of funcA is something like this.

mov __some_register__, __stack_top(return value of function)__;
pop; (pop out return value)
mov __stack_pointer__, __base_pointer__ (deallocate local variable)
mov __base_pointer_register__, __stack_top__ (restore saved base-pointer)
pop;
mov __program_counter__, __stack_top__ (stored return adress before call)
pop;
push __some_register__ (restore return value on top of stack)
(usually, these procedure is packed as "ret" instruction)

So answer is, "call" instruction stores necessary information to recover the state of the program before jump into the function. Usually base pointer and return address. So when function "returns", you can pop out those information from the stack by "ret" instruction. In addition to it, "stack machine" needs some register to temporarily store some information (something like return value) so that program can use return value after control back to callee.

Usually, if your computation in "funcA" is somehow legit, how long the computation is, it going to left only one value on the stack when one "statement" is done. Therefore you can expect original state of the stack is recovered when you return from "funcA" (stack pointer must be in original position plus one, because return value appears on stack top). If funcA messes up the stack when it's done, you can assume design of your vm is not legit or the compilation of funcA must be corrupted.

Both of "register machine" and "stack machine" has similar call-stack structure in general. So if you don't understand what "base pointer" or "stack poitner" for, do some more research on call-stack. Actually, it's a lot easier than you think, so you can get it soon I think.

| improve this answer | |
1

The simplest answer would be that more than one stack is unnecessary for a wide array of languages.

Take a look at Automata Theory.

As much as we would like to say otherwise a true Turing machine does not exist. Its always a Turing machine with this maximum length of tape.

The max tape length is critical, with that constraint we can map any such machine down to pushdown automata. The simplest pushdown automata is a state machine with a single stack.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.