Структура данных для хранения переменных в интерпретируемом языке

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, поэтому переменные во вложенных блоках имеют более высокий уровень.В приведенном выше коде a и b являются переменными уровня 1.Локальные переменные someFunction будут иметь уровень 2. Первая строка функции должна читать глобальную переменную a (уровень 1), но вторая строка должна снова создать переменную с именем a, но с уровнем 2, который затеняет глобальную a с этого момента.Третья строка должна создать переменную x с уровнем 2. Как хранить и отслеживать все это в памяти?

Что я пробовал до сих пор:

Метод 1: Хранение карт variable=>value в массиве уровней:

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

Но это сделает поиск переменных очень медленным, так как нужно искать все уровни для данной переменной.

Метод 2: Хранение пар (переменных, уровня) в качестве ключей карты:

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

Это та же проблема, что и раньше, так как мы должны попробовать пару (переменная, уровень) со всеми возможнымиуровни для данной переменной.

Какой метод следует использовать для оптимального использования памяти и максимально быстрого времени доступа?

Дополнительные примечания:

Я знаю окак переменные управляются в стеке и куче на других «реальных» языках, но мне сложно сделать это на интерпретируемом языке.«Это не должно быть так, как это делают Луа и Питон», - всегда думаю я.Поправьте меня если я ошибаюсь.Я пытаюсь сохранить переменную в картах и ​​внутренних структурах 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

Легкая вещь, аналогичная вашему массиву, - это поддержка стека карт.Каждая карта содержит привязки для этой области.Чтобы связать переменную, добавьте ее в верхнюю карту;чтобы найти переменную, начните с верха стека и остановитесь, когда достигнете карты, содержащей привязку для этой переменной.Поиск занимает немного времени, но начиная с верха / конца, вам нужно только искать, пока вы его не найдете - в большинстве случаев этот поиск не будет очень длинным.

Вы также можете сделать стек неявным путем инкапсуляцииэта логика в классе Environment с локальными привязками и унаследованной средой, используемой для разрешения неизвестных переменных.Нужно войти в новую сферу?Создайте новую среду с текущей средой в качестве основы, используйте ее, а затем отмените ее, когда область будет завершена.Корневая / глобальная среда может просто иметь нулевую унаследованную среду.Это то, что я, вероятно, сделал бы.

Answer 2

Стоит отметить, что если внутри функции у вас нет доступа к каким-либо переменным из функции вызывающей стороны, это уменьшает количество уровней, которые вам нужно посмотреть. Например:

variable a;

function one() {
    variable b;
    // in this function, we can see the global a, local b
    two();
}

function two() {
    // in this function, we can see the global a, local c
    // we cannot see the local b of our caller
    variable c;
    while (true) {
        variable d;
        // here we can see local d, local c, global a
    }
}

Идея состоит в том, что границы функций ограничивают видимость переменных, а глобальная область видимости "особенная".

При этом вы можете рассмотреть вопрос об удалении специальных глобальных переменных, но разрешить коду указывать, что они хотят получить доступ к нелокальным переменным

variable a;

function one() {
    global a; // or upvar #0 a;
    variable b;
    // in this function, we can see the global a, local b
    two();
}

function two() {
    // in this function, we can see the local c
    // and the local b of our caller
    // (since we specifically say we want access to "b" one level up)
    upvar 1 b;
    variable c;
}

Сначала это выглядит сложно, но действительно легко понять, как только вы к этому привыкнете (upvar - это конструкция из языка программирования Tcl). То, что он позволяет вам, - это доступ к переменным в области видимости вашего вызывающего, но он позволяет избежать некоторых дорогостоящих поисков, требующих, чтобы вы точно указали, откуда берется эта переменная (где 1 - один уровень вверх по стеку вызовов, 2 - два уровня вверх, и # 0 является «особенным», говоря «самый верхний стек вызовов, глобальный)