Esercizio: punti e segmenti
! Punti e segmenti nel piano,
con data abstraction
Carlo Strapparava - Informatica
Esercizio: punti e segmenti
! Punti e segmenti nel piano,
con data abstraction
! Lunghezza di un segmento
l = (x 2 " x1 ) 2 + (y 2 " y1 ) 2
y2
! Data abstraction:
! Segmento
!
y1
"
"
Costruttore
make-seg pt1 pt2
Selettori
start-point seg
end-point seg
! Punto
"
x1
x2
"
Costruttore
make-point x y
Selettori
x-coor point
y-coor point Carlo Strapparava - Informatica
1
Esercizio: punti e segmenti
(define (segment-length segment)
(let ((dx (- (x-coord (end-point segment))
(x-coord (start-point segment))))
(dy (- (y-coord (end-point segment))
(y-coord (start-point segment)))))
(sqrt (+ (square dx) (square dy)))))
Implementazione segmento
Implementazione punto (coordinate rettangolari)
(define (make-seg pt1 pt2)
(cons pt1 pt2))
(define (make-point x y)
(cons x y))
(define (start-point seg)
(car seg))
(define (x-coor point)
(car point))
(define (end-point seg)
(cdr seg))
(define (y-coor point)
(cdr point))
Carlo Strapparava - Informatica
Esercizio: punti e segmenti
! Cambiamo la rappresentazione dei punti e usiamo la
rappresentazione polare p=(r,!)
! I programmi di alto livello (es. segment-length) non
cambiano: usano costruttori e selettori con gli stessi nomi
x = r cos"
y = r sin "
(define (make-point r ang)
(cons r ang))
r
!
!
(define (x-coor p)
(* (car p) (cos (cdr p))))
(define (y-coor p)
(* (car p) (sin (cdr p))))
Carlo Strapparava - Informatica
2
Che cosa intendiamo per “dati” ?
! I dati sono definiti da una collezione di
costruttori e selettori, insieme a specifiche
condizioni che queste procedure devono
soddisfare
! Data abstraction interviene a tutti i livelli
! Es. Non abbiamo mai detto cosa sia una
coppia, ma soltanto che avevamo le
procedure cons, car e cdr per operare sulle
coppie
Carlo Strapparava - Informatica
Che cosa intendiamo per “dati” ?
! Riguardo le coppie, l’unica cosa che ci
interessa sapere è che
(car (cons x y)) => x
(cdr (cons x y)) => y
! cons, car, e cdr sono primitive nello
Scheme
! Tuttavia qualunque tripla di procedure che
soddisfa le precedenti condizioni, può essere
usata per implementare le coppie
Carlo Strapparava - Informatica
3
Che cosa intendiamo per “dati” ?
! Per esempio, possiamo implementare le
coppie, senza usare nessuna struttura dati,
ma soltanto le procedure
(define (cons x y)
(lambda (pick)
(cond ((= pick 1) x)
((= pick 2) y)
(else (error "L'argomento non e' ne' 1 ne' 2”))))
)
(define (car z) (z 1))
(define (cdr z) (z 2))
Carlo Strapparava - Informatica
Che cosa intendiamo per “dati” ?
(define (cons x y)
(lambda (pick)
(cond ((= pick 1) x)
((= pick 2) y)
(else (error "L'argomento non e' ne' 1 ne' 2”))))
)
(define (car z) (z 1))
(define (cdr z) (z 2))
(cons 6 9) => (lambda (pick)
(cond ((= pick 1) 6)
((= pick 2) 9)
(else (error "L'argomento non e' ne' 1 ne' 2”))))
Carlo Strapparava - Informatica
4
Cons, car, cdr in versione procedurale
! Esiste una versione ancora più elegante di
implementare le coppie “proceduralmente”
(define (cons x y)
(lambda (m) (m x y)))
(define (car z)
(z (lambda (p q) p)))
Esercizio: verificare
che funzionano con il
modello di sostituzione
(define (cdr z)
(z (lambda (p q) q)))
Carlo Strapparava - Informatica
Che cosa intendiamo per “dati” ?
! L’uso di queste procedure appena viste è quanto di
!
!
!
!
più lontano ci sia dalla nostra intuizione di dato
Tuttavia possiamo verificare che soddisfano le
condizioni date per cons, car e cdr
Se usiamo queste procedure, esse sono indistinguibili
da quelle che usano strutture dati “reali”
La rappresentazione procedurale dei dati gioca un
ruolo fondamentale nelle techniche di
programmazione avanzata, come l’object-oriented
In particolare quanto visto prima, è un esempio di
object-oriented di stile message-passing
Carlo Strapparava - Informatica
5
Visualizzare le coppie
! Abbiamo visto che le coppie (pairs)
costituiscono una sorta di “colla” per costruire
oggetti composti complessi
! La notazione “standard” per visualizzare le
coppie - ad es. (cons 1 2) - è chiamata
notazione box-and-pointer
2
(cons 1 2)
1
(car (cons 1 2))
" 1
(cdr (cons 1 2))
" 2
Carlo Strapparava - Informatica
Dati gerarchici e proprietà di chiusura
! Abbiamo visto che cons può essere usato per
combinare coppie
! Le coppie costituiscono una sorta di mattone
universale per costruire ogni sorta di strutture
dati
(cons (cons 1 2)
(cons 3 4))
3 4
1 2
Carlo Strapparava - Informatica
6
Dati gerarchici e proprietà di chiusura
4
(cons (cons 1 (cons 2 3))
4))
1
2 3
! La capacità di creare coppie i cui elementi sono altre
coppie è l’essenza dell’importanza della struttura a
lista
! Questa capacità si chiama proprietà di chiusura del
cons
! cons può prendere coppie in input e produce coppie
in output
Carlo Strapparava - Informatica
Proprietà di chiusura
! La parola “chiusura” viene dall’algebra
astratta
! Un insieme di elementi si dice chiuso secondo
una certa operazione, se applicando
l’operazione agli elementi dell’insieme, si
ottengono elementi che appartengono ancora
all’insieme
Carlo Strapparava - Informatica
7
Proprietà di chiusura
! La proprietà di chiusura ci permette di creare
!
!
!
!
strutture gerarchiche
Strutture gerarchiche: strutture composte di
parti che a loro volta sono composte di parti
ecc…
Le procedure composte sono ancora procedure
I dati composti sono ancora dati
Vedremo alcune tecniche standard per
rappresentare sequenze (liste) e alberi, usando
le coppie
Carlo Strapparava - Informatica
Rappresentare le sequenze (liste)
! Una sequenza è una collezione ordinata di
oggetti
! Un modo semplice di rappresentare le
sequenze in termini di coppie è usando una
catena di coppie
(cons 1
(cons 2
(cons 3
(cons 4 nil))))
1
2
3
4
Carlo Strapparava - Informatica
8
Rappresentare le sequenze (liste)
! Il car di ciascuna coppia corrisponde ad un
elemento della catena
! Il cdr di una coppia è la coppia successiva
nella catena
! Il cdr della coppia finale segnala la fine della
catena:
"
"
"
nella rappresentazione box-and-pointer è indicato
come un barra /
nei programmi con la variabile nil
nil può essere pensato come la sequanza di
nessun elemento (cioè la lista vuota)
Carlo Strapparava - Informatica
Liste
! Lo Scheme fornisce una procedura primitiva list che è
il costruttore delle liste
! La lista vista prima può essere costruita con
(list 1 2 3 4)
! In generale
(list <el1> <el2> … <eln>)
! È equivalente a
(cons <el1> (cons <el2> (cons … (cons <eln> nil)…)))
! (list) ritorna la lista vuota: (define nil (list))
! I sistemi Scheme stampano le liste come sequenze di
elementi
(list 1 2 3 4)
" (1 2 3 4)
Carlo Strapparava - Informatica
9
Operazioni sulle liste
! Tramite car e cdr possiamo scrivere
!
procedure che manipolano le liste
Per esempio, scriviamo una procedura
list-ref che prende due argomenti:
1.
2.
una lista
un numero n
! e ritorna l’ n-esimo elemento della lista
! Il primo elemento è in posizione 0
Carlo Strapparava - Informatica
Operazioni sulle liste
(define (list-ref items n)
(if (= n 0)
(car items) ;per n=0 torna il car della lista
(list-ref (cdr items) (- n 1))))
;altrimenti torna l’ (n-1) esimo elemento del cdr della lista
3
2
1
0
(define lista-quadrati (list 1 4 9 16 25))
(list-ref lista-quadrati 3)
"16
Carlo Strapparava - Informatica
10
Operazioni sulle liste
! Spesso dobbiamo scandire la lista tramite il
cdr
! Lo Scheme fornisce una procedura primitiva
null? che testa se il suo argomento è la lista
vuota
(null? nil)
" #t
(null? (list 1 2))
" #f
Carlo Strapparava - Informatica
Esempio: lunghezza di una lista
(define (length items)
(if (null? items)
0 ;la lunghezza della lista vuota è 0
(+ 1 (length (cdr items)))))
;altrimenti la lunghezza è 1 più la lunghezza del cdr
(define dispari (list 1 3 5 7))
(length dispari)
" 4
Carlo Strapparava - Informatica
11
Esempio: lunghezza di una lista
! Riconosciamo nella definizione di length il
classico piano dell’induzione
"
"
la lunghezza della lista vuota è 0
la lunghezza di una lista è 1 più la lunghezza del cdr
della lista
! Possiamo anche definire length in stile iterativo
(define (length items)
(define (length-iter a count)
(if (null? a)
count
(length-iter (cdr a) (+ 1 count))))
(length-iter items 0))
Carlo Strapparava - Informatica
Esempio: append
! Un’altra tecnica comune è quello di costruire
nuove liste con una successione di cons
! Es. La procedura append prende due liste
come argomenti, e da queste forma una
nuova lista
(append lista-quadrati dispari)
" (1 4 9 16 25 1 3 5 7)
(append dispari lista-quadrati)
" (1 3 5 7 1 4 9 16 25)
Carlo Strapparava - Informatica
12
Esempio: append
! Per implementare append usiamo ancora un
piano ricorsivo:
! Fai append di list1 list2
"
"
se list1 è la lista vuota, allora il risultato è list2
altrimenti, fai append del cdr di list1 con list2,
e fai cons del car di list1 con questo risultato
(define (append list1 list2)
(if (null? list1)
list2
(cons (car list1) (append (cdr list1) list2))))
Carlo Strapparava - Informatica
Esercizi:last-pair e reverse
(define (last-pair list) ;restituisce
(if (null? (cdr list))
list
(last-pair (cdr list))))
l’ultimo pair di una lista
(define (reverse items)
(if (null? items)
nil
(append (reverse (cdr items)) (list (car items)))))
(define (reverse items) ;reverse in versione iterativa
(define (rev-iter items acc)
(if (null? items)
acc
(rev-iter (cdr items) (cons (car items) acc))))
(rev-iter items nil))
Carlo Strapparava - Informatica
13