Sottoprogrammi

Un linguaggio senza parametri puo'esistere? Si (es. assembly)

Astrazione

• identificare proprietà importanti di cosa si vuole descrivere
• concentrarsi sulle questioni rilevanti e ignorare le altre
• cosa è rilevante dipende dallo scopo del progetto

Voglio asseganare a un gruppo di istruzioni un nome e fare fare a questo gruppo di istruzioni delle op su dei paramentri che passo. Il codice diventa piu astratto e piu leggibile

Nota: I LP sono essi stessi astrazioni del calcolatore sottostante

Astrazione sul controllo e sui dati

Astrazione sul controllo

Sono per es: sottoprogrammi, blocchi, parametri

double P (int x) {
    double z;
    /* CORPO DELLA FUNZIONE
    return expr;
}

Astrazione del controllo

Fornisce astrazione funzionale al progetto:

• ogni componente fornisce servizi al suo ambiente
• la sua astrazione descrive il comportamente esterno
• e nasconde i dettagli interni necessari a produrlo

Interazione limitata al comportamento esterno

Comunicazione attraverso:

• parametri
• ambiente globale (ma distrugge l’astrazione)

Astrazione sui dati

Tipo di dato = valori e operazioni (integer = [-maxint..maxint] e ` {+,-,*,div,mod}`) La rappresentazione (implementazione) dei dati delle operazioni inaccessibile all’utente, perché protetta da una capsula che la isola

Nota: impossibile nel linguaggi più vecchi

• FORTRAN, Pascal, C

Parametri

Terminologia

• dichiarazione/definizione int f (int n) {return n+1} n si dice parametro formale

Nota: Una funz comunica con il chiamante (return)

Modalita' di passaggio dei parametri

Per valore:

• il val dell'attuale e'assegnato al formale, che si comporta come una var locale
• pragmatica: main -> proc
• attuale qualsiasi; modifiche al formale non passano all'attuale

Per riferimento:

• viene passato un riferimento (indirizzo) all'attuale; i riferimenti al formale sono referimenti all'attuale (aliasing)
• pragmatica: main <-> proc
• attuale: variabile; modifiche al formale passano all'attuale

Es passaggio per valore:

void foo (int x) { x = x+1; }
    …
    y = 1;
    foo(y+1);

dopo foo y vale comunque 1.

• Il formale x è una var locale (sulla pila)
• Alla chiamata, l’attuale y+1 è valutato ed il valore è assegnato al formale x
• Nessun legame tra x nel corpo di foo e y nel chiamante
• Al ritorno da foo, x viene distrutto (tolto dalla pila)
• Non è possibile trasmettere info da foo al chiamante mediante il parametro
• Costoso per dati grandi: copia
• Java, Scheme, Pascal (default), C e Java (unico modo);

Es: passaggio per riferimento

void foo (reference int x){ x = x+1;}
    …
    y = 1;
    foo(y);

dopo foo y vale 2.

• viene passato un riferimento (indirizzo; puntatore)
• Il formale x è un alias di y
• L’attuale deve essere un L-valore (“una variabile”)
• Al ritorno da foo, viene distrutto il (solo) legame tra x e l’indirizzo di y
• Trasmissione bidirezionale tra chiamante e chiamato
• Efficiente nel passaggio, ma indirezione nel corpo
• Pascal (var); in C simulato passando un puntatore…

Passaggio per risultato:

simile al passaggio per riferimento.

void foo (result int x) {x = 8;}
    …
    y = 1;
    foo(y);

• Il formale x è una var locale (sulla pila)
• Al ritorno da foo, il valore di x è assegnato all’attuale y
• Nessun legame tra x nel corpo di foo e y nel chiamante
• Al ritorno da foo, x viene distrutto (tolto dalla pila)
• Non è possibile trasmettere info dal chiamante a foo mediante il parametro
• Costoso per dati grandi: copia
• Ada: out

Passaggio per valore/risultato:

Insieme valore+risultato. Pragmatica: main ↔ proc

Esiste(-va) in Algol-W: void foo (value-result int x) { x = x+1; } … y = 8; foo(y); qui y vale 9 • Il formale x è a tutti gli effetti una var locale (sulla pila) • Alla chiamata, il valore dell’attuale è assegnato al formale • Al ritorno, il valore del formale è assegnato all’attuale • Nessun legame tra x nel corpo di foo e y nel chiamante • Al ritorno da foo, x viene distrutto (tolto dalla pila) • Costoso per dati grandi: copia • Ada: in out (ma solo per dati piccoli; per dati grandi passa riferimento)

Valore e riferimento: morale

Passaggio per valore: • semantica semplice: il corpo non ha necessità di conoscere come la procedura verrà chiamata (trasparenza referenziale) • implementazione abbastanza semplice • potenzialmente costoso il passaggio; efficiente il riferimento al parametro formale • necessità di altri meccanismi per comunicare main ← proc • Passaggio per riferimento: • semantica complessa; aliasing • implementazione semplice • efficiente il passaggio; un po’ più costoso il riferimento al parametro formale (un indiretto)

Valore, e non riferimento

I vantaggi del passaggio per valore:

• in particolare la trasparenza referenziale suggeriscono linguaggi con passaggio solo per valore più meccanismi separati per ottenere il passaggio per riferimento: puntatori in C variabili in modello a riferimento (tipi classe) in Jav

Passaggio per nome

Regole di copia:

• una chiamata alla procedura P e' la stessa cosa che eseguire il corpo di P dopo aver sostituito i parametri attuali al posto dei parametri formali

La macro espansione viene realizzata in modo semanticamente corretto In algol-w era il default:

int y;
void foo (name int x) {x= x + 1; }
…
y = 1;
foo(y);

foo esegue y=y+1

Caso piu complicato conflitto di variabili! Le due variabili y e y rossa sono diverse. fie incrementa l'attuale (y) attraverso il formale x e crea e distrugge la nuova y rossa

Soluzione: Viene passata una coppia: <exp, amb> • exp è il parametro attuale (testo, non valutato) • amb è l’ambiente di valutazione (in scoping statico) • Ogni volta che il formale è usato, exp è valutata in amb

Altro esempio:

void fie (int x, int y) {
    x = x+1;
    y = 1;}
…
int i = 1;
int[] A = new int[5];
A[1]=4;
fie (i,A[i]);

Passaggio per nome il corpo della proc viene riscritto al posto della chiamata e sostituisco le var con quelle in input

La i e A[i] sono valutate nel main (il loro amb)

quand arrivo al punto A[i] (ovvero y) = 1 visto che prima i e' stato incrementato allora andro' a modificare anche la i di A[i] quindi diventa A[2] = 1

f(nome x)
    y =  x
    y =  x
    y =  x

z = 1
f(z++)

con passaggio per nome la sostituzione viene fatta ogni volta che viene trovato il param corrispondente

quindi diventa:

f(nome x)
    y =  z++
    y =  z++
    y =  z++

z = 1
f(z++)

quindi y diventa 4 (o 3, in base a quando viene fatto z++)

Implementazione passaggio per nome

Come passare la coppia <exp,env>? – un puntatore al testo di exp – un puntatore di catena statica (sullo stack) al record di attivazione del blocco di chiamata

cioè una chiusura (perché chiude un’espressione: elimina le sue variabili libere legandole nell’ ambiente del chiamante)

Le chiusure servono a passare funzioni come argomenti ad altre procedure Parametro per nome = funzione nascosta senza argomenti che valuta il parametro nell’ambiente del chiamante (un thunk, nel gergo Algol)

Funzioni di ordine superiore

Alcuni linguaggi permettono di: – passare funzioni come argomenti di procedure – restituire funzioni come risultato di procedure • Entrambi i casi: come gestire l’ambiente della funzione ? • Caso più semplice – Funzioni come argomento – Occorre un puntatore al record di attivazione all’interno della pila: passa una chiusura ! • Caso più complicato – Funzione restituita da una chiamata di procedura – Occorre mantenere il record di attivazione della funzione restituita: disciplina a pila non funziona!!

in scope dinamico la x dentro la f puo velere 7 (se pero si valuta lo scope di f quando viene chiamata e non quando viene passata) quindi guardo il suo ambiente quando viene chiamata non passata. Questa regola si chiama regola di shallow binding Altrimenti (nel caso in cui io valuti l'ambiente della funz quando essa viene passata e non quand o viene chiamata), ovvero alla riga g(f) quindi la x vale 5. Questa regola si chiama deep binding

i funarg problems: downward

Quando una procedura viene passata come parametro si crea un riferimento tra un nome (h) e una procedura (f)

nt x=4; int z=0;
int f (int y){
return x*y;}
void g ( int h(int n) ) {
int x;
x = 7;
z = h(3) + x ;
end;
…
{int x = 5;
g(f);
}

deep binding: quando nel corpo di g vado ad usare f (quando andro a chiamare f da dentro g) essa avra' delle var non locali (x) che valuto nell'ambiente che c'e al momento della chiamata della funz alla quale f e' stata passata Ricapitolando: il bind viene fatto quando g chiama f shallow binding: il bind viene valutato dentro g quando f viene eseguito

Chiusure

Passare dinamicamente sia il legame col codice della funzione, che il suo ambiente non locale,cioè una chiusura <code, env> Alla chiamata di una procedura passata per parametro – alloca (come sempre) il record di attivazione – prendi il puntatore di catena statica dalla chiusura

Riassumendo: parametri funzioni (e per nome)

Chiusure per mantenere puntatore all’ambiente statico del corpo di una funzione

Alla chiamata, il puntatore di catena statica determinato mediante la chiusura

Tutti i puntatori di catena statica puntano sempre indietro nella pila – record di attivazione possono essere “saltati” per accedere a var non locali – de-allocazione dei record di attivazione secondo stretta politica a pila (lifo: last-in-first-out)

Scope dinamico: implementazione

Shallow binding: – non necessita di alcuna attenzione • per accedere a x, risali la pila • uso delle strutture dati solite (A-list, CRT)

Deep binding – usa necessariamente qualche forma di chiusura per “congelare” uno scope da riattivare più tardi

Deep e shallow binding con scope statico

Esercizio:

Esercizio in classe

{void foo (int f(), int n){
    int m = 10;
    int fie(){ write (n,m)}
    if (n==0) f();
    else {m=30;
            foo(fie,0);
    }
    }
    int g(){
        write(10);
    }
    foo(g,1);
}

si dica cosa stampa in frammento con shallow e deep bindig deep binding:

• n=1 e m=30

shallow binding:

• Es: spiegare vantaggi e svantaggi scope statico e scope dinamico scope statico: vantaggio: maggiore chiarezza del codice (trasparenza referenziale) e la stessa funz chiamata in tempi diversi con stessi param non cambiano il risultato svantaggi: difficile da implementare (catena) scope dinamico: impl facile, svantaggio: progr molto meno comprensibili

upward funarg problema

Alcuni linguaggi (eg funzionali) permettono di restituire una funzione Se la funzione ha variabili locali queste devono sopravvivere indipendentemente dalla struttura a pila: hanno vita indefinitamente lunga

(la pila va dall'alto verso il basso)

Morale: funzioni come risultato • Uso delle chiusure, ma… • I record di attivazione persistono indefinitamente – perdita proprietà della pila (lifo) • Come implementare la “pila” in questo caso: – non deallocare esplicitamente – record di attivazione sullo heap – le catene statica e dinamica collegano i record – invoca il garbage collector quando necessario

domande orale: quasi mai esercizi domande sui concetti del corso es per verdere se siamo in geado di esporre gli arg tecnici es cos'e un tipo di dato, cos'e una variabile, siegami in dettaglio come funz l'impl del meccanismo di deep binding con le chiusure

differenza tra meccanismo di invocazione di un mentodo e chiamata di funz in un ling imperativo. i ling oop in cosa sono meglio dei ling normali (procedurali?)