A.Natali DL Maggio1999

La costruzione del software

Meccanismi, principi, concetti e metodologie

A.Natali DL Maggio1999

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”?

A.Natali DL Maggio1999

Fatto bene?

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

A.Natali DL Maggio1999

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

A.Natali DL Maggio1999

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?

A.Natali DL Maggio1999

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? ...

A.Natali DL Maggio1999

Modelli computazionali

Imperativo Funzionale Dichiarativo

A oggetti (?)

A.Natali DL Maggio1999

Gli ingredienti comuni 1

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

Variabili (Puntatori) Binding e visibilita’ (scope)

A.Natali DL Maggio1999

Gli ingredienti comuni 2 Strutture di controllo

Comandi e procedure Funzioni

Moduli Classi

A.Natali DL Maggio1999

Elementi fondamentali

espressioni primitive

meccanismi di combinazione

meccanismi di astrazione

A.Natali DL Maggio1999

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

A.Natali DL Maggio1999

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:

A.Natali DL Maggio1999

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");

A.Natali DL Maggio1999

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

A.Natali DL Maggio1999

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’, ...

A.Natali DL Maggio1999

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

A.Natali DL Maggio1999

Famiglie di linguaggi

Imperativi Applicativi Dichiarativi Ad oggetti

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

A.Natali DL Maggio1999

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

A.Natali DL Maggio1999

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

A.Natali DL Maggio1999

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

A.Natali DL Maggio1999

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

A.Natali DL Maggio1999

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)

A.Natali DL Maggio1999

Ottimizzazione sui loop

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

A.Natali DL Maggio1999

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]

A.Natali DL Maggio1999

Andamento

0

50

100

150

200

1 2 3 4 5 6 7 8 9 10

A.Natali DL Maggio1999

La funzioni come componenti software

Fondamentali, ma non sufficienti

A.Natali DL Maggio1999

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); }

A.Natali DL Maggio1999

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.

A.Natali DL Maggio1999

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 )

A.Natali DL Maggio1999

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)

A.Natali DL Maggio1999

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 )

A.Natali DL Maggio1999

Il modello cliente-servitore

Cliente

Servitore

Ambiente condiviso

informazione

controllo

A.Natali DL Maggio1999

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.

A.Natali DL Maggio1999

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.

A.Natali DL Maggio1999

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

A.Natali DL Maggio1999

Funzione come servitore

Passivo Rientrante Privato o condiviso Di se’ stesso quando ricorsiva

A.Natali DL Maggio1999

Meccanismi per il trasferimento di argomenti

per valore per indirizzo per riferimento

per valore-risultato per nome ...

A.Natali DL Maggio1999

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

A.Natali DL Maggio1999

Funzioni?

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

}//sqr

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

A.Natali DL Maggio1999

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)

A.Natali DL Maggio1999

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

A.Natali DL Maggio1999

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 );

}

A.Natali DL Maggio1999

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

A.Natali DL Maggio1999

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

A.Natali DL Maggio1999

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)

A.Natali DL Maggio1999

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);

A.Natali DL Maggio1999

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

A.Natali DL Maggio1999

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

A.Natali DL Maggio1999

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).

A.Natali DL Maggio1999

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

A.Natali DL Maggio1999

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

A.Natali DL Maggio1999

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.

A.Natali DL Maggio1999

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

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

return nw;}//numeroParole

A.Natali DL Maggio1999

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

A.Natali DL Maggio1999

Dal codice al progetto

Reverse engineering

A.Natali DL Maggio1999

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;

A.Natali DL Maggio1999

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;

A.Natali DL Maggio1999

Una rilflessione

Dati– conviene siano impostati come oggetti

appartenenti a precisi tipi (astratti)

Elaborazione– conviene sia chiaro quale modello o pattern

realizzano

A.Natali DL Maggio1999

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

A.Natali DL Maggio1999

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

A.Natali DL Maggio1999

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;

A.Natali DL Maggio1999

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; }}

A.Natali DL Maggio1999

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

A.Natali DL Maggio1999

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 ){

A.Natali DL Maggio1999

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

A.Natali DL Maggio1999

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?