Riassunto Teoria Linguaggi

B.

Anche per la gestione della catena statica chiamante e chiamato possono dividere in vario modo le

operazioni da svolgere. Secondo l’approccio più comune al momento in cui si entra in un nuovo blocco il

chiamante calcola il puntatore di catena statica del chiamato e quindi passa tale puntatore al chiamato. Tale

calcolo può essere compreso dividendo due casi:

chiamato all’interno del chiamante : il chiamante passa al chiamato il puntatore al proprio RdA;

 chiamato all’esterno del chiamante : il chiamante calcola il puntatore di catena statica deferenziando

 k+1 volte il proprio puntatore di catena statica, con k = distanza di livello di annidamento fra

chiamato e chiamante (nota a compile-time).

Il chiamato riceve il puntatore di catena statica e lo memorizza nel proprio RdA.

Display (scope statico) = La tecnica del display serve a ridurre il numero degli accessi alla memoria per

scorrere la memoria statica ad un numero fisso. Questa tecnica usa un vettore detto display contenente tanti

elementi quanti sono i livelli di annidamento dei blocchi presenti nel programma, dove l’elemento k-esimo del

vettore contiene il puntatore all’ RdA di livello di annidamento k correntemente attivo. La gestione del display

è più semplice ma più costosa di quella della catena statica, in quanto quando si esce o entra da un

ambiente oltre a aggiungere il puntatore nel vettore si deve anche salvare il vecchio valore.

Seguire RdA (scope dinamico) = Per risolvere un riferimento a un nome x basterà percorrere a ritroso la

pila, partendo dal record di attivazione corrente, fino a trovare il RdA corrispondente al blocco nel quale il

nome x è stato dichiarato. Le varie associazioni nome-oggetto sono memorizzate nel RdA.

A-list (scope dinamico) = Alternativamente a questa memorizzazione diretta nell’ RdA, queste associazioni

possono essere memorizzate in una lista di associazioni detta A-list e gestita come una pila. Ci sono però

due inconvenienti:

1. Occorre memorizzare i nomi in strutture presenti a tempo di esecuzione (al contrario dello scope

statico);

2. Inefficienza della ricerca a run-time.

Questi due inconvenienti sono limitati dalla tabella centrale dell’ambiente.

Tabella centrale dell’ambiente (CRT) (scope dinamico) = Tutti i blocchi del programma fanno riferimento

a una sola tabella (CRT), che contiene:

tutti i nomi usati nel programma, e per ogni nome:

 o Un flag che indica se l’associazione per il nome è attiva;

o Un puntatore alle informazioni sull’ oggetto.

I nomi hanno posizioni fisse in tabella (perché tutti gli identificatori usati nel programma sono noti),

 quindi l’accesso a run-time è costante;

Se dal blocco A si entra nel blocco B, la CRT è modificata per descrivere il nuovo ambiente di B; le

 associazioni deattivate devono essere salvate (per quando esco da B);

A ogni nome della CRT è associata una pila che contiene nella prima posizione l’associazione

 valida e (nelle successive quelle disattivate. Oppure si usa una sola pila nascosta per memorizzare

tutte le associazioni deattivate per ogni nome. Usando quest’ ultima per conoscere un’associazione

dell’ambiente occorre:

o Accedere alla tabella (diretto);

o Accedere alla memoria con il puntatore trovato nella tabella;

o Non serve nessuna ricerca a run-time.

Notazione infissa = x + y. È quella utilizzata comunemente in matematica e nei linguaggi di

programmazione per gli operatori binari.

Notazione prefissa = + x y. È anche chiamata notazione polacca prefissa ed è spesso utilizzata per gli

operatori unari.

Notazione postfissa = x y +. È anche chiamata notazione polacca inversa

Notazioni polacche = Entrambe hanno come vantaggio la mancata necessità di parentesi e di operatori

ausiliari quando si agisce su più operandi.

Strategie di valutazione delle sotto-espressioni = Eager - si valutano prima tutti gli operandi per poi

passare ad applicare l’operatore e i valori ottenuti dalla valutazione degli operandi.

Corto-circuito (Lazy) - consiste nel non valutare gli operandi prima dell’operatore, ma nel passare gli

operandi non valutati all’operatore il quale al momento della sua valutazione deciderà quali operandi sono

effettivamente necessari valutando solo questi.

Ricorsione = Una funzione ricorsiva è una procedura nel cui corpo comprare una chiamata a se stessa. Si

può avere anche ricorsione indiretta, o mutua ricorsione, quando una procedura P chiama un’altra procedura

Q che a sua volta chiama P.

Ricorsione in coda = La chiamata ricorsiva è l’ultima cosa che viene fatta nel corpo della procedura, dopo

la chiamata ricorsiva non dev’essere compiuta alcuna ulteriore computazione.

Sia f una funzione che nel suo corpo contenga la chiamata ad una funzione g, la chiamata di g si dice

chiamata in coda se f restituisce il valore restituito da g senza dover fare alcuna ulteriore computazione.

Diciamo che la funzione f ha la ricorsione in coda se tutte le chiamate ricorsive presenti in f sono chiamate in

coda.

Parametro formale = Compaiono nella definizione della funzione, esempio: int foo(int n) in questo caso n è

parametro formale.

Parametro attuale = Compaiono nella chiamata, esempio foo(3) in questo caso il 3 è il parametro attuale

A differenza dei parametri formali i parametri attuali possono essere espressioni anziché semplici nomi.

Passaggio per valore = È una modalità che corrisponde ad un parametro di ingresso. L’ambiente locale

della procedura è esteso con un’associazione tra parametro formale ed una nuova variabile.

Il parametro attuale può essere una generica espressione; al momento della chiamata, l’attuale viene

valutato e lo r-valore così ottenuto viene assegnato al parametro formale. Al termine della procedura il

parametro formale viene distrutto con l’ambiente locale della procedura stessa. Durante l’esecuzione del

corpo non c’è alcun legame tra parametro formale e attuale. Non c’è alcun modo di sfruttare un parametro

per valore per trasferire informazioni dal chiamato al chiamante.

Passaggio per riferimento = Realizza un meccanismo nel quale il parametro è sia di ingresso che di uscita.

Il parametro attuale dev’essere un’espressione dotata di l-valore. Al momento della chiamata viene valutato

lo l-valore dell’attuale e l’ambiente locale della procedura è esteso con un’associazione tra il parametro

formale e lo l-valore dell’attuale. Ogni modifica al formale è una modifica all’attuale. Il caso più comune è che

il parametro attuale sia una variabile: in questo caso il formale e l’attuale sono due nomi per la stessa

variabile.

Passaggio per costante = Stessa semantica del passaggio per valore. I parametri passati per costante

sono soggetti al vincolo statico di non poter essere modificati nel corpo della funzione.

Passaggio per risultato = Il passaggio per risultato è l’esatto duale del passaggio per valore. Si tratta di

una modalità che realizza una comunicazione di sola uscita. Il parametro attuale dev’essere un’espressione

dotata di l-valore. Al momento della chiamata non avviene alcuna forma di comunicazione, mentre al termine

della procedura, subito prima della distruzione dell’ambiente locale, il valore corrente del parametro formale

viene assegnato alla locazione corrispondente al parametro attuale. Non c’è alcun modo di sfruttare un

parametro per risultato per trasferire informazioni dal chiamante al chiamato.

Passaggio per valore-risultato = Realizza una comunicazione bidirezionale, col formale che è a tutti gli

effetti una variabile locale alla procedura. Il parametro attuale dev’essere un’espressione dotata di l-valore.

Al momento della chiamata il parametro attuale viene valutato e lo r-valore così ottenuto viene assegnato al

parametro formale. Al termine della procedura subito prima della distruzione dell’ambiente locale il valore

corrente del parametro formale viene assegnato alla locazione corrispondente al parametro attuale.

Passaggio per nome = È quella modalità la cui semantica è data dalla regola di copia, nella quale però la

nozione di sostituzione è sempre da intendersi senza cattura. Possiamo dire che ciò che viene sostituito non

è il mero parametro attuale, ma il parametro attuale insieme al proprio ambiente di valutazione che è fissato

al momento della chiamata. Si osservi come la regola di copia imponga che il parametro attuale sia valutato

ogni volta che il formale viene incontrato durante l’esecuzione, con le relative conseguenze in presenza di

eventuali effetti collaterali. È una modalità che corrisponde ad un parametro sia in ingresso che in uscita.

Eccezioni = Sono eventi particolari che si verificano durante l’esecuzione di un programma e che non

devono essere gestiti dal normale flusso del controllo. Si può trattare del verificarsi di un errore di semantica

dinamica o del verificarsi di una situazione nella quale il programmatore decide esplicitamente di terminare la

computazione corrente e trasferire il controllo in un altro punto del programma, spesso al di fuori del blocco

correntemente in esecuzione.

Tipi Ricorsivi = E’ un tipo composto nel quale un valore del tipo può contenere un riferimento a un valore

dello stesso tipo. Per terminare la ricorsione il linguaggio può fornire un valore speciale, per esempio null che

possiamo immaginare come assenza di valori. Es: type int_list = {int val; int_list next;};

Tipo di dato = È una collezione di valori omogenei (devono condividere alcune proprietà strutturali, che li

rendono simili tra loro) ed effettivamente presentati (valori che sia possibile presentare in modo finito), dotata

di un insieme di operazioni che manipolano tali valori.

Conversioni implicite (coercizioni) = In presenza di compatibilità tra due tipi, il linguaggio permette la

presenza di un valore del primo tipo laddove sarebbe richiesto un valore del secondo tipo. In corrispondenza

di ogni situazione del genere il compilatore e/o la macchina astratta inseriscono una conversione implicita

del primo tipo al secondo tipo che chiamiamo coercizione di tipo.

Conversioni esplicite (cast) = Sono annotazioni nel linguaggio che specificano che un valore di un tipo

deve essere convertito in un altro tipo. Anche in questo caso tale conversione può essere solo un

indicazione sintattica o può corrispondere a codice eseguito dalla macchina astratta. I linguaggi moderni

favoriscono i cast in quanto più espressivi dal punto di vista della documentazione, non dipendono dal

contesto sintattico in cui compaiono e si comportano meglio in presenza di overloading e polimorfismo.

Polimorfismo = Un sistema di tipi è polimorfo quando uno stesso oggetto può avere pi&