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

问题描述

我正在查看调用堆栈上的Wikipedia 页面，并尝试了解此图像：

据我所知，这是大声笑：

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

我这样做的一些关键问题包括：

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

标签： javascriptalgorithmassemblycallstackvm-implementation

解决方案

帧指针和其他关键内容是否硬编码到内存中的已知位置？

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

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

如何仅使用此内存系统将参数推送到堆栈上？

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

接下来，您将需要两条指令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()and而不是操纵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,
]

尝试为此编写解释器。一些需要注意的细节：可变长度指令（addvs push 1），定位要执行的程序，放置堆栈的位置（提示：您可以使用一些可用空间），有限的堆栈空间（照顾堆栈溢出！），如何/何时停止解释程序。

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

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

问题描述

解决方案

推荐阅读