javascript - 如何仅使用单个数组在 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 代码来展示它。因此，这是我尝试进行代码评估，例如构建处理器或虚拟机之类的东西，以评估代码。

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 在机器代码之上提供的抽象功能的受害者，并且我可以模拟一个更真实的虚拟机，就好像它是在汇编中实现的一样。有什么想法可以做到这一点吗？

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

1. 帧指针和其他关键内容是否已硬编码到内存中的已知位置，就像我有内存[3]？之类的东西？
2. 如何仅使用此内存系统而不是 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 fp 中即可旁边var memory .
• 或者如果您坚持使用单个 memory对象，通过使用memory.fp作弊:)

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

你对“参数”的理解是什么？给出它的定义实际上意味着定义一个调用约定。您可能有一些想法，您的 add和store操作似乎遵循堆栈机模型而不是寄存器机模型，并且在堆栈机中，每个指令的使用类似于过程/函数调用。

接下来，您将需要两条指令 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;
    }
  }
}

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

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 与 push 1 )、定位要执行的程序、堆栈的放置位置(提示:有一些可用空间可以使用)、堆栈有限空间(注意堆栈溢出!)，如何/何时停止解释程序。

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