Struttura dati per la memorizzazione di variabili in un linguaggio interpretato

Question

Sto progettando il mio linguaggio di scripting sperimentale allo scopo di incorporarlo nella mia applicazione più grande.

Quasi tutto ciò che volevo fare era programmato senza problemi, ma il "semplice" atto di memorizzare le variabili in memoria sembrava essere la parte più difficile qui. Non so come memorizzarli per consentire il controllo di tutti i tipi, le variabili globali e le bandiere speciali su di essi. Primo sguardo a un codice di esempio:

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 

io chiamo il "località" di variabili loro level s così variabili in blocchi nidificati hanno un livello più elevato. Nel codice precedente, a e sono variabili di livello 1. Le variabili locali di someFunction avranno il livello 2. La prima riga della funzione dovrebbe leggere la variabile globale a (livello 1) ma la seconda riga dovrebbe creare nuovamente una variabile denominata a ma con il livello 2 che ombreggia il a globale da quel punto in poi. La terza riga dovrebbe creare la variabile x con il livello 2. Come memorizzare e tenere traccia di tutti questi in memoria?

quello che ho provato finora:

Metodo 1: Memorizzazione mappe di variable=>value nella gamma di livelli:

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

Ma che farà look-up variabile molto lento in quanto si deve cercare tutti i livelli per una determinata variabile.

Metodo 2: Memorizzazione dei (, livello variabile) paia come chiavi di una mappa:

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

Questo ha lo stesso problema di prima poiché abbiamo provare la coppia (variabile, livello) con tutte le possibili livelli per una data variabile.

Quale metodo devo utilizzare per l'utilizzo ottimale della memoria e il tempo di accesso più veloce?

Note aggiuntive:

che so su come le variabili sono gestiti su stack e heap su altri linguaggi "reali", ma trovo difficile da fare questo su un linguaggio interpretato. "Questo non deve essere quello che fanno Lua e Python", penso sempre. Correggimi se sbaglio. Sto cercando di memorizzare la variabile in mappe e strutture interne in C++.

E infine, questo è il modo in cui rappresento una variabile. Pensi che sia grande e ci possono essere più rappresentazioni efficienti per la memoria? (Ho anche provato a mettere il "livello" come membro qui ma aveva lo stesso problema come l'altro anche.)

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 facile da fare, simile a l'array, è quello di mantenere un pila di mappe. Ogni mappa contiene i collegamenti per tale ambito. Per associare una variabile, aggiungila alla mappa superiore; per cercare una variabile, inizia in cima allo stack e fermati quando raggiungi una mappa che contiene un legame per quella variabile. La ricerca richiede un po ', ma partendo dalla parte superiore/finale devi solo cercare finché non la trovi - nella maggior parte dei casi, questa ricerca non sarà molto lunga.

È inoltre possibile rendere implicita la pila incapsulando questa logica in una classe Environment con binding locali e un ambiente ereditato utilizzato per la risoluzione di variabili sconosciute. Hai bisogno di entrare in un nuovo ambito?Crea un nuovo ambiente con l'ambiente corrente come base, usalo, quindi scartalo quando l'ambito è finito. L'ambiente root/globale può avere solo un ambiente ereditato null. Questo è quello che probabilmente farei.

Answer 2

Vale la pena notare che se, all'interno di una funzione, non si ha accesso a nessuna variabile dalla funzione chiamante, si abbassa il numero di livelli che è necessario osservare. Per esempio:

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

L'idea è che i confini funzione di limitazione della visibilità delle variabili, con la portata globale di essere "speciale".

Detto questo, si può considerare di rimuovere la particolarità di variabili globali, ma consente il codice per specificare che vogliono accedere alle variabili non locali

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

Sembra complicato in un primo momento, ma è davvero facile capire quando ci si abitua (upvar è un costrutto dal linguaggio di programmazione Tcl). Ciò che ti consente è l'accesso alle variabili nell'oscillazione del chiamante, ma evita parte della costosa ricerca implicita richiedendo di specificare esattamente da dove proviene quella variabile (con 1 di livello superiore allo stack di chiamate, 2 di due livelli in su, e # 0 è "speciale" nel dire "lo stack di chiamate più in alto, il globale)