Esercitazione E2

Argomento: Funzioni e Ricorsione

Framework da utilizzare: F-F

Fase 1) Semplice prova

In questo framework si definiscono funzioni, e poi si valuta una espressione che può utilizzare tali funzioni. Ad esempio la funzione "successivo" sui numeri interi può essere definita come segue:

int succ(int i){ return i+1;}

in tale dichiarazione, chiamiamo "signature" la parte di definizione "int succ(int i)", che ci dà tutte le informazioni necessarie sulla struttura "esterna" della funzione, ossia il nome, il tipo di ritorno, ed il tipo di ogni argomento. 

Per testare il funzionamento di una funzione di questo tipo:

• copiare la sua definizione nel box in alto (usare copia e incolla di windows!)
• indicare una espressione qualsiasi (anche 0) nel box in basso
• valutando, se si ottiene 0 vuol dire che la funzione è corretta semanticamente
• poi testare la funzione per qualche input, mettendo una espressione del tipo succ(5) e valutando
• fare varie prove
• per passare ad un'altra funzione ricopiarla al posto della precedente

Fase 2) La correttezza semantica delle dichiarazioni e invocazioni di funzioni

A) La correttezza di una dichiarazione di funzione può sempre essere collegata a due aspetti:

• I suoi parametri sono usati in modo compatibile col loro tipo, così come dichiarato nella signature della funzione
• Il tipo dell'espressione corpo è convertibile in modo implicito (per coercizione) al tipo ritornato dalla funzione

Si ricorda che la nozione di conversione implicita (per coercizione) di un valore di tipo T1 ad un certo tipo T2 è possibile quando:

• T1 e T2 sono lo stesso tipo
• se T1 e T2 sono numeri, e considerando la gerarchia int->long->float->double, quando T1 è a sinistra di T2 in tale gerarchia
• se T2 è String, e solo nel caso ci si trovi in un argomento dell'operatore "+" (concatenazione di stringhe)

Predicendo prima il risultato, e poi verificando col framework F-F, testare la correttezza semantica delle seguenti funzioni (come indicato al punto 1) tale correttezza è verificabile inserendo ogni funzione, una alla volta, nel box in alto, e valutando una qualunque espressione nel box in basso, es.: 1+2 ):

• int f1(double x,int y){ return x+y;}
• int f2(boolean b,boolean b2){ return (b & b2)?0:1f;}
• boolean f3(int x,int y){ return x==y;}
• boolean f4(double x,double y){ return x!=y;}
• long f5(){ return 1;}

B) Invece, la correttezza di una invocazione di funzione può sempre essere collegata a due aspetti:

• Il tipo degli argomenti deve essere convertibile al tipo dei corrispondenti parametri formali
• Il tipo da associare all'invocazione è il tipo di ritorno della funzione

Considerando le due definizioni corrette:

• boolean f3(int x,int y){ return x==y;}
• boolean f4(double x,double y){ return x!=y;}

e, una a una, le invocazioni qui sotto, predirre il loro risultato, e poi verificarlo valutando col framework (per almeno un esempio, disegnare l'AST e usarlo per effettuare Typing e Valutazione)

• f3(1,2L)
• f4(1,2L)
• f3(1,1/2)
• f3(1,1/2f)
• f3(1,1/2)+3.4
• ""+f4(1,1/2f)

Fase 3) Analisi di funzioni date

• Usando il codice qui sotto, testare il funzionamento della funzione fattoriale (fino a quale valore di input dà un risultato corretto? E per interi negativi?)

            int fatt (int n){
                return n==0?1:n*fatt(n-1);
            }

• Studiare la seguente funzione, cercando di capire quale relazione intercorre fra input ed output (ossia, che cosa succede con input pari, dispari, positivi, negativi, etc..)

            int f(int x,int y){ 
                return x<0 ? 0 : x%2==0? 1: -1 ; 
            }

          Dopo aver risposto alla domanda fare qualche test col framework, per verificare se la previsione era giusta.

• Studiare la seguente funzione, cercando di capire quale relazione intercorre fra input ed output (ossia, che cosa succede con input pari, dispari, positivi, negativi, etc..)

            int f(int x){ 
                return x<0 ? 0 : (x==0 ? 1: f(x-2)); 
            }

          Dopo aver risposto alla domanda fare qualche test col framework, per verificare se la previsione era giusta.

• Considerare le due funzioni qui sotto (ricopiandole nel box in alto). 

            int f(int x,int y){ 
                return f2(x,y,x,y);
            }

            int f2(int x,int y,int z, int w){
                return (z==w)? z :
                          (z>w ? f2(x,y,z,w+y) : f2(x,y,z+x,w) );
            }

Predire quale algoritmo realizza la funzione f (che utilizza la funzione d'appoggio f2). Aiutarsi cercando di capire l'output producendo l'albero delle invocazioni relativo alle chiamate:

• f(2,2) 
• f(2,4)
• f(6,4)
• f(5,3) 

(seguire l'ordine proposto, e ogni volta verificare se il risultato è quello che ci si aspettava). Alla fine si dovrebbe aver capito quale risultato produce la funzione in generale. 

Fase 4) Test di funzioni

• Si consideri la seguente funzione somma, che somma tutti gli elementi dell'array in ingresso. (Fare qualche prova col framework per accertarsi del suo corretto funzionamento):

            int somma(int[] array){
                return somma(array,0);
            }

            int somma(int[] array,int start){
                return (start==array.length)
                ? 0
                : array[start]+somma(array,start+1);
            }

• Verificare che la funzione soddisfa il seguente test, ossia incollare la funzione test nel framework e poi verificare che l'invocazione test() dia risultato true.

boolean test(){
        return   somma(new int[]{10,20,30})==60 &&
                    somma(new int[]{10,20,30,40})==100 &&
                    somma(new int[]{10})==10 &&
                    somma(new int[]{})==0;
}

• Modificare la funzione di test aggiungendo un caso in cui, se l'array è lungo più di 5 elementi, il risultato della somma sia 0. Rivalutando si noterà che ora la funzione somma non passa più il test (perchè ovviamente con l'array lungo più di 5 elementi non ritorna 0).
• Provare a modificare la funzione somma in modo che passi il test. Per fare ciò cambiare il corpo della funzione somma (quella con un argomento) in modo che SE la lunghezza dell'array (denotata con array.length) è maggiore di 5 ALLORA si ritorni 0, ALTRIMENTI si ritorni somma(array,0).
• Verificare che la funzione così modificata passa il test.

Fase 5) Modifica di funzioni date

• Considerare la funzione somma sopra riportata (prima della modifica richiesta). Cosa succede se si sostituisce il pezzo start+1 con start+2??? 
  • Quale nuova funzione si realizza?  Provare con l'input new int[]{10,2,30,4}
  • Notare che con l'input new int[]{10,2,30} si ha un errore. Perchè?
  • Sostituendo l'operatore == con >= il problema viene risolto, perchè?
• Sulla base delle funzioni appena viste, costruire una nuova funzione sommaPari che somma solo gli elementi di posizione pari. Costruirla (testandola) in modo che funzioni bene anche con array di lunghezza zero, lunghezza pari e dispari.
• Costruire l'analoga funzione sommaDispari
• Costruire una funzione sommaSePositivi che somma gli elementi dell'array positivi, non considerando quelli negativi. Esempio: valutando sommaSePositivi(new int[]{10,-5,20,30,40,-1}) si deve avere il risultato 100.

Fase 6) Progetto di nuove funzioni

• Costruire una funzione contaPositivi che conta quanti elementi positivi sono presenti in un array. La funzione dovrà soddisfare il seguente test:

  boolean test(){
      return   contaPositivi(new int[]{})==0 &&
                  contaPositivi(new int[]{1,2,3})==3 &&
                  contaPositivi(new int[]{-5,1,2,3})==3 &&
                  contaPositivi(new int[]{1,2,3,-7})==3 &&
                  contaPositivi(new int[]{-5,3,-4})==1 &&
                  contaPositivi(new int[]{-2})==0;
  }

• Considerando l'esempio visto a lezione relativo al riconoscimento della grammatica A::= {2}1, provare a realizzare il riconoscitore della gramatica EBNF: A::= 1{2}. Formulare una funzionalità di test per questa funzione e verificarne il funzionamento.

Facoltativo) Come approfondimento. Con il linguaggio visto sino ad ora siete in grado di realizzare il riconoscitore di qualunque grammatica EBNF, quindi provare via via a realizzare i riconoscitori per

• {1|2}
• {1}{2}
• {12}
• 1{2}3
• ..