Estructura de datos para almacenar variables en un lenguaje interpretado

Question

Estoy diseñando mi propio lenguaje de scripting experimental con el fin de incrustarlo en mi aplicación más grande.

Casi todo lo que quería hacer se programó sin problemas, pero el acto "simple" de almacenar variables en la memoria parecía ser la parte más difícil aquí. No sé cómo almacenarlos para permitir todas las comprobaciones de tipos, variables globales y banderas especiales en ellos. Primer vistazo a un código de ejemplo:

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 

Debo llamar a la "localidad" de las variables de sus level es tan variables en bloques anidados tienen un nivel más alto. En el código anterior, a y b son variables de nivel 1. Las variables locales de alguna función tendrán el nivel 2. La primera línea de la función debería leer la variable global a (nivel 1) pero la segunda línea debería crear nuevamente una variable llamada a pero con el nivel 2 que sombrea el a global desde ese punto en adelante. La tercera línea debería crear la variable x con nivel 2. ¿Cómo almacenar y realizar un seguimiento de todo esto en la memoria?

lo que he intentado hasta ahora:

Método 1: Almacenamiento de mapas de variable=>value en variedad de niveles:

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

Pero eso va a hacer que la variable de consulta muy lento ya que uno tiene que buscar todos los niveles para una variable dada.

Método 2: Almacenamiento de los (, nivel variable) pares como las llaves de un mapa:

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

Esto tiene el mismo problema que antes ya que tenemos que tratar el par (variable, nivel) con todas las posibles niveles para una variable dada.

¿Qué método debo usar para optimizar el uso de la memoria y el tiempo de acceso más rápido?

Notas adicionales:

que sé acerca de cómo las variables se gestionan en la pila y montón de otras lenguas "reales", pero me resulta difícil de hacer esto en un lenguaje interpretado. "Esto no debe ser como lo hacen Lua y Python", siempre pienso. Corrígeme si estoy equivocado. Intento almacenar la variable en mapas y estructuras internas de C++.

Y, por último, así es como represento una variable. ¿Crees que es grande y que puede haber más representaciones eficientes en la memoria? (También he tratado de poner el "nivel" como miembro aquí, pero tenía el mismo problema que el otro también.)

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

Una cosa fácil de hacer, de forma similar a la matriz, es mantener una pila de mapas. Cada mapa contiene los enlaces para ese alcance. Para enlazar una variable, agréguela al mapa superior; para buscar una variable, comience en la parte superior de la pila y cese cuando llegue a un mapa que contiene un enlace para esa variable. La búsqueda lleva un poco, pero a partir de la parte superior/final solo tienes que buscar hasta que la encuentres; en la mayoría de los casos, esta búsqueda no será muy larga.

También puede hacer que la pila esté implícita al encapsular esta lógica en una clase Environment que tenga enlaces locales y un entorno heredado utilizado para resolver variables desconocidas. ¿Necesitas entrar en un nuevo alcance?Cree un nuevo entorno con el entorno actual como su base, úselo y luego deséchelo cuando termine el alcance. El entorno raíz/global solo puede tener un entorno heredado nulo. Esto es lo que probablemente haría.

Answer 2

Vale la pena señalar que si, dentro de una función, no tiene acceso a ninguna variable de la función de llamada, se reduce el número de niveles que debe mirar. Por ejemplo:

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

La idea es que los límites de la función límite de la visibilidad de las variables, con el alcance global de ser "especial".

Dicho esto, se puede considerar la eliminación de lo especial de variables globales, pero permitiendo que el código para especificar que quieren tener acceso a las variables no locales

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

Parece complicado al principio, pero es muy fácil para entender una vez que te acostumbras (upvar es una construcción del lenguaje de programación Tcl). Lo que le permite es acceso a variables en el alcance de su interlocutor, pero evita parte de la búsqueda costosa al requerir que especifique exactamente de dónde viene esa variable (con 1 un nivel arriba de la pila de llamadas, 2 está dos niveles arriba, y # 0 siendo "especial" al decir "la pila de llamadas más alta, la global"