Linguaggi Moderni: tda I programmi possono essere organizzati in moduli separati, la cui implementazione e’ invisibile al resto del programma



Scaricare 0.49 Mb.
03.06.2018
Dimensione del file0.49 Mb.













Linguaggi Moderni: TDA

  • I programmi possono essere organizzati in moduli separati, la cui implementazione e’ invisibile al resto del programma

  • l’implementazione dei moduli puo’ essere moficata-aggiornata senza modificare il resto del programma



Correttezza e Proprieta’

  • E’ possibile garantire in modo semplice proprieta’ invarianti del tipo di dato (il codice esterno non puo’ accedere all’implementazione)

  • Esempio: Btree ordinato





OCAML

  • Classi, oggetti, ereditarieta’ : brevemente le differenze piu’ rilevanti

  • Moduli ed Interfacce







Moduli ed Interfacce

  • per supportare in modo semplice i concetti di encapsulation e data hiding

  • l’interfaccia e’ definita da una module signature (.mli)

  • l’implementazione (o le) e’ definita da una module structure (.ml)



Signature: interfaccia

  • dichiara il tipo

  • dichiara i metodi pubblici, tramite la parola chiave val (nome, parametri, tipo)









Commenti

  • Il tipo astratto ’ a stack e’ implementato tramite una definizione ricorsiva

  • I metodi sono implementati di conseguenza

  • L’implementazione resta invisibile (in questo caso non ci sono definizioni ausiliarie, rimarrebbero comunque non visibili)



Come si usa un modulo?

  • Chiamando i metodi con

  • nome-modulo.nome-metodo

  • #let p= ref PILA.emptystack;;

  • #p:=push p “prova”;;



Applicazione

  • Useremo il sistema dei moduli per presentare alcuni esempi di TDA rilevanti

  • Diverse implementazioni, diversi livelli di astrazione (corrispondenti alla stessa structure, interfaccia)

  • Semantica algebrica, specifica astratta

  • Implementazione concreta



# module type PILA =

  • # module type PILA =

  • sig

  • type 'a stack

  • val emptystack : int * 'a -> 'a stack

  • val push : 'a * 'a stack -> 'a stack

  • val pop : 'a stack -> 'a stack

  • val top : 'a stack -> 'a

  • val empty : 'a stack -> bool

  • val lungh : 'a stack -> int

  • exception Emptystack

  • exception Fullstack

  • end



Commenti

  • emptystack prende come parametro un intero (la dimensione, il numero massimo di elementi memorizzabili) ed il tipo

  • push, pop, top, empty standard

  • lungh per avere il numero degli elementi, correntemente memorizzati

  • Emptystack,Fullstack eccezioni usate dal modulo



# module SemPila: PILA =

  • # module SemPila: PILA =

  • struct

  • type 'a stack = Empty of int | Push of 'a stack * 'a

  • exception Emptystack

  • exception Fullstack

  • let emptystack (n, x) = Empty(n)

  • let rec max = function

  • | Empty n -> n

  • | Push(p,a) -> max p

  • let rec lungh = function

  • | Empty n -> 0

  • | Push(p,a) -> 1 + lungh(p)

  • let push (a, p) = if lungh(p) = max(p) then raise Fullstack else Push(p,a)

  • let pop = function

  • | Push(p,a) -> p

  • | Empty n -> raise Emptystack

  • let top = function

  • | Push(p,a) -> a

  • | Empty n -> raise Emptystack

  • let empty = function

  • | Push(p,a) -> false

  • | Empty n -> true

  • end



semantica “isomorfa” ad una specifica in stile algebrico

  • semantica “isomorfa” ad una specifica in stile algebrico

    • trascuriamo i casi eccezionali
  • 'a stack = Empty of int | Push of 'a stack * 'a

  • emptystack (n, x) = Empty(n)

  • lungh(Empty n) = 0

  • lungh(Push(p,a)) = 1 + lungh(p)

  • push(a,p) = Push(p,a)

  • pop(Push(p,a)) = p

  • top(Push(p,a)) = a

  • empty(Empty n) = true

  • empty(Push(p,a)) = false

  • tipo (ricorsivo) definito per casi (con costruttori)

  • semantica delle operazioni definita da un insieme di equazioni fra termini

  • il metodo lungh fornisce il numero di valori memorizzati

  • il metodo max fornisce la dimensione massima (non fa parte dell’interfaccia, non e’ visibile da fuori)





# module ImpPila: PILA =

  • # module ImpPila: PILA =

  • struct

  • type 'a stack = Pila of ('a array) * int

  • exception Emptystack

  • exception Fullstack

  • let emptystack (nm,x) = Pila(Array.create nm x, -1)

  • let push(x, Pila(s,n)) = if n = (Array.length(s) - 1) then

  • raise Fullstack else

  • (Array.set s (n +1) x;

  • Pila(s, n +1))

  • let top(Pila(s,n)) = if n = -1 then raise Emptystack

  • else Array.get s n

  • let pop(Pila(s,n)) = if n = -1 then raise Emptystack

  • else Pila(s, n -1)

  • let empty(Pila(s,n)) = if n = -1 then true else false

  • let lungh(Pila(s,n)) = n

  • end



# module type LISTAINT =

  • # module type LISTAINT =

  • sig

  • type intlist

  • val emptylist : intlist

  • val cons : int * intlist -> intlist

  • val tail : intlist -> intlist

  • val head : intlist -> int

  • val empty : intlist -> bool

  • val length : intlist -> int

  • exception Emptylist

  • end



# module SemListaInt: LISTAINT =

  • # module SemListaInt: LISTAINT =

  • struct

  • type intlist = Empty | Cons of int * intlist

  • exception Emptylist

  • let emptylist = Empty

  • let rec length = function

  • | Empty -> 0

  • | Cons(n,l) -> 1 + length(l)

  • let cons (n, l) = Cons(n, l)

  • let tail = function

  • | Cons(n,l) -> l

  • | Empty -> raise Emptylist

  • let head = function

  • | Cons(n,l) -> n

  • | Empty -> raise Emptylist

  • let empty = function

  • | Cons(n,l) -> false

  • | Empty -> true

  • end



intlist = Empty | Cons of int * intlist

  • intlist = Empty | Cons of int * intlist

  • emptylist = Empty

  • length(Empty) = 0

  • length(Cons(n,l)) = 1 + length(l)

  • cons (n, l) = Cons(n, l)

  • tail(Cons(n,l)) = l

  • head(Cons(n,l)) = n

  • empty(Empty) = true

  • empty(Cons(n,l)) = false

  • 'a stack = Empty of int | Push of 'a stack * 'a

  • emptystack (n, x) = Empty(n)

  • lungh(Empty n) = 0

  • lungh(Push(p,a)) = 1 + lungh(p)

  • push(a,p) = Push(p,a)

  • pop(Push(p,a)) = p

  • top(Push(p,a)) = a

  • empty(Empty n) = true

  • empty(Push(p,a)) = false



non conviene implementare una lista con un array

  • non conviene implementare una lista con un array

    • vorremmo una implementazione sequenziale in cui un unico array viene utilizzato per rappresentare “tante” liste
    • la heap!
  • l’array unico va bene per la pila perché è un tipo di dato di sistema

    • ne esistono un numero piccolo e predefinito nella implementazione del linguaggio
  • la lista è tipicamente un tipo di dato d’utente

    • che ne può costruire un numero arbitrario nei propri programmi
  • mostriamo l’implementazione delle liste con una heap senza operazioni per “disallocare”





# module ImpListaInt: LISTAINT =

  • # module ImpListaInt: LISTAINT =

  • struct

  • type intlist = int

  • let heapsize = 100

  • let heads = Array.create heapsize 0

  • let tails = Array.create heapsize 0

  • let next = ref(0)

  • let emptyheap =

  • let index = ref(0) in

  • while !index < heapsize do

  • Array.set tails !index (!index + 1); index := !index + 1

  • done;

  • Array.set tails (heapsize - 1) (-1); next := 0

  • exception Fullheap

  • exception Emptylist

  • let emptylist = -1

  • let empty l = if l = -1 then true else false

  • let cons (n, l) = if !next = -1 then raise Fullheap else

  • ( let newpoint = !next in next := Array.get tails !next;

  • Array.set heads newpoint n; Array.set tails newpoint l; newpoint)

  • let tail l = if empty l then raise Emptylist else Array.get tails l

  • let head l = if empty l then raise Emptylist else Array.get heads l

  • let rec length l = if l = -1 then 0 else 1 + length (tail l)

  • end



tipo (polimorfo) utilizzato nella semantica e nelle implementazioni per mantenere una associazione fra stringhe (identificatori) e valori di un opportuno tipo

  • tipo (polimorfo) utilizzato nella semantica e nelle implementazioni per mantenere una associazione fra stringhe (identificatori) e valori di un opportuno tipo

  • la specifica definisce il tipo come funzione

  • l’implementazione che vedremo utilizza le liste

  • è simile il dominio store



# module type ENV =

  • # module type ENV =

  • sig

  • type 't env

  • val emptyenv : 't -> 't env

  • val bind : 't env * string * 't -> 't env

  • val bindlist : 't env * (string list) * ('t list)

  • -> 't env

  • val applyenv : 't env * string -> 't

  • exception WrongBindlist

  • end



# module Funenv:ENV =

  • # module Funenv:ENV =

  • struct

  • type 't env = string -> 't

  • exception WrongBindlist

  • let emptyenv(x) = function y -> x

  • let applyenv(x,y) = x y

  • let bind(r, l, e) =

  • function lu -> if lu = l then e else applyenv(r,lu)

  • let rec bindlist(r, il, el) = match (il,el) with

  • | ([],[]) -> r

  • | i::il1, e::el1 -> bindlist (bind(r, i, e), il1, el1)

  • | _ -> raise WrongBindlist

  • end



# module Listenv:ENV =

  • # module Listenv:ENV =

  • struct

  • type 't env = (string * 't) list

  • exception WrongBindlist

  • let emptyenv(x) = [("",x)]

  • let rec applyenv(x,y) = match x with

  • | [(_,e)] -> e

  • | (i1,e1) :: x1 -> if y = i1 then e1 else applyenv(x1, y)

  • | [] -> failwith("wrong env")

  • let bind(r, l, e) = (l,e) :: r

  • let rec bindlist(r, il, el) = match (il,el) with

  • | ([],[]) -> r

  • | i::il1, e::el1 -> bindlist (bind(r, i, e), il1, el1)

  • | _ -> raise WrongBindlist

  • end



a livello semantico, riconduciamo la modificabilità alla nozione di variabile

  • a livello semantico, riconduciamo la modificabilità alla nozione di variabile

    • lo stato “modificabile” corrispondente sarà in realtà modellato con il dominio store
  • per l’implementazione usiamo varie strutture dati modificabili come l’array



# module type MPILA =

  • # module type MPILA =

  • sig

  • type 'a stack

  • val emptystack : int * 'a -> 'a stack

  • val push : 'a * 'a stack -> unit

  • val pop : 'a stack -> unit

  • val top : 'a stack -> 'a

  • val empty : 'a stack -> bool

  • val lungh : 'a stack -> int

  • val svuota : 'a stack -> unit

  • val access : 'a stack * int -> 'a

  • exception Emptystack

  • exception Fullstack

  • exception Wrongaccess

  • end



# module SemMPila: MPILA =

  • # module SemMPila: MPILA =

  • struct

  • type 'a stack = ('a SemPila.stack) ref

  • exception Emptystack

  • exception Fullstack

  • exception Wrongaccess

  • let emptystack (n, a) = ref(SemPila.emptystack(n, a) )

  • let lungh x = SemPila.lungh(!x)

  • let push (a, p) = p := SemPila.push(a, !p)

  • let pop x = x := SemPila.pop(!x)

  • let top x = SemPila.top(!x)

  • let empty x = SemPila.empty !x

  • let rec svuota x = if empty(x) then () else (pop x; svuota x)

  • let rec faccess (x, n) =

  • if n = 0 then SemPila.top(x) else faccess(SemPila.pop(x), n-1)

  • let access (x, n) = let nofpops = lungh(x) - 1 - n in

  • if nofpops < 0 then raise Wrongaccess else faccess(!x, nofpops)

  • end



module ImpMPila: MPILA =

  • module ImpMPila: MPILA =

  • struct

  • type 'x stack = ('x array) * int ref

  • exception Emptystack

  • exception Fullstack

  • exception Wrongaccess

  • let emptystack(nm,(x: 'a)) = ((Array.create nm x, ref(-1)): 'a stack)

  • let push(x,((s,n): 'x stack)) = if !n = (Array.length(s) - 1) then

  • raise Fullstack else (Array.set s (!n +1) x; n := !n +1)

  • let top(((s,n): 'x stack)) = if !n = -1 then raise Emptystack

  • else Array.get s !n

  • let pop(((s,n): 'x stack)) = if !n = -1 then raise Emptystack

  • else n:= !n -1

  • let empty(((s,n): 'x stack)) = if !n = -1 then true else false

  • let lungh( (s,n): 'x stack) = !n

  • let svuota (((s,n): 'x stack)) = n := -1

  • let access (((s,n): 'x stack), k) =

  • (* if not(k > !n) then *)

  • Array.get s k

  • (* else raise Wrongaccess *)

  • end



la struttura dati fondamentale di LISP

  • la struttura dati fondamentale di LISP

    • alberi binari con atomi (stringhe) sulle foglie
    • modificabili
  • vedremo solo interfaccia e semantica

    • l’implementazione (a heap) simile a quella delle liste


# module type SEXPR =

  • # module type SEXPR =

  • sig

  • type sexpr

  • val nil : sexpr

  • val cons : sexpr * sexpr -> sexpr

  • val node : string -> sexpr

  • val car : sexpr -> sexpr

  • val cdr : sexpr -> sexpr

  • val null : sexpr -> bool

  • val atom : sexpr -> bool

  • val leaf : sexpr -> string

  • val rplaca: sexpr * sexpr -> unit

  • val rplacd: sexpr * sexpr -> unit

  • exception NotALeaf

  • exception NotACons

  • end



# module SemSexpr: SEXPR =

  • # module SemSexpr: SEXPR =

  • struct

  • type sexpr = Nil| Cons of (sexpr ref) * (sexpr ref)| Node of string

  • exception NotACons

  • exception NotALeaf

  • let nil = Nil

  • let cons (x, y) = Cons(ref(x), ref(y))

  • let node s = Node s

  • let car = function Cons(x,y) -> !x

  • | _ -> raise NotACons

  • let cdr = function Cons(x,y) -> !y

  • | _ -> raise NotACons

  • let leaf = function Node x -> x

  • | _ -> raise NotALeaf

  • let null = function Nil -> true

  • | _ -> false

  • let atom = function Cons(x,y) -> false

  • | _ -> true

  • let rplaca = function (Cons(x, y), z) -> x := z

  • | _ -> raise NotACons

  • let rplacd = function (Cons(x, y), z) -> y := z

  • | _ -> raise NotACons

  • end





Condividi con i tuoi amici:


©astratto.info 2019
invia messaggio

    Pagina principale