如何在解释器中跟踪变量索引
How to track the index of variables in an interpreter
我正在创建一个解释器（一个字节码解释器，也是一个编译器），我发现了一个我无法解决的问题。我需要在某处存储变量。将它们存储在字典中并在运行时查找它们会变慢，所以我想将它们存储在寄存器中并使用它们的索引而不是它们的名称。
所以在编译时我给每个变量一个索引，并创建一个寄存器数组。这对于单一范围的语言来说很好。但是我为其创建解释器的语言具有嵌套范围（和函数调用）。所以另一种方法可能是我有一组全局寄存器，以及一堆用于函数调用的寄存器列表。所以我的虚拟机会是这样的：
Register globalRegisters[NUMBER_OF_GLOBALS];
Stack<Register[]> callstack;
但是还有一件事。我的语言允许函数内嵌函数。示例：
var x = 1;
function foo() {
y = 2;
function bar() {
z = 3;
y = y - 1;
}
}
函数bar()引用了一个属于foo()的变量。所以这意味着虚拟机必须查看堆栈顶部寄存器下方的寄存器列表。但是如果 bar() 是递归的呢？如果递归次数由用户输入定义怎么办？那么虚拟机就不知道要找到包含 y 值的寄存器组需要经过多少个堆栈元素。
什么是解决此问题的有效方法？这是我第一次处理寄存器，计算发生在值堆栈上。
表示闭包的常用方法是创建一个包含函数指针本身及其环境的结构。表示环境的最简单方法是作为指向外部函数堆栈帧的指针。然后，在访问外部函数的变量时，内部函数可以简单地取消引用该指针（当然是给定变量的偏移量）。
然而还有另一个问题你必须考虑：如果 foo returns bar 然后 bar 在 foo 之后被调用怎么办 return编辑？在这种情况下，指向 foo 的堆栈帧的指针将无效，因为该堆栈帧此时将不再存在。因此，如果您想允许这种情况（而不是简单地使其对 return 函数非法），您需要另一种解决方案。
一个常见的解决方案是将所有局部变量表示为指向堆分配值的指针，并将所有这些指针的副本存储在函数的结构中。
另一个解决方案是限制闭包，这样外部函数的变量只有在永远不会被重新分配的情况下才能被内部函数访问。这就是 Java 8 中的闭包所做的。然后结构可以简单地包含变量的副本而不是指针。
我认为这里的基本问题与您所写的问题有很大不同，所以我写了一篇解释为什么我认为这个问题格式错误以及我认为基本问题是什么的答案。如果我弄错了，我深表歉意，但请多多包涵 :-)
题目的问题
I'm creating an interpreter (a bytecode interpreter, so also a compiler)
解释器不是编译器，即使它是针对低级语言的——除非你的意思是你的程序既将某种语言编译成某种字节码解释，又对其进行解释。在任何情况下，除非你在 jitting 代码，否则实际上 运行 的程序就是解释器。
Storing them in a dictionary and looking them up at runtime would be way to slow, so I'd like to store them in registers and use their indexes instead of their name.
在解释器中，将目标语言变量强制写入寄存器对我来说并不合适。例如，假设您有一种方法可以解释使用变量的特定语句。您可以快速提取变量，因为您将它们强制放入寄存器中，但是对于 运行 有效地在您自己的方法中进行操作的寄存器太少了。另外，说 "yea, I'll just store those in registers" 让我怀疑你高估了可用的寄存器数量。
我猜 "registers" 这是一个误称，您只关心在存在嵌套范围和递归的情况下存储和访问局部变量的一些有效方法。所以我认为你的问题真的可以表述为 "I want some data structure storing locals, how do I do that in the presence of nested scopes and recursive functions?" 如果我错了，我很抱歉，但如果不是：
我的回答
要回答"I want some data structure storing locals, how do I do that in the presence of nested scopes and recursive functions?"，我认为最好首先在局部上下文中阐明作用域和框架之间的区别。
A scope 是标识符到局部变量的一些映射。在范围内，您知道 x 标识符的所有实例（大致）指的是同一事物。范围是您在解析输入语言时关心的东西 - 它是您用来理解代码语义的东西 ("oh, the x the coder is incrementing is the same x from 2 lines ago")。
A frame 是调用函数时分配的内存（通常在堆栈上）。每个本地通常会在框架上保留一个位置来存储其值。
当你解析代码时，处理范围，你不关心递归（因为你不是 运行 任何东西，只是解析）。您确实关心嵌套范围，但它们永远不会不受约束——因为代码本身（不是它的执行，只是代码）总是有限的。解析时处理范围内局部变量的标准方法是保留字典堆栈。打开范围时创建并推送一个新字典，关闭时弹出它。每当访问 x 时，在堆栈中最顶层字典的字典中查找它 - 如果不存在，则继续下一个，依此类推。
您生成的代码（或在解释器中直接执行）将准确知道 x 的每个实例所指的位置。这些内存位置将在创建框架时分配。这样你也不关心递归 - 你已经将变量映射到当前帧中的位置，并且无论从何处调用该帧都是有效的。
最后说一下闭包
在我现在能记得的所有语言中，闭包通过在 定义 时间捕获封闭变量来工作。例如，在 Java 中，在属于外部 class 的内部 class 中访问的每个本地，实际上，在它的创建 - 将其视为构建内部 class 的另一个论据。 C++ 更明确地说明它捕获哪些变量，但除此之外它的工作原理是一样的——lambda 对象只是在创建时获取传递给它的那些变量（按值或按引用，具体取决于指令）。在任何情况下，捕获的对象在捕获后都与原始对象不同（它们可能都是指向同一个地方的指针，但这并不意味着它们是同一个对象），所以应该不难解析。
我正在创建一个解释器（一个字节码解释器，也是一个编译器），我发现了一个我无法解决的问题。我需要在某处存储变量。将它们存储在字典中并在运行时查找它们会变慢，所以我想将它们存储在寄存器中并使用它们的索引而不是它们的名称。
所以在编译时我给每个变量一个索引，并创建一个寄存器数组。这对于单一范围的语言来说很好。但是我为其创建解释器的语言具有嵌套范围（和函数调用）。所以另一种方法可能是我有一组全局寄存器，以及一堆用于函数调用的寄存器列表。所以我的虚拟机会是这样的：
Register globalRegisters[NUMBER_OF_GLOBALS];
Stack<Register[]> callstack;
但是还有一件事。我的语言允许函数内嵌函数。示例：
var x = 1;
function foo() {
y = 2;
function bar() {
z = 3;
y = y - 1;
}
}
函数bar()引用了一个属于foo()的变量。所以这意味着虚拟机必须查看堆栈顶部寄存器下方的寄存器列表。但是如果 bar() 是递归的呢？如果递归次数由用户输入定义怎么办？那么虚拟机就不知道要找到包含 y 值的寄存器组需要经过多少个堆栈元素。
什么是解决此问题的有效方法？这是我第一次处理寄存器，计算发生在值堆栈上。
表示闭包的常用方法是创建一个包含函数指针本身及其环境的结构。表示环境的最简单方法是作为指向外部函数堆栈帧的指针。然后，在访问外部函数的变量时，内部函数可以简单地取消引用该指针（当然是给定变量的偏移量）。
然而还有另一个问题你必须考虑：如果 foo returns bar 然后 bar 在 foo 之后被调用怎么办 return编辑？在这种情况下，指向 foo 的堆栈帧的指针将无效，因为该堆栈帧此时将不再存在。因此，如果您想允许这种情况（而不是简单地使其对 return 函数非法），您需要另一种解决方案。
一个常见的解决方案是将所有局部变量表示为指向堆分配值的指针，并将所有这些指针的副本存储在函数的结构中。
另一个解决方案是限制闭包，这样外部函数的变量只有在永远不会被重新分配的情况下才能被内部函数访问。这就是 Java 8 中的闭包所做的。然后结构可以简单地包含变量的副本而不是指针。
我认为这里的基本问题与您所写的问题有很大不同，所以我写了一篇解释为什么我认为这个问题格式错误以及我认为基本问题是什么的答案。如果我弄错了，我深表歉意，但请多多包涵 :-)
题目的问题
I'm creating an interpreter (a bytecode interpreter, so also a compiler)
解释器不是编译器，即使它是针对低级语言的——除非你的意思是你的程序既将某种语言编译成某种字节码解释，又对其进行解释。在任何情况下，除非你在 jitting 代码，否则实际上 运行 的程序就是解释器。
Storing them in a dictionary and looking them up at runtime would be way to slow, so I'd like to store them in registers and use their indexes instead of their name.
在解释器中，将目标语言变量强制写入寄存器对我来说并不合适。例如，假设您有一种方法可以解释使用变量的特定语句。您可以快速提取变量，因为您将它们强制放入寄存器中，但是对于 运行 有效地在您自己的方法中进行操作的寄存器太少了。另外，说 "yea, I'll just store those in registers" 让我怀疑你高估了可用的寄存器数量。
我猜 "registers" 这是一个误称，您只关心在存在嵌套范围和递归的情况下存储和访问局部变量的一些有效方法。所以我认为你的问题真的可以表述为 "I want some data structure storing locals, how do I do that in the presence of nested scopes and recursive functions?" 如果我错了，我很抱歉，但如果不是：
我的回答
要回答"I want some data structure storing locals, how do I do that in the presence of nested scopes and recursive functions?"，我认为最好首先在局部上下文中阐明作用域和框架之间的区别。
A scope 是标识符到局部变量的一些映射。在范围内，您知道 x 标识符的所有实例（大致）指的是同一事物。范围是您在解析输入语言时关心的东西 - 它是您用来理解代码语义的东西 ("oh, the x the coder is incrementing is the same x from 2 lines ago")。
A frame 是调用函数时分配的内存（通常在堆栈上）。每个本地通常会在框架上保留一个位置来存储其值。
当你解析代码时，处理范围，你不关心递归（因为你不是 运行 任何东西，只是解析）。您确实关心嵌套范围，但它们永远不会不受约束——因为代码本身（不是它的执行，只是代码）总是有限的。解析时处理范围内局部变量的标准方法是保留字典堆栈。打开范围时创建并推送一个新字典，关闭时弹出它。每当访问 x 时，在堆栈中最顶层字典的字典中查找它 - 如果不存在，则继续下一个，依此类推。
您生成的代码（或在解释器中直接执行）将准确知道 x 的每个实例所指的位置。这些内存位置将在创建框架时分配。这样你也不关心递归 - 你已经将变量映射到当前帧中的位置，并且无论从何处调用该帧都是有效的。
最后说一下闭包
在我现在能记得的所有语言中，闭包通过在 定义 时间捕获封闭变量来工作。例如，在 Java 中，在属于外部 class 的内部 class 中访问的每个本地，实际上，在它的创建 - 将其视为构建内部 class 的另一个论据。 C++ 更明确地说明它捕获哪些变量，但除此之外它的工作原理是一样的——lambda 对象只是在创建时获取传递给它的那些变量（按值或按引用，具体取决于指令）。在任何情况下，捕获的对象在捕获后都与原始对象不同（它们可能都是指向同一个地方的指针，但这并不意味着它们是同一个对象），所以应该不难解析。