Regole di Scoping e Binding nei Linguaggi di Programmazione: Statico vs Dinamico, Ricorsione e Compilatori vs Interpreti

Regole di Scoping

A cosa servono

Determinano a quale dichiarazione si riferisce una variabile non locale (libera) usata in un blocco o funzione.

Tipi

Possono essere statiche (basate sulla struttura testuale del codice) o dinamiche (basate sulla catena delle chiamate).

Regole di Binding

A cosa servono

Servono a stabilire quale ambiente usare quando una funzione con variabili non locali viene passata come parametro a un'altra. Con lo scoping statico il problema non si pone (vale sempre l'ambiente di definizione), mentre con lo scoping dinamico si divide in due casi:

• Deep Binding: si usa l'ambiente attivo nel momento in cui la funzione viene passata come parametro.
• Shallow Binding: si usa l'ambiente attivo nel momento in cui la funzione viene chiamata/eseguita.

Gli Ambienti Coinvolti

• Ambiente di definizione: il blocco originario in cui la funzione è scritta (usato nello scoping statico).
• Ambiente di passaggio: lo stato delle variabili nel punto in cui la funzione viene passata (usato nel deep binding).
• Ambiente di chiamata: lo stato delle variabili nel punto in cui la funzione viene invocata (usato nello shallow binding).

Esempio

(*) int y := 1; int pluto(){ return y; }
(**) y := i;

Idea. pluto usa una y non locale. Con scoping statico si riferisce alla y globale, che è costante. Con scoping dinamico si riferisce alla y locale di pippo, che cambia con i. Il ciclo esegue due iterazioni: con i = 0 e con i = 2, dopo le quali i diventa 4 e il ciclo termina.

(a) Scoping statico

y in pluto si risolve nell'ambiente di definizione, cioè il blocco esterno, quindi è la y globale, che vale 1. L'istruzione y := i in pippo modifica solo la y locale di pippo, che pluto non vede.

• Prima iterazione: x = 1.
• Seconda iterazione: x = 1.
• I due valori sono uguali.

(b) Scoping dinamico

y in pluto si risolve nella dichiarazione attiva più recente sulla pila, cioè la y locale di pippo, che vale i.

• Prima iterazione: y = 0, quindi x = 0.
• Seconda iterazione: y = 2, quindi x = 2.
• I due valori sono diversi.

Passaggio dei Parametri

Nel passaggio per valore viene effettuata una copia dei valori dei parametri attuali in quelli formali.

Nel passaggio per riferimento viene creato un collegamento tramite indirizzo tra i parametri attuali e quelli formali.

Ricorsione

Ricorsione in coda

Una funzione è ricorsiva in coda quando la chiamata ricorsiva è l'ultima operazione eseguita e il suo risultato viene restituito senza ulteriori calcoli. In questo caso il record di attivazione del chiamante può essere riutilizzato, quindi la funzione usa memoria costante, come un ciclo.

Implementazione dello Scoping

Le regole di scoping servono a stabilire come si risolvono i riferimenti alle variabili non locali, in particolare quando una funzione viene eseguita in un ambiente diverso da quello in cui è stata definita.

Scoping Statico

Una variabile non locale si riferisce alla dichiarazione presente nel blocco che contiene testualmente la funzione, cioè nell'ambiente in cui la funzione è stata definita. Per realizzarlo si usa il RDA (Record di Attivazione), una struttura creata ogni volta che una funzione viene chiamata. Al suo interno, oltre alle variabili locali e ad altre informazioni, si trova un link statico, cioè un puntatore all'RDA del blocco in cui la funzione è stata scritta.

Quando serve una variabile non locale, si risale lungo questi link statici fino a trovare la dichiarazione.

Scoping Dinamico

Una variabile non locale si riferisce alla sua dichiarazione attiva più recente, in base all'ordine delle chiamate durante l'esecuzione. Si può implementare con la CRT (tabella centrale dei riferimenti), dove a ogni nome corrisponde una pila di associazioni: entrando in un blocco che lo dichiara si aggiunge un'associazione in testa; uscendo, la si rimuove. La testa è l'associazione da usare.

Compilatore e Interprete

Compilatore

Intuitivamente, un compilatore è un programma traduttore. Prende un programma scritto in un linguaggio sorgente L (ad alto livello) e produce un programma equivalente in un linguaggio oggetto L_o (tipicamente linguaggio macchina). La traduzione avviene una volta sola, prima dell'esecuzione e senza vedere i dati; il programma tradotto può poi essere eseguito più volte. Durante la traduzione può segnalare errori e ottimizzare il codice.

Interprete

Intuitivamente, un interprete è un programma esecutore. Prende il programma scritto in L insieme ai suoi dati e produce direttamente il risultato, senza generare un programma tradotto. Analizza ed esegue le istruzioni una alla volta, quindi ogni istruzione viene rianalizzata ogni volta che viene eseguita: è più lento, ma più flessibile e portabile.

Pseudocodice del Compilatore

compila(sorgente):
    token   = analisi_lessicale(sorgente)       // caratteri -> token
    albero  = analisi_sintattica(token)         // token -> albero sintattico
    albero  = analisi_semantica(albero)         // controllo tipi e dichiarazioni
    if ci sono errori then
        segnala errori e termina
    interm  = genera_codice_intermedio(albero)
    interm  = ottimizza(interm)
    oggetto = genera_codice_oggetto(interm)     // programma in Lo
    return oggetto

Pseudocodice dell'Interprete

interpreta(P, input):
    stato = inizializza(input)
    repeat
        istr     = acquisisci_istruzione_successiva(P)   // fetch
        op       = decodifica(istr)                      // decode
        operandi = acquisisci_operandi(istr, stato)
        ris      = esegui(op, operandi)                  // execute
        stato    = memorizza(ris, stato)
    until istr = stop
    return output(stato)