Progetto 2021/22

Questa pagina descrive il progetto per il corso di Informatica della Laurea in Matematica per gli appelli dell'anno accademico 2021/2022.

Un semplice linguaggio di programmazione

Descrizione generale

Il progetto consiste nello sviluppo di un interprete per un semplice linguaggio di programmazione imperativo, SuperBasic, che descriveremo sotto. L'interprete (scritto in Java) dovrà aprire un file di testo contenente il codice di un programma (scritto nel linguaggio SuperBasic), e simularne l'esecuzione.

Un programma in SuperBasic ha la seguente forma 

NV NL MS
linea0
linea1
linea2
...
lineaNL-1

dove la prima riga contiene tre numeri naturali NV NL NS che hanno il seguente significato.

L'esecuzione del programma può portare o a un valore intero risultato, memorizzato nella variabile x2 o a un errore in fase di esecuzione. L'interprete dovrà riportare nel suo output se l'esecuzione è terminata con successo (e con quale risultato), o se invece c'è stato un errore (e quale).

Ogni linea del programma contiene un comando in SuperBasic, spiegati in dettaglio sotto. I comandi di SuperBasic sono:

Semantica informale del linguaggio

Concetti generali

L'esecuzione di un programma SuperBasic inizia dalla linea0. Dopo l'esecuzione di una linea di codice, salvo dove diversamente previsto dal comando, si continua con la linea sottostante.

Tutte le variabili usate in SuperBasic sono intere e hanno lo stesso comportamento degli int di Java. All'inizio dell'esecuzione, le variabili x0,x1 sono inizializzate con dei valori di input (vedi sotto), mentre le altre non sono inizializzate.

Alla fine dell'esecuzione la variabile x2 contiene invece un valore di output.

Le variabili diverse da x0,x1 non possono essere lette prima della loro inizializzazione (prima che si assegni un valore a esse).

All'interprete del codice SuperBasic viene fornito un naturale timeout che indica il numero massimo di linee di codice da eseguire, superato il quale il programma viene forzatamente terminato (vedi sotto).

L'esecuzione di un programma SuperBasic può causare degli errori. Oltre ai possibili errori degli specifici comandi (vedi sotto), il programma può causare alcuni errori generali:

Possibili errori generali

Elenco comandi

Assegnamento di una costante 

  let xA = K

dove A è un numero naturale mentre K è una costante intera. L'effetto del comando è quello di assegnare alla variabile xA l'intero K.

Possibili errori:

Assegnamento di un'espressione 

  let xA = xB OP xC

dove A,B,C sono numeri naturali mentre OP è un operatore tra +,-,*,/. Come in Java, l'operatore / indica il quoziente tra due interi. L'effetto del comando è quello di assegnare alla variabile xA il risultato dell'operazione OP tra le variabili menzionate.

Nota bene: l'operazione viene eseguita necessariamente fra due variabili! NON è possibile eseguire un comando come ad esempio 

  let x2 = x1 + 2

il quale dovrà causare l'errore "ERROR: syntax error in line N", dove N è la linea corrente del programma.

Possibili errori:

If - goto 

  if xA OP xB goto N
  if xA OP xB goto +N
  if xA OP xB goto -N

dove A,B,N sono numeri naturali mentre OP è un operatore di confronto tra ==,!=,<,<=,>,>=. L'effetto del comando è quello di controllare la guardia espressa tra le due variabili. Se la guardia NON vale, il programma prosegue dalla riga sottostante. Se invece la guardia vale, l'esecuzione del programma prosegue dalla riga di codice L, definita come segue:

Nota bene: la guardia è espressa tra due variabili. Analogamente a quanto avviene per il comando let, NON è possibile effettuare confronti con costanti. Ad esempio, il comando 

  if x0 < 2 goto +2

dovrà restituire la stringa "ERROR: syntax error in line M", dove M è il numero di linea corrente.

Possibili errori:

While - exit 

  while xA OP xB exit N
  while xA OP xB exit +N
  while xA OP xB exit -N

dove A,B,N sono numeri naturali mentre OP è un operatore di confronto tra ==,!=,<,<=,>,>=. L'effetto del comando è quello di controllare la guardia espressa tra le due variabili. Se la guardia NON vale, l'esecuzione del programma prosegue dalla riga L, definita in modo analogo a quanto fatto per il comando if .. goto ... Se invece la guardia vale, la riga di codice corrente viene aggiunta alla cima dello stack, e l'esecuzione del programma prosegue dalla riga di codice sottostante.

Nota bene: la guardia è espressa tra due variabili. Analogamente a quanto avviene per il comando if ... goto ..., NON è possibile effettuare confronti con costanti. Ad esempio, il comando 

  while x0 < 2 exit +2

dovrà restituire la stringa "ERROR: syntax error in line M", dove M è il numero di linea corrente,

Possibili errori:

Next 

  next

L'effetto del comando è quello di riprendere l'esecuzione del programma dall'ultimo while eseguito e aggiunto sullo stack. Per questo, viene estratto un numero di riga L dalla cima dello stack, e l'esecuzione del programma dovrà proseguire da tale riga.

Possibili errori:

Commenti 

  rem TESTO

dove TESTO è una riga di testo arbitraria. Il comando non ha alcun effetto.

Possibili errori: nessuno.

End 

  end

Il comando termina il programma, restituiendo come valore finale quello della variabile x2. Se non ci sono errori (vedi sotto), a questo punto l'output dovrà restituire la stringa "OK: V", dove V è il valore della variabile x2.

Possibili errori:

Precedenza tra errori

Può capitare che più errori si verifichino contemporaneamente durante l'esecuzione del programma. La precedenza degli errori è data dall'ordine in cui sono stati presentati sopra, nei concetti generali e nell'elenco comandi. Gli errori generali hanno sempre la precedenza sugli errori dello specifico comando in esecuzione.

Alcuni esempi:

Gestione dello stack

Per gestire il comando while ... exit ... e il comando next è necessario utilizzare uno stack (chiamato anche pila). Intuitivamente, si tratta di una struttura dati che può essere visualizzata come una sequenza di interi A0 A1 A2 ... Ak. Su uno stack possiamo fare due operazioni: aggiungere valori sulla cima della pila (aggiungendo un intero dopo l'ultimo della sequenza) ed estrarre il valore in cima alla pila (rimuovendo l'ultimo intero dalla sequenza). Per rappresentare lo stack, potete usare un vettore di interi di lunghezza MS insieme a una variabile di tipo int con cui tenete traccia della posizione della cima della pila. Gli interi del vettore dalla posizione 0 fino alla posizione della cima (esclusa) rappresentano gli interi delle sequenza rappresentata dallo stack, mentre il valore degli altri interi del vettore è irrilevante.

L'idea è che lo stack serve per tenere in memoria il numero di linea dei cicli while che sono ancora in esecuzione, in maniera da poter riportare l'esecuzione del programma alla riga corretta nel momento in cui si incontra il comando next.

Ad esempio, se vogliamo eseguire il seguente programma con gli input x0 = 0 e x1 = 0: 

    3 4 3
    while x0 == x0 exit 1
    while x1 == x0 exit 3
    let x1 = 1
    next

Dovremo allocare un vettore di interi di lunghezza 3 con cui rappresentare lo stack: 

    _  _  _

All'inizio lo stack sarà vuoto. Quando l'esecuzione raggiunge la linea 0, poiché la guardia è vera dobbiamo salvare la linea di codice corrente sullo stack, in modo da sapere da dove riprendere l'esecuzione quando incontriamo un'istruzione next. 

    0  _  _

Eseguendo poi la linea 1, di nuovo la guardia è vera, quindi dobbiamo salvare la linea di codice corrente sullo stack, in modo da poterci ritornare quando incontriamo un'istruzione next 

    0  1  _

A questo punto in riga 3 incontriamo un'istruzione next. Questo significa che dobbiamo riprendere l'esecuzione dall'ultimo while visitato. Il numero di riga dell'ultimo while visitato è contenuto in cima allo stack (ed è 1), quindi lo estraiamo dallo stack. A questo punto lo stato dello stack sarà il seguente 

    0  _  _

e l'esecuzione riprende da linea 1. Osservate che in questo momento, se incontrassimo un'altra istruzione next, l'esecuzione ritornerebbe alla posizione dell'ultimo while visitato, che a questo punto è linea 0. Il while in linea 1 è stato "chiuso" dal next che abbiamo appena incontrato.
Proseguendo con l'esecuzione del nostro programma (quindi da linea 1), abbiamo un'istruzione while, la cui guardia ora è falsa (x0 = 1 e x1 = 0), pertanto l'esecuzione salta alla linea di codice indicata da exit, ossia linea 3, e sullo stack non viene fatto nulla.
A questo punto troviamo un'altra istruzione next, quindi viene estratta dallo stack la posizione dell'ultimo while incontrato (in linea 0). Lo stato dello stack a questo punto sarà il seguente 

    _  _  _

e l'esecuzione riprenderà da linea 0. In questo esempio il while esterno continuerà a eseguire per sempre, fino a quando non si raggiunge l'errore di timeout.

Sotto trovate altri esempi di programmi SuperBasic.

Implementazione in Java

Si chiede di scrivere una funzione Java avente (esattamente) nome e tipo come segue: 

public static String semantica(String inputFile, int in0, int in1, int timeout)

Il parametro inputFile indica un nome di un file da cui leggere, contenente il codice del programma SuperBasic da eseguire.
I parametri in0 e in1 indicano i valori di input del programma, a cui saranno inizializzate le variabili x0 e x1 a inizio esecuzione.
Il parametro timeout indica il numero massimo di linee di codice che saranno eseguite prima che venga terminata l'esecuzione del programma con un errore di timeout.

L'output della funzione semantica(...) dovrà essere una stringa, il cui contenuto è il risultato dell'esecuzione del programma, sia esso uno degli errori descritti sopra o il risultato ottenuto terminando l'esecuzione con end ("OK: V").

Quando la funzione viene chiamata, vi viene garantito che il file di input inputFile è un file di testo con esattamente la forma seguente: 

  NV NL MS
  linea0
  linea1
  linea2
  ...
  lineaNL-1

Nella prima riga del file troviamo le costanti NV NL MS che sono i parametri del programma (già descritti sopra). Dalla seconda riga in poi troviamo NL linee di testo arbitrarie, da interpretare secondo la semantica informale descritta sopra.

Si noti che non è garantito che tali linee contengano comandi nella sintassi data sopra, nel qual caso l'interprete deve generare un errore di sintassi non appena una linea invalida viene eseguita.

In caso di input malformato non corrispondente a quanto garantito sopra (per esempio, NV non è un naturale, o NL non corrisponde al numero di linee sottostante nel file) non si richiede nessun comportamento particolare. Il vostro programma Java può dare un risultato qualunque, o anche generare un errore a tempo di esecuzione.

Esempio 1

Per sommare N+(N-1)+...+1 in Java scriveremmo così: 

  // x0 contiene N, in x2 mettiamo la somma
  x2 = 0;
  while (x0 > 0) {
     x2 = x2 + x0;
     x0 = x0 - 1;
  }

Traducendo il codice di sopra in SuperBasic, potremmo scrivere: 

5 11 1
rem x0 contiene N, in x2 mettiamo la somma
rem le costanti 0 e 1 le mettiamo in x3 e x4
let x3 = 0
let x4 = 1
rem inizializziamo x2
let x2 = 0
while x0 > x3 exit +4
let x2 = x2 + x0
let x0 = x0 - x4
next
end

Sull'input di sopra, su input x0=5,x1=0 e timeout sufficientemente grande, va generato come output OK: 15.

Esempio 2

Dati x0 e x1 verifichiamo se x0 è il quadrato di un numero minore di x1. In Java scriveremmo: 

  y = 0;
  x2 = 0;
  while (y < x1) {
    if (y*y == x0) {
      x2 = 1;
    }
    y++;
  }

In questo modo, alla fine x2 sarà rimasto 0 se e solo se x0 non è uno dei quadrati, e sarà diventato 1 altrimenti. Traducendo il codice di sopra in SuperBasic, potremmo scrivere: 

6 13 1
rem la costante 1 la metto in x3
let x3 = 1
rem y la chiamo x4
let x4 = 0
let x2 = 0
while x4 < x1 exit +7
rem metto il quadrato in x5
let x5 = x4 * x4 
if x5 != x0 goto +2
let x2 = 1
let x4 = x4 + x3
next
end

Esempio 3

Dato x0, contiamo quante triple pitagoriche a*a = b*b + c*c ci sono con 1 <= a,b,c < x0 . In Java scriveremmo: 

  x2 = 0;
  a = 1;
  while (a < x0) {
    b = 1;
    while (b < x0) {
      c = 1;
      while (c < x0) {
        if (a*a == b*b + c*c) {
          x2++;
        }
        c++;
      }
      b++;
    }
    a++;
  }

In SuperBasic scriveremmo: 

11 25 3
rem la costante 1 la mettiamo in x3
let x3 = 1
rem le variabili a,b,c le chiamiamo x4,x5,x6
let x2 = 0
let x4 = 1
while x4 < x0 exit +19
let x5 = 1
while x5 < x0 exit +15
let x6 = 1
while x6 < x0 exit +11
rem i quadrati in x7,x8,x9
let x7 = x4 * x4
let x8 = x5 * x5
let x9 = x6 * x6
rem la somma dei quadrati in x10
let x10 = x8 + x9
if x7 != x10 goto +2
let x2 = x2 + x3
let x6 = x6 + x3
next
let x5 = x5 + x3
next
let x4 = x4 + x3
next
end

Consigli

Ricordatevi che, quando confrontate due String in Java dovete usare s1.equals(s2) e non s1 == s2.

Potrebbe essere utile usare i comandi s.split(...), s.charAt(...), s.substring(...) per manipolare le stringhe.

Potrebbe essere utile anche ricordare che il metodo Integer.parseInt(..) può generare un'eccezione di tipo NumberFormatException se la stringa che viene passata non è un intero (ad esempio Integer.parseInt("45ye2")). Potete gestire questa eccezione a vostro piacimento con un blocco try { ... } catch (NumberFormatException e) { ... }

Per gestire le variabili non inizializzate si può usare un vettore di booleani.

Svolgimento

Si chiede di scrivere una singola classe Java Progetto, che contenga la funzione semantica descritta sopra. In particolare, è obbligatorio usare come base per il progetto un progetto Eclipse contenente il seguente scheletro di di classe Java.

La classe scheletro va posizionata in un progetto Eclipse come segue. Create un progetto Eclipse chiamato cognome_matricola (usate i vostri dati, per esempio tramaglino_000001 o de_paperoni_000002), e create la classe Progetto al suo interno nella cartella src. Dovete ottenere un file come segue:

È obbligatorio rispettare la posizione del file della classe come descritto sopra. Dentro quel file potete quindi inserire il codice dello scheletro fornito.

È tassativamente proibito modificare lo scheletro nelle parti segnate al suo interno come da non modificare. In particolare, non si può modificare il tipo o il nome delle procedure / funzioni già presenti all'interno. In nessun caso il file consegnato dovrà contenere una dichiarazione package.

È invece consentito (e consigliabile) definire delle procedure/funzioni addizionali all'interno della classe Progetto. È consentito aggiungere import per usare le librerie standard di Java.

È consentito modificare il metodo main della classe nello scheletro. Si noti, tuttavia, che tale metodo potrà essere cancellato e sovrascritto, o comunque non eseguito, da chi corregge. Di conseguenza, se si decidono di usare variabili globali, queste devono essere inizializzate dentro la funzione semantica, e non dentro il main, in quanto quest'ultimo non verrà eseguito.

Durante la correzione, la funzione semantica verrà chiamata ripetutamente eseguendo (anche) test automatizzati.

Helper

Per potere testare più facilmente il vostro progetto, vi viene fornita la seguente libreria Java e un archivio di test. L'uso di questa libreria è opzionale.

Dopo avere scaricato il file helper di sopra in una qualunque cartella, potete inserire la libreria helper nel vostro progetto Eclipse, selezionando il vostro progetto, facendo clic destro, e selezionando dal menù la voce Build Path -> Add External Archives.... Comparirà un finestra dove potete selezionare il file jar fornito sopra.

Dopo avere aggiunto la libreria helper al vostro progetto, all'interno del file Java Progetto.java potete usare le funzioni della libreria, che mostriamo sotto. Nello scheletro di progetto che vi forniamo, trovate già degli esempi su come usarle nel main(), dopo avere usato import progetto2021.Helper; all'inizio del file. 

static boolean Helper.checkSemantica(String inputFile, int in0, int in1, int timeout, String yourOutput)

La funzione Helper.checkSemantica prende come parametri gli stessi parametri della funzione semantica, più un parametro addizionale String yourOutput che rappresenta l'output della funzione semantica che vogliamo controllare.

La funzione Helper.checkSemantica restituisce il booleano true quando yourOutput coincide col risultato atteso dell'esecuzione del programma SuperBasic, e false altrimenti. In caso l'output non coincida, la funzione stampa a video un messaggio con l'output atteso, in modo da aiutarvi nella correzione del vostro programma.

Usare l'helper non è obbligatorio (anche se fortemente raccomandato). Se non lo volete usare, per potere compilare lo scheletro dovete rimuovere dal file sia la riga import progetto2021.Helper; che tutti i riferimenti alle funzioni Helper.

Nota bene: se usate l'helper su tutti i test forniti, e se su questi test la vostra funzione semantica fornisce il risultato atteso, questo non vuol dire che la funzione sia corretta in tutti i casi possibili. È possibile che, in fase di valutazione del progetto, vengano controllati altri casi, e che su questi si scopra che il vostro codice non funziona correttamente. In altre parole: con i test possiamo solo dimostrare che un programma è scorretto, ma mai che è corretto.

Requisiti e criteri di valutazione

Il progetto verrà valutato secondo i seguenti criteri, che descrivono un insieme di requisiti sul codice consegnato. Ogni requisito primario deve essere rispettato rigidamente: in caso di violazione, anche minima, di uno di questi requisiti la prova d'esame non è superata. I requisiti secondari devono essere comunque rispettati. Violazioni minori saranno tollerate, ma violazioni gravi possono comunque causare il non superamento della prova.

Requisiti tecnici (primario). La soluzione consegnata deve seguire lo scheletro di progetto fornito sopra, modificato nel modo descritto sopra.

Devono inoltre essere rispettati questi requisiti:

  1. Non modificate il nome della classe Progetto, i nomi o i tipi delle procedure/funzioni segnate come da non modificare. Non ci deve essere nessuna dichiarazione di package della classe.
  2. Posizionate la classe Progetto come descritto sopra nel vostro progetto Eclipse.
  3. Il file di input deve essere quello passato come parametro, e non altri con un nome prefissato. Per esempio, new File(fileName) usa il parametro, mentre new File("fileName") usa un nome prefissato.
  4. Le procedure/funzioni richieste non devono interagire con l'utente in nessun modo (ad es., chiedere di inserire dati all'utente). I nostri test devono potere chiamare ripetutamente quelle funzioni in modo automatico, senza il nostro intervento manuale. Il main invece può interagire con l'utente, se desiderato (ma comunque come detto sopra il codice del main può essere ignorato da noi durante i test.)

Il non rispettare questi requisiti tecnici può causare il fallimento dei nostri test automatizzati, ed in tal caso la prova non sarà superata.

Correttezza (primario). Non ci devono essere errori a tempo di compilazione: il programma deve compilare. Non ci devono essere errori a tempo di esecuzione: il programma non deve generare eccezioni (per esempio, DivisionByZero oppure ArrayIndexOutOfBounds) quando eseguito su un input ben formato. Il programma deve dare l'output desiderato su qualunque input compatibile con la specifica.
Nota bene: Nel caso il programma sia scorretto, non è compito di chi corregge fare il debugging, ovvero identificare la causa dell'errore e suggerire una modifica per rimuoverla. Anche quando tale causa fosse nota a chi corregge, non verrà comunicata allo studente, in quanto sarebbe come suggerire una parte non banale della soluzione della prova. Infatti, capita frequentemente che correggere l'errore dopo averlo individuato diventi banale ("devo usare x, e non x+1"), e che la prova di conseguenza consista prevalentemente nella ricerca dell'errore.
Corollario: se provando il programma su un insieme di input campione si riscontrano già errori di correttezza, chi corregge non è tenuto ad esaminare il codice del programma.

Leggibilità (secondario). Il codice deve essere scritto in modo tale da permettere a un altro programmatore di comprenderne la logica. Non è sufficiente che il codice "funzioni", o che sia chiaro a chi lo ha scritto. Per aiutare la lettura del codice da parte di altri, si consiglia di usare dei nomi di variabile e di funzione appropriati, strutturare il codice adeguatamente (dove ha senso, meglio dividere una funzione lunga in più funzioni ausiliarie), e di inserire dei commenti.

Non commentate come state calcolando qualcosa, commentate piuttosto cosa state calcolando. Per esempio, il seguente commento è altamente inutile: 

	// incremento i
	i++;

Al contrario, il seguente aiuta a comprendere il codice: 

	// passo a coordinate polari
	rho = Math.sqrt(x*x + y*y);
	theta = Math.atan2(y, x);

Efficienza (secondario). Il vostro programma deve svolgere il suo compito in tempi ragionevoli. Noi dobbiamo essere in grado di svolgere agevolmente i nostri test chiamando la funzione semantica molte volte anche su input complessi.

Se il vostro programma è così lento da impedirci di eseguire tutti i test nel tempo di pochi minuti, riterremo tutti i test falliti.

Consegna del progetto

Per potere partecipare allo scritto di un appello di esame, il progetto deve essere consegnato entro le date indicate nell'elenco degli appelli d'esame. La consegna si svolge su Moodle, in modo simile a quanto fatto per il tutorato.

Note Finali

Se avete dubbi sul testo del progetto, ovvero su che cosa vi sta venendo chiesto, chiedete pure delucidazioni per email o a ricevimento. Se invece avete dubbi sulla soluzione dell'esercizio, ovviamente non possiamo suggerirvi nulla.

Il progetto non viene svolto in un ambiente "controllato" come per esempio avviene per un esame scritto, ma vi viene lasciata libertà di svolgerlo dove e quando preferite (compatibilmente con le scadenze). Per esempio, potete usare i laboratori quando liberi, o farlo su un vostro computer personale.

Il progetto è individuale, non di gruppo. Tuttavia, vi è consentito discutere del progetto con altre persone per scambiarsi opinioni a riguardo. Non è consentita, ovviamente, la copia di pezzi di codice inerenti al progetto da uno studente all'altro. Allo stesso modo, farsi fare il progetto da un'altra persona è considerato equivalente a copiare. In caso di dubbi sull'autenticità del progetto, ci riserviamo la possibilità di convocarvi per un colloquio sul codice che avete consegnato, anche dopo l'esame scritto.

Vi è consentito di "copiare" invece pezzi di codice che vi abbiamo fornito noi, o di "tradurre in Java" dei pezzi di codice che potreste trovare su qualche libro o tutorial online, e che non siano soluzioni degli esercizi proposti sopra o di una loro parte significativa. Nei casi consentiti dovete obbligatoriamente citare la fonte in un commento nel codice.

Il discutere del progetto su forum di discussione su Internet o simili non è vietato a prescindere, ma è soggetto alle stesse regole della comunicazione tra altri studenti. Inoltre, se iniziate una discussione su un forum riguardo al progetto, dovete obbligatoriamente dichiarare 1) che l'esercizio in questione è un progetto di esame, e 2) che non desiderate che qualcuno vi scriva una soluzione al posto vostro. Se anche chiarendo ciò qualcuno vi risponde includendo del codice, voi non potete includerlo nel progetto.

Varie e domande degli studenti

Se preferite, potete usare anche caratteristiche di Java non viste a lezione (costrutti diversi come gli oggetti, librerie non viste a lezione purché incluse tra quelle standard di Java), anche se il progetto si può svolgere benissimo senza. Dovete però comprendere il codice che state usando: se venite chiamati ad un colloquio (vedi sopra) vi può essere chiesto di spiegarlo.

Se ci sono parti del testo del progetto che ritenete non chiare, vi invitiamo a fare domande usando il forum che trovate su Moodle, in modo che tutti gli studenti possano leggere le nostre risposte. Allo stesso modo, per domande di interesse generale, vi invitiamo a usare il forum e non l'email.

Informatica - Teaching - Home

Valid CSS Valid XHTML 1.1 Roberto Zunino, 2021