Linguaggi di Programmazione avanzati Linguaggi funzionali

Linguaggi di Programmazione avanzati Linguaggi funzionali

Simone Martini

Dipartimento di Scienze dell’Informazione Universit`a di Bologna

Italy

A.a. 2005-2006

Outline

Il paradigma funzionale puro Un lambda-calcolo esteso Strategie di riduzione

Programmare in un linguaggio funzionale Zucchero sintattico

Tipi e polimorfismo Aspetti imperativi La macchina SECD

Monadi

Le continuazioni e la continuation passing transformation Continuazioni

La CPS

Le continuazioni come oggetti manipolabili:

Monadi: effetti collaterali in ambiente puro

I

In linguaggi call-by-value gli effetti collaterali sono aggiunti, ottenendo linguaggi impuri

I

Nei linguaggi puri, il flusso dei dati ` e totalmente esplicito

I

Talvolta questo ` e molto pesante, quando non impossibile

I

Discuteremo un esempio (P. Wadler, 1995)

Valutatore di espressioni

I

Sintassi Haskell-like

I

Il tipo dei termini

d a t a T e r m = Con Int | Div T e r m T e r m ; I

La funzione di valutazione

e v a l :: T e r m - > Int e v a l ( Con n ) = n

e v a l ( Div t u ) = ( e v a l t ) / ( e v a l u ) I

Due termini

ok = Div ( Div ( Con 2 0 0 0 ) ( Con 2)) ( Con 5) ko = Div ( Con 2 0 0 0 ) ( Con 0)

I e v a l ok = 200 e v a l ko indefinito

Eccezioni

I

Per sollevare eccezioni dobbiamo estendere il tipo dei valori:

eval pu` o restituire un Int oppure un’eccezione

I type M a = Excp | Value a

I ExcpeValuesonocostruttori

I M a `e un tipo polimorfo. Per ogni tipo T abbiamo il tipo M T

I A noi interessa M Int, i cui valori sono:

I Excp

I Value n

I

Il nuovo tipo di eval

eval :: Term -> M Int

Valutatore con eccezioni

I e v a l :: T e r m - > M Int e v a l ( Con a ) = V a l u e a e v a l ( Div t u ) =

c a s e e v a l t of E x c p - > E x c p

V a l u e a - > c a s e e v a l u of E x c p - > E x c p V a l u e b - > if b = 0

t h e n E x c p

e l s e V a l u e ( a / b )

I e v a l ok = V a l u e 200 e v a l ko = E x c p

I

Il risultato deve essere controllato ad ogni chiamata

Valutatore con I/O

I

Si vogliono stampare tutti i valori intermedi calcolati dal valutatore

I

Occorre estendere il tipo dei valori: eval restituisce sia un Int, sia l’output (una stringa, per esempio)

I d a t a M a = ( Output , a ) t y p e O u t p u t = S t r i n g I e v a l :: T e r m - > M Int

e v a l ( Con a ) = ( ’ Con ’ ++ ( s h o w I n t a ) , a ) e v a l ( Div t u ) =

let ( x , a ) = e v a l t in let ( y , b ) = e v a l u in

( x ++ y ++ ’ Div ’ ++ ( s h o w I n t a / b ) , a / b ) I showInt :: Int -> String

converte un intero in stringa

Valutatore con I/O, 2

I e v a l :: T e r m - > M Int

e v a l ( Con a ) = ( ’ Con ’ ++ ( s h o w I n t a ) , a ) e v a l ( Div t u ) =

let ( x , a ) = e v a l t in let ( y , b ) = e v a l u in

( x ++ y ++ ’ Div ’ ++ ( s h o w I n t a / b ) , a / b ) I ok = Div (Div (Con 2000) (Con 2)) (Con 5)

I eval ok = (x, 100)

dove

` e la stringa:

Con 2000 Con 2 Div 1000 Con 5 Div 200 I

Se volessimo ottenere la stampa a rovescio

Div 200 Con 5 Div 1000 Con 2 Con 2000

basterebbe usare il termine

’Div’ ++ (showInt a/b) ++ y ++ x

Valutatore con stato

I

Si vuole contare il numero di moltiplicazioni

I

Il tipo dei valori:

d a t a M a = S t a t e - > ( a , S t a t e ) t y p e S t a t e = Int

Un valore ` e una funzione che prende lo stato iniziale e restituisce il valore calcolato e accoppiato allo stato finale.

I e v a l :: T e r m - > M Int e v a l ( Con a ) x = ( a , x ) e v a l ( Div t u ) x =

let ( a , y ) = e v a l t x in let ( b , z ) = e v a l u y in

( a / b , z + 1)

Impariamo dagli esempi

I

Un tratto comune degli esempi Invece di:

Abbiamo:

I

Intuitivamente:

restituisce un

, pi` u gli effetti aggiuntivi descritti dall’opportuno

.

I

Quali sono le operazioni che sono possibili sui valori di tipo

M a

?

I

Cerchiamo di capirlo guardando i nostri valutatori. . .

Operazioni sui tipi monadici, 1

I

Il valutatore con eccezioni:

e v a l :: T e r m - > M Int eval (Con a) = Value a e v a l ( Div t u ) =

c a s e e v a l t of E x c p - > E x c p

V a l u e a - > c a s e e v a l u of E x c p - > E x c p V a l u e b - > if b == 0

t h e n E x c p

e l s e V a l u e ( a / b ) I

Usiamo un modo “canonico” per trasformare un valore di tipo

Int

nel corrispondente valore di tipo

.

I

Chiamiamo

questa “immersione”

return n = Value n

Operazioni sui tipi monadici, 2

I e v a l :: T e r m - > M Int e v a l ( Con a ) = V a l u e a e v a l ( Div t u ) =

c a s e e v a l t of E x c p - > E x c p Value a - > ...

V a l u e (a/ b )

I eval t

d` a il risultato

dal quale estraiamo il valore

per usarlo successivamente (nella divisione

)

I

Una funzione

I

Dobbiamo applicare

al “risultato di

” (ma i tipi non

tornano esattamente)

Operazioni sui tipi monadici, 3

I

Ricapitolando:

,

In generale:

applicare una funzione di tipo

ad una computazione di tipo

I

Abbiamo bisogno dunque di un’operazione

>>= :: M a -> (a -> M b) -> M b

che scriviamo infissa

t >>= g

Osserva che

mentre

Nel caso delle eccezioni:

t > >= g = c a s e t of

E x c p - > E x c p V a l u e a - > g a

Monadi

I

Una monade ` e una tripla

dove:

I M

` e un costruttore di tipo

I return :: a -> M a

I >>= :: M a -> (a -> M b) -> M b

I

Le due operazioni devono soddisfare tre leggi che vedremo tra

poco

Valutatore monadico

I

Data una monade M, possiamo scrivere il generico valutatore su di essa

I e v a l :: T e r m - > M Int e v a l ( Con a ) = r e t u r n a e v a l ( Div t u ) =

e v a l t > >= (λ a . e v a l u > >=

λ b . return ( a / b ))

Valutatore monadico per le eccezioni

I

Monade

I type M a = Excp | Value a

I return :: a -> M a return a = Value a

I >>= :: M a -> (a -> M b) -> M b t > >= g = c a s e t of

E x c p - > E x c p V a l u e a - > g a I

Valutatore

e v a l :: T e r m - > M Int e v a l ( Con a ) = r e t u r n a e v a l ( Div t u ) =

e v a l t > >= (λ a . e v a l u > >=

λ b . if b =0

t h e n E x c p

e l s e r e t u r n ( a / b ))

Monade dello I/O

I

Monade

I type M a = (Output, a)

I type Output = String

I return :: a -> M a return a = (’’,a)

I >>= :: M a -> (a -> M b) -> M b t > >= g = let ( x , a ) = t in

let ( y , b ) = g a in ( x ++ y , b )

I out :: Output -> M () out e = (x, ())

Valutatore monadico con I/O

I

Ricorda:

t > >= g = let ( x , a ) = t in

let ( y , b ) = g a in ( x ++ y , b ) out :: Output -> M ()

out e = (x, ()) I

Valutatore

e v a l :: T e r m - > M Int

e v a l ( Con a ) = out ( ’ Con ’ ++ ( s h o w I n t a ))

> >= λ(). r e t u r n a e v a l ( Div t u ) =

e v a l t > >= (λ a . e v a l u > >= λ b .

out ( ’ Div ’ + + ( s h o w I n t a / b )) > >=

λ(). return ( a / b )

Monade dello stato

I

Monade

I type M a = State -> (a, State)

I type State = Int

I return :: a -> M a r e t u r n a = λx .( a , x )

I >>= :: M a -> (a -> M b) -> M b

t > >= g = λx . let ( a , y ) = t x in

let ( b , z ) = g a y in ( b , z )

I tick :: M ()

t i c k = λx .(() , x +1)

Valutatore monadico con stato

I

Ricorda:

t > >= g = λx . let ( a , y ) = t x in

let ( b , z ) = g a y in ( b , z ) t i c k :: M ()

t i c k = λx .(() , x +1) I

Valutatore

e v a l :: T e r m - > M Int e v a l ( Con a ) = r e t u r n a e v a l ( Div t u ) =

e v a l t > >= (λ a . e v a l u > >= λ b .

t i c k > >= λ(). r e t u r n ( a / b )

Leggi

I

Neutro a sinistra

r e t u r n a > >= λb . n = n [ a / b ] I

Neutro a destra

m > >= λ a . r e t u r n a = m I

Associativit` a

m > >= λ a . ( n > >= λ b . o ) = ( m > >= λ a . n ) > >= λ b . o

Osserva che deve essere a 62 FV (o)

I

Esercizio: Verifica le leggi per le monadi introdotte

I

Le leggi servono per dimostrare propriet` a dei programmi

Monadi: una variante

I

Una monade pu` o essere definita anche come

(M, return, join, map)

con

map :: ( a - > b ) - > ( M a - > M b ) j o i n :: M ( M a ) - > M a

e le leggi

I map id = id

map ( f  g) = map f  map g map f  return = return  f

map f  join = join  map ( map f ) j o i n  return = id

j o i n  map return = id

j o i n  map join = join  join

Le due definizioni sono equivalenti

I

Definiamo

e

in termini di

map f m = m > >= λa . r e t u r n ( f a ) j o i n z = z > >= λm . m

I

Definiamo

in termini di

e

I

Esercizio: verificare le leggi in entrambi i casi.

La monade pi` u semplice: Identit` a

I

Monade

I type M a = a

I return :: a -> M a return a = a

I >>= :: M a -> (a -> M b) -> M b t >>= g = g t

I

Il generico valutatore monadico su questa monade concide col

valutatore “puro”

Liste come monadi

I

Vedere le liste come monadi pu` o essere utile

I

Monade

I type L a = [a]

Notazione Haskell: [Int] liste di interi

I return :: a -> L a return a = [a]

I >>= :: L a -> (a -> L b) -> L b l >>= g = concat (map g l) I

Esempio:

[10 ,20 ,30] > >= λx .[ x , x +1]

ha come risultato

[10,11,20,21,30,31]

Notazioni Haskell

I

Riprendiamo il valutatore con I/O

e v a l :: T e r m - > M Int

e v a l ( Con a ) = out ( ’ Con ’ ++ ( s h o w I n t a ))

> >= λ(). r e t u r n a e v a l ( Div t u ) =

e v a l t > >= (λ a . e v a l u > >= λ b .

out ( ’ Div ’ + + ( s h o w I n t a / b )) > >=

λ(). return (a/b) I

Alcune volte in

il valore di

non ` e usato

I

Notazione apposita:

>> :: M a -> M b -> M b

, definito come

m > > n = m > >= λ(). n I

Cos`ı risparmiamo qualche λ. . .

Notazione do

I

Il valutatore con I/O, ottimizzando i λ

e v a l ( Con a ) = out ( ’ Con ’ ++ ( s h o w I n t a )) >>

r e t u r n a e v a l ( Div t u ) =

e v a l t > >= (λ a . e v a l u > >= λ b .

out ( ’ Div ’ + + ( s h o w I n t a / b )) >>

r e t u r n ( a / b ) I

Osserva:

` e come

in C

>>=

` e simile ad un assegnamento.

I

La notazione

:

e v a l ( Con a ) = do out ( ’ Con ’ ++ ( s h o w I n t a )) r e t u r n a

e v a l ( Div t u ) = do a < - e v a l t b < - e v a l u

out ( ’ Div ’ + + ( s h o w I n t a / b )) r e t u r n ( a / b )

Notazione do, 2

I

Il valutatore con stato

e v a l ( Con a ) = r e t u r n a e v a l ( Div t u ) =

e v a l t > >= (λ a . e v a l u > >= λ b .

t i c k >> return (a/b) I

Diviene:

e v a l ( Con a ) = do r e t u r n a e v a l ( Div t u ) = do a < - e v a l t

b < - e v a l u t i c k

r e t u r n ( a / b )