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

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 ы так переменных во вложенных блоках, имеют более высокий уровень. В приведенном выше коде 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: Сохранение (Variable, уровень) пар в качестве ключей карты:

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

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

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

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

Я знаю о том, как переменные управляются в стеке и куче на других «настоящих» языков, но я считаю, это сложно сделать это на интерпретируемых языках. «Это не должно быть так, как это делают Луа и Питон», - я всегда думаю. Поправьте меня если я ошибаюсь. Я пытаюсь сохранить переменную в картах и ​​внутренних структурах C++.

И, наконец, я представляю переменную. Считаете ли вы, что он большой, и могут быть более эффективные с точки зрения памяти представления? (Я также попытался поставить «Level» в качестве члена здесь, но это была та же проблема, как и другие тоже.)

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). То, что это позволяет вам, - это доступ к переменным в области вашего звонящего, но это позволяет избежать некоторого дорогостоящего поиска, связанного с требованием указать, где именно вы укажете, откуда эта переменная (с одним уровнем на уровне стека вызовов, 2 на два уровня вверх, и # 0 является «специальным», говоря «самый верхний стек вызовов, глобальный»