如何仅使用单个数组在JavaScript中模拟调用堆栈 [英] How to simulate a call stack in JavaScript using only a single array

问题描述

我正在查看调用堆栈上的 Wikipedia页面，并尝试显示这张图片:

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

据我所知:

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，以及执行堆栈操作所需的所有内容.我如何向它提供数据流以执行一些示例代码?我不是要严格遵守参数顺序或调用约定，主要是因为我还不在那里.但这证明了我要追求的目标.

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

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

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

这基本上是我所能得到的.但是，除了这一系列简单的指令外，我还想了解如何仅使用此数组进行嵌套调用和维护堆栈.另外，为了可读性，我只有这些 JavaScript 局部变量，例如frame_address和operation.实际上，我会这样:

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

这样，我就不会成为利用JavaScript作为机器代码基础上的摘要的牺牲品，而且我可以模拟更现实的VM，就像它是在汇编中实现的一样.任何想法如何做到这一点?

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. 像我有memory[3]一样，帧指针和其他关键内容是否已硬编码到内存中的已知位置?有点事吗?
2. 如何仅使用此内存系统而不是JavaScript对象或任何使其变得更简单(即欺骗㋡)的东西将参数压入堆栈

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 ㋡)

推荐答案

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

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

是的.或者实际上它们是在真实机器中注册的.您可以使用memory[3]，但我建议不要使用

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

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

• at least have function getFp() { return memory[3] } and function setFp(v) { memory[3] = v } to make your code that uses the frame pointer more readable
• simply store it in a var fp next to the var memory.
• or if you insist on using a single memory object, cheat by using memory.fp :)

如何仅使用此存储系统将参数压入堆栈?

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

您对参数"有什么了解?提出一个定义实际上意味着定义一个调用约定. 您可能有一些想法，您的add和store操作似乎遵循堆栈计算机模型而不是寄存器计算机模型，并且在堆栈计算机中，每条指令的使用类似于过程/函数调用.

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.

接下来，您将需要两个说明call和return.我将留下弄清楚它们对您的作用的乐趣:-)

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

您可以参考stack.length而不是操纵tos，甚至使用stack.pop()和stack.push().到目前为止，对于最简单的堆栈机.但是我想你还在考虑作弊.因此，让我们稍微低一点一些，然后将程序，堆栈和静态变量放在同一内存中(从哈佛体系结构切换到冯·诺伊曼体系结构):

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

尝试为此编写翻译.需要注意的一些细节:可变长度指令(add与push 1)，定位要执行的程序，将堆栈放置在何处(提示:您可以使用一些可用空间)，堆栈有限空间(注意堆栈溢出！)，如何/何时停止解释程序.

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.

这篇关于如何仅使用单个数组在JavaScript中模拟调用堆栈的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！