Linguaggi di Programmazione (28 Febbraio 2014)




Esercizio 1
La seguente funzione Erlang firstList2secondList prende due liste non vuote di uguale lunghezza e restituisce una funzione che, preso un elemento della prima lista restituisce l'elemento della seconda lista nella stessa posizione.
In Erlang la funzione predefinita lists:nth(N,L) restituisce l'N-esimo elemento della lista L. Inoltre la funzione position prende un elemento ed una lista che lo contiene e restituisce la sua posizione. Notare inoltre l'uso di "fun" per denotare una funzione anonima.
firstList2secondlist(First,Second) -> 
              fun(Elem) -> N = position(Elem,First);
	                   lists:nth(N,Second)
	      end.
Scrivere la stessa funzione in Haskell, senza utilizzare funzioni ausiliarie come position e lists:nth.
Fornire il tipo principale calcolato da Haskell per la funzione definita.
Come mai in Haskell e' possibile fornire la funzione richiesta in modo semplice ed elegante, mentre in Erlang cio' risulterebbe piu' complesso?

Esercizio 2
Enunciare il teorema di Subject Reduction e quello di Progress per FJ.
Quali proprieta' di FJ ci garantiscono tali teoremi?
Enunciare poi i teoremi Reduction preserves safety e Progress of safe programs.
Quale altra proprieta' ci garantiscono?

Esercizio 3
Dire se il seguente termine possiede forma normale ed eventualmente fornirla insieme ai vari passi di riduzione:

(λxxx.((λxx.x)(xx)(λx.x)))x(xx)


Esercizio 4
Si consideri la seguente funzione Haskell 
factg g 0 = g 1

factg g n = (g n)*(factg g (n-1))
Poiche' il calcolo di (g n) potrebbe richiedere tempo, vogliamo definire la stessa funzione in Erlang in modo che il calcolo di (g n) venga eseguito da un processo, mentre altri processi si occupano del calcolo di (factg g (n-1)).
Esercizio 5
Cos'e' la structural congruence per i termini del pi-calcolo?
La seguente condizione, che deve essere soddisfatta dalla structural congruence, e' scritta correttamente? 
   P | new x in Q   ≡  new x in (P | Q)
Perche' e' indispensabile postulare la validita' di questa condizione? qual e' il suo scopo?

Esercizio 6
Si consideri il seguente programma Prolog: 
permutation([], []).                                          

permutation(List, [Element | Permutation]) :-                
                                 select(Element, List, Rest),
                                 permutation(Rest, Permutation).
Se forniamo all'interprete il seguente goal 
?- permutation([a,b],P).
dire, descrivendo brevemente come si comporta l'interprete, qual e' il primo subgoal relativo al predicato permutation che viene prodotto durante la ricerca di una soluzione.