Linguaggi di Programmazione avanzati Linguaggi funzionali

(1)

Linguaggi di Programmazione avanzati Linguaggi funzionali

Simone Martini

Dipartimento di Scienze dell’Informazione Universit` a di Bologna

Italy

A.a. 2005-2006

(2)

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: call/cc

(3)

Ricorsione di coda

I Sia f una funzione il cui corpo contenga una chiamata a g

I La chiamata di g ` e una chiamata in coda (tail call) se f restituisce il valore restituito da g senza ulteriore computazione.

I f ` e ricorsiva in coda (tail recursive) se tutte le chiamate in f sono chiamate in coda.

I Le funzioni ricorsive in coda possono (al primo ordine) essere eseguite con un solo RdA

I La continuation passing transformation permette di

trasformare ogni funzione in una ricorsiva in coda.

(4)

Continuation passing style

I Usato come trasformazione intermedia per alcuni linguaggi funzionali

I Eliminazione delle ricorsione

I Semplice

I Espone situazioni che possono essere (pi` u) facilmente ottimizzate da un compilatore

I Elimina molte sottoespressioni annidate

(5)

Continuazioni

I Fissato un punto in un programma, la sua continuazione ` e una funzione che esprime la computazione che verr` a eseguita dal resto del programma

I Una funzione che restituisce un valore, lo restituisce (implicitamente) alla sua continuazione

I La CPS rende esplicita sia la continuazione, sia il passaggio di valori alle continuazioni

I fun foo x = x+1;

Se k ` e un nuovo parametro di foo , che “sta per” la continuazione:

fun foo’ x k = k(x+1);

I “Una funzione non ritorna, continua”

I “Le continuazioni sono goto con argomenti”

(6)

Continuazioni, 2

I Supponiamo di avere due funzioni f(x,y) e g(x,y) con le quali definiamo una nuova funzione

fun fie x y = g(f(2,x),y)

I Trasformiamo f e g in CPS; otterremo

fun f’ (x,y) k = ...;

fun g’ (x,y) k = ...;

I Come viene trasformato fie ?

I Innanzitutto avremo fun fie’ (x,y) c = ...

I c ` e la continuazione di fie’

I Dunque c ` e la continuazione che deve essere passata a g’

I Ma quale continuazione deve essere passata a f’ ?

(7)

Continuazioni, 3

I fun fie x y = g(f(2,x),y)

I fun fie’ (x,y) c = ... g’ (...) c ...

I Ma quale continuazione deve essere passata a f’ ?

I f passa il proprio valore al “contesto” nel quale avviene la chiamata:

λv . g (v , y )

o meglio, usando g’ :

λv .g ’ (v , y ) c I Dunque avremo

fun fie ’ ( x , y ) c = f ’ (2 , x ) (λv . g ’ ( v , y ) c )

(8)

Continuazioni, 4

I fun fie x y = g(f(2,x),y)

I fun fie ’ ( x , y ) c = f ’ (2 , x ) (λv . g ’ ( v , y ) c )

I La CPS “isola” le sottoespressioni e le “sequenzializza”

introducendo dei nomi locali ( v ) per esse.

I Queste informazioni sono usate dal compilatore per la generazione di codice efficiente

I La chiamata di f’ ` e in coda

(9)

Ricorsione e CPS

I fun f a c t 0 = 1

| f a c t ( S n ) = ( S n ) * ( f a c t n ) I Supponiamo (per ora) che * non sia in CPS

I Otteniamo

fun fact ’ 0 k = k 1

| fact ’ ( S n ) k = fact ’ n (λv . k (( S n ) * v ) ) I La funzione fact’ ` e tail recursive, la sua valutazione ` e

sequenzializzata e ai temporanei ` e stato assegnato un nome.

I Se anche * ` e in CPS:

fun fact ’ 0 k = k 1

| fact ’ ( S n ) k = fact ’ n (λv . * ’ ( S n ) v k )

(10)

Continuation passing transformation

I Linguaggio sorgente, call by-value:

M, N ::= c | x | (λx.M) | (MN)

I Per M termine e k continuazione, definiamo [[M]]k la traduzione CPS di M con continuazione k

I Un programma M ` e tradotto con [[M]](λx .x )

I I valori (c, x , λx .M) li passiamo semplicemente alla continuazione:

I

[[c]]k = k c

I

[[x ]]k = k x

I

[[λx .M]]k = k (λx .λh.[[M]]h)

I In un’applicazione usiamo le continuazioni per esprimere l’ordine di valutazione:

I

[[MN]]k = [[M]] (λf .[[N]](λz.f z k))

(11)

CPS per altri costrutti

I Funzioni primitive unarie (non in cps) [[f (M)]]k = [[M]](λi .k(f (i )))

I Funzioni primitive binarie (non in cps) [[g (M, N)]]k = [[M]](λi .[[N]](λj .k(g (i , j ))))

I Condizionale

[[cond (M, N, P)]]k = [[M]](λb.if b then [[N]]k else [[P]]k)

(12)

Simulare call-by-value con call-by-name

I Sia M un termine del nucleo (λ-calcolo)

I Sia I = λx .x , la continuazione nulla (cio` e la continuazione dell’intero programma)

Theorem (Plotkin) (i) Indifferenza:

Eval N ([[M]] I ) = Eval V ([[M]] I ) (ii) Simulazione:

Ψ(Eval _V (M)) = Eval _N ([[M]] I )

dove Ψ manda valori in valori ed ` e definita come

Ψ(a) = a; Ψ(x ) = x ; Ψ(λx .M) = λx .[[M]].

(13)

Interpreti e semantica

I Dato un linguaggio L, ` e prassi comune usare L per scrivere un interprete (o un compilatore) per L stesso.

I Ma: con quale strategia di valutazione deve essere “inteso”

l’interprete, che a sua volta descrive la strategia di valutazione di L?

I Se l’interprete ` e scritto in CPS tale problema non si pone

(Reynolds, 1972)

(14)

Call/cc

I Alcuni linguaggi (Scheme, ML New Jersey: call/cc ) e sistemi operativi (Solaris: getcontext() ) hanno un comando che permette di manipolare la “continuazione corrente” (che diviene cos`ı esplicitamente presente nel linguaggio).

I Si tratta di una sorta di goto dinamico

I Scheme:

call-with-current-continuation M (abbreviato in call/cc M )

chiama il suo argomento M (che deve essere una funzione

unaria) passandogli come argomento la continuazione corrente

(15)

Call/cc: semantica

I La semantica formale di call/cc pu` o essere data mediante la CPS

I In generale:

[[call/cc M]]k = [[M]](λf .f k k)

I Se assumiamo che M sia della forma λc.N, si ottiene pi` u semplicemente

[[call/cc (λc.N)]]k = ([[N]]k)[k/c]

che corrisponde alla semantica informale.

([[N]]k)[k/c] indica, come al solito, la sostituzione di k al

posto di c in [[N]]k.

(16)

Call/cc: esempi

I Le seguenti espressioni hanno tutte valore 5:

3 + ( c a l l / cc (λ k . 2)) 3 + ( c a l l / cc (λ k . k 2)) 3 + ( c a l l / cc (λ k . 4 + ( k 2 ) ) )

I Nell’ultimo esempio, call/cc ` e analogo ad un’eccezione:

3 + try {4 + ( t h r o w k 2)} c a t c h ( k x ) { x }

(17)

Intermezzo: un po’ di calcoli

I Valutazione di un’espressione della pagina precedente, usando la traduzione “semantica” di call/cc

I Sia v (λj.3 + j):

[[3 + (call /cc (λk.k 2))]]I = [[call /cc (λk.k 2)]](λj .3 + j )

= [[λk.k 2]](λf .f v v )

= (λf .f v v )(λk.λh.k 2 h)

= (λk.λh.k 2 h)v v

= (λj .3 + j ) 2 v

= (3 + 2) v

I C’` e una v (una continuazione) di troppo.

I Il problema sta nella CPS dell’espressione k 2

(18)

Invocare una continuazione: semantica

I Quando invochiamo una continuazione, dobbiamo gettar via la continuazione corrente

I Se k ` e una continuazione, dobbiamo stipulare che [[kM]]h = [[M]]k

invece dell’usuale gestione dell’applicazione.

I Se applichiamo questa traduzione all’esempio si ottiene ora:

[[3 + (call /cc (λk.k 2))]]I = [[call /cc (λk.k 2)]](λj .3 + j )

= [[λk.k 2]](λf .f v v )

= (λf .f v v )(λk.λh.k 2)

= (λk.λh.k 2)v v

= (λj .3 + j ) 2

= (3 + 2)

(19)

Invocare una continuazione: throw

I In modo formalmente pi` u corretto, sarebbe bene distinguere linguisticamente tra la normale applicazione di una funzione e l’applicazione di una continuazione

I Il costrutto

throw M N

valuta M per ottenere una continuazione e poi valuta N in questa nuova continuazione.

I In “semantica” CPS:

[[throw M N]]k = [[M]](λk ⁰ .[[N]]k ⁰ )

I In Scheme, questa ` e la semantica delle chiamate di

continuazione

(20)

Call/cc: Eccezioni

I Abbiamo discusso l’analogia

3 + ( c a l l / cc (λ k . 4 + ( k 2))

3 + try {4 + ( t h r o w k 2)} c a t c h ( k x ) { x } I Si tratta di eccezioni statiche: k ` e legata nel try

I Le eccezioni statiche possono essere espresse con call/cc I try { M } c a t c h ( K x ) { N }

diviene

c a l l / cc (λ k . let K = λ x . k N in M )

I throw solleva un’eccezione e passa un valore:

t h r o w K N

diviene

K N

(21)

Call/cc: esempi

I call/cc ` e molto pi` u potente delle semplici eccezioni

I Problema: qual ` e il valore della seguente espressione?

let f = c a l l / cc (λ k . λ x . k (λ y . x + y )) in f 6

I 12

I Informalmente:

(λ f . f 6) ( c a l l / cc λ k . λ x . k (λ y . x + y ))

= ( c a l l / cc λ k . λ x . k (λ y . x + y )) 6

La continuazione da passare a call/cc ` e λ f.f 6 :

= (λ k . λ x . k (λ y . x + y )) (λ f . f 6) 6

= (λ x . (λ f . f 6) (λ y . x + y )) 6

= (λ f . f 6) (λ y . 6+ y ))

= (λ y . 6+ y ) 6 = 6+6 = 12

I Osserva: l’espressione λ ` e valutata due volte

(22)

Memorizzare una continuazione

I In Scheme abbiamo variabili modificabili

I Possiamo memorizzare una continuazione in una variabile

I (+ ( c a l l / cc (λk . k ( b e g i n

( set ! c o n t k )

( d i s p l a y " I n s i d e b o d y " ) 5 ) ) )

8)

I Stampa Inside body e restituisce 13

I In cont ` e memorizzata la continuazione λ v.(+ v 8) relativa al top level del ciclo dell’interprete

I Pi` u avanti possiamo valutare

(+ (/ ( c o n t 35) 0) 1 0 0 )

e ottenere 43

(23)

Loop infinito

( let (( c o n t # f )) ( c a l l / cc

( l a m b d a ( k )

( set ! c o n t k )))

( c o n t # f ))

(24)

Il costrutto BREAK I Lisp, come Scheme, ha un interprete iterativo che valuta

un’espressione, ne stampa il valore, e aspetta la prossima exp

I Il costrutto BREAK sospende la valutazione corrente e ritorna al top level (dove l’interprete aspetta la prossima espressione).

I Il costrutto RESUME permette la ripresa della computazione a partire dall’ultimo BREAK

I Con call/cc possiamo definire BREAK e RESUME ( c a l l / cc (λc . ( set ! escape - to - top c )))

( d e f i n e B R E A K ( c a l l / cc

(λk . ( set ! R E S U M E k )

( escape - to - top I ) ) ) )

(25)

Backtracking

( let (( b a c k t r a c k - k any ) ( non - blind - k any )) ( if ( c a l l / cc

( l a m b d a ( k )

( set ! b a c k t r a c k - k k ) ( b a c k t r a c k - k # t ))) ( b e g i n

begin first approach (when time-to-backtrack

( c a l l / cc

( l a m b d a ( k )

( set ! non - blind - k k ) ( b a c k t r a c k - k # f ) ) ) ) continue first approach)