javascriptalgorithmassemblycallstackvm-implementation

How to simulate a call stack in JavaScript using only a single array

I am looking at the Wikipedia page on Call Stack, and trying to grok this image:

enter image description here

This is as far as I get lol:

const memory = []
memory[0] = 3 // top of stack pointer
memory[1] = 4 // stackframe pointer
memory[2] = 1000 // max call stack size

memory[3] = 5 // first frame
memory[4] = 0 // first frame return address (exit let's say)

But let's say we have 2 actions: add == 1, and load == 2, plus whatever is required to do the stack manipulation. How do i feed it a stream of data to execute some example code? I'm not being to stringent on the parameter order or calling conventions, mainly because I'm not there yet. But this demonstrates what I'm trying to get after.

function add_twice(a, b, c) {
  add(a, add(b, c))
}

function start() {
  add_twice(1, 2, 3)
}

So that's what we want to accomplish. This is what I imagine (sort of) how it's laid out in memory:

// this is as far as I can get,
// just trying to simulate the `add` function
memory[5] = 2 // load
memory[6] = 100 // some address?
memory[7] = 1 // the first number to add

memory[8] = 2 // load
memory[9] = 101 // some address?
memory[10] = 2 // the second number to add

memory[11] = 1 // call `add`
memory[12] = 102 // where to store result

Now for the execution. We don't even have the nested subroutines yet, I am nowhere close to figuring that out, but I imagine someone knows it easily and could show it with some demo JavaScript code. So here is my attempt at doing the code evaluation, like building a processor or VM sort of thing, to evaluate the code.

function evaluate() {
  while (true) {
    let frame_address = memory[3]
    let operation = memory[frame_address]
    switch (operation) {
      case 2: // load
        let a = memory[operation + 1]
        let b = memory[operation + 2]
        memory[a] = b
        memory[frame_address] = operation + 3
        break
      case 1: // add
        let a = memory[operation + 1]
        let input_a = ??
        let input_b = ??
        break
    }
  }
}

That's basically as far as I can get. But I would like to, in addition to just this flat list of instructions, see how to do nested calls and maintain the stack, using only this array. Also, I only have these JavaScript local variables like frame_address and operation for readability. In reality I would do it like this:

function evaluate() {
  while (true) {
    switch (memory[memory[3]]) {
      case 2: // load
        memory[something_a] = memory[memory[memory[3]] + 1]
        memory[something_b] = memory[memory[memory[3]] + 2]
        memory[memory[3]] = memory[memory[3]] + 3
        break
      case 1: // add
        memory[something_a_2] = memory[memory[memory[3]] + 1]
        memory[something_input_a_2] = ??
        memory[something_input_b_2] = ??
        break
    }
  }
}

That way I am not falling victim to taking advantage of what JavaScript offers as abstration on top of the machine code, and I can simulate a more realistic VM as if it was implemented in assembly. Any ideas how to do this?

Some key questions I have in doing this include:

  1. Are the frame pointer and other key things hardcoded into a known place in memory, like I have memory[3]? Sort of thing?
  2. How to push parameters onto the stack using only this memory system, not JavaScript object or anything that would make it a lot easier (i.e. cheating ㋡)
Solution

  • Are the frame pointer and other key things hardcoded into a known place in memory?

    Yes. Or actually they're registers in a real machine. You could use memory[3], but I would recommend instead to either

    How to push parameters onto the stack using only this memory system?

    What do you understand by "parameter"? Coming up with a definition of it actually means defining a calling convention. You probably have something in mind, your add and store operations seem to follow a stack machine model instead of a register machine model, and in a stack machine each instruction is used similar to a procedure/function call.

    Next, you will need two instructions call and return. I'll leave the fun of figuring out what they do exactly to you :-)

    let operation = memory[frame_address]

    Uh, no. The current instruction is determined by the program counter. The frame address is irrelevant in your interpreter loop. Before starting with function calls using the stack, I would recommend to get a working interpreter first. Here's a rough sketch:

    const program = [
  {op: "push", val: 1},
  {op: "push", val: 2},
  {op: "add"},
  {op: "push", val: 3},
  {op: "add"},
  {op: "print"},
];
const stack = [];
let tos = 0; // top of stack: alias for `stack.length`
let pc = 0; // program counter: index into `program`

while (pc >= 0 && pc < program.length) {
  const instruction = program[pc++];
  switch (instruction.op) {
    case "push": {
      stack[tos++] = instruction.val;
      break;
    }
    case "add": {
      const b = stack[tos--];
      const a = stack[tos--];
      const res = a+b;
      stack[tos++] = res;
      break;
    }
    case "print": {
      const x = stack[tos--];
      console.log("Printing", x);
      break;
    }
  }
}

    Instead of manipulating tos, you could have referred to stack.length and even used stack.pop() and stack.push(). So far for the simplemost stack machine. But I guess you're still considering that cheating. So let's get a bit lower-level and put program and stack and static variables in the same memory (switching from a Harvard architecture to a von Neumann one):

    const memory = [
  8, // initial program counter
  0,
  0,
  0,
  0,
  0,
  0,
  0,
  "push",
  1,
  "push",
  2,
  "add",
  "push",
  3,
  "add",
  "print",
  "exit",
  0,
  0,
]

    Try writing an interpreter for that. Some details that need to be taken care of: variable-length instructions (add vs push 1), locating the program to execute, where to place the stack (hint: there's some free space you can use), having limited stack space (taking care of stack overflows!), how/when to stop interpreting the program.

    Notice that before working on recursive function calls, you need to investigate branching, i.e. conditional jumps.