How to simulate the call stack with parameters and local variables in JavaScript with 1 global memory array?

Question

I have been stuck on this for a few days. Basically I can sum it up into asking, how do you simulate this function like it were written in assembly (or machine code even, something using only 1 memory array), but doing everything in JavaScript?

function start() {
  let x = doX(1, 2)
  let y = doX(3, 4)
  let z = doX(x, y)
  return z
}

function doX(a, b) {
  let x = a + b
  let y = a - b
  let z = x * y
  return z
}

So my attempt at it is something along these lines:

const memory = []

function start() {
  // capture push (function prologue)?
  memory[0] = 1
  memory[1] = 2
  doX()
  memory[2] = memory[100]
  memory[0] = 3
  memory[1] = 4
  doX()
  memory[0] = memory[2]
  memory[1] = memory[100]
  doX()
  // capture pop (function epilogue)?
  memory[100] = memory[100]
}

function doX() {
  // somehow allocate space "on the stack"
  // using only this memory object?
  // don't know how to do that....
  memory[10] = memory[0] + memory[1]
  memory[11] = memory[0] - memory[1]
  memory[12] = memory[10] * memory[11]
  // put it on the return register?
  memory[100] = memory[12]
}

How do I properly add the push and pop operations using only this memory array and make this look right? Also, I hardcoded all the memory addresses, how do I properly make them relative?

Answer 1

You need a stack pointer, either as a separate global (like a CPU with registers separate from memory), or just pick a memory location for this special use. Like @bergi explained in answer to your earlier question, you need to do things like memory[tos++] to push things on the stack, instead of assuming that the starting value of the stack pointer is 0 by hard-coding stores to memory[0].

(In many ISAs, including x86, the stack pointer starts at the highest address in a region, and pushing stuff on the stack subtracts from the stack pointer. So it grows down).

You're already using memory[100] as a return-value register instead of letting JavaScript return a value. Use memory[99] as a stack pointer if you want, so you might have something like mem[ --mem[99] ] = val_to_push. It's obviously much more readable if you use a separate variable that you can call sp, or state.sp if you want to define a state object with memory and some scalar registers including a sp stack pointer.

---

Real calling conventions return in registers, not memory; using a retval register "in memory" is an unnecessary complication. It's still CPU-like if you let JS functions return values via the JS mechanism, and consider that a register. As long as you limit it to simple numbers.

Since you get to make up the details of your machine, you could use JS local variables as scratch registers, and allow functions to have as many as they want.

So programming for this machine is somewhat like LLVM-IR where you just use as many "registers" as you want and LLVM takes care of where to actually store them. But not really; your code wouldn't "compile" to spill excess registers to the stack, it really does have as many registers as you care to use.

To treat them as registers and not let it degenerate into pure JS that doesn't use memory[], you could still require arg passing to happen via memory (i.e. a stack-args calling convention), and pretend that a function call destroyed the values of all local variables.