Paradigma Funzionale -...

ParadigmaFunzionaleParadigmaFunzionaleNicola FanizziDipartimento di InformaticaUniversità degli Studi di Bari

Linguaggi diProgrammazione [010194]25 mag, 2016

SommarioSommario

1 Computazione Senza StatoEspressioni e FunzioniRicorsioneComputazione comeRiduzioneIngredienti FondamentaliSemantica2 ValutazioneValoriSostituzione senza catturaStrategie di valutazione

Valutazione per valoreValutazione per nomeValutazione lazyConfronto delle strategie3 Programmazione neiLinguaggi FunzionaliAmbiente LocaleInterattivitàTipiPattern MatchingOggetti InfinitiAspetti Imperativi

LdP.ITPS/[email protected]/[email protected] Paradigma FunzionaleParadigma Funzionale 25 mag, 201625 mag, 2016 2 / 562 / 56

http://www.di.uniba.it/~fanizzi/corsi/lp


AgendaAgenda

1 Computazione Senza StatoEspressioni e FunzioniComputazione comeRiduzione

Ingredienti Fondamentali2 Valutazione3 Programmazione neiLinguaggi Funzionali




Introduzione: Linguaggi ConvenzionaliIntroduzione: Linguaggi ConvenzionaliLinguaggi convenzionali:modello di calcolo basato sulla trasformazione di stato

base: variabile modificabilecontenitore con un nome al quale si possono assegnare valoridiversi durante la computazionel’associazione con il nome viene conservata nell’ambiente

costrutto principale: assegnazionecambia il valore della variabile non l’associazionenome-locazione ossiamodifica r-valori ma non l-valori,fissati una volta per tutte [al momento della dichiarazione]

si differenziano per livello d’astrazione, tipi, istruzioni per lamanipolazione delle variabilidiverse astrazioni dellamacchina di von Neumann




Intro – linguaggi funzionaliIntro – linguaggi funzionaliCalcolare senza usare var. modificabili, cioè senza assegnazioneossia senza ricorrere ad uno stato (omemoria)

calcolo = riscrittura di espressionii cambiamenti si verificano nell’ambientepossibilità di manipolare funzioni [anche di ordine superiore]

senza assegnazione cade la necessità dell’iterazione:basta la ricorsione per poter definire computazioniindefinitamente lunghe [anche divergenti]I linguaggi di questo paradigma si dicono funzionali

Storia: paradigma vecchio come quello imperativoDagli anni ’30 oltre a MDT esisteva il λ-calcolo:modello astratto per definire funzioni calcolabiliLISP primo ling. seguito da SCHEME, ML, MIRANDA, HASKELL,. . .




Espressioni e FunzioniEspressioni e FunzioniIn matematica, spesso ambiguità sui concetti di definizione edapplicazione di una funzioneEsempio sia f (x) = x2 che associa ad x il suo quadrato;se x = 3, ne consegue che f (x) = 9l’espressione sintattica f (x) denota due cose molto diverse:

la prima volta,serve ad introdurre il nome f di una data funzione;la seconda,denota il risultato dell’applicazione di f ad un dato valore

In matematica il contesto aiuta a distinguere i due casi;nei ling. di programmazione questi casi vanno distinti




Espressioni e Funzioni [. . . cont.]Espressioni e Funzioni [. . . cont.]Per distinguere linguisticamente nome e corpo della funzione,nella sintassi di ML:val f = fn x => x * x;

val introduce una dichiarazione: si aggiunge all’ambienteuna nuova associazione nome-valorenome: fvalore: trasformazione di x in x * x

nei ling. funzionali le funzioni sono valori esprimibili:risultato della valutazione di un’espressione complessafn introduce un’espressione che denota una funzione




Espressioni e Funzioni [. . . cont.]Espressioni e Funzioni [. . . cont.]

Per l’applicazione di una funzione ad un argomento,si mantiene la notazione consueta:f(2)(f 2)f 2

si può usare val per introdurre nuovi nomi:val quattro = f 2;




Espressioni e Funzioni [. . . cont.]Espressioni e Funzioni [. . . cont.]

Conseguentemente, si può definire (ed applicare) una funzionesenza doverle assegnare un nome: funzione anonimaEsempio l’espressione (fn y => y+1) (6); ha valore 7come risultato dell’applicazione della funzione fn y => y+1all’argomento 6Si assumerà (come in ML) che l’applicazione sia denotata con lagiustapposizione, con associatività a sinistra (notazione prefissa)Esempio Se g è il nome di una funzioneg a1 a2 ... ak sta per (...((g a1) a2) ... ak)




Espressioni e Funzioni [. . . cont.]Espressioni e Funzioni [. . . cont.]Un’espressione funzionale può occorrere all’interno di un’altraEsempio val somma = fn x => (fn y => y+x);il valore di somma è una funzione che, dato l’argomento, x,restituisce una funzione anonima che, dato un argomento y,restituisce x+ySi può usare somma in tante maniere diverse:val tre = somma 1 2;val sommadue = somma 2;val cinque = sommadue 3;

NB sommadue funzione definita come risultato della valutazione diun’altra espressione




Notazione compattaNotazione compattaEsempio in ML, funzione f che calcola il quadrato definita:fun f x = x*x;

In generale, la formafun F x1 x2 ... xn = corpo ;

è un’abbreviazione (syntactic sugar) dival F = fn x1 => (fn x2 => ... (fn xn => corpo )...);

Esempio Si considerifun comp f g x = f(g(x));

che restituisce la composta dai suoi primi due argomenti,a loro volta due funzioniLdP.ITPS/[email protected]/[email protected] Paradigma FunzionaleParadigma Funzionale 25 mag, 201625 mag, 2016 11 / 5611 / 56



RicorsioneRicorsione

Ogni linguaggio funzionale consente la definizione di funzioniricorsiveEsempio Supponendo di avere un costrutto condizionale(sintassi ML: if then else),si può definire il fattoriale:fun fatt n = if n=0 then 1 else n*fatt(n-1);




Computazione come RiduzioneComputazione come Riduzione

riduzione: valutazione come processo di riscrittura:le funzioni aritmetiche e l’espressione condizionale hannouna propria semantica predefinitain un’espressione complessa,una sotto-espressione della forma funzione applicata ad unargomento viene sostituita testualmente dal corpo dellafunzione istanziando il parametro formale con quelloeffettivo (regola di copia del passaggio per nome)




Computazione come Riduzione [. . . cont.]Computazione come Riduzione [. . . cont.]

Esempiofact 3 7−→ (fn n => if n=0 then 1 else n*fact(n-1)) 3

7−→ if 3=0 then 1 else 3*fact(3-1)7−→ 3*fact(3-1)7−→ 3*fact(2)7−→ 3*((fn n => if n=0 then 1 else n*fact(n-1)) 2)7−→ 3*(if 2=0 then 1 else 2*fact(2-1))7−→ 3*(2*fact(2-1))7−→ 3*(2*fact(1))7−→ 3*(2*((fn n => if n=0 then 1 else n*fact(n-1)) 1))7−→ 3*(2*(if 1=0 then 1 else 1*fact(1-1))7−→ 3*(2*(1*fact(0))7−→ 3*(2*(1*((fn n => if n=0 then 1 else n*fact(n-1)) 0)))7−→ 3*(2*(1*(if 0=0 then 1 else 0*fact(0-1))))7−→ 3*(2*(1*1))7−→ 6

NB: manipolazione di stringhe: no variabili, no stackLdP.ITPS/[email protected]/[email protected] Paradigma FunzionaleParadigma Funzionale 25 mag, 201625 mag, 2016 14 / 5614 / 56




Esempio [identità]1 fun K x y = x;2 fun S p q r = p r (q r);3 val a = ...;

si valuta S K K a:S K K a 7−→ (fn p => (fn q => (fn r => p r (q r)))) K K a

7−→ (fn q => (fn r => K r (q r))) K a7−→ (fn r => K r (K r)) a7−→ K a (K a)7−→ (fn x => (fn y => x)) a (K a)7−→ (fn y => a) (K a)7−→ a





Data la definizione:fun r x = r(r(x));

ogni computazione che comporti la valutazione di rporta ad una riscrittura all’infinito:computazione divergente con risultato indefinito




Ingredienti FondamentaliIngredienti FondamentaliDa un punto di vista sintattico: espressione

non esiste la nozione di comando (necessita di quella di stato)valori ed operatori primitivi

Costrutti per la def. di espressioni:astrazione data una espressione exp e un identificatore x,consente la costruzione dell’espressione

fn x => exp che denota la funzione che trasformail parametro formale x in exp(exp astratta dal valore specifico legato a x)applicazione f_exp a_exp, denota l’applicazione della funzione

f_exp all’argomento a_exp




Ingredienti Fondamentali [. . . cont.]Ingredienti Fondamentali [. . . cont.]

Omogeneità tra dati e programmi:nessun vincolo sulla possibilità dipassare funzioni come argomenti di altre funzionirestituire funzioni come risultato di altre funzioni(di ordine su superiore)




SemanticaSemantica

Programma serie di definizioni di valori cheintroducono nuove associazioni nell’ambiente epossono richiedere la valutazione di espressioni complesseOperazioni per la valutazione (riduzione):ricerca di binding di un identificatore in un ambientee sostituzione con la definizione

nome = abbreviazione per il valore associatoapplicazione di un’espressione funzionale ad un argomento

si usa la β-regola, una variante della regola di copia




Semantica [. . . cont.]Semantica [. . . cont.]

redex (reducible expression): applicazione della forma((fn x => corpo) arg)

ridotto di una redex ((fn x => corpo) arg):espressione ottenuta sostituendo in corpo ogni occorrenzalibera di x con una copia di arg (evitando la cattura)β-regola se in exp compare una redex come sotto-espressione,essa si riduce a exp1; notazione:

exp→ exp1

exp1 ottenuta da exp sostituendo la redex con il ridottoImplementazioneLamacchina astratta adotta meccanismi di garbage-collection:in caso presenza di funzioni come risultato,va preservato l’ambiente locale per un tempo illimitatoLdP.ITPS/[email protected]/[email protected] Paradigma FunzionaleParadigma Funzionale 25 mag, 201625 mag, 2016 20 / 5620 / 56



AgendaAgenda

1 Computazione Senza Stato2 ValutazioneValori

Sostituzione senza catturaStrategie di valutazione3 Programmazione neiLinguaggi Funzionali




ValutazioneValutazione

Punti aperti:condizione di terminazione della riduzione,la forma semplice per un valoresemantica precisa della β-regola:(cattura,) ordine di riduzione in caso di più redex




ValoriValorivalore: espressione non ulteriormente riducibileTipologiesemplici primitivi predefiniti (interi, booleani, caratteri, . . . )funzionali val nome = expcomporta la valutazione dell’espressione a destra di =e il binding del valore risultante con il nome a sinistraNB: la valutazione non ha luogo nell’astrazione

fn x => exp

rappresenta un valore funzionale:le redex eventualmente contenute in exp non vengonosemplificate fino alla sua applicazione ad un argomento




Valori [. . . cont.]Valori [. . . cont.]Esempio valore associato a G?val G = fn x => ((fn y => y+1) 2);

Alternative:secondo la semantica informale, il valore sarebbe:fn x => 3

corpo semplificato valutando la redex contenutainvece: come nei ling. convenzionali, valutazione allachiamata/applicazione:fn x => ((fn y => y+1) 2)

nessuna valutazione del corpo




Sostituzione senza catturaSostituzione senza cattura

Sostituzione senza cattura: implementata attraverso le chiusure

Sintatticamente: nomi distinticonvenzione in ogni espressione, si tengono distintii nomi per i parametri formali equelli delle altre variabili (non param.)In tal modo non si verifica cattura




Strategie di valutazioneStrategie di valutazioneEsempio valutazione di v1 fun K x y = x;2 fun r z = r(r(z));3 fun D u = if u=0 then 1 else u;4 fun succ v = v+1;5 val v = K (D (succ 0)) (r 2);

per la β-regola, a destra della def. di v ci sono 4 redexcandidate: K (D (succ 0)), D (succ 0), succ 0, r 2

Quale ridurre prima? Da sinistra destra?Allora quale fra K (D (succ 0)), D (succ 0), succ 0 ?Anche con questo ordinamento 3 possibili strategie




Valutazione per valoreValutazione per valoreStrategia dell’ordine d’applicazione, eager, o interna:

una redex viene valutata solo se l’espressione checostituisce la parte argomento è già un valore

algoritmo1 cercare da sinistra la prima occorrenza di applicazione:

(f_exp a_exp)

2 applicando ricorsivamente lo stesso metodo,valutare f_exp riducendola ad un valore funzionale(fn x => ...)

3 valutare a_exp, riducendola ad un valore val4 ridurre ((fn x => ...) val) e tornare a (1)




Valutazione per valore [. . . cont.]Valutazione per valore [. . . cont.]

Nell’es. precedente val v = K (D (succ 0)) (r 2);

al passo (1) si seleziona K (D (succ 0))

con i passi (1), (2) e (3) si ha che K, D e succ sono già valoriil nome è un’abbreviazione dell’espressione associata

redex da semplificare:succ 0→ ((fn v => v + 1) 0)→ 1

successiva:(D 1)→ ((fn u => if u = 0 then 1 else u) 1)→ 1

successiva:(K 1)→ (fun y => 1) val. funzionale semplice(fun y => 1)(r 2) espr. complessiva, arg. da valutare(r 2)→ r (r 2)→ r (r (r 2))→ · · · divergente!

In conclusione, v indefinitoLdP.ITPS/[email protected]/[email protected] Paradigma FunzionaleParadigma Funzionale 25 mag, 201625 mag, 2016 28 / 5628 / 56



Valutazione per nomeValutazione per nomeStrategia dell’ordine normale o esterna:

una redex viene valutata prima della sua parte argomento

algoritmo1 sia (f_exp a_exp) la prima applicazione che occorre,a partire da sinistra, nell’espressione2 si valuta f_exp(applicando questo algoritmo ricorsivamente)fino a ridurla ad un valore funzionale (fn x => ...)

3 si riduce ((fn x => ..) a_exp) usando la β-regola esi torna a (1)




Valutazione per nome [. . . cont.]Valutazione per nome [. . . cont.]

Nell’es. precedente: val v = K (D (succ 0)) (r 2);

la prima redex da ridurre èK (D (succ 0))→ fn y => D (succ 0) valore funzionalela nuova forma dell’espressione sarà:(fn y => D (succ 0)) (r 2) nota: prescinde da yriducendo la redex più esterna (passo 3.):D (succ 0)→ if (succ 0)=0 then 1 else (succ 0)→ if 1=0 then 1 else (succ 0)→ succ 0→ 1associato a v




Valutazione lazyValutazione lazy

Osservazioni sulla valutazione per nomeuna stessa redex può essere valutata più volte perduplicazioni richieste dalla riscrittura

nell’es. precedente, (succ 0) è duplicata a causa di De viene ridotta due volte nel condizionale nel corpo di Dif (succ 0)=0 then 1 else (succ 0)

Idea: posporre la valutazione di un argomento rispettoall’applicazione di una funzioneconsente di non divergerema ha un prezzo

dipende dal costo per la valutazione di ogni copia




Valutazione lazy [. . . cont.]Valutazione lazy [. . . cont.]

Strategia lazycome quella per nome ma il valore di una redexviene calcolato solo alla prima occorrenza econservato per essere utilizzato in caso di duplicati

Le strategie per nome e lazy sono dette a chiamata, o by need:si semplifica una redex solo se necessario




Confronto delle strategieConfronto delle strategieTeorema (strategie di valutazione)Sia exp un’espressione chiusa∗. Se la valutazione di exp la riduce alvalore primitivo val per ognuna delle strategie allora si produceval per la strategia per nome. Se, invece, diverge usando lastrategia per nome allora diverge anche usando le altre.

Osservazioninon è possibile che da exp si producano valori primitividifferenti a seconda della strategiale strategie possono differenziarsi solo in caso di divergenzadi una mentre le altre convergono su un valore

(*) Un’espressione è chiusa sse tutte le sue variabili sono legate in qualche costrutto fnLdP.ITPS/[email protected]/[email protected] Paradigma FunzionaleParadigma Funzionale 25 mag, 201625 mag, 2016 33 / 5633 / 56



Confronto delle strategie [. . . cont.]Confronto delle strategie [. . . cont.]

Criterio per avere un linguaggio funzionale puro:Fissata la strategia in un dato ambiente,la valutazione di tutte le occorrenze di una stessaespressione produce sempre lo stesso valore

Questo sembra favorire le strategie con chiamate by needanche dal punto di vista dell’efficienzaLISP, SCHEME e ML adottano la strategia per valore(includendo anche alcuni dei principali aspetti imperativi)MIRANDA e HASKELL adottano quella lazy(ling. funzionali puri)




AgendaAgenda

1 Computazione Senza Stato2 Valutazione3 Programmazione neiLinguaggi Funzionali

Ambiente LocaleInterattivitàTipiPattern MatchingOggetti InfinitiAspetti Imperativi




Programmazione nei Linguaggi FunzionaliProgrammazione nei Linguaggi Funzionali

Il meccanismi presentati sono sufficienti per descrivere unlinguaggio Turing-completo:si può esprimere qualunque funzione computabile

Ogni linguaggio funzionale aggiunge a tale nucleo altri costruttipiù espressivi per facilitare la programmazione




Ambiente LocaleAmbiente LocaleUn linguaggio di prog. moderno necessità di un ambientestrutturato per le definizioni (non solo uno scope globale)

si adotta una politica con scope a più livelliesempio, costrutto letlet x = exp in exp1 end

binding di x al valore di exp in un ambito che include exp1nota: le espressioni funzionali determinano scope annidati

gli ambienti relativi includono i parametri formalilegati a quelli effettiviai fini della valutazione, il costrutto dell’es. può essereconsiderato come syntactic sugar per(fn x => exp1) exp




InterattivitàInterattività

Ogni linguaggio funzionale presenta anche unambiente interattivosi usa il linguaggio per immettere espressioniche la macchina astratta valuta restituendone il valorele definizioni sono espressioni che modificano l’ambienteglobale (e possono restituire valori)le implementazioni sono tipicamente interpretate

esistono, tuttavia, implementazioni che compilano ledefinizioni alla loro prima immissione nell’ambiente




TipiTipiSistemi dei tipi

tipi primitivi standard (interi, boolean, caratteri):valori ed operazionitipizzazione statica

tranne SCHEME, che adotta la tipizzazione dinamicadefinizione di nuovi tipi

es. coppie, liste, record (n-ple con etichette dei campi)in ML, si può definire la funzione somma_c che prende in inputuna coppia di interi e ne restituisce la somma:fun somma_c (n1,n2) = n1 + n2;

NB: fornire a somma_c un solo argomento come nel currying(o applicazione parziale)tipi di funzioni, funzioni come valori

valori denotabili ed esprimibili(anchememorizzabili, se sono inclusi anche aspetti imperativi)LdP.ITPS/[email protected]/[email protected] Paradigma FunzionaleParadigma Funzionale 25 mag, 201625 mag, 2016 39 / 5639 / 56



Tipi [. . . cont.]Tipi [. . . cont.]

espressioni funzionali illegali (nei ling. tipizzati)perché non può essere assegnato un tipo precisoes. funzione illegale:

fun F f n = if n=0 then f(1) else f("pippo");

tipo di f ? int -> ’a oppure string -> ’a ?dove ’a denota una variabile di tipo,ossia un tipo generico non istanziato




Tipi [. . . cont.]Tipi [. . . cont.]espressione illegale, auto-applicazione:fun Delta x = x x;

(x x) è illegale: non c’è modo di assegnare a x un singolo tipooccorrendo a sinistra di una applicazione,dev’essere di tipo ’a -> ’bessendo anche argomento di una funzione,deve avere il tipo richiesto, ossia ’a

non c’è modo di unificare tali espressioniIn SCHEME , mancando la tipizzazione forte:X Delta è legaleX si può anche applicare Delta a se stessa:(Delta Delta)è un esempio di programma divergente

X senza controllo statico si può scrivere(4 3)dato che 4 non è una funzione, errore a runtimeIn ML, è ammesso il polimorfismo




Pattern MatchingPattern Matching

Esempio calcolo dell’n-esimo termine della serie di Fibonacci:1 fun Fibo n = if n = 0 then 12 else if n = 1 then 13 else Fibo(n-1) + Fibo(n-2);

inefficiente!




Pattern Matching [. . . cont.]Pattern Matching [. . . cont.]

Meccanismo di pattern matchingammesso da ML e HASKELL

1 fun Fibo 0 = 12 | Fibo 1 = 13 | Fibo n = Fibo(n-1) + Fibo(n-2);

def. (ricorsiva) per casiparametro formale: pattern

schema (modello) di espressione fatto di variabili, costanti ealtri costrutti, a seconda del sistema di tipoquando la funzione viene applicata ad un param. effettivoquesto viene confrontato con i pattern (nell’ordine) esi sceglie il corpo relativo alla prima corrispondenza (match)





Meccanismo flessibile con tipi strutturatiEsempio liste, in ML:

si usano valori separati da virgole tra parentesi quadre["uno", "due", "tre"] lista di 3 stringhe

:: denota l’operatore cons (aggiunta di un elemento in testa)"zero"::["uno", "due", "tre"]espressione che ha per valore la lista["zero", "uno", "due", "tre"]

nil denota la lista vuota"quattro"::nil ha valore ["quattro"]

Esempio Funzione che calcola la lunghezza di una lista1 fun lung nil = 02 | lung e::resto = 1 + lung(resto);





Osservazionii nomi nei pattern servono come parametri formali perdenotare parti del parametro effettivomaggiore concisione rispetto a:1 fun lung list = if list = nil then 02 else 1 + lung(tl list);

che richiede una funzione di selezione (tl) della lista privadella testa (coda o tail)selezione implicita nel pattern matching





Vincolo: una variabile non deve comparire più volte in unpatternEsempio funzione per il test di uguaglianza1 fun Eq nil = false2 | Eq [e] = false3 | Eq x::x::resto = true4 | Eq x::y::resto = false;

illegale dal punto di vista sintattico (il 3° pattern contiene due x)Pattern-matching 6= unificazione

unificazione meccanismo più generale (ma più complesso),adottato dai ling. del paradigma logico




Oggetti InfinitiOggetti Infiniti

Adottando strategie per nome o lazy (come in HASKELL1),si possono definire e manipolare strutture dati potenzialmenteinfinite (es. gli stream)Nozione di valore

valutazione eager, un valore di tipo T list è una lista i cuielementi sono valori di tipo Tvalutazione lazy, questa non è una buona nozione di valoreperché potrebbe richiedere la valutazione di redex inutili,contro la filosofia call-by-need




Oggetti Infiniti [. . . cont.]Oggetti Infiniti [. . . cont.]

Esempio valutazione lazySelezione di testa e coda di una lista non-vuota1 fun hd x::resto = x;2 fun tl x::resto = resto;

Consideriamohd [2, ((fn n => n+1) 2)]

Per calcolarne il valore (cioè 2),non serve ridurre la redex nel secondo elemento(mai usato nel corpo di hd)




Oggetti Infiniti [. . . cont.]Oggetti Infiniti [. . . cont.]In un contesto by-need,un valore di tipo list è un’espressione della forma:exp1 :: exp2

dove exp1 e exp2 possono contenere redexEsempio Si può definire una lista in modo ricorsivo:val infiniti2 = 2 :: infiniti2;

infiniti2 corrisponde ad una lista, potenzialmente infinita,i cui elementi sono tutti 2valutazione eager: la valutazione divergerebbevalutazione lazy: valore perfettamente manipolabile

hd infiniti2la valutazione termina con 2hd (tl (tl (tl infiniti2)))idem




Oggetti Infiniti [. . . cont.]Oggetti Infiniti [. . . cont.]Esempio Si definisce la funzione che costruisce una listainfinita di numeri naturali a partire dal parametro n:fun numeriDa n = n :: numeriDa(n+1);

Si possono definire funzioni di ordine superiore che applicano ilproprio argomento funzionale a tutti gli elementi di una lista:1 fun map f nil = nil2 | map f e::resto = f(e)::map(f,resto);

Si può produrre ora la lista infinita dei quadrati a partire da n*n:fun quadratiDa n = map (fn y => y*y) (numeriDa n);

1si usa la sintassi di ML ma considerando la valutazione lazyLdP.ITPS/[email protected]/[email protected] Paradigma FunzionaleParadigma Funzionale 25 mag, 201625 mag, 2016 50 / 5650 / 56



Aspetti ImperativiAspetti Imperativi

Molti ling. funzionali (es. ML) includono meccanismi chenecessitano della nozione di statoSono date variabili modificabili (reference cell), attraverso effetticollaterali, con propri tipi

per ogni tipo T (inclusi quelli funzionali) si ha il tipo T ref,i cui valori sono variabili modificabili con valori di tipo Tref v crea una var. inizializzata con il valore v (di tipo T)




Aspetti Imperativi [. . . cont.]Aspetti Imperativi [. . . cont.]i costrutti standard valgono anche per il tipo T refes. val I = ref 4;crea la variabile I di tipo int ref, inizializzata a 4

I è il nome della variabile non del valore contenuto (l-value)dereferenziando esplicitamente con l’op. ! si ottiene l’r-value:val n = !I + 1;con n (nome, non var.) associato al valore 5 e !I di tipo int

In generale, se V è un’espressione di tipo T ref, !V è di tipo Tassegnazione: modifica delle variabiliI := !I + 1;

notare la differenza con la def. del valore n di cui soprasi sta modificando l’r-value di una variabile che già esiste

il tipo di un costrutto imperativo è unit




Aspetti Imperativi [. . . cont.]Aspetti Imperativi [. . . cont.]

la presenza di var. modificabili rende possibile l’aliasing:1 val I = ref 4;2 val J = I;

la 2 associa il valore del nome I (cioè la var.) al nome JI e J sono nomi diversi (alias) per lo stesso l-value

Dopo l’esecuzione di3 I := 5;4 val z = !J;

il nome z è associato al valore 5




Aspetti Imperativi [. . . cont.]Aspetti Imperativi [. . . cont.]La definizione di ML non specifica come implementarel’assegnazione tra variabili

implementazione tradizionale: r-value copiato dalla sorgentealla destinazione ma le var. possono avere fabbisogni dimemoria molto diversiEs. variabili con liste e stringhe1 val S = ref "corta";2 val L = ref ["uno", "due", "tre"];

Il nome S è di tipo string ref,mentre L è di tipo (string list) refle due var. associate ai nomi S e L possono contenere, risp.,qualunque stringa e qualunque lista, ad es.:1 S := "stringa molto piu’ lunga delle precedenti";2 L := "zero" :: "quattro" :: "cinque" :: !L;

i nuovi valori di L e S richiedono più memoria dei precedentiLdP.ITPS/[email protected]/[email protected] Paradigma FunzionaleParadigma Funzionale 25 mag, 201625 mag, 2016 54 / 5654 / 56



Aspetti Imperativi [. . . cont.]Aspetti Imperativi [. . . cont.]È possibile implementare queste assegnazioni usando unasemplice (e standard) copia di valori

la macchina astratta copia i riferimenti (puntatori) a tali valoritutto trasparente all’utentel’implementazione gestisce i due fabbisogni di spazio,allocando la mem. necessaria per ognuno dei casi emodificando i riferimentiML fornisce anche costrutti di controllo imperativocome la sequenza (;) e i cicliOsservazione l’uso di caratteristiche imperative lede il teoremaprecedente: risultati non corretti




RiferimentiRiferimenti

Gabbrielli & Martini: Linguaggi di Programmazione,McGraw-Hill 2a edizione. Cap. 13




Paradigma Funzionale -...

Documents

Transcript of Paradigma Funzionale -...