memory-management - 用于以解释语言存储变量的数据结构

Question

我正在设计自己的实验性脚本语言，以便将其嵌入到我更大的应用程序中。

几乎我想做的所有事情都被顺利编程，但是将变量存储在内存中的“简单”行为似乎是这里最难的部分。我不知道如何存储它们以允许对其进行所有类型检查、全局变量和特殊标志。首先看一个示例代码:

a = 1
b = 2

someFunction()
  print(a)   --> This should read the global variable and print `1`
  a = 3      --> Now `a` should become a local variable of this function
                 and the global `a` remain unchanged
  x = 4      --> `x` should always be local of this function
end

我称变量的“局部性”为 level s 所以嵌套 block 中的变量具有更高的级别。在上面的代码中， a和 b是 1 级变量。 someFunction 的局部变量将具有级别 2。函数的第一行应读取全局变量 a (级别 1)但第二行应该再次创建一个名为 a 的变量但在第 2 层阴影下全局 a从那时起。第三行应该创建变量 x 2级。如何在内存中存储和跟踪所有这些？

到目前为止我尝试过的:

方法一:存储 variable=>value的 map 在级别数组中:

variables
{
    level=1 //global variables
    {
        a => 1,
        b => 2
    },
    level=2 //function variables
    {
        a => 3,
        x => 4
    }
}

但这将使变量查找变得非常缓慢，因为必须搜索所有级别以查找给定变量。

方法2:将(变量，级别)对存储为 map 的键:

variables
{
    (a, 1) => 1, //global
    (b, 1) => 2, //global
    (a, 2) => 3, //function
    (x, 2) => 3  //function
}

这与以前有相同的问题，因为我们必须尝试对给定变量的所有可能级别的对 (variable, level)。

我应该使用什么方法来优化内存使用和最快的访问时间？

附加说明:

我知道如何在其他“真实”语言的堆栈和堆上管理变量，但我发现在解释语言上这样做很棘手。 “这不应该是 Lua 和 Python 这样做的方式，”我一直认为。如我错了请纠正我。我正在尝试将变量存储在 map 和内部 C++ 结构中。

最后，这就是我表示变量的方式。你认为它很大并且可以有更多的内存效率表示吗？ (我也尝试将“级别”作为成员在这里，但它也有与另一个相同的问题。)

struct Member
{
    uchar type;  //0=num, 1=str, 2=function, 3=array, etc
    uchar flags; //0x80 = read-only, 0x40 = write-only, etc
    union {
        long double value_num;
        char* value_str;
        int value_func;
        //etc
    };
};

Answer 1

一个简单的事情，类似于你的数组，是维护一堆 map 。每个映射都包含该范围的绑定(bind)。要绑定(bind)变量，请将其添加到顶部 map ；要查找变量，请从堆栈顶部开始，并在到达包含该变量绑定(bind)的映射时停止。搜索需要一点时间，但从顶部/末端开始，您只需搜索直到找到它 - 在大多数情况下，此搜索不会很长。

您还可以通过将此逻辑封装在 Environment 中来使堆栈隐含。具有本地绑定(bind)和用于解析未知变量的继承环境的类。需要进入一个新的范围？以当前环境为基础创建一个新环境，使用它，然后在范围完成时将其丢弃。根/全局环境只能有一个空继承环境。这就是我可能会做的。