Paradigmi - imperativo Flashcards
Imp
Breve presentazione
Imp è un linguaggio imperativo. Come fun, anche imp ha 2 modalità eager per la valutazione dei parametri di una procedura: il passaggio per valore e quello per reference, ed una modalità lazy: il passaggio per nome.
Differenza tra lazy e eager
Imp
Locazione
Un’astrazione sulla nozione di indirizzo di memoria
Store
è l’insieme delle memorie. è una funzione parziale che va dalle locazioni ai valori.
Store = loc –fin–> val
Intuitivamente associa a ogni cella di memoria un valore (mentre l’ambiente serve a ricorda ogni cella di memoria - locazione - a quale variabile è associata)
Ambiente
Imp
L?ambiente in Imp è una funzione parziale che associa variabili a locazioni
Env = var –fin–> loc
è complementare a Store, l’insieme che ricorda i valori contenuti nelle loc
Imp
sintassi
Abbiamo le costanti k€val;
le variabili x,y€var;
Le metavaribili (Espressioni) M,N€Exp;
i programmi p,q€Imp;
Val, Exp ed Imp sono definiti induttivamente dalla seguente sintassi astratta:
k ::= 0 | 1 | . . . | true | false
M ::= k | x | M + N | M < N
p ::= skip | p; q | if M then p else q | while M do p |
var x = M in p | x := M
skip è il programma che non cambia il mondo;
var rappresenta la dichiarazione (ed inizializzazione) di una nuova variabile e := rappresenta l’assegnamento di un valore
ad una variabile già definita
Imp
Relazioni di valutazione –p–>, –M–>
La semantica operazionale di Imp definisce due relazioni di valutazione: una per le espressioni M, che producono un valore senza avere side-effects, ed una per i programmi p, che non producono valori ma cambiano la memoria:
–M–> ⊆ Env × Exp × Store × Val
–p–> ⊆ Env × Imp × Store × Store
Const
Imp
E|- k, S –> k
x
Imp
E|- x, S –> v
(se E(x) = l ed S(l) = v)
Skip
Imp
E|- skip, S –>S
All
Breve presentazione
All è un linguaggio imperativo, che arricchisce Imp con array e procedure. è l’acronimo di algol-like-language, infatti è considerabile il nucleo di un linguaggio Algol.
All - call by value
Ambiente
Le variabili dichiarate come array saranno associate nell’ambiente a sequenze finite e non vuote di
locazioni. Indichiamo con Loc+ l’insieme di tali sequenze. Nota che la dichiarazione di una singola variabile x mediante il costrutto var assocerà ora ad x una sequenza <l> di lunghezza 1.
Le variabili dichiarate come procedure saranno associate a
chiusure.
Dunque, mentre l’insieme Val dei valori e quello Store delle memorie rimangono invariati rispetto ad Imp, per gli ambienti si ha:
Env = Var --fin--> Loc+ ∪ (Var × All × Env)</l>
All
Relazioni di valutazione
–V–> ⊆ Env × LExp × Store × Loc
–M–>⊆ Env × Exp × Store × Val
–p–> ⊆ Env × All × Store × Store
Loc 1 - x non array
All - Call by value
E|- x, S –V–> l
(se E(x) = l)
Loc 2 - x array
All - Call by value
Ref
All - Call by value
Assign
All - Call by value
Array
All - Call by value
Procedure
All - Call by value
Call
All - Call by value
In all non c’è la regola diretta per calcolarsi il valore di x, come si fa?
All - Call by value
Per ottenere il valore referenziato da una
variabile x sono necessari ora due passi: [loc 1] e [ref ].
Call by reference
Si impone che l’espressione che si passa come argomento ad una chiamata per riferimento deve essere di tipo assegnabile. Cambia solo la regola della chiamata:
call-ref
var x = 5 in proc y(z) is z := 1 in y(x)
Valutare il seguente programma con la semantica call-by-value e con quella call-by-reference
Cosa cambia?
Call by value: passiamo alla funzione y il valore che x ha al momento della chiamata, ossia 5; quindi proviamo ad assegnare 1 a 5;
Call by reference: passiamo alla funzione y la locazione l, associata alla variabile x.
Dare un programma che dà risultati diversi se valutati call-by-value o call-by-reference
var x = 5 in proc y(z) is z := 1 in y(x)
Call by name
Come cambia l’ambiente e le regole
Come per la chiamata per riferimento, l’espressione che si passa come argomento ad una chiamata per nome deve essere di tipo assegnabile. Tale espressione deve inoltre rimanere non valutata fino a quando l’esecuzione del corpo della procedura non richieda la valutazione del parametro. Si tiene quindi nell’ambiente l’espressione non valutata.
L’ambiente diventa quindi:
Env = Var –fin–> Loc+ ∪ (Var × All × Env) ∪ (LExp × Env)
E le regole:
per valutare la variabile in un parametro loc3
call-by-name
Seq
Imp
If1 - condizione true
Imp
If2 - condizione false
Imp
While1 - condizione true
Imp
While2 - condizione false
Imp
Assign
Imp
Var
Imp
Valutare il seguente programma con la semantica call-by-reference e con quella call-by-name:
var x = 0 in arr y = [3, 4, 5] in proc z(w) is (x := x + 1; u := w) in call z(y[x])
Cosa cambia?
Call by reference: passiamo alla funzione z la locazione di y[x] al momento della chiamata di z. x vale 0, quindi questa locazione si riferisce al primo elemento dell’array y. Allora quando eseguiamo la funzione z (ossia x := x + 1; u := w), x diventa 1,e associamo alla locazione di u il valore di w=y[0] nello Store.
Call by name: passiamo alla funzione z direttamente il parametro V e l’ambiente E (quello al momento della chiamata), senza calcolarci la locazione. La calcoliamo invece quando e se servirà effettivamente. Quindi quandoe seguiamo la funzione z (ossia x := x + 1; u := w), x diventa 1, e associamo alla locazione di u il valore di w=y[1]
Programma che cambia se valutato call by name o by reference?
Dare esempio
var x = 0 in arr y = [3, 4, 5] in proc z(w) is (x := x + 1; u := w) in call z(y[x])
Differenza call by reference, by value, by name?
Reference e value sono eager, vengono subito valutati quando viene chiamata la funzione. Name è lazy perchè viene valutata quando e se viene effettivamente usato il parametro nel corpo della funzione.
Value passa una variabile come parametro che valutata torna un valore.
Reference passa una variabile di tipo assegnabile che valutata dà una locazione.
Name passa una coppia variabile(assegnabile)-ambiente, che valutata nel suo ambiente darà una locazione.
