Date post: | 01-May-2015 |
Category: |
Documents |
Upload: | gaetano-parodi |
View: | 216 times |
Download: | 3 times |
1
Metodologie di Programmazione = decomposizione basata su astrazioni
2
Vari programmi possono risolvere lo stesso problema
Efficienti (Algoritmi) Ben Strutturati:
1. Facili da capire e su cui ragionare (per esempio per convincersi della loro correttezza)
2. Facili da mantenere e da modificare (per esempio che ammettono modifiche locali e che siano estendibili)
Questi aspetti sono spesso in contrasto tra loro, e’ necessario un compromesso
Esistono delle tecniche da seguire per strutturare in modo efficace un programma?
3
Osservazione di partenza…
quando si devono sviluppare programmi abbastanza grandi e’ necessario decomporre in moduli
i moduli risolvono sotto-problemi piu’ semplici i moduli che risolvono i sotto-problemi devono riuscire a cooperare nella
soluzione del problema originale
moduli il piu’ possibile indipendenti le interazioni tra i moduli che risolvono il problema devono
essere chiare e facili da capire
4
Importanza dei “moduli” persone diverse possono/devono essere coinvolte
si deve poter lavorare in modo indipendente (ma coerente) nello sviluppo dei diversi moduli
deve essere possibile eseguire “facilmente” (da parte di persone diverse da quelle coinvolte nello sviluppo) modifiche e aggiornamenti (manutenzione)
• a livello dei singoli moduli, senza influenzare il comportamento degli altri
5
Processo di Sviluppo: decomposizione e astrazione
la decomposizione può essere effettuata in modo produttivo ricorrendo all’astrazione
cambiamento del livello di dettaglio, nella descrizione di un problema, limitandosi a “considerare” solo alcune delle sue caratteristiche
• cose che sono diverse diventano uguali Si puo’ semplificare l’analisi, separando gli attributi che si
ritengono rilevanti da quelli che si ritiene possano essere trascurati
si passa ad un problema più semplice• su questo si effettua la decomposizione in sotto-problemi
6
Astrazione
noi studieremo alcuni meccanismi di astrazione legati alla programmazione, quelli presenti nei linguaggi ad alto livello (in particolare Java)
come utilizzare i meccanismi di astrazione per sviluppare programmi di buona qualita’ (in base alle caratteristiche dette in precedenza)
7
Presenteremo un insieme di tecniche basate su vari tipi di astrazione
alcune supportate da Java in modo più o meno diretto
la più importante non è supportata da Java
•l’astrazione attraverso la specifica
•invece di (o in aggiunta a) codice Java
–specifiche informali (semantica intesa dei programmi)
8
Il più comune tipo di astrazione l’astrazione procedurale
presente in tutti i linguaggi di programmazione la separazione tra “definizione” e “chiamata” rende
disponibili nel linguaggio i due meccanismi fondamentali di astrazione
l’astrazione attraverso parametrizzazione l’astrazione attraverso specifica
9
Astrazione via parametrizzazione l’introduzione dei parametri permette di descrivere un
insieme (anche infinito) di computazioni diverse con un singolo programma che le astrae tutte
x * x + y * y descrive una computazione
x,y:int.(x * x + y * y) descrive tutte le computazioni che si possono ottenere
chiamando la procedura, cioè applicando la funzione ad una opportuna n-upla di valori
x,y:int.(x * x + y * y)(w,z) ha la stessa semantica dell’espressione w * w + z * z
10
Astrazione via specificaastrarre dalla specifica computazione descritta nel
corpo della procedura, associando ad ogni procedura una specifica
semantica intesa della procedura (cosa fa e non come la fa)
la specifica deve contenere tutte le informazioni necessarie a chi usa la procedura, e’ di fatto l’interfaccia con l’esterno
chi utilizza la procedura vede cosa fa (la specifica) e non come lo fa (l’implementazione)
11
Vantaggi Se la specifica e l’implementazione sono progettati in
modo opportuno, ovvero sono chiaramente separate e l’implementazione e’ invisibile a chi usa la procedura
si rende la procedura indipendente dai moduli che la usano
1. l’implementazione per esempio puo’ essere cambiata, estesa
12
Astrazione via specifica
non è di solito supportata dal linguaggio di programmazione se non in parte (vedi specifiche di tipo)
si realizza con specifiche semi-formali sintatticamente, commenti tipo quelli che abbiamo usato a LIP
13
Un esempio
public static int search (int[] a, int x) // EFFECTS: se x occorre in a,ritorna un
// indice in cui occorre, altrimenti -1
{if{ if (a==null) return -1; for (int i=0; i < a.length; i++) {if (a[i]==x return i;} return -1;}
postcondizione (asserzione effects)tutto ciò che possiamo assumere valere quando la chiamata di procedura termina
14
Il punto di vista di chi usa la procedura
gli utenti della procedura vedono “solo” la specifica
gli utenti della procedura non possono osservare le computazioni descritte dal corpo e dedurre da questo proprietà diverse da quelle specificate dalle asserzioni
astraendo dal corpo (implementazione), si “dimentica” informazione evidentemente considerata non rilevante
Per esempio che ritorna il primo indice in cui x occorre
public static int search (int[] a, int x) // EFFECTS: se x occorre in a,ritorna un
// indice in cui occorre, altrimenti -1
15
Un’ altra implementazione
public static int search (int[] a, int x) // EFFECTS: se x occorre in a,ritorna un
// indice in cui occorre, altrimenti -1
{if{ if (a==null) return -1; for (int i=a.length-1; i <= 0; i--) {if (a[i]==x return i;} return -1;}
Dal punto di vista dell’utente non c’e’ differenza tra le due implementazioni (vede solo la specifica che e’ la stessa)
entrambe soddisfano la stessa specifica, anche se possono dare risultati diversi
16
Cosa vedremo:come utilizzare l’astrazione tramite specifica in modo
corretto (separazione tra specifica ed implementazione) relazione tra specifica ed implementazione:
l’implementazione deve soddisfare la specifica (di fatto una dimostrazione di correttezza)
vedremo come utilizzare la specifica per ogni meccanismo di astrazione supportato da Java
Daremo per ogni meccanismo la relativa sequenza di operazioni di: specifica, implementazione e dimostrazione
17
Tipi di astrazione
astrazione procedurale• si aggiungono nuove operazioni a quelle della macchina astratta del
linguaggio di programmazione astrazione di dati
• si aggiungono nuovi tipi di dato a quelli della macchina astratta del linguaggio di programmazione
iterazione astratta• permette di iterare su elementi di una collezione, senza sapere come
questi vengono ottenuti gerarchie di tipo
• permette di astrarre da specifici tipi di dato a famiglie di tipi correlati
18
Astrazione procedurale fornita da tutti i linguaggi ad alto livello
aggiunge nuove operazioni a quelle della macchina astratta del linguaggio di programmazione
per esempio, sqrt sui float
la specifica descrive le proprietà della nuova operazione
19
Astrazione sui dati fornita da tutti i linguaggi ad alto livello moderni
aggiunge nuovi tipi di dato e relative operazioni a quelli della macchina astratta del linguaggio
tipo Insieme con le operazioni vuoto, inserisci, rimuovi, e dimensione
La specifica descrive il tipo di dato e le proprieta’ delle operazioni
L’implementazione richiede di dare: la rappresentazione dei valori di tipo MultiInsieme e la realizzazione delle operazioni
l’implementazione deve essere invisibile all’utente che deve fare solo riferimento alle proprietà presenti nella specifica
la specifica descrive le relazioni fra le varie operazioni per questo, è cosa diversa da un insieme di astrazioni procedurali
20
Iterazione astrattanon è fornita da nessun linguaggio di uso comune
può essere simulata (per esempio, in Java)
permette di iterare su elementi di una collezione, senza sapere come questi vengono ottenuti
evita di dire cose troppo dettagliate sul flusso di controllo all’interno di un ciclo
per esempio, potremmo iterare su tutti gli elementi di un Insieme senza imporre nessun vincolo sull’ordine con cui vengono elaborati
astrae (nasconde) il flusso di controllo nei cicli
21
Gerarchie di tipo fornite da alcuni linguaggi ad alto livello moderni
per esempio, Java (ereditarieta’)
L’ereditarieta’ permette di definire nel supertipo
tutte le operazioni, comuni ai sottotipi
Il supertipo astrae i dettagli che rendono diversi tra loro i vari sottotipi
Meccanismo fondamentale per avere codice compatto, per fattorizzare le informazioni comuni, estendere etc..
Relazione tra le specifiche del sottotipo e del supertipo