Paradigma FunzionaleParadigma Imperativo: Programma = transizione di stato Paradigma Funzionale: Programma = valutazione di un’espressione La maggior parte dei linguaggi imperativi ha costrutti applicativi.
Prog ::= Decs eval Exp.Decs ::= Dec | Dec Decs. Dec ::= CDec | FDec.CDec ::= Type Id = Exp;.FDec ::= Type Id(PDecs) {Exp}.PDecs ::= PDec | PDec PDecs. PDec ::= Type Id;Type ::= int | bool | Types Type Types ::= Type | Type TypesExp ::= Id | Id(Exps) | Exp + Exp | … if (Exp) {Exp} else {Exp}.Exps ::= Exp | Exp, Exps.
Esempio: consideriamo la seguente grammatica LF
Confronto con LWI costrutti di LF sono in gran parte simili a quelli di LW.Rispetto a LW, una (grossa) differenza è che oltre ai tipi base, compaiono dei tipi funzionali o higher-order.Quindi LF è un linguaggio per manipolare valori che possono essere base ([int] = Z, [bool] = B) o funzionali (definiti induttivamente da
[t1 ... tn t] = [[t1] ... [tn] P [t]]).Nel seguito useremo Value = tLType(LF) [t].
I tipi higher-order sono cittadini di prima classe, cioè possono comparire in tutti i contesti in cui può comparire un tipo base (eg come argomenti e risultati di funzioni).Principale differenza con linguaggi funzionali “reali”: manca il polimorfismo e i tipi sono dichiarati invece che dedotti.La semantica di LF sarà molto simile a quella di LW, ma, non essendo necessaria la nozione di stato, tutto si semplificherà.
Semantica Statica
Envs = [LId(LF) P LType(LF) ]Fin
Ignoriamo il trattamento di errore (cioè definiamo la semantica statica come funzione parziale)
[_]sD:LDecs(LF) Envs Envs P Envs
[_]sE:LExps(LF) EnvsP LType(LF)+
[_]sP:LProg(LF) P LType(LF)
[dl eval e]sP = t
[dl]sD([],[]) = [e]s
E () = t
[d dl]sD (g, l) =
[d]sD(g, l) = l’ [dl]s
D(g, l’) =
[t x = e;]sD (g, l) = l[t/x] xDom(l)
[e]sE(g[l]) = t
[t f(pl){e}]sD (g, l) = l[lt t/f]
fDom(l)lt = types(pl)
[e]sE(g[l][l’]) = t[pl]s
PD(g[l],[lt t/f]) = l’
types(t x; pl)= t tltypes(pl)= tl
types(t x;)= t
[t x;]sPD (g, l) = l[t/x] xDom(l)
[_]sPD:LPDecs(LF) Envs Envs P Envs
Semantica Statica 2
[x]sE () = t (x) = t
[f(es)]sD () = t
[f]sE () = lt t [es]s
E () = lt
[if (b) {e} else {e’}]sE() = t
[e]sE() = t [e’]s
E() = t[b]sE() = bool
Esercizio proposto: aggiungere altri costrutti base al linguaggio, ad esempio costrutti per la funzione identica, composizione di funzioni, tipi prodotto, pairing (se f: A B e g: C D, allora (f,g): A C B D è definita da (f,g)(a,c) = (f(a),g(b)))...
[e + e’]sE() = int
[e]sE() = int [e’]s
E() = int
Semantica Dinamica (Denotazionale)
[dl eval e]P = v[dl]D([]) = r [e]E (r) = v
[d dl]D (r) = r”[d]D(r) = r’ [dl]D(r’) = r”
[t x = e;]D (r) = r[v/x][e]E(r) = v
Le dichiarazioni modificano l’ambiente: [_]Decs:LDecs(LF) Env Envdove Env = [LId(LF) P Value]Fin
Le espressioni producono un valore: [_]Exps:L Exps(LF) Env Value+
[RT f(T x) {e}]D(r) = r[F/f]
Dove F : [T] [RT] è definita induttivamente da tutte le regole della semantica più le seguenti due:
[f(e)] (r[/f]) = aF(v) = a[e](r[/f]) = v
Caso base Regola ad hoc per la chiamata di f
F(v) = a[e](r[/f, v/x])= a
Rispetto a LW è sparito lo stato
Il valore del parametro attuale è associato direttamente al nome del parametro formale
Semantica Dinamica (2)
[e es]E(r) = v lv[e]E(r) = v [es]E(r) = lv
[x]E(r) = r(x)
[f(es)]E(r) = r(f)(lv) [es]E(r) = lv v1 + v2 = a
[e1 + e2]E(r) = a[e1]E(r) = v1 [e2]E(r) = v2
Top Related