AN FI 98-99 Un denominatoe comune Lo stile funzionale Concetti fondamentali.

AN FI 98-99 Un denominatoe comune

Lo stile funzionale

Concetti fondamentali


Concetti comuni

Dati primitivi e tipi di dato Espressioni e Comandi Funzioni e Procedure Variabili Riferimenti Strutture di dati


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


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.


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)


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


Il modello cliente-servitore

Cliente Servitore

ambiente condiviso

Servitore

Cliente

controllo &informazione


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


La funzione come servitore

passivo che serve un cliente per volta che può trasformarsi in cliente,

invocando sé stessa


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 come componentif(x) + g( f(x), q( x + f(y)))

fx

f

+f

q+

g

x

xy

x1

x2

x3x4

x5

x6

x7


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


Funzioni come componentif(x) + g( f(x), q( x + f(y)))

fx

f

+

q+

g

y

x7

x1


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)


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


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)


Funzioni: Comunicazione

La comunicazione di informazione tra un cliente e una funzione avviene tramite l’interfaccia della funzione


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?


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.


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.


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


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.


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


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


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.


L’approccio funzionale

Quali funzioni primitive e quali meccanismi di combinazione introdurre per poter esprimere la soluzione di un problema come una funzione?


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


Strategie di composizione

la composizione di funzioni; i predicati e le espressioni

condizionali; la ricorsione.


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.


Un linguaggio reale

Dati e funzioni


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.


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.


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.


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


Variabili nei linguaggi imperativi

3.22

la corrispondenza tra la variabile x e il valore 3.22 puo' venire rappresentata come segue:

x


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


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


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.


Stringhe: esempi

“” e’ la stringa vuota“0” e’ una stringa (di un solo carattere)

“hello world” e’ una stringa


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.


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


Operatori predefiniti in Java[] . ()[] -> .! ~ -- ++* / %+ -<< >> >>>>== !=&^|&&||? := += -= *= /= %= &= ^= |= <<= >>=


Categorie di dati in Java

valori primitivi (di tipo boolean o di un tipo numerico)

riferimenti (valori di un qualunque reference type)


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


Predicati

Un predicato e’ una funzione che restituisce un valore di tipo boolean


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


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


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


L’espressione condizionale

<condizione >? <espressione1> : <espressione2>

(x>=0)?x:-x


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.


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


Problema del triangolo: codice

(a+b)<=c ? "non triangolo" : (a==c) ? ”equilatero" :

(a==b)||(b==c) ? " isoscele" : " scaleno ";


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.



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.



int max (int x, int y ){return x >y ? x : y; }

<tipoUscita> nomeFunzione (<listaArgomenti>) {<corpo della funzione>

}


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


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.


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’



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


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)


Funzione ricorsive: un esempio

int fact ( int n ){

//return n ==0 ? 1 : n * fact( n-1 ); return n>0 ? n * fact( n-1 ) : 1;

}


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.


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.


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


Il funzionamento del programma

Cliente ChiamaPred(3) raggiungi(3,0)raggiungi(3,0) raggiungi(3,1)raggiungi(3,1) raggiungi(3,2) -> 2


Somma

int sum( int x, int y ){ return

(x==0)? y : succ(sum(pred(x),y)); }

x + y = ((x-1)+y)+1


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


Prodotto

int mul( int x, int y ){ return

(x==0)? 0 : sum(mul(pred(x),y),y); }

x*y = (x-1)*y+y


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


Sottrazione

int diff( int x, int y ){ return

(y==0)? x : pred(diff(x,pred(y)));}

x-y= (x - (y-1))-1


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


Modulo |x-y|

int mod( int x, int y ){ return sum(diff(x,y),diff(y,x));}


Operatori relazionali

int magZero( int x ){return (x==0) ? 0 : succ(0);

}

int minore( int x, int y ){ return magZero(diff(y,x));

}


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.


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

AN FI 98-99 Un denominatoe comune Lo stile funzionale Concetti fondamentali.

Documents

Transcript of AN FI 98-99 Un denominatoe comune Lo stile funzionale Concetti fondamentali.