Trick or technique to allocating variables given only one “memory store”?

Question

I have a problem where I am using a Uint32Array in JavaScript as a store:

const store = new Uint32Array(1 << 16)

I am going to use this store like a runtime environment. Basically, everything occurs within this store (all functions are defined here, all data is stored here). Ignore the implementation detail of having to call "native" driver methods in the actual environment to perform the real action (like addition, saving to store, reading from store, etc.). For now just assume that the main problem is how to read and write to the store without creating any temporary variables.

That is, how do I allocate stuff on "the stack" and know where I can actually place something new? And how do I keep it organized, knowing where things are in the store?

What I'm stuck at is step number 1 basically.

store[0] = 1
store[1] = 2
store[2] = store[0] + store[1]

This is different than cheating and using temporary variables:

let a = 1
let b = 2
store[2] = a + b

Imagine it gets more complicated and I am dynamically reading a stream of input and parsing it. Not only that, say our store has already been filled in to some degree. So it's not just as easy to do this:

let address = 0
let i = 0
while (input.length) {
  store[address] = input[i++]
  store[address + 1] = input[i++]
  store[address + 2] = store[address] + store[address + 1]
  store[address + 3] = store[address + 1] << store[address + 2]
  address = address + 4
}

Well really it's like this (no temporary variables, other than the input which comes from the environment):

store[0] = 0 // first address
store[1] = 0 // i
while (input.length) {
  store[store[0]] = input[i++]
  store[store[0] + 1] = input[i++]
  store[store[0] + 2] = store[store[0]] + store[store[0] + 1]
  store[store[0] + 3] = store[store[0] + 1] << store[store[0] + 2]
  store[0] = store[0] + 4
}

You need to keep track of something else, like the available places in memory to write to. But where I get lost, and where my question comes about, is if you have the notion of memory allocation blocks, you still need to store those into the store as well! So it's like the chicken and egg problem and my mind shuts down.

How do you handle this situation? What is the key trick or technique? Do you need the notion of magic numbers or special places in the store where certain things are put? That sort of stuff.

Answer 1

What you describe in your question looks very similar to an emulator for a CPU. Even if you are not exactly writing that, you can use the information on CPU emulators as inspiration for solving problems you encounter.

If you are actually writing an emulator, keep in mind that nearly all processors cheat in that they use some non-memory storage for intermediate results and very frequently used bits of information. This non-memory storage is the set of registers of the processor.

One important register is the Instruction Pointer (IP) and it refers to the current (or next, depending on processor architecture) instruction that will be executed. The IP is updated automatically when executing an instruction and saved automatically when calling a subroutine.

Another important register is the Stack Pointer (SP) which points into the stack area of the memory.

As for the memory, that can be divided into three parts:

• Global variables (or rather, variables with a lifetime equal to that of the application). These variables have a fixed address that is determined when building the application and these addresses are mentioned literally in the instruction stream.
• Stack-allocated variables. These are often parameters to functions and local variables. During compilation, the compiler determines their location relative to the Stack Pointer register. The variables are then accessed with relative addressing (6 bytes below the SP; 4 bytes above the SP, etc.).
• Heap allocated variables. The heap is a part of the memory that is managed either by the language runtime or library functions. In either case, there will be global variables keeping track of which parts of the heap are used and which parts are free (often using a tree or list-like data structure where the first node is referenced by a global variable).

Using pointer variables (variables that store a memory location as their value), you can reference from one part of the memory to another part.