Linguaggi di Programmazione (6 Luglio 2012)

Esercizio 1
Sia    data InfNBT = Join Int InfNBT InfNBT
il tipo di dato degli alberi binari con rami infiniti ed etichette numeriche.
Si definisca myIT come il seguente elemento di InfNBT 
                        
                          1
                         / \
                        /   \
                       /     \
                     2         3
                   /  \       /  \
                 4      5     6   7
                / \    / \   / .......
               8   9  10 11 12 ........
               .......................
e poi si definisca la funzione levelOrder :: InfNBT → [Int] che restituisce la lista delle etichette di un albero infinito ordinate livello per livello da sinistra a destra.
Per esempio, la valutazione di (levelOrder myIT) produrra' la lista infinita di tutti gli interi a partire da 1.
(Una possibile soluzione potrebbe utilizzare una funzione che, preso un albero ed un numero n, restituisca la lista di tutti i sottoalberi di livello n)
Si scriva inoltre la piu' breve espressione Haskell il cui valore e' la lista di tutti gli interi a partire da 1.
Esercizio 2
Discutere brevemente del concetto di subtyping e del suo uso in Haskell, Pict e OCaml.
Esercizio 3
A.A. 11/12 Dimostrare formalmente che in Pict si puo' sostituire un canale di tipo ![T1 ![T2]] con uno di tipo ![T1' ![T2']] se si suppone che T1<:T1' e che T2'<:T2
A.A.precedenti (e A.A. 11/12 per chi non riesce a fare l'esercizio precedente)
Definire un processo Core PICT che stampi (non necessariamente nel loro ordine) tutti i numeri dispari.
Esercizio 4
Enunciare il Teorema di Confluenza del λ-calcolo ed utilizzarlo per dimostrare la proprieta' di unicita' della forma normale.
Esercizio 5
Il seguente codice Prolog dovrebbe calcolare i numeri di Fibonacci.
Dopo aver trovato la soluzione pero' il programma ne cerca una seconda e va in loop. Perche'? Modificare il programma in modo che restituisca solo la soluzione corretta, giustificando le modifiche fatte. 
fib(0,1).
fib(1,1).
fib(N,M) :- P is N-1, Q is N-2, fib(P,N1), fib(Q,N2), M is N1+N2.
Esercizio 6
Descrivere brevemente cosa si intende per Discrete Syncronous Programming e