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