Post on 01-May-2015
AN FI 98-99 Un denominatoe comune
Lo stile funzionale
Concetti fondamentali
AN FI 98-99 Un denominatoe comune
Concetti comuni
Dati primitivi e tipi di dato Espressioni e Comandi Funzioni e Procedure Variabili Riferimenti Strutture di dati
AN FI 98-99 Un denominatoe comune
Dati
Un elaboratore di informazione e' un manipolatore di segni
L'architettura fisica di ogni elaboratore moderno e' intrinsecamente capace di trattare vari domini di dati, detti tipi primitivi
AN FI 98-99 Un denominatoe comune
Tipi di dato
Questo concetto viene introdotto per raggiungere due obiettivi:– esprimere in modo sintetico un insieme
di valori, la loro rappresentazione in memoria e un insieme di operazioni ammissibili;
– permettere di effettuare controlli statici (al momento della compilazione) di correttezza sul programma.
AN FI 98-99 Un denominatoe comune
Espressioni
Le espressioni sono notazioni che denotano un valore attraverso una operazione di valutazione. – Ogni linguaggio introduce un insieme di
operatori che permettono di aggregare espressioni semplici per formare espressioni complesse con riferimento ai valori di vari domini (numeri, testi, etc.)
2+3*sin(0.75)
AN FI 98-99 Un denominatoe comune
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); }
AN FI 98-99 Un denominatoe comune
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); }
AN FI 98-99 Un denominatoe comune
Il modello cliente-servitore
Cliente Servitore
ambiente condiviso
Servitore
Cliente
controllo &informazione
AN FI 98-99 Un denominatoe comune
La funzione come servitore
riceve dati di ingresso informazioni in corrispondenza agli argomenti;
ha come corpo una espressione, la cui valutazione fornisce un risultato;
denota un valore in corrispondenza al suo nome.
se x vale 1 e f e’ la funzione R->R, f = 3 * x2 + x - 3
allora f(x) restituisce il valore 1
AN FI 98-99 Un denominatoe comune
La funzione come servitore
passivo che serve un cliente per volta che può trasformarsi in cliente,
invocando sé stessa
AN FI 98-99 Un denominatoe comune
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.
AN FI 98-99 Un denominatoe comune
Funzioni come componentif(x) + g( f(x), q( x + f(y)))
fx
f
+f
q+
g
x
xy
x1
x2
x3x4
x5
x6
x7
AN FI 98-99 Un denominatoe comune
La computazione
f(x) + g( f(x), q( x + f(y))) x1 = f(x) x2 = f(x) //mossa evitabile da un automa “intelligente” x3 = f(y) x4 = x + x3 x5 = q( x4 ) x6 = g( x2,x5 ) x7 = x1 + x6
AN FI 98-99 Un denominatoe comune
Funzioni come componentif(x) + g( f(x), q( x + f(y)))
fx
f
+
q+
g
y
x7
x1
AN FI 98-99 Un denominatoe comune
Funzioni: trasparenza referenziale
f(x) + g( f(x), q( x + f(y)))
a + g( a, q(x + b) ) – essendo a=f(x), b=f(y)
a + g( a, q(x + a) )– essendo a=f(x)
AN FI 98-99 Un denominatoe comune
Funzioni: interfaccia
L’interfaccia di una funzione e’ costituita dal suo nome, dalla lista degli argomenti e dal tipo del valore restituito.
L’interfaccia di una funzione viene spesso denominata firma (signature).
AN FI 98-99 Un denominatoe comune
Funzioni: corpo
Il corpo costituisce la struttura interna di una funzione, completamente inaccessibile dall’esterno, – garantendo in questo modo
protezione dell’informazione secondo il principio del suo “nascondimento” (information hiding)
AN FI 98-99 Un denominatoe comune
Funzioni: Comunicazione
La comunicazione di informazione tra un cliente e una funzione avviene tramite l’interfaccia della funzione
AN FI 98-99 Un denominatoe comune
Il problema dei simboli
f(x) + g( f(x), q( x + f(y))) per fornire il risultato, dobbiamo
prima conoscere la definizione delle funzioni f,g,q e i valori di x e y.
g( f(x), q( x + f(y))) cosa dobbiamo conoscere?
AN FI 98-99 Un denominatoe comune
Simboli e significato
esiste una convenzione diffusa, una “cultura comune” che associa ad un simbolo un preciso significato;
esiste un ente di riferimento che specifica in modo esplicito il significato di un simbolo.
AN FI 98-99 Un denominatoe comune
Binding ed environment
La conoscenza di cosa un simbolo denota viene espressa da una legame (binding) tra il simbolo e uno o piu’ attributi
Si definisce environment la collezione dei binding valida in (un certo punto di) un programma.
AN FI 98-99 Un denominatoe comune
Scope: esempio
Sia f N->N: Sia z = 2
f(z) + f(z) vale 8 f(2) + f( y ) vale ??? g(z) vale ???
f(x)=x+x
AN FI 98-99 Un denominatoe comune
Scope e scope rules
Tutte le occorrenze di un nome nel testo di un programma al quale si applica un particolare binding si dicono essere entro la stessa portata o scope del binding.
Le regole in base alle quali si stabilisce la portata di un binding si dicono regole di visibilita' o scope rules.
AN FI 98-99 Un denominatoe comune
Scope: esempio Sia f N->N: f(x)=x+x Sia z = 2
f(z) + f(z) vale 8 f(2) + f( y ) vale ??? Sia g N->N: g(x)=x*x g(z) vale 4 f( g(z) ) vale 8
AN FI 98-99 Un denominatoe comune
Funzioni: il modello applicativo
Valutazione, nell’environment corrente, del simbolo che denota il nome della funzione;
Valutazione, nell’environment corrente, delle espressioni che denotano gli argomenti;
Commutazione all’environment di definizione della funzione
AN FI 98-99 Un denominatoe comune
Funzioni: il modello applicativo
Chiamata della funzione; Esecuzione del corpo della funzione
(nel suo environment di definizione); Restituzione del controllo al
chiamante e del risultato con ripristino dell’environment esistente al momento della chiamata.
AN FI 98-99 Un denominatoe comune
L’approccio funzionale
Quali funzioni primitive e quali meccanismi di combinazione introdurre per poter esprimere la soluzione di un problema come una funzione?
AN FI 98-99 Un denominatoe comune
Funzioni primitive: un possibile insieme
la funzione zero: zero: N->N la funzione successore: succ: N -> N una famiglia di funzione proiezione
pni: Nn -> N, 1 i n– la funzione pni seleziona l’i-mo
argomento della lista di n argomenti di ingresso.
p3,2(x1,x2,x3)=x2
AN FI 98-99 Un denominatoe comune
Strategie di composizione
la composizione di funzioni; i predicati e le espressioni
condizionali; la ricorsione.
AN FI 98-99 Un denominatoe comune
Funzioni ricorsive generali
Le funzioni definibili in termini di un insieme prescelto di primitive e delle precedenti strategie di composizione costituiscono un insieme detto delle funzioni ricorsive generali.
AN FI 98-99 Un denominatoe comune
Un linguaggio reale
Dati e funzioni
AN FI 98-99 Un denominatoe comune
Un linguaggio: i dati
Per modello di dato si intende una astrazione in cui si distinguono: i valori che i dati possono assumere; le notazioni con cui denotare i valori; le operazioni possibili sui dati.
AN FI 98-99 Un denominatoe comune
Un linguaggio: i dati
Una delle metodologie piu' incisive per la costruzione di sistemi software corretti, modulari, documentati e riusabili consiste nel mantenere quanto piu' possibile separate le parti del programma (detti gestori) che accedono e manipolano la rappresentazione concreta in memoria dei dati, dalle parti (clienti) che trattano i dati come enti concettuali, ignorandone i dettagli interni e realizzativi.
AN FI 98-99 Un denominatoe comune
Tipi di dato
Questo concetto viene introdotto per raggiungere due obiettivi:– esprimere in modo sintetico un insieme
di valori, la loro rappresentazione in memoria e un insieme di operazioni ammissibili;
– permettere di effettuare controlli statici (al momento della compilazione) di correttezza sul programma.
AN FI 98-99 Un denominatoe comune
Variabili nei linguaggi imperativi
Rappresentano astrazioni delle celle di memoria di un elaboratore piuttosto che sinonimi di dati
Sono associate a due diverse informazioni: – l'indirizzo di una cella di memoria (o
della prima cella di un blocco di celle) – il contenuto
AN FI 98-99 Un denominatoe comune
Variabili nei linguaggi imperativi
3.22
la corrispondenza tra la variabile x e il valore 3.22 puo' venire rappresentata come segue:
x
AN FI 98-99 Un denominatoe comune
Tipi di dato primitivi
int float doubleC 16 bit
da -32768 a 3276732 bit,singolaprecisione
64 bit,doppiaprecisione
Java 32 bitda -2147483648a 2147483647
32 bit,singolaprecisione
64 bit,doppiaprecisione
AN FI 98-99 Un denominatoe comune
Tipi di dato primitivibyte short long
C 8 bitda 0 a 255
8 bitda -128 a 127
32 bitda -2147483648a 2147483647
Java 8 bitda -128 a 127
16 bit,da -32768 a 32767
64 bit
AN FI 98-99 Un denominatoe comune
Stringhe
Collezioni di caratteri delimitate da doppi apici sono dette stringhe. – In Java le stringhe appartengono a un tipo
predefinito dalla classe String . In C le stringhe sono semplici
sequenze di caratteri di cui l'ultimo e' ’\0'. – Esiste un insieme di operazioni di libreria
per la manipolazione delle stringhe.
AN FI 98-99 Un denominatoe comune
Stringhe: esempi
“” e’ la stringa vuota“0” e’ una stringa (di un solo carattere)
“hello world” e’ una stringa
AN FI 98-99 Un denominatoe comune
Boolean
In Java, gli identificatori true e false denotano rispettivamente il valore “vero” e il valore “falso” e sono gli unici valori del tipo di dato boolean. – In C il tipo di dato boolean non esiste: il
valore falso e’ denotato da 0 ed e’ considerato “vero” ogni naturale diverso da zero.
AN FI 98-99 Un denominatoe comune
Operatori COperatori C Simboli Associativita'
1.Chiamatafun.
() da sinistra a destra
2.Selezioni [] -> . da sinistra a destra3.Unari ! ~ + - ++ -- & sizeof da destra a sinistra4.Moltiplicativi
* / % da sinistra a destra
5.Additivi + - "6.Shift << >> "7.Relazionali < <= > >= "8.Uguaglianza == != "9.bit (AND) & "10.bit(exOR) ^ "11.bit(OR) | "12.Logici(AND) && "13.Logici(OR) || da sinistra a destra14.Condizionale ? : da destra a sinistra15.Assegnamenti = += -= *= /= %= &= ^= |=
<<= >>=da destra a sinistra
16.Concatenaz. , da sinistra a destra
AN FI 98-99 Un denominatoe comune
Operatori predefiniti in Java[] . ()[] -> .! ~ -- ++* / %+ -<< >> >>>>== !=&^|&&||? := += -= *= /= %= &= ^= |= <<= >>=
AN FI 98-99 Un denominatoe comune
Categorie di dati in Java
valori primitivi (di tipo boolean o di un tipo numerico)
riferimenti (valori di un qualunque reference type)
AN FI 98-99 Un denominatoe comune
Riferimenti
Molti linguaggi imperativi permettono di trattare gli indirizzi di memoria come valori e di introdurre variabili che possono assumere come valore un indirizzo
3.22x px
AN FI 98-99 Un denominatoe comune
Predicati
Un predicato e’ una funzione che restituisce un valore di tipo boolean
AN FI 98-99 Un denominatoe comune
Composizione
La composizione di funzioni si ottiene permettendo di esprimere i valori trasmessi agli argomenti di una funzione come espressioni in cui possono comparire altre funzioni
AN FI 98-99 Un denominatoe comune
Composizione: un esempio
f(x) + g( f(x), q( x + f(y))) x1 = f(x) x2 = f(x) //mossa evitabile da un automa “intelligente” x3 = f(y) x4 = x + x3 x5 = q( x4 ) x6 = g( x2,x5 ) x7 = x1 + x6
AN FI 98-99 Un denominatoe comune
L’espressione condizionale
L’espressione condizionale riflette la consuetudine matematica di definire le funzioni per casi.
abs: N-> N, abs(x) vale x se x 0abs(x) vale -x se x 0
AN FI 98-99 Un denominatoe comune
L’espressione condizionale
<condizione >? <espressione1> : <espressione2>
(x>=0)?x:-x
AN FI 98-99 Un denominatoe comune
Un problema (triangolo)
Dati tre valori interi positivi a,b,c con a<=b<=c, dire se essi possono rappresentare i lati di un triangolo e di che triangolo si tratta.
AN FI 98-99 Un denominatoe comune
Problema del triangolo: progetto si ha un triangolo
– se : a + b > c (1) Nel caso la (1) sia vera,
– se a=c il triangolo e' equilatero (in quanto deve essere anche a=b e b=c),
– se ac ma a=b oppure b=c il triangolo e' isoscele.
– se abc, allora il triangolo e' scaleno
AN FI 98-99 Un denominatoe comune
Problema del triangolo: codice
(a+b)<=c ? "non triangolo" : (a==c) ? ”equilatero" :
(a==b)||(b==c) ? " isoscele" : " scaleno ";
AN FI 98-99 Un denominatoe comune
Definizione di nuove funzioni
Cio’ che occorre e’ una notazione con cui esprimere non tanto la volonta’ di valutare una espressione, quanto la volonta’ di segnalare al sistema che una certa espressione costituisce una nuova funzione che potra’ poi essere invocata ed eseguita.
AN FI 98-99 Un denominatoe comune
Definizione di nuove funzioni
Se si desidera attribuire un nome alla nuova funzione, allora il linguaggio deve introdurre costrutti per estendere un environment con il nuovo binding che lega il nome scelto per la funzione all’oggetto computazionale che rappresenta quella specifica funzione.
AN FI 98-99 Un denominatoe comune
Definizione di nuove funzioni
int max (int x, int y ){return x >y ? x : y; }
<tipoUscita> nomeFunzione (<listaArgomenti>) {<corpo della funzione>
}
AN FI 98-99 Un denominatoe comune
Funzioni: denominazione Un unico costrutto unisce la
denotazione di una nuova funzione con l’attribuzione ad essa di un nome; Il simbolo max denota il nome della nuova
funzione; L’environment corrente viene arricchito
con uno nuovo binding tra il nome della funzione e la sua rappresentazione interna [max / rappresentazioneFunzione];
AN FI 98-99 Un denominatoe comune
Funzioni: argomenti
I simboli che compaiono nella lista degli argomenti sono variabili il cui scope e’ il corpo della funzione– Le variabili intere x e y sono gli argomenti
della funzione.
AN FI 98-99 Un denominatoe comune
Funzioni: il corpo La sequenza di istruzioni racchiusa tra
le parentesi graffe { } costituisce il corpo della funzione. { return x > y ? x : y; } L’istruzione return provoca la restituzione
del controllo al cliente, unitamente al valore dell’espressione che la segue;
– Il corpo della funzione costituisce un blocco in cui valgono precise regole di visibilita’
AN FI 98-99 Un denominatoe comune
Definizione di nuove funzioni
Permette di definire nuove operazioni
Permette di introdurre variabili per denotare i dati in modo simbolico
Permette di esprimere la ripetizione di una espressione per un numero prefissato o non prefissato di volte
AN FI 98-99 Un denominatoe comune
La ricorsione
La ricorsione consiste nella possibilita’ di definire una funzione in termini di se stessa.
fact: N->N,
fact(n) se n = 0, vale 1fact(n) se n>0, vale n*fact(n-1)
AN FI 98-99 Un denominatoe comune
Funzione ricorsive: un esempio
int fact ( int n ){
//return n ==0 ? 1 : n * fact( n-1 ); return n>0 ? n * fact( n-1 ) : 1;
}
AN FI 98-99 Un denominatoe comune
Funzioni elementari
Partendo dalle funzioni primitive sul dominio dei numeri naturali, ed utilizzando l’operatore (predicato) di uguaglianza, le espressioni condizionali e la ricorsione e’ possibile definire alcune funzioni che siamo da sempre a considerare come date a priori.
AN FI 98-99 Un denominatoe comune
Funzioni elementari
In questi esempi non avremo bisogno delle funzioni di selezione, in quanto possediamo la capacita' espressiva di denotare ogni singolo argomento nel corpo della funzione.
Inoltre denoteremo con 0 il valore restituito dalla funzione zero.
AN FI 98-99 Un denominatoe comune
Predecessoreint pred( int x ){ return ( x == 0 ) ? 0 : raggiungi( x,0 ); }
int raggiungi( int x, int y ){ return (succ(y)==x) ? y : raggiungi(x,succ(y)); }
AN FI 98-99 Un denominatoe comune
Il funzionamento del programma
Cliente ChiamaPred(3) raggiungi(3,0)raggiungi(3,0) raggiungi(3,1)raggiungi(3,1) raggiungi(3,2) -> 2
AN FI 98-99 Un denominatoe comune
Somma
int sum( int x, int y ){ return
(x==0)? y : succ(sum(pred(x),y)); }
x + y = ((x-1)+y)+1
AN FI 98-99 Un denominatoe comune
Il funzionamento
Cliente Chiamasum(3,5) succ <- sum(2,5)sum(2,5) succ <- sum(1,5)sum(1,5) succ <- sum(0,5) ->5
AN FI 98-99 Un denominatoe comune
Prodotto
int mul( int x, int y ){ return
(x==0)? 0 : sum(mul(pred(x),y),y); }
x*y = (x-1)*y+y
AN FI 98-99 Un denominatoe comune
Il processoCliente Chiamamul(3,6) sum(xxx,6) ove xxx = mul(2,6)mul(2,6) sum(zzz,6) ove zzz = mul(1,6) mul(1,6) sum(kkk,6) ove kkk = mul(0,6) ->0
AN FI 98-99 Un denominatoe comune
Sottrazione
int diff( int x, int y ){ return
(y==0)? x : pred(diff(x,pred(y)));}
x-y= (x - (y-1))-1
AN FI 98-99 Un denominatoe comune
Il processo
Cliente Chiamadiff(2,3) pred( xxx) ove xxx = diff(2,2)diff(2,2) pred( yyy) ove yyy = diff(2,1)diff(2,1) pred( zzz) ove zzz = diff(2,0) ->2
AN FI 98-99 Un denominatoe comune
Modulo |x-y|
int mod( int x, int y ){ return sum(diff(x,y),diff(y,x));}
AN FI 98-99 Un denominatoe comune
Operatori relazionali
int magZero( int x ){return (x==0) ? 0 : succ(0);
}
int minore( int x, int y ){ return magZero(diff(y,x));
}
AN FI 98-99 Un denominatoe comune
Operatori booleani
int and( int p, int q ){return p ? q : 0; }
int or( int p, int q ){return p ? p : q; }
Si fa la convenzione che 0 denoti il valore false e qualunque naturale positivo denoti il valore true.
AN FI 98-99 Un denominatoe comune
TriangoloString triangolo( int a, int b, int c ){return (a<=b) && (b<=c) ? ( (a+b)<=c ? "non triangolo" :
(a==c) ? "equilatero " : (a==b)||(b==c) ? "isoscele" :
"scaleno " ) : "dati errati"; }