Linguaggi e Traduttori

Prof. Marco Gavanelli

2 luglio 2018

Esercizio 1

Si scriva in Haskell una funzione di ordine superiore

che prende come parametri

• una lista di interi Lx
• una lista di interi Ly
• una funzione f

e genera una matrice (cioè una lista di liste) di Bool . La matrice di Bool contiene una riga per ogni elemento della lista Ly e una colonna per ogni elemento della lista Lx.

Sia

• x l'elemento di posizione c nella Lx,
• y l'elemento di posizione r nella lista Ly,

la cella della matrice nella riga r e colonna c è vera se (e solo se) y = = f x.

Quindi si può immaginare la visualizzaMatr come una funzione che mostra il grafico della funzione f sulla matrice. Ad esempio, se

allora

fornisce la matrice

Per chiarire meglio, disegnamo la matrice in corrispondenza alle liste Lx e Ly:

Si può notare come le celle contenenti True (evidenziate) identifichino proprio la parabola y=x².

Es 1.1 (punti 8)

Si definisca la funzione visualizzaMatr.

In tutti gli esercizi su Haskell, è fondamentale utilizzare (ed, eventualmente, definire) funzioni di ordine superiore. Nel voto finale è inclusa una valutazione basata sull'utilizzo di funzioni di ordine superiore, list comprehension, lazy evaluation.

Es 1.2 (punti 5)

Si desidera ora avere una funzione di ordine superiore che disegna non solo una funzione, ma una lista di funzioni. Si scriva la funzione di ordine superiore

Ad esempio, supponiamo che si voglia tracciare anche l'asse x insieme alla parabola. Invocando

si otterrà la matrice:

Si definisca la funzione visualizzaMatFunzioni.

Es 1.3 (punti 4)

Si desidera ora salvare la visualizzazione delle funzioni in un'immagine di tipo PGM, la cui struttura è definita sotto.

Nel formato PGM, le immagini sono rappresentate come file di testo. Inizialmente il file contiene, separati da spazi:

• la stringa "P2"
• la larghezza W dell'immagine (intero)
• l'altezza H dell'immagine (intero)
• il numero S di sfumature

Ci sono poi W×H numeri interi che vanno da 0 a S; i numeri rappresentano l'intensità di ciascun pixel dell'immagine:

• 0 rappresenta il colore nero,
• S rappresenta il bianco
• e i numeri intermedi rappresentano le varie tonalità di grigio.

Nel nostro caso, si desidera salvare in un'immagine la matrice generata al punto 1.2, in cui ogni valore True è rappresentato dall'intero 1 e ogni valore False dall'intero 0. Il numero di sfumature S sarà quindi 1.

Si scriva una funzione

che, data la lista di funzioni fs, la lista xs dei possibili valori di ascissa e la lista ys dei possibili valori di ordinata, salva sul file con nome filename l'immagine PGM che disegna le funzioni fs.

Ad esempio, invocando

si otterrà il file funzioni.pgm .

Esercizio 2 (punti 3)

Il catalogo di una biblioteca è fornito come spreadsheet in formato CSV (comma separated values). Il formato CSV è un file di testo, in cui si usa la virgola come separatore fra i campi, più il carriage return come separatore fra le righe (come in tutti i file di testo). All'interno di un campo, è possibile avere qualunque sequenza di caratteri che non comprenda la virgola. Se è necessario avere in un campo una stringa contenente la virgola, allora il campo va messo fra doppie virgolette: "". Si supponga per semplicità che all'interno di una stringa non possano esserci le doppie virgolette (le doppie virgolette si usano solo come delimitatore di stringa).

Ad esempio, se il file contiene

Camilleri,Il metodo Catalanotti,11.90,in prestito
Sicignano,"Io, te e il mare",13.60,"restituito, ma danneggiato"
Bassani,Il giardino dei Finzi-Contini,8.07,restituito
Orwell,1984,11.90,disponibile
Asimov,"Io, robot",9.35,in prestito

significa che lo spreadsheet contiene i dati raggruppati come nella seguente tabella:

Si desidera scrivere un programma Lex che sostituisce ogni virgola con un punto e virgola ';', a meno che non si trovi fra doppie virgolette. Nell'esempio precedente il programma dovrà produrre:

Camilleri;Il metodo Catalanotti;11.90;in prestito
Sicignano;"Io, te e il mare";13.60;"restituito, ma danneggiato"
Bassani;Il giardino dei Finzi-Contini;8.07;restituito
Orwell;1984;11.90;disponibile
Asimov;"Io, robot";9.35;in prestito

Si noti come le virgole all'interno delle stringhe non siano state sostituite. Si noti anche come, nella seconda riga, le virgole prima e dopo il numero 13.60 siano state sostituite.

Soluzione 1

visualizzaMatr xs ys f =
    reverse (map (\y -> [f x == y | x <-xs]) ys)

visualizzaMatFunzioni fs xs ys =
    foldl orMat (falseMat xs ys) (map (visualizzaMatr xs ys) fs)

map2 f xss =
    map (map f) xss

-- date due matrici di Bool, cstruisce la matrice degli or
orMat iss jss =
    zipWith (\is js -> zipWith (||) is js) iss jss

-- costruisce una matrice che ha lo stesso numero di righe della lista ys
-- e lo stesso numero di colonne della lista xs
-- e contiene solo valori False
falseMat xs ys = map (\_ -> [False | _ <- xs]) ys

visualizzaFunzioni fs xs ys filename = do
    let preamble = "P2 "++(show (length xs))++" "++(show (length ys))++" 1\n"
        outMat = (map2 (\x -> if x then "1 " else "0 ") (visualizzaMatFunzioni fs xs ys))
        string = foldr ((++).concatenaRiga) [] outMat
    writeFile filename (preamble++string)

concatenaRiga xs = (foldr (++) "" xs)++"\n"

Soluzione 2

STRINGA     \"[^\"]*\"

%%

{STRINGA}   printf("%s",yytext);
,           printf(";");

%%