如何仅使用单个数组在 JavaScript 中模拟调用堆栈

Question

我正在查看调用堆栈上的 Wikipedia page，并试图理解这张图片：

这是我所了解的，哈哈：

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)

但是假设我们有 2 个操作：add == 1 和 load == 2，加上进行堆栈操作所需的任何操作。我如何向它提供数据流以执行一些示例代码？我不会严格遵守参数顺序或调用约定，主要是因为我还没有做到这一点。但这证明了我想要得到的东西。

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

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

这就是我们想要完成的。这就是我想象的（某种程度上）它在内存中的布局方式：

// 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

现在执行。我们甚至还没有嵌套的子例程，我离弄清楚还差得很远，但我想有人很容易知道它并且可以用一些演示 JavaScript 代码来展示它。因此，这是我尝试进行代码评估的尝试，例如构建处理器或 VM 之类的东西，以评估代码。

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
    }
  }
}

这基本上是我能得到的。但我想，除了这个简单的指令列表之外，还想看看如何只使用这个数组进行嵌套调用和维护堆栈。此外，我只有这些 JavaScript 局部变量，如 frame_address 和 operation 以提高可读性。实际上我会这样做：

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
    }
  }
}

这样我就不会成为利用 JavaScript 在机器代码之上提供的抽象的牺牲品，而且我可以模拟一个更真实的虚拟机，就好像它是在汇编中实现的一样。任何想法如何做到这一点？

我在执行此操作时遇到的一些关键问题包括：

帧指针和其他关键内容是否被硬编码到内存中的已知位置，就像我有 memory[3]？有点事？
如何仅使用此内存系统而不是 JavaScript 对象或任何会使它更容易的东西（即作弊㋡）将参数压入堆栈

Answer 1

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

是的。或者实际上它们是真实机器中的寄存器。您可以使用 memory[3]，但我建议您使用

至少要有 function getFp() { return memory[3] } 和 function setFp(v) { memory[3] = v } 才能使使用帧指针的代码更具可读性
只需将其存储在 var memory 旁边的 var fp 中。
或者如果您坚持使用单个 memory 对象，请使用 memory.fp 作弊 :)

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

你对"parameter"的理解是什么？提出它的定义实际上意味着定义一个调用约定。您可能有一些想法，您的 add 和 store 操作似乎遵循堆栈机器模型而不是寄存器机器模型，并且在堆栈机器中，每条指令的使用类似于 procedure/function 打电话。

接下来，您将需要两条指令call和return。我会留下弄清楚他们对你做了什么的乐趣:-)

let operation = memory[frame_address]

呃，不。当前指令由程序计数器决定。 帧地址 与您的解释器循环无关。在开始使用堆栈进行函数调用之前，我建议先获得一个可用的解释器。这是一个粗略的草图：

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;
    }
  }
}

您可以参考 stack.length 甚至使用 stack.pop() 和 stack.push()，而不是操纵 tos。到目前为止最简单的堆栈机器。但我猜你还在考虑作弊。因此，让我们稍微降低一点，将程序、堆栈和静态变量放在同一内存中（从哈佛架构切换到冯诺依曼架构）：

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,
]

尝试为此编写一个解释器。需要注意的一些细节：可变长度指令（add vs push 1），定位要执行的程序，放置堆栈的位置（提示：有一些空闲 space你可以使用），有限的堆栈 space（注意堆栈溢出！），how/when 停止解释程序。

请注意，在处理递归函数调用之前，您需要研究分支，即条件跳转。

如何仅使用单个数组在 JavaScript 中模拟调用堆栈

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

javascript

algorithm

assembly

callstack

vm-implementation