A.Natali DL Maggio1999 La costruzione del software Meccanismi, principi, concetti e metodologie.

A.Natali DL Maggio1999

La costruzione del software

Meccanismi, principi, concetti e metodologie


Il problema di fondo

Cosa caratterizza il passaggio dalla costruzione di un “algoritmo” alla costruzione di un “sistema software”?

Quali elementi permettono ad un progettista-sviluppatore di ottenere in modo sistematico non solo un sistema che “funzioni” ma che sia anche “fatto bene”?


Fatto bene?

Ben organizzato Modulare Riconfigurabile Flessibile Estendibile A componenti … ???


La costruzione del software

Ingredienti computazionali– le mosse di un linguaggio di programmazione

Requisiti– non basta un sistema che “funzioni”

Principi– regole per una buona organizzazione

Modelli, Concetti, Paradigmi, Pattern– fonti di ispirazione


Lo sviluppo storico

1950-1970 : – cosa significa computare?– quali mosse primitive deve avere un linguaggio

di programmazione? Secondo quale modello? 1970-1980 :

– quali principi di organizzazione del software?– perche’ la programmazione strutturata non

basta?


Lo sviluppo storico

1980-1990 :– perche’ il modello ad oggetti e’ importante?– vi sono alternative alla classificazione?

1990-2000 :– quali ripercussioni se la piattaforma computazionale

diventa una rete?– come recuperare vecchie applicazioni sulle nuove

piattaforme? ...


Modelli computazionali

Imperativo Funzionale Dichiarativo

A oggetti (?)


Gli ingredienti comuni 1

Valori Costanti (Riferimenti) Tipi di dato (scalari e strutturati)

Variabili (Puntatori) Binding e visibilita’ (scope)


Gli ingredienti comuni 2 Strutture di controllo

Comandi e procedure Funzioni

Moduli Classi


Elementi fondamentali

espressioni primitive

meccanismi di combinazione

meccanismi di astrazione


Cosa cambia?

Il modello del “collante”, cioe’ i meccanismi di combinazione ed astrazione

Modello funzionale:– elemento fondamentale: la funzione e l’espressione– meccanismo fondamentale: la “chiamata”

Modello logico:– elemento fondamentale: l’assioma– meccanismo fondamentale: la deduzione logica


Modello imperativo

Espressioni Comandi Dati Componenti

Entiprimitivi

valoriatomici

assegnamentochiamata afunzione

scalari dichiarazioniazioni

Combinatori operatori strutture dicontrollo

costruttoridi strutturedati

blocchiprocedurefunzionimoduli

Astrazioni funzioni procedure interfacceclassi

oggetti

– elemento fondamentale: il comando– meccanismi fondamentali:


Conteggio parole (da un testo famoso)

#include <stdio.h>

void main(){ char c; int nw = 0; int inw = 0; FILE* fp;

fp = fopen("testo.txt","rt");


Conteggio paroleif( fp == 0 ) exit(1); }while( (c=getc(fp) ) != EOF ) {

if( c==' ' || c=='\n' || c=='\t' )inw = 0;

else if( inw == 0 ){inw = 1;++nw;

}}

fclose( fp );printf("il file contiene %d parole\n", nw );}//main


Requisiti del software 1950-1970: Correttezza, Efficienza, Generalita’ 1970-1980: Strutturazione, Modularita’,

Incapsulamento (ADT), 1980-1990: Riusabilita’,

Estendibilita’, Genericita’, Incrementalita’

1990-2000: Distribuzione, Mobilita’ 2000- …: Interoperabilita’, ...


Linguaggi di programmazione

AN - 1995

Evoluzione dei linguaggi

19601950 1970 1980 1990 2000

Linguaggi-macchina

FORTRANLISP

LISP

LISP

LISP

ALGOL

SIMULA67

SMALLTALKPROLOG

ADA C++

APL

ALGOLCOBOL

PASCAL

FORTRAN77

C

1945PlanKalcul

VISICALC JAVA


Famiglie di linguaggi

Imperativi Applicativi Dichiarativi Ad oggetti

Ogni famiglia promuove uno specifico stile di progettazione e sviluppo del software


Efficienza : qualche slogan

Premature optimization is the root of all evil– Donald E. Knuth

Make it work first before you make it work fast– Bruce Whiteside

Make it fail-safe before you make it faster Make it clear before you make it faster

– Kernighan A. Plaugher


Principio generale 1

If you need a little speedup, work at the best level (which delivers the most speedup for the less effort)

– problem definition– system structure– algorithm tuning– data structure reorganization– code tuning– system software and hardware


Principio generale 2

If you need a big speedup, work at many levels– quando le modifiche ad un livello sono

indipendenti dai cambiamenti negli altri livelli, i miglioramenti di velocita’ si moltiplicano


Punti critici

The fastest IO is no IO– Nils Peter Nielson

In non IO bound programs a few percent of thje service code typically accounts for over half of the run time– Donald E. Knuth


Principi di ottimizzazione

Mantenere il progetto e l’ implementazione quanto piu’ possibile semplice

Salvare lo stato per evitare ricomputazioni Pre-calcolare e memorizzare soluzioni a

problemi che appaiono di frequente Applicare algoritmi divide-et-impera Sfruttare le identita’ algebriche Eliminare la ricorsione (non tail)


Ottimizzazione sui loop

Combinare in test Usare sentinelle Combinare loop sullo stesso range Rimuovere dal corpo espressioni invarianti


Esempio

Determinazione del massimo della somma dei valori su ogni possibile sotto vettore contiguo di un vettore dato che contiene almeno un valore positivo.

int v[]={ 31, -41, 59, 26, -55, 58, 99, -93, -23, 84 };

somma parziale= 187 per v[2]..v[6]


Andamento

0

50

100

150

200

1 2 3 4 5 6 7 8 9 10


La funzioni come componenti software

Fondamentali, ma non sufficienti


Funzioni

Le funzioni sono costrutti che permettono di attribuire un nome ad una espressione e renderla parametrica.

float f(){ 2 + 3 * sin(0.75); }

float f1( int x) { 2 + x * sin(0.75); }


Funzioni: trasparenza referenziale

f(x) + g( f(x), q( x + f(y))) f,g,q sono simboli che denotano funzioni; il simbolo x denota un valore; qualunque sia il valore denotato da x, x

denota sempre lo stesso valore in ogni punto in cui compare nell’espressione;

l’espressione f(x) denota sempre lo stesso valore in ogni punto in cui compare nell’espressione.


Funzioni: signature

L’interfaccia di una funzione e’ costituita dal suo nome, dalla lista degli argomenti e dal tipo del valore restituito (signature).

tipo nome ( args )


Funzioni: Corpo

Il corpo costituisce la struttura interna di una funzione, completamente inaccessibile dall’esterno – garantendo protezione

dell’informazione secondo il principio del suo “nascondimento” (information hiding)


Funzioni: Comunicazione

La comunicazione di informazione tra un cliente e una funzione avviene – da cliente a funzione: con gli argomenti

di ingresso– da funzione a cliente: con il valore di

ritorno

tipo nome ( args )


Il modello cliente-servitore

Cliente

Servitore

Ambiente condiviso

informazione

controllo


Clienti e servitori

Servitore– un qualunque ente computazionale

capace di nascondere la propria organizzazione interna, presentando ai clienti una precisa interfaccia per lo scambio di informazione.

Cliente– qualunque ente in grado di invocare uno

o piu' servitori per svolgere il proprio compito.


Comunicazione

La comunicazione di informazione tra un cliente e un servitore puo' avvenire in modo esplicito tramite le interfacce stabilite dal servitore oppure in modo implicito tramite aree-dati accessibili ad entrambi.


Servitore Puo’ essere passivo o attivo puo' servire un cliente alla volta, in sequenza,

oppure piu' clienti per volta, in parallelo. servire molti clienti oppure costituire la

risorsa privata di uno specifico cliente.

puo’ a sua volta trasformarsi in cliente, invocando altri servitori o anche se' stesso.

Servitore


Funzione come servitore

Passivo Rientrante Privato o condiviso Di se’ stesso quando ricorsiva


Meccanismi per il trasferimento di argomenti

per valore per indirizzo per riferimento

per valore-risultato per nome ...


Funzioni?

void sqr( int* v){ *v = *v * *v;

}//sqr

int x=3; int const y=5;sqr( &x ); sqr( &y );

Warning: passing arg 1 of `sqr' discards `const' from pointer target


Funzioni?

void sqr( int& v){ //C++v = v * v; //dereferenziamento automatico

}//sqr

int x=3; int const y=5;sqr( x ); sqr( y );


Valori, costanti e variabili

#define x 3

int const x=3;

int x = 3;

x sinonimo di 3non ha lvalue

x variabile che nonmodifica il suo valore

puo’ avere un lvalue

x variabile (contenitore)


Comandi

notazioni che esprimono azioni che, una volta eseguite, comportano una modifica permanente dello stato interno del programma o quello del mondo circostante. – Le strutture di controllo (if,-then-else, while-do, for, repeat-unitl, switch, etc.) permettono di aggregare comandi semplici in macrocomandi


Procedure (vs. funzioni)

costrutti che permettono di attribuire un nome ad un macrocomando e renderlo parametrico

if( x % 2 == 0 ) printf(“x= %d pari \n” );else printf(“x= %d dispari \n” );

void viewEvenOdd( int x ){if(x % 2 == 0) printf(“x= %d pari \

n”,x );else printf(“x= %d dispari \n”,x );

}


ContaParoleNew: una funzioneint contaParole( FILE* fp ){ char c; int nw = 0; int inw = 0; if( fp == 0 ) { return -1; }

while( (c=getc(fp) ) != EOF ) {if( c==' ' || c=='\n' || c=='\t' )

inw = 0;else if( inw == 0 ){

inw = 1; ++nw; }}

return nw;}//contaParole


ContaParoleNew: il mainvoid main(){ FILE* fp; int nw=10; char fName[80]; int a=10;

printf("nome del file: "); gets( fName );fp = fopen(fName ,"rt");nw = contaParole( fp );

fclose( fp ); if( nw >= 0 )

printf("il file contiene %d parole\n", nw );else printf("errore nell'accesso al file \n" );

}//main


Lo stile funzionale

La funzione contaParole realizza un algoritmo

Utilizza variabili locali non visibili all’esterno

Stabilisce un contratto con i clienti Non deve avere effetti collaterali (nemmeno

sul file di ingresso)


Riusabilita’

La funzione contaParole delega al chiamante il compito di aprire-chiudere il file

Protocollo d’uso:fp = fopen(fName ,"rt");

nw = contaParole ( fp );fclose( fp );

Impedisce la composizione in espressioni:contaParole(fp)+contaParole(fp);


Una funzione piu’ riusabileint contaParole( char* fName ){ char c; int nw = 0; int inw = 0; FILE* fp;

fp = fopen( fName ); if( fp == 0 ) return -1;

while( (c=getc(fp) ) != EOF ) {if( c==' ' || c=='\n' || c=='\t' )

inw = 0;else if( inw == 0 ){

inw = 1; ++nw; }}fclose( fp );

return nw;}//contaParole


Trasparenza referenziale e riusovoid main(){ FILE* fp; int nw=10; char s[80]; int a=10;

printf("nome del file: "); gets( fName );nw = contaParole( s );

if( nw >= 0 ) printf(”vi sono %d parole == %d", nw,

contaParole( s ) );else printf("errore nell'accesso al file \n" );

}//main


La funzione come servitore

La funzione contaParole e’ un servitore passivo,

che serve un cliente per volta, che puo’ trasformarsi in cliente,

(anche di se’ stessa).


Ricorsione e iterazioneint inw = 0;

int numParole( char* fName ){FILE* fp;int nw = 0; inw = 0;

fp = fopen( fName, "rt" );nw = numParoleRic( fp, 0 );fclose( fp );

return nw;}//numParole

Questa funzione1) inizializza la variabile di stato inw.2) apre il file3) invoca un algoritmo di conteggio4) chiude il file


Versione ricorsivaint numParoleRic( FILE* fp, int nw ){char c; if( fp == 0 ) return -1;

if( (c=getc(fp) ) == EOF ) return nw; if( c==' ' || c=='\n' || c=='\t' )

inw = 0; else if( inw == 0 ){

inw = 1; ++nw; }

return numParoleRic(fp,nw);}//numParoleRic

Questa funzionepercorre in modoricorsivo il fileusando il parametro nwcome accumulatoredel risultato


Non basta che funzioni

L’introduzione della variabile globale inw viola i principi di localita’ e di information hiding

Sostituirla con una variabile static entro numParole non e’ possibile perche’ inw deve essere visibile anche da numParoleRic

Concettualmente, inw e’ una variabile di stato, analoga a nw.


Argomenti come statoint numeroParole( char* fName ){int nw;FILE* fp;

fp = fopen( fName, "rt" );nw = contaNumeroParole(fp, 0, 0);fclose( fp );

return nw;}//numeroParole


La versione ricorsiva appropriataint contaNumeroParole( FILE* fp,

int nw, int inw ){char c; if( fp == 0 ) return -1; if( (c=getc(fp) )==EOF) return nw; if(c==' ' || c=='\n' || c=='\t')

return contaNumeroParole(fp,nw,0); if( inw == 0 )

return contaNumeroParole(fp,++nw,1); else

return contaNumeroParole(fp,nw,inw);}//contaNumeroParole


Dal codice al progetto

Reverse engineering


Il ragionamento

nw – numero corrente di parole contate

inw – se 1 denota lo stato “entro una parola”– se 0 denota lo stato “fuori da una parola”

Se il file non esiste, restituisci -1; Se EOF, restituisci il valore corrente di nw;


Il ragionamento Se il primo carattere sul file e’ un separatore di

parole, allora il risultato e’ dato dalla iterazione del procedimento sul resto del file con inw=0 e nw inalterato;

Se il primo carattere sul file appartiene ad una parola, allora il risultato e’ fornito: – se inw==0, dalla iterazione del procedimento sul

resto del file con inw=1 e nw incrementato di 1;– se inw==1, dalla iterazione del procedimento sul

resto del file con inw=1 e nw inalterato;


Una rilflessione

Dati– conviene siano impostati come oggetti

appartenenti a precisi tipi (astratti)

Elaborazione– conviene sia chiaro quale modello o pattern

realizzano


Il conteggio delle parole

Dati del dominio– Contatore– File (e’ gia’ un ADT realizzato dal sistema)– Parola (non formalmente espressa)

Elaborazione– Realizza un automa a stati finiti


END

ASF del conteggio parole

START

SKIPSeparatore

EOF

FIRSTCarattere parola

INW

Separatore

Carattere parola

Carattere parola

Separatore

EOF

Nello statoFIRSTsi incrementadi 1 il contatore di parole (nw)

EOF

EOF


Analisi del codice

int contaParole( char* fName ){

//VARIABILI DI COMODO char c; FILE* fp;

//VARIABILI DI USCITA int nw = 0; //contatore //VARIABILI DI STATO int inw = 0;


Analisi del codice

//ACQUISIZIONE DEGLI INGRESSIwhile( (c=getc(fp) ) != EOF ) {

//TRANSIZIONI DI STATO (ASF DI MOORE)if( c==' ' || c=='\n' || c=='\t' )

inw = 0;else if( inw == 0 ) {

inw = 1; ++nw; }}


Realizzazione sistematica di un ASF1. La transizione di stato e’ espressa

(implicitamente) dal flusso di controllo2. Lo stato e’ rappresentato in modo esplicito

da variabili e la transizione di stato e’ espressa mediante if o switch

3. Ogni nodo del grafo e’ rappresentato da una procedura (funzione). La transizione di stato e’ espressa mediante invocazione di funzione

4. L’ASF e’ rappresentato da una matrice di transizione


Versioni dell’ASF di conteggio-parole

1. Transizioni di stato realizzate dal flusso di controlloint contaParoleASFControllo( char* fName ){ 2.Variabili esplicite di stato e transizioni con switchint contaParoleASFSwitch( char* fName ){

3. Stati mappati in procedure int contaParoleASFStatiFunzione( char* fName ){

3. Matrice di transizioneint contaParoleASFMatrice( char* fName ){


Valutazione della soluzione

Il problema del conteggio delle parole contenute in un file e’ stato risolto senza introdurre alcun oggetto di tipo parola, ma solo il concetto di separatore di parole.

La soluzione e’ – semplice ed efficiente– non molto comprensibile, non modulare, poco

riusabile e difficilmente estendibile


Quali alternative?

E’ possibile impostare il problema in modo diverso, in modo da ottenere una soluzione ancora ragionevolmente efficiente, ma piu’ modulare, riusabile ed estendibile?

A.Natali DL Maggio1999 La costruzione del software Meccanismi, principi, concetti e metodologie.

Documents

Transcript of A.Natali DL Maggio1999 La costruzione del software Meccanismi, principi, concetti e metodologie.