Programmazione Funzionale 2006/2007

Ogni anno ci sono due borse erasmus da 5 a 9 mesi ciascuna per l'Isola della Réunion (Oceano Indiano, Francia). Anche quest'anno andranno perse? Clicca qui per saperne di piú.

• Si parta dalla seguente implementazione di una coda FIFO. Dal momento che la programmazione funzionale non ammette l'assegnamento distruttivo, l'inserzione in coda può solo essere effettuata o creando una nuova coda con un elemento in piú (prima possibilità) o, come facciamo in questa implementazione, rappresentando la coda come due liste f ed r. La lista f è la front list, cioà la lista dei primi elementi della coda. La lista r è la rear list, cioè la lista degli ultimi elementi della coda, mantenuta in ordine inverso. Per ottenere la lista degli elementi della coda si potrebbe quindi scrivere append f (reverse r). Si mantiene l'invariante che se f è vuota allora anche r è vuota. Si giustifichi la scelta di questa implementazione rispetto alla prima possibilità. Si scriva poi una funzione invert che inverte una coda. Questo significa che l'ultimo elemento deve diventare il primo e viceversa. Tale funzione deve essere esportata all'esterno del tipo Queue.
• Si scriva un tipo Tree che implementa una segnatura TREE per alberi binari. Tali tipo/segnatura devono avere funzioni per creare l'albero vuoto, per creare un albero, dati i due sottoalberi e la radice, e per ordinare l'albero in modo che il sottoalbero sinistro di ciascun nodo abbia altezza non minore del sottoalbero destro dello stesso nodo. Tale funzione deve lavorare in tempo lineare nel numeri dei nodi dell'albero.
• Si scriva un tipo Grammar con una funzione getEmpty che restituisce una grammatica vuota e una funzione addRule che aggiunge a una grammatica una produzione, restituendo la grammatica risultante. Terminali e non terminali sono elementi di un qualche tipo Atom che dovete definire. Una regola è un elemento di un tipo coppia formato da un Atom (il lato sinistro) e da una lista di Atom (il lato destro). Infine si aggiunga al tipo Grammar un metodo derive k che restituisce la lista di tutte le forme sentenziali derivabili in al piú k passi dal primo non terminale a sinistra della prima regola inserita nella grammatica. Si definisca quindi un metodo derive_ground k che restituisce le sole forme sentenziali di cui sopra che sono fatte da soli terminali.
• La nostra compilazione dei lambda termini traduce termini del tipo 3 + (4 + 5) in del codice che a tempo di esecuzione somma a 3 la somma di 4 e di 5. In laboratorio avevamo un po' ottimizzato tale compilazione evitando di sommare 4 e 5 ma precalcolando a tempo di compilazione il risultato 9. Purtroppo la somma con 3 veniva effettuata ancora a tempo di esecuzione. Si definisca una funzione intConstant che determina se un lambda-termine è una costante intera, cioè contiene solo operazioni aritmetiche fra numeri interi. In particolare, se un lambda-termine contiene una variabile allora non è una costante intera. Si usi tale funzione per modificare lo schema di compilazione in modo che nell'esempio precedente si generi del codice che carica in cima allo stack, al posto dell'ambiente, il valore 12.

• una funzione che calcola la lista delle variabili libere in una lambda espressione
• una funzione che calcola la lista delle variabili che occorrono legate in una lambda espressione
• una funzione che calcola la lista delle variabili che occorrono libere in una lambda espressione

• Si parta dalla precedente implementazione dell'inferenza dei tipi e si aggiungano le costanti empty e cons con segnatura empty:list(α) e cons:α×list(α)->list(α). Si modifichi la definizione di ml_type e la funzione inferAux in modo da inferire i tipi per lambda-termini che usano anche tali costanti.
• Si aggiunga quindi una funzione occurs_in_type n t che determina se la variabile di tipo numero n occorre nel tipo t, una funzione occurs n l che determina se la variabile di tipo numero n occorre nella lista l di vincoli (cioè una lista di coppie di tipi), una funzione substitute_in_type n t1 t2 che sostituisce ogni occorrenza della variabile di tipo numero n nel tipo t2 col tipo t1 e una funzione substitute n t1 l che fa lo stesso per una lista di vincoli l.
• La soluzione è qui.

• Si parta dalla precedente implementazione dell'inferenza dei tipi con unificazione e si aggiunga la possibilità di unificare vincoli che usano il funtore di tipo List. Si provi l'inferenza di tipo su exp6 ed exp8.
• Si defisca un tipo per degli alberi binari i cui nodi contengono valori di tipo arbitrario.
• Si definisca una funzione complete x d che che crea un albero binario completo di altezza d i cui nodi contengono tutti x. Un albero binario è completo quando le sue foglie sono tutte allo stesso livello. Tale funzione deve lavorare in tempo O(d).
• Si definisca una funzione balanced x n che restituisce un albero binario massimamente bilanciato i cui nodi contengono tutti x. Un albero binario è massimamente bilanciato quando, preso un qualsiasi nodo q, la differenza del numero di nodi dei due sottoalberi di q è al piú uno. Tale funzione deve lavorare in tempo O(log n). Suggerimento: si definisca una funzione ausiliaria create2 x m che restituisce una coppia di alberi binari massimamente bilanciati, il primo con m nodi e il secondo con m+1 nodi, tutti contenenti x. Si ragioni sulla parità di n ed m.
• Soluzione dell'unificazione con tipi per liste. Soluzione delle due costruzioni di alberi binari completi e massimamente bilanciati.

• Si aggiunga alla implementazione degli heap sinistrorsi una funzione fromList: t list -> heap che crea un heap sinistrorso da una lista non ordinata di elementi, convertendo prima ciascun elemento della lista in un heap di un solo elemento e quindi fondendo gli heap risultanti fra di loro finché non ne resta che uno solo. Tale funzione deve lavorare in tempo lineare nella lunghezza della lista.
• La soluzione

• Si aggiunga agli stream una funzione fibs che restituisce lo stream infinito dei numeri di Fibonacci: [1,1,2,3,5,8,.... Suggerimento: si definisca una funzione ausiliaria fib_aux first second che restituisce lo stream infinito dei numeri di Fibonacci a partire da first e second (che si assume essere due numeri di Fibonacci consecutivi)
• Si definisca una funzione union s1 s2 che restituisce l'unione di due stream s1 ed s2. Si richiede che se x è un elemento di s1 o di s2 allora x figura nell'unione dopo un numero finito di elementi che lo precedono. Questo implica che, se s1 è infinito, non si può implementare la union come una append, la quale metterebbe prima tutti gli elementi di s1 e solo dopo tutti quelli di s2
• Si definisca una funzione primes che restituisce lo stream infinito dei numeri primi
• Ecco la soluzione

• Si aggiunga all'implementazione della compilazione dei lambda-termini un bytecode GT che sostituisce i primi due elementi dello stack con un booleano che dice se la cima dello stack è maggiore del valore che le sta sotto. Lo si usi per la compilazione di una nuova classe di sintassi astratta Gt da aggiungere ai lambda-termini
• Si scriva un lambda termine ack che rappresenta la sintassi astratta della funzione di Ackermann invocata su 3 e 2
• Si provi a compilare tale funzione: compile ack
• Si provi ad eseguirla: run ack. Si dovrebbe ottenere il valore intero 29
• Si ottimizzi lo schema di compilazione usando le seguenti osservazioni:
  • se uno degli addendi di un Plus è una IntConstant, si può caricare in cima allo stack il valore della costante intera senza duplicare e consumare il riferimento all'ambiente che c'è in cima allo stack all'inizio della valutazione del Plus. A tal fine, si aggiunga un bytecode PUSHINT(i) che aggiunge in cima allo stack il valore intero i senza modificare quel che sta sotto
  • se entrambi gli addendi di un Plus sono delle IntConstant, si può sostituire l'ambiente che sta in cima allo stack all'inizio della valutazione del Plus con il risultato dell'addizione, calcolato già in fase di compilazione
  • se l'argomento di una chiamata di funzione è una IntConstant, si può evitare di duplicare il riferimento all'ambiente prima di valutare l'argomento; ancora una volta, si usi il nuovo bytecode PUSHINT
• Fatte le precedenti ottimizzazioni, si provi a ricompilare il lambda-termine ack. Si dovrebbe ottenere del codice semplificato
• Si provi a rieseguire ack. Il risultato dovrebbe ancora essere 29
• Soluzione