I’m planning to implement a simple VM/interpreter kind of thing for a simple language I’m making. The compiler of the language emits mostly stack-oriented instructions to be executed by the VM.
The structure of the program will be something like this:
- The execution part (for lack of a better term): interprets the
opcodes and executes them. - The call stack: to keep track of function calling, and for parameter
passing and return values. - The data stack: for none function-calling-related computation, such as
arithmetic. - The variable-storing area, where variable names are matched with values.
The “variable-storing area” will be implemented basically with a HashTable/dictionary thing. When the programmer creates a variable (assuming for now only numeric variables), a new entry is added to the table. When he/she assigns a value to a variable, the entry with the matching name in the table is assigned this value. When the programmer accesses a variable, again we fetch the value from the table.
I’m pretty sure that’s the only data-storing part I need in the application, aside from the data stack and the call stack. I don’t see why I’d need anything else.
Now, I looked at what a ‘heap’ is in Wikipedia and other sources online. I found mostly technical terms that I’m having trouble understanding.
But in simpler non-very-technical terms, if I understand correctly, the heap is where the ‘constant’ data is saved, things that aren’t local computation such as arithmetic.
So if my understanding is correct, is my ‘variable-storing area’ basically a ‘heap’? Why or why not? If my understanding of what a heap is is wrong please explain it.
1
The term heap is tied to dynamic memory allocation. If your programs dynamically create “variables”, your “variable storing area” might be considered a heap. But what one usually calls variables is far from dynamic:
for (int i = 0; i < N; ++i) {
int var = i * i;
}
Here at most three variables exist at any point in time. You’d have to write additional code to create more variables. The lifetime of all variables is very much statically determined. And so on.
The heap is not “all data, except constants”. A common (simplified, of course) model of real computers is: You have registers and the stack (which house not only temporary values but also variables), memory that is statically allocated (i.e. exactly once for the entire time the program is running), and the heap for everything that doesn’t fit in those categories. Usually variables and their values are not part of the heap at all, at most the variable values are references/pointers to data that’s stored on the heap.
In this context, the stack is called stack because allocations are FIFO: When variables a, b, c were created in that order, c must be removed first before b and then a can be destroyed. But it’s still random access memory, so accessing a variable looks like this in pseudo-C: stackpointer[-10] for the tenth value from the top of the stack.
A bytecode instruction dec a does not mean dynamic creation of variables in the sense used above. Obviously the memory management that makes room for the variable has to happen at run time, this is true even in C. But can a program perform a loop that creates a variable number of “variables”? If not, the set of variables is set in stone at the time the program is written and there is nothing dynamic about it.
7