Linguaggi di Programmazione (23 Giugno 2010)

Esercizio 1
(a) Cosa si intende per Principal Pair nel lambda calcolo? Descrivere l'algoritmo di principal pair.
(b)
  • Definire in Haskell i tipi di dato Abn ("Albero binario con etichette numeriche") e Abf ("Albero binario con etichette di tipo Int -> Int"). Definire due semplici elementi di tipo Abn e Abf.
  • Definire una funzione Haskell 
    appT :: Abf -> Abn -> Abn
    che prenda un albero Abf ed uno Abn con la stessa struttura (non occorre implementare il controllo che abbiano la stessa struttura) e restituisca un albero Abn (con la stessa struttura degli alberi in input) in cui le etichette corrispondano alle applicazioni delle funzioni dell'albero Abf ai numeri dell'albero Abn.
  • (da fare solo se si e' svolto almeno un punto dell'esercizio 2 e almeno un punto del 3) Nel caso di alberi con struttura differente, e volendo gestire tale situazione non con la generazione di un messaggio di errore, si potrebbe utilizzare la monade Maybe. Ridefinire quindi la funzione appT in modo che abbia il seguente tipo 
    appT :: Abf -> Abn -> (Maybe Abn)
    Esercizio 2
    (a) Definire in generale la nozione di sottotipo. Quali sono i tipi utilizzati in PICT? Esiste in PICT la nozione di sottotipo? In caso affermativo, come viene definita ed utilizzata? In caso negativo, perche' tra i tipi di PICT non e' possibile definire la nozione di sottotipo?
    (b)
  • Quali aspetti di Java non sono rappresentati nel calcolo FJ?
  • Descrivere il significato della seguente regola di tipo di FJ
    • Esercizio 3
    (a) Cosa si intende per "Observable Nondeterminism"?. E' presente nel paradigma chiamato "Declarative concurrency"? Giustificare la risposta.
    (b) Si consideri il seguente programma PROLOG. Esso determina se, dato un grafo orientato ed aciclico (rappresentato tramite un predicato myGraph tra nodi) e due nodi, esiste un cammino tra i due. 
    path(X,X).
path(X,Y) :- myGraph(X,Z), path(Z,Y).
  • Modificare il programma in modo tale che si possa sapere, non solo se esiste un cammino tra due nodi, ma anche quali sono i possibili cammini.