Paradigmi - imperativo

Question 1

Imp

Breve presentazione

Answer 1

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.

Question 2

Differenza tra lazy e eager

Imp

Question 3

Locazione

Answer 3

Un’astrazione sulla nozione di indirizzo di memoria

Question 4

Store

Answer 4

è 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)

Question 5

Ambiente

Imp

Answer 5

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

Question 6

Imp

sintassi

Answer 6

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

Question 7

Imp

Relazioni di valutazione –p–>, –M–>

Answer 7

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

Question 8

Const

Imp

Answer 8

E|- k, S –> k

Question 9

x

Imp

Answer 9

E|- x, S –> v
(se E(x) = l ed S(l) = v)

Question 10

Plus

Imp

Answer 10

plus

Question 11

Min 1 - M < N true

Imp

Answer 11

min1

Question 12

Min 2 - M < N false

Imp

Answer 12

min2

Question 13

Skip

Imp

Answer 13

E|- skip, S –>S

Question 14

All

Breve presentazione

Answer 14

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.

Question 15

All - call by value

Ambiente

Answer 15

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>

Question 16

All

Relazioni di valutazione

Answer 16

–V–> ⊆ Env × LExp × Store × Loc
–M–>⊆ Env × Exp × Store × Val
–p–> ⊆ Env × All × Store × Store

Question 17

Loc 1 - x non array

All - Call by value

Answer 17

E|- x, S –V–> l
(se E(x) = l)

Question 18

Loc 2 - x array

All - Call by value

Answer 18

loc2

Question 19

Ref

All - Call by value

Answer 19

ref

Question 20

Assign

All - Call by value

Answer 20

assign

Question 21

Array

All - Call by value

Answer 21

array

Question 22

Procedure

All - Call by value

Answer 22

procedure

Question 23

Call

All - Call by value

Answer 23

call

Question 24

In all non c’è la regola diretta per calcolarsi il valore di x, come si fa?

All - Call by value

Answer 24

Per ottenere il valore referenziato da una
variabile x sono necessari ora due passi: [loc 1] e [ref ].

Question 25

Call by reference

Answer 25

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

Question 26

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?

Answer 26

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.

Question 27

Dare un programma che dà risultati diversi se valutati call-by-value o call-by-reference

Answer 27

var x = 5 in proc y(z) is z := 1 in y(x)

Question 28

Call by name

Come cambia l’ambiente e le regole

Answer 28

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

Question 29

Seq

Imp

Answer 29

seq

Question 30

If1 - condizione true

Imp

Answer 30

If1

Question 31

If2 - condizione false

Imp

Answer 31

If2

Question 32

While1 - condizione true

Imp

Answer 32

while1

Question 33

While2 - condizione false

Imp

Answer 33

while2

Question 34

Assign

Imp

Answer 34

assign

Question 35

Var

Imp

Answer 35

var

Question 36

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?

Answer 36

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]

Question 37

Programma che cambia se valutato call by name o by reference?

Dare esempio

Answer 37

var x = 0 in arr y = [3, 4, 5] in proc z(w) is (x := x + 1; u := w) in call z(y[x])

Question 38

Differenza call by reference, by value, by name?

Answer 38

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.