Paradigma
Funzionale
Nicola Fanizzi
Corso di Linguaggi di Programmazione - 010194
Dipartimento di Informatica
Università degli Studi di Bari
27 maggio 2015
Sommario
1
Valutazione per valore
Valutazione per nome
Valutazione lazy
Confronto delle strategie
Computazione Senza Stato
Espressioni e Funzioni
Ricorsione
Computazione come
Riduzione
Ingredienti Fondamentali
Semantica
2
Valutazione
Valori
Sostituzione senza cattura
Strategie di valutazione
N. Fanizzi ( LdP)
3
Programmazione nei
Linguaggi Funzionali
Ambiente Locale
Interattività
Tipi
Pattern Matching
Oggetti Infiniti
Aspetti Imperativi
Paradigma Funzionale
27 maggio 2015
2 / 56
Agenda
1
Computazione Senza Stato
Espressioni e Funzioni
Computazione come Riduzione
Ingredienti Fondamentali
2
Valutazione
3
Programmazione nei Linguaggi Funzionali
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
3 / 56
Introduzione: Linguaggi Convenzionali
Linguaggi convenzionali:
modello di calcolo basato sulla trasformazione di stato
base: variabile modificabile
contenitore con un nome al quale si possono assegnare valori
diversi durante la computazione
l’associazione con il nome viene conservata nell’ambiente
costrutto principale: assegnazione
cambia il valore della variabile non l’associazione
nome-locazione ossia
modifica r-valori ma non l-valori,
fissati una volta per tutte [al momento della dichiarazione]
si differenziano per livello d’astrazione, tipi, istruzioni per la
manipolazione delle variabili
diverse astrazioni della macchina di von Neumann
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
4 / 56
Intro – linguaggi funzionali
Calcolare senza usare var. modificabili, cioè senza assegnazione
ossia senza ricorrere ad uno stato (o memoria)
calcolo = riscrittura di espressioni
i cambiamenti si verificano nell’ambiente
possibilità di manipolare funzioni [anche di ordine superiore]
senza assegnazione cade la necessità dell’iterazione:
basta la ricorsione per poter definire computazioni
indefinitamente lunghe [anche divergenti]
i linguaggi di questo paradigma si dicono funzionali
Storia: paradigma vecchio come quello imperativo
Dagli anni ’30 oltre a MDT esisteva il λ-calcolo:
modello astratto per definire funzioni calcolabili
LISP primo ling. seguito da SCHEME, ML, MIRANDA, HASKELL,
...
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
5 / 56
Espressioni e Funzioni
In matematica, spesso ambiguità sui concetti di definizione ed
applicazione di una funzione
Esempio sia f (x) = x2 che associa ad x il suo quadrato;
se x = 3, ne consegue che f (x) = 9
l’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
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
6 / 56
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’ambiente
una nuova associazione nome-valore
nome: f
valore: trasformazione di x in x * x
nei ling. funzionali le funzioni sono valori esprimibili:
risultato della valutazione di un’espressione complessa
fn introduce un’espressione che denota una funzione
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
7 / 56
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 four = f 2;
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
8 / 56
Espressioni e Funzioni [. . . cont.]
Conseguentemente, si può definire (ed applicare) una funzione
senza doverle assegnare un nome: funzione anonima
Esempio l’espressione (fn y => y+1)(6); ha valore 7
come risultato dell’applicazione della funzione fn y => y+1
all’argomento 6
Si assumerà (come in ML) che l’applicazione sia denotata con la
giustapposizione, con associatività a sinistra (notazione prefissa)
Se g è il nome di una funzione
g a1 a2 ... ak sta per (...((g a1) a2) ... ak)
Esempio
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
9 / 56
Espressioni e Funzioni [. . . cont.]
Un’espressione funzionale può occorrere all’interno di un’altra
Esempio val add = fn x => (fn y => y+x);
il valore di add è una funzione che, dato l’argomento, x, restituisce
una funzione anonima che, dato un argomento y, restituisce x+y.
Si può usare add in tante maniere diverse:
val three = add 1 2;
val addtwo = add 2;
val five = addtwo 3;
NB addtwo funzione definita come risultato della valutazione di
un’altra espressione
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
10 / 56
Notazione compatta
Esempio
in ML, funzione f che calcola il quadrato definita:
fun f x = x*x;
In generale, la forma
fun F x1 x2 ... xn = corpo ;
è un’abbreviazione (syntactic sugar) di
val F = fn x1 => (fn x2 => ... (fn xn => corpo )...);
Esempio
Si consideri
fun comp f g x = f(g(x));
che restituisce la composta dai suoi primi due argomenti,
a loro volta due funzioni
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
11 / 56
Ricorsione
Ogni linguaggio funzionale consente la definizione di funzioni
ricorsive
Esempio 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);
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
12 / 56
Computazione come Riduzione
riduzione: valutazione come processo di riscrittura:
le funzioni aritmetiche e l’espressione condizionale hanno
una propria semantica predefinita
in un’espressione complessa,
una sotto-espressione della forma funzione applicata ad un
argomento viene sostituita testualmente dal corpo della
funzione istanziando il parametro formale con quello
effettivo (regola di copia del passaggio per nome)
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
13 / 56
Computazione come Riduzione [. . . cont.]
Esempio
fact 3 7−→
7−→
7−→
7−→
7−→
7−→
7−→
7−→
7−→
7−→
7−→
7−→
7−→
7−→
7−→
(fn n => if n=0 then 1 else n*fact(n-1)) 3
if 3=0 then 1 else 3*fact(3-1)
3*fact(3-1)
3*fact(2)
3*((fn n => if n=0 then 1 else n*fact(n-1)) 2)
3*(if 2=0 then 1 else 2*fact(2-1))
3*(2*fact(2-1))
3*(2*fact(1))
3*(2*((fn n => if n=0 then 1 else n*fact(n-1)) 1))
3*(2*(if 1=0 then 1 else 1*fact(1-1))
3*(2*(1*fact(0))
3*(2*(1*((fn n => if n=0 then 1 else n*fact(n-1)) 0)))
3*(2*(1*(if 0=0 then 1 else n*fact(n-1))))
3*(2*(1*1))
6
NB: manipolazione di stringhe: no variabili, no stack
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
14 / 56
Computazione come Riduzione [. . . cont.]
Esempio
[identità]
fun K x y = x;
fun S p q r = p r (q r);
3 val a = ...;
1
2
si valuta S K K a:
S K K a 7−→
7−→
7−→
7−→
7−→
7−→
7−→
(fn
(fn
(fn
K a
(fn
(fn
a
N. Fanizzi ( LdP)
p => (fn q => (fn r => p r (q r)))) K K a
q => (fn r => K r (q r))) K a
r => K r (K r)) a
(K a)
x => (fn y => x)) a (K a)
y => a) (K a)
Paradigma Funzionale
27 maggio 2015
15 / 56
Computazione come Riduzione [. . . cont.]
Data la definizione:
fun r x = r(r(x));
ogni computazione che comporti la valutazione di r
porta ad una riscrittura all’infinito:
computazione divergente con risultato indefinito
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
16 / 56
Ingredienti Fondamentali
Da 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 trasforma
il 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
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
17 / 56
Ingredienti Fondamentali [. . . cont.]
Omogeneità tra dati e programmi:
nessun vincolo sulla possibilità di
passare funzioni come argomenti di altre funzioni
restituire funzioni come risultato di altre funzioni
(di ordine su superiore)
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
18 / 56
Semantica
Programma serie di definizioni di valori che
introducono nuove associazioni nell’ambiente e
possono richiedere la valutazione di espressioni complesse
Operazioni per la valutazione (riduzione):
ricerca di binding di un identificatore in un ambiente
e sostituzione con la definizione
nome = abbreviazione per il valore associato
applicazione di un’espressione funzionale ad un argomento
si usa la β-regola, una variante della regola di copia
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
19 / 56
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 occorrenza
libera 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 ridotto
Implementazione
La macchina astratta adotta meccanismi di garbage-collection:
in caso presenza di funzioni come risultato,
va preservato l’ambiente locale per un tempo illimitato
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
20 / 56
Agenda
1
Computazione Senza Stato
2
Valutazione
Valori
Sostituzione senza cattura
Strategie di valutazione
3
Programmazione nei Linguaggi Funzionali
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
21 / 56
Valutazione
Punti aperti:
condizione di terminazione della riduzione,
la forma semplice per un valore
semantica precisa della β-regola:
(cattura,) ordine di riduzione in caso di più redex
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
22 / 56
Valori
valore: espressione non ulteriormente riducibile
Tipologie
semplici primitivi predefiniti (interi, booleani, caratteri, . . . )
funzionali val nome = exp
comporta la valutazione dell’espressione a destra di =
e il binding del valore risultante con il nome a sinistra
NB: la valutazione non ha luogo nell’astrazione
fn x => exp
rappresenta un valore funzionale:
le redex eventualmente contenute in exp non vengono
semplificate fino alla sua applicazione ad un argomento
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
23 / 56
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 contenuta
invece: come nei ling. convenzionali, valutazione alla
chiamata/applicazione:
fn x => ((fn y => y+1) 2)
nessuna valutazione del corpo
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
24 / 56
Sostituzione senza cattura
Sostituzione senza cattura: implementata attraverso le chiusure
Sintatticamente: nomi distinti
convenzione in ogni espressione, si tengono distinti
i nomi per i parametri formali e
quelli delle altre variabili (non param.)
In tal modo non si verifica cattura
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
25 / 56
Strategie di valutazione
Esempio
fun
fun
3 fun
4 fun
5 val
1
2
valutazione di v
K x y = x;
r z = r(r(z));
D u = if u=0 then 1 else u;
succ v = v+1;
v = K (D (succ 0)) (r 2);
per la β-regola, a destra della def. di v ci sono 4 redex
candidate: 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
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
26 / 56
Valutazione per valore
Strategia dell’ordine d’applicazione, eager, o interna:
una redex viene valutata solo se l’espressione che
costituisce la parte argomento è già un valore
algoritmo
1
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 val
4
ridurre ((fn x => ...) val) e tornare a (1)
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
27 / 56
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à valori
il 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, argomento da valutare
(r 2) → r (r 2) → r (r (r 2)) → · · ·
divergente!
In conclusione, v indefinito
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
28 / 56
Valutazione per nome
Strategia dell’ordine normale o esterna:
una redex viene valutata prima della sua parte argomento
algoritmo
1
sia (f_exp a_exp) la prima applicazione che occorre,
a partire da sinistra, nell’espressione
2
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 e
si torna a (1)
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
29 / 56
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 funzionale
la nuova forma dell’espressione sarà:
(fn y => D (succ 0))(r 2)
nota: prescinde da y
riducendo – al passo (3) – la redex più esterna:
D (succ 0)
→ if (succ 0)=0 then 1 else (succ 0)
→ if 1=0 then 1 else (succ 0)
→ succ 0 → 1
associato a v
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
30 / 56
Valutazione lazy
Osservazioni sulla valutazione per nome
una stessa redex può essere valutata più volte per
duplicazioni richieste dalla riscrittura
nell’es. precedente, (succ 0) è duplicata a causa di D
e viene ridotta due volte nel condizionale nel corpo di D
if (succ 0)=0 then 1 else (succ 0)
Idea: posporre la valutazione di un argomento rispetto
all’applicazione di una funzione
consente di non divergere
ma ha un prezzo
dipende dal costo per la valutazione di ogni copia
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
31 / 56
Valutazione lazy [. . . cont.]
Strategia lazy
come quella per nome ma il valore di una redex
viene calcolato solo alla prima occorrenza e
conservato 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
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
32 / 56
Confronto delle strategie
Teorema (strategie di valutazione)
Sia exp un’espressione chiusa∗ . Se la valutazione di exp converge al
valore primitivo val per ognuna delle strategie allora si produce
val per la strategia per nome. Se, invece, diverge usando la
strategia per nome allora diverge anche usando le altre.
Osservazione
non si contempla il caso che da exp si producano valori primitivi
differenti a seconda della strategia
(*) Un’espressione è chiusa sse tutte le sue variabili sono legate in qualche costrutto fn
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
33 / 56
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 stessa
espressione produce sempre lo stesso valore
Questo sembra favorire le strategie con chiamate by need
anche dal punto di vista dell’efficienza
LISP, SCHEME e ML adottano la strategia per valore
(includendo anche alcuni dei principali aspetti imperativi)
MIRANDA e HASKELL adottano quella lazy
(ling. funzionali puri)
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
34 / 56
Agenda
1
Computazione Senza Stato
2
Valutazione
3
Programmazione nei Linguaggi Funzionali
Ambiente Locale
Interattività
Tipi
Pattern Matching
Oggetti Infiniti
Aspetti Imperativi
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
35 / 56
Programmazione nei Linguaggi Funzionali
Il meccanismi presentati sono sufficienti per descrivere un
linguaggio Turing-completo:
si può esprimere qualunque funzione computabile
Ogni linguaggio funzionale aggiunge a tale nucleo altri costrutti
più espressivi per facilitare la programmazione
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
36 / 56
Ambiente Locale
Un linguaggio di prog. moderno necessità di un ambiente
strutturato per le definizioni (non solo uno scope globale)
si adotta una politica con scope a più livelli
esempio, costrutto let
let x = exp in exp1 end
binding di x al valore di exp in un ambito che include exp1
nota: le espressioni funzionali determinano scope annidati
gli ambienti relativi includono i parametri formali
legati a quelli effettivi
ai fini della valutazione, il costrutto dell’es. può essere
considerato come syntactic sugar per
(fn x => exp1) exp
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
37 / 56
Interattività
Ogni linguaggio funzionale presenta anche un
ambiente interattivo
si usa il linguaggio per immettere espressioni
che la macchina astratta valuta restituendone il valore
le definizioni sono espressioni che modificano l’ambiente
globale (e possono restituire valori)
le implementazioni sono tipicamente interpretate
esistono, tuttavia, implementazioni che compilano le
definizioni alla loro prima immissione nell’ambiente
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
38 / 56
Tipi
Sistemi dei tipi
tipi primitivi standard (interi, boolean, caratteri):
valori ed operazioni
tipizzazione statica
tranne SCHEME, che adotta la tipizzazione dinamica
definizione di nuovi tipi
es. coppie, liste, record (n-ple con etichette dei campi).
in ML, si può definire la funzione add_p che prende in input
una coppia di interi e ne restituisce la somma:
fun add_p (n1,n2) = n1+n2;
NB: non avrebbe senso fornire a add_p un solo argomento
come nel currying
tipi di funzioni, funzioni come valori
valori denotabili ed esprimibili
(anche memorizzabili, se sono inclusi anche aspetti imperativi)
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
39 / 56
Tipi [. . . cont.]
espressioni funzionali illegali (nei ling. tipizzati)
perché non può essere assegnato un tipo preciso
es. 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
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
40 / 56
Tipi [. . . cont.]
espressione illegale, auto-applicazione:
fun Delta x = x x;
(x x) è illegale: non c’è modo di assegnare a x un singolo tipo
occorrendo a sinistra di una applicazione, dev’essere di tipo
’a -> ’b
essendo anche argomento di una funzione, deve avere il tipo
richiesto, ossia ’a
non c’è modo di unificare tali espressioni
In SCHEME , mancando la tipizzazione forte:
X Delta è legale
X 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 runtime
In ML, è ammesso il polimorfismo
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
41 / 56
Pattern Matching
Esempio
calcolo dell’n-esimo termine della serie di Fibonacci:
fun Fibo n = if n=0 then 1
else if n=1 then 1
3
else Fibo(n-1)+Fibo(n-2);
1
2
inefficiente!
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
42 / 56
Pattern Matching [. . . cont.]
Meccanismo di pattern matching
ammesso da ML e HASKELL
fun Fibo 0 = 1
| Fibo 1 = 1
3 |
Fibo n = Fibo(n-1)+Fibo(n-2);
1
2
def. (ricorsiva) per casi
parametro formale: pattern
schema (modello) di espressione fatto di variabili, costanti e
altri costrutti, a seconda del sistema di tipo
quando la funzione viene applicata ad un param. effettivo
questo viene confrontato con i pattern (nell’ordine) e
si sceglie il corpo relativo alla prima corrispondenza (match)
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
43 / 56
Pattern Matching [. . . cont.]
Meccanismo flessibile con tipi strutturati
Esempio liste, in ML:
si usano valori separati da virgole tra parentesi quadre
["one", "two", "three"] lista di 3 stringhe
:: denota l’operatore cons (aggiunta di un elemento in testa)
"zero"::["one", "two", "three"]
espressione che ha per valore la lista
["zero", "one", "two", "three"]
nil denota la lista vuota
"four"::nil ha valore ["four"]
Funzione che calcola la lunghezza di una lista
1
2
fun length nil = 0
| length e::rest = 1 + length(rest);
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
44 / 56
Pattern Matching [. . . cont.]
Osservazioni
i nomi nei pattern servono come parametri formali per
denotare parti del parametro effettivo
maggiore concisione rispetto a:
1
2
fun length list = if list = nil then 0
else 1 + length(tl list);
che richiede una funzione di selezione (tl) della lista priva
della testa (coda o tail).
La selezione è implicita nel pattern matching
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
45 / 56
Pattern Matching [. . . cont.]
Vincolo: una variabile non deve comparire più volte in un pattern
Esempio
fun
|
3 |
4 |
1
2
Eq
Eq
Eq
Eq
funzione per il test di uguaglianza
nil = false
[e] = false
x::x::rest = true
x::y::rest = 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
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
46 / 56
Oggetti Infiniti
Adottando strategie per nome o lazy (come in HASKELL1 ),
si possono definire e manipolare strutture dati potenzialmente
infinite (es. gli stream)
Nozione di valore
valutazione eager, un valore di tipo T list è una lista i cui
elementi sono valori di tipo T
valutazione lazy, questa non è una buona nozione di valore
perché potrebbe richiedere la valutazione di redex inutili,
contro la filosofia call-by-need
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
47 / 56
Oggetti Infiniti [. . . cont.]
Esempio valutazione lazy
Selezione di testa e coda di una lista non-vuota
1
2
fun hd x::rest = x;
fun tl x::rest = rest;
Consideriamo
hd [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)
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
48 / 56
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 redex
Esempio
Si può definire una lista in modo ricorsivo:
val infinity2 = 2 :: infinity2;
infinity2 corrisponde ad una lista, potenzialmente infinita,
i cui elementi sono tutti 2
valutazione eager: la valutazione divergerebbe
valutazione lazy: valore perfettamente manipolabile
hd infinity2
la valutazione termina con 2
hd (tl (tl (tl infinity2)))
idem
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
49 / 56
Oggetti Infiniti [. . . cont.]
Esempio Si definisce la funzione che costruisce una lista
infinita di numeri naturali a partire dal parametro n:
fun numbersFrom n = n :: numbersFrom(n+1);
Si possono definire funzioni di ordine superiore che applicano il
proprio argomento funzionale a tutti gli elementi di una lista:
1
2
fun map f nil = nil
| map f e::rest = f(e)::rest;
Si può produrre ora la lista infinita dei quadrati a partire da n*n:
fun squaresFrom n = map (fn y => y*y) (numbersFrom n);
1
si usa la sintassi di ML ma considerando la valutazione lazy
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
50 / 56
Aspetti Imperativi
Molti ling. funzionali (es. ML) includono meccanismi che
necessitano della nozione di stato
Sono date variabili modificabili (reference cell), attraverso effetti
collaterali, 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 T
ref v crea una var. inizializzata con il valore v (di tipo T)
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
51 / 56
Aspetti Imperativi [. . . cont.]
i costrutti standard valgono anche per il tipo T ref
es. 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 T
assegnazione: modifica delle variabili
I := !I + 1;
notare la differenza con la def. del valore n di cui sopra
si sta modificando l’r-value di una variabile che già esiste
il tipo di un costrutto imperativo è unit
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
52 / 56
Aspetti Imperativi [. . . cont.]
la presenza di var. modificabili rende possibile l’aliasing:
1
2
val I = ref 4;
val J = I;
la 2 associa il valore del nome I (cioè la var.) al nome J
I e J sono nomi diversi (alias) per lo stesso l-value
Dopo l’esecuzione di
3
4
I := 5;
val z = !J;
il nome z è associato al valore 5
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
53 / 56
Aspetti Imperativi [. . . cont.]
La definizione di ML non specifica come implementare
l’assegnazione tra variabili
implementazione tradizionale: r-value copiato dalla sorgente
alla destinazione ma le var. possono avere fabbisogni di
memoria molto diversi
Es. variabili con liste e stringhe
1
2
val S = ref "pear";
val L = ref ["one", "two", "three"];
Il nome S è di tipo string ref,
mentre L è di tipo (string list)ref
le due var. associate ai nomi S e L possono contenere, risp.,
qualunque stringa e qualunque lista, ad es.:
1
2
S := "stringa molto piu’ lunga della precedente";
L := "zero" :: "four" :: "five" :: !L;
i nuovi valori di L e S richiedono più memoria dei precedenti
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
54 / 56
Aspetti Imperativi [. . . cont.]
È possibile implementare queste assegnazioni usando una
semplice (e standard) copia di valori
la macchina astratta copia i riferimenti (puntatori) a tali valori
tutto trasparente all’utente
l’implementazione gestisce i due fabbisogni di spazio,
allocando la mem. necessaria per ognuno dei casi e
modificando i riferimenti
ML fornisce anche costrutti di controllo imperativo
come la sequenza (;) e i cicli
Osservazione l’uso di caratteristiche imperative lede il teorema
precedente: risultati non corretti
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
55 / 56
Riferimenti
Gabbrielli & Martini: Linguaggi di Programmazione,
McGraw-Hill 2a edizione
N. Fanizzi ( LdP)
Paradigma Funzionale
27 maggio 2015
56 / 56