Programmazione Funzionale:
ML






implementazione del l-calcolo tipato
definizione di nuovi tipi ricorsivi
i valori dei nuovi tipi sono termini, che possono essere visitati con
un meccanismo di pattern matching (versione semplificata
dell’unificazione)
scoping statico (a differenza di LISP)
semantica statica molto potente (inferenza e controllo dei tipi)
• un programma “corretto” per la semantica statica quasi sempre
va bene
gestione della memoria a heap con garbage collector
1
Lo strumento utilizzato seconda
parte del corso
 Ocaml (Objective CaML), una estensione, orientata ad
oggetti (e con un frammento imperativo), di uno dei più
importanti linguaggi funzionali (ML)

progettato ed implementato all’INRIA (Francia)
 l’implementazione (per tutte le piattaforme importanti) si
può scaricare dal sito
http://caml.inria.fr/
 il manuale on line al sito
http://caml.inria.fr/ocaml/htmlman/index.html
2
OCAML
 nucleo funzionale puro



funzioni (ricorsive)
tipi e pattern matching
primitive utili: liste
 componente imperativo


variabili e assegnamento
primitive utili: arrays
 moduli e oggetti
 meccanismi per la definizione di tipi e di tipi di
dato astratto
3
Applicazione: macchina astratta
 semantica operazionale: implementazione e
strutture a tempo di esecuzuioone
 riprenderemo l’interprete di un semplice
linguaggio imperativo (frammento C) visto a
Programmazione I
 vedremo come utilizzare le caratteristiche del
linguaggio ad oggetti (meccanismi di astrazione
sui dati)
Seguendo il tutorial
 sessione interattiva
 l’utente scrive frasi CAML che iniziano con
prompt #
 a seguito del prompt, il sistema compila le frasi,
le esegue e stampa il risultato della valutazione
 per ogni frase il risultato e’ un valore ed il tipo
(type inference)
Espressioni pure
Objective Caml version 2.00+3/Mac1.0a1
# 25;;
- : int = 25
# true;;
- : bool = true
# 23 * 17;;
- : int = 391
# true & false;;
- : bool = false
# 23 * true;;
This expression has type bool but is here used with type int
# if 2 = 3 then 23 * 17 else 15;;
- : int = 15
# if 2 = 3 then 23 else true;;
This expression has type bool but is here used with type int
6
Funzioni
# function x -> x + 1;;
- : int -> int = <fun>
# (function x -> x + 1) 3;;
- : int = 4
# (function x -> x + 1) true;;
This expression has type bool but is here used with
type int
anche i parametri delle funzioni non richiedono
annotazioni di tipo (il tipo e’ inferito dal loro uso nel
corpo)
il valore di una funzione e’ <fun>
7
Funzioni
#
#
#
#
#
#
-
function x -> x;;
: 'a -> 'a = <fun>
function x -> function y -> x y;;
: ('a -> 'b) -> 'a -> 'b = <fun>
(function x -> x) 2;;
: int = 2
(function x -> x) (function x -> x + 1);;
: int -> int = <fun>
function (x, y) -> x + y;;
: int * int -> int = <fun>
(function (x, y) -> x + y) (2, 33);;
: int = 35
‘a e’ una variabile di tipo, puo’ assumere qualsiasi tipo (polimorfismo)
le funzioni sono valori, possono essere passate come parametri
(funzioni di ordine superiore)
8
Il costrutto let \ let in
 permette di definire un nuovo identificatore a con
associato un valore
 valori: simple expressions o funzioni
Let binding
# let x
val x :
# x;;
- : int
# let y
- : int
# y;;
Unbound
•
= 3;;
int = 3
= 3
= 5 in x + y;;
= 8
value y
(definizione globale/locale)
10
Let binding
# let f = function x -> x + 1;;
val f : int -> int = <fun>
# f 3;;
- : int = 4
# let f x = x + 1;;
val f : int -> int = <fun>
# f 3;;
- : int = 4
# let fact x = if x = 0 then 1 else x * fact(x - 1) ;;
Unbound value fact
11
Let rec binding
# let rec fact x = if x = 0 then 1 else x * fact(x - 1)
;;
val fact : int -> int = <fun>
# fact (x + 1);;
- : int = 24
12
Type
 per definire nuove strutture dati vengono
forniti records e variants (unione)
 entrambi si definiscono con una
dichiarazione di tipo type
Record
# type ratio={num:int; denum:int};;
type ratio={num:int; denum:int}
# let x={num=1;denum=3);;
val x: ratio={num=1;denum=3;}
# x.num;;
- int =1
• un record per memorizzare numeri razionali
• creare e selezionare i campi
14
Unione disgiunta, variant
• enumera tutti i casi che possono assumere i
valori di quel tipo
• ogni caso e’ identificato da un nome
(costruttore) che serve per costruire valori
di quel tipo e per riconscerlo per patternmatching
• utile per definire tipi di dato ricorsivi
15
# type number = | Int of int
type number=
| Int of int
| Float of float
| Error
| Float of float
# let add_num n1 n2=
match (n1,n2) with
(Int i1,Int i2)--->.......
(Int i1,Float i2)--->
(Float i1,Float i2)--->
(Float i1,Int i2)--->
(Error,-)---------->Error
(-,Error)---------->Error
val add_num: number->number->number=<fun>
# Int 3;;
- : number= Int 3;
| Error;;
Espressioni: sintassi astratta
# type ide = string;;
type ide = string
# type expr = | Den of ide | Val of ide | Fun of ide * expr
| Plus of expr * expr | Apply of expr * expr;;
type expr =
| Den of ide
| Val of ide
| Fun of ide * expr
| Plus of expr * expr
| Apply of expr * expr
E ::= I | val(I) | lambda(I, E1) | plus(E1, E2) | apply(E1, E2)
# Apply(Fun("x",Plus(Den "x", Den "x")), Val "y");;
- : expr = Apply (Fun ("x", Plus (Den "x", Den "x")), Val "y")
17
L’ambiente
# type eval = Int of int | Bool of bool | Efun of expr
| Unbound;;
type eval = | Int of int | Bool of bool | Efun of expr |
Unbound
# type env = ide -> eval;;
type env = ide -> eval
# let bind (rho, i, d) =
function x -> if x = i then d else rho x;;
val bind : (ide -> eval) * ide * eval -> (ide -> eval) = <fun>
- env = IDE  eval
- eval = [ int + bool + fun ]
18
Comandi: sintassi astratta
# type com = Assign of ide * expr | Ifthenelse of expr *
com list * com list | While of expr * com list;;
type com =
| Assign of ide * expr
| Ifthenelse of expr * com list * com list
| While of expr * com list
C ::= ifthenelse(E, C1, C2) | while(E, C1) | assign(I, E) | cseq(C1, C2)
# While(Den "x", [Assign("y", Plus(Val "y", Val "x"))]);;
- : com =
While (Den "x", [Assign ("y", Plus (Val "y", Val "x"))])
19
Tipi e pattern matching
type expr =
| Den of ide
| Fun of ide * expr
| Plus of expr * expr
| Apply of expr * expr
type eval = | Int of int | Bool of bool | Efun of expr | Unbound
type env = ide -> eval
E(I, ) = (I)
E(plus(E1, E2), )= E(E1, ) + E(E2, )
E(lambda(I, E1), )= lambda(I, E1)
E(apply(E1, E2), ) = applyfun (E(E1, ), E(E2, ), )
applyfun(lambda(I, E1), d, ) = E(E1) [ / I  d ]
# let
|
|
|
|
rec sem (e, rho) = match e with
Den i -> rho i
Plus(e1, e2) -> plus(sem (e1, rho), sem (e2, rho))
Fun(i, e) -> Efun(Fun(i, e))
Apply(e1, e2) -> match sem(e1, rho) with
| Efun(Fun(i, e)) -> sem(e, bind(rho, i, sem(e2, rho))
| _ -> failwith("wrong application");;
val sem : expr * env -> eval = <fun>
20
Un tipo primitivo utile: le liste
 Si costruiscono enumerando esplicitamente
gli elementi, racchiusi tra []
 Oppure a partire dalla lista vuota [] tramite
l’operatore di cons
 Operazioni primitive standard
Liste
# let l1 = [1; 2; 1];;
val l1 : int list = [1; 2; 1]
# let l2 = 3 :: l1;;
val l2 : int list = [3; 1; 2; 1]
# let l3 = l1 @ l2;;
val l3 : int list = [1; 2; 1; 3; 1; 2; 1]
# List.hd l3;;
- : int = 1
# List.tl l3;;
- : int list = [2; 1; 3; 1; 2; 1]
# List.length l3;;
- : int = 7
22
Caratteristiche Imperative
 variabili e assegnamento
 arrays (mutabili)
 comandi iterativi, while, for
Variabili e frammento
imperativo
# let x = ref(3);;
val x : int ref = {contents=3}
# !x;;
- : int = 3
# x := 25;;
- : unit = ()
# !x;;
- : int = 25
# x := !x + 2; !x;;
- : int = 27
 references sono mutable indirection cells, il cui
valore puo’ essere modificato da un assegnamento
24
Un tipo primitivo mutabile:
l’array
# let a = [| 1; 2; 3 |];;
val a : int array = [|1; 2; 3|]
# let b = Array.make 12 1;;
val b : int array = [|1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1|]
# Array.length b;;
- : int = 12
# Array.get a 0;;
- : int = 1
# Array.get b 12;;
Uncaught exception: Invalid_argument("Array.get")
# Array.set b 3 131;;
- : unit = ()
# b;;
- : int array = [|1; 1; 1; 131; 1; 1; 1; 1; 1; 1; 1; 1|]
25
Programmi Stand-alone
 Il programma da eseguire deve essere
memorizzato in un file .ml
 Compilare ed eseguire
26
Esercizio 1
 Funziona per ordinare una lista polimorfa
 Le liste sono un tipo di dato primitivo immutabile
(in stile funzionale), a differenza degli array
 La funzione sort ha tipo
'a list -> 'a list
• Gli operatori di confronto (=,<=,….) sono
polimorfi, si applicano ad ogni tipo
27
Cosa vogliamo?
# let l1 = [6; 2; 5; 3];;
val l1 : int list = [6; 2; 5;3]
# sort l1 ;;
- : int list = [2; 3; 5;6]
# let l2 = [3.14; 2.17];;
val l1 : int list = [3.14; 2.17]
# sort l2 ;;
- : float list = [2.17; 3.14]
• La lista passata come input non e’ modificata, la funzione
restituisce una nuova lista, che contiene gli elementi in
ordine crescente
Insertion sort
 Realizzare sort in modo ricorsivo
caso base: []
caso ricorsivo cons: head:: tail
• Pattern matching
• Insertion sort (funzione ausiliaria che
inserisce un elemento in una lista ordinata)
Funzioni di ordine superiore
 in puro stile funzionale le funzioni sono
valori, possono essere passate come
parametri ad altre funzioni
• E’ utile per realizzare operazioni su
strutture dati
List.map
# let l1 = [6; 2; 5; 3];;
val l1 : int list = [6; 2; 5;3]
# List.map (function n -> n+1) l1 ;;
- : int list = [7; 3; 6;4]
• E’ un funzionale standard, applica una funzione ad ogni
elemento di una lista
• E’ fornito dalla libreria, ma non c’e’ niente di magico
• Definiamolo, come una funzione ricorsiva di ordine
superiore
Alberi binari
 Definire un tipo unione ‘a btree che specifica
alberi binari polimorfi
 Definizione ricorsiva:
caso base: vuoto
caso ricorsivo: un nodo che contiene un valore
di tipo ‘a, e due sottoalberi ‘a btree sx e dx
32
Btree
# type ‘a btree= Empty| Node of ‘a * ‘a btree * ‘a btree;;
type ‘a btree= Empty| Node of ‘a * ‘a btree * ‘a btree
# Empty;;
- : ‘a btree = Empty
# Node(1,Empty,Empty);;
-: int btree = Node(1,Empty,Empty)
# Node;;
the constructor node expects 3 arguments, but is here applied to zero
arguments
Funzioni
 Scrivere una funzione che, dato un ‘a btree,
calcola il numero di nodi
 Ordered Binary Btree: ‘a btree polimorfi ma
ordinati, il sottoalbero sx ha un valore strettamente
minore, e quello dx un valore strettamente
maggiore di quello del nodo
 Scrivere due funzioni che, dato un ordered ‘a
btree ed un valore x di tipo ‘a , fanno la
ricerca o l’inserimento di x
Osservazione
 Le funzioni member e insert come
parametro un btree
 Assumiamo che sia di tipo Ordered
 Non possiamo definire un tipo di dato
Ordered per costruzione
 Che cosa serve? Un meccanismo per
definire un tipo di dato astratto
Tipi di dato astratto
 Dati + operazioni : insieme
 In questo modo possiamo definire proprieta’
dei dati (tipo l’ordine per costruzione)
 Meccanismi di astrazione, incapsulamento
dell’informazione, in modo da garantire che
le proprieta’ non siano violate dal codice
che usa il tipo di dato