How do Stack Machine store global vars?

Question

How exactly do stack machines (both real and virtual stack machines) store global variables?

I know that C(++) just compile it to the .data segment of a program's memory segmentation.

Then there's Java's JVM which uses a stack-heap system (both data-stack and heap are stacks that grow towards one another) and stores static locals to the heap.

The reason for this question is I'm developing a stack-based VM and I'm trying to decide whether I implement the stack-heap system or use C's .data segment system?

Are there other ways of storing global data besides these two?

Answer 1

I believe your question is fundamentally conflating (a) the executable (file) format and instruction set of a virtual machine — how that format supports the declaration & accesses of globals/statics — with (b) the underlying implementation of such virtual machine, which may be in C or even in another VM-based language, like Java or C#.

Regarding the former (the executable format & instruction set), for instance in the JVM executable (class file) format, is that this format allows declaring fields for classes, and the field can be tagged as static vs. instance. The instruction set, like real machines, provides an addressing mode that is applicable to the access of global or static variables. Since this is a stack machine, these addressing modes are offered within push and pop/store instructions that target statics instead of local variables or instance variables.

Regarding the latter, since the virtual machine itself almost certainly dynamically loads the code to execute/interpret, it does not know in advance about the globals/statics in the code it will be loading. Thus, it is highly impractical for the virtual machine itself to map the globals/statics into the implementation language's concept of globals/statics, and instead it will map the globals/statics into heap objects in the implementation language, translating access instructions in the vm-loaded code into pointer accesses (or object references) during execution or interpretation.

Let's also be clear that the same design for a virtual machine file format and instruction set can be implemented by a variety of widely different ways and in different implementation languages. So, there is the abstraction that represents the virtual machine, namely by defining its file format and instruction set, and then there is the implementation of a virtual machine that observes/executes that format & instruction set.

Answer 2

A pure stack machine is not sufficient to implement arbitrary computations. As such, most stack VMs are not pure stack machines.

Variables that are initialized when the program is loaded are not much of an issue, because they can simply be allocated at the bottom of the stack, thus outliving every other value.

But stack machines pose two important questions:

• How can I access values that are not at the top of the stack? Is there random-access to memory? Can I copy around references to other objects? You will need to deal with arrays or lists in any nontrivial program.

• How can I store objects with different lifetimes? Stack-allocated objects must be deallocated in the reverse order they were allocated. That makes many programs impossible, in particular regarding closures or OOP. A free store/heap is necessary.

I.e. a stack is a good model for local data within a procedure, but not for data that is shared between procedures.

Aside from C-style heap management, other strategies involve:

• environments or dictionaries that can hold global or local variables.
• separate stacks for data and control flow

It is worth studying the SECD machine, an abstract stack machine that can be used as a lambda calculus interpreter. S, E, C, D are registers that each hold a stack; these registers can be changed to point to a different stack. S is an ordinary data stack, E is holds the environment (variable bindings), the control stack C holds code to be executed, and the dump D is a stack of (S, E, C)-tuples which are continuations. This tuple is generally equivalent to a return address.

Answer 3

The important notion is that of closures and (in mathematics) of free and bound variables. Learn also more about λ-calculus (and Scheme).

In some crude sense, the global or static variables (and also the literal constants, and the directly called functions) in a C program are the only closed values in a C function. See also this answer.

In Java, the data inside objects can be thought as closed values. Notice that static data belongs to the class (which is an object itself) so Java has no really global data (but read more about Java classloaders, including the primordial one of the JVM).

BTW, both closures (or lambda abstractions) and objects are mixing data with code.

Practically speaking, the client data passed to callbacks can be thought as closed values. In other words, a callback routine with its client data is a closure.

So you could consider closed values inside closures as somehow "global" -to the code of the closure- values.

Conversely, you don't need any global "data" segments or global variables once closures are first class and you have anonymous functions (ie lambda abstraction).

Read absolutely SICP, Lisp In Small Pieces, Programming Language Pragmatics. You could later also read the Dragon Book and the GC handbook.

^{(I strongly recommend taking a few weeks to read all these first three books before coding your VM)}

So have first-class closures in your VM. Look also into the Lua & Neko & Guile & Parrot & Ocaml VMs (at least for inspiration) and SECD machine.

Once you have first class closures, you really want to have a garbage collector.