Dipartimento di Informatica e Scienze dell'Informazione

Anno Accademico 96/97

Corso di

Linguaggi di Programmazione

Docente: Professor Catuscia Palamidessi

Guida all'esame

L'esame si svolge in due parti: la prova scritta e la prova orale. L'orale si svolgera' in genere qualche giorno dopo lo scritto, e saranno ammessi solo coloro che avranno superato lo scritto con almeno 15/30, e che avranno svolto il progetto. Il progetto si puo' consegnare e discutere prima dell'orale, o, al limite, durante l'orale. La discussione del progetto sara' mirata a verificare che ogni componente del gruppo abbia partecipato attivamente al progetto, e che conosca approfonditamente i dettagli di tutto lo svolgimento.

Prossime date d'esame

Prova Scritta

• Data un'espressione E, dire se E e` tipabile, e, in caso affermativo, derivare formalmente il suo tipo piu' generale. Esempi di tale espressione possono essere:
  • lambda x. lambda y. x
  • lambda x. lambda y. (x y)
  • lambda x. lambda y. (x,y)
  • lambda x. lambda x. (x x)
  • let x = lambda y.y in (x x)
  
  
• Data un'espressione di tipo T, dire se esiste una espressione E di ML puro (cioe' senza primitive) che abbia tale tipo, e, in caso affermativo, dire se T e` il tipo piu` generale di E. Esempi di tale T possono essere:
  • a -> a -> a
  • a -> b -> (a x b)
  • (a -> a) -> (a -> a)
  • (a -> a) -> a
  • (a -> b) -> (b -> b)
  
  Nota: ricordare che i tipi delle espressioni corrispondono a tautologie del calcolo intuizionista, quindi se abbiamo una formula che non e` una tautologia, come nel caso di (a -> a) -> a, potremmo dedurre che essa non e` il tipo di nessuna espressione. Nel compito bastera` dire questo (cioe` dire: "tale formula non e` il tipo di nessuna espressione perche' non e` una tautologia") e dimostrare che non e` una tautologia.
  
  
• Qualche esercizio "concettuale" tipo:
  • cosa succederebbe se in un linguaggio eager (come ML) si sostituisse il costrutto if-then-else con una funzione ite dichiarata da
    fun ite true y z = y | ite false y z = z Hint: pensare alla tipica definizione di una funzione ricorsiva ....
  • Considerare i termini (lambda f. (f 2, f true))(lambda x.x) e let f = lambda x.x in (f 2, f true) Dire se sono equivalenti, sia dal punto di vista statico (stesso tipo) che dal punto di vista dinamico (riduzioni allo stessa forma normale)
    
  
  
• ... Si suggerisce di consultare anche i testi degli esami precedenti.

  Prova Orale

  L'orale sara` teso ad esaminare che il candidato abbia assimilato le nozioni fondamentali presentate nel corso. Esempi tipici di domande che verranno poste all'orale sono:
  • Mi dica quali sono le caratteristiche principali della programmazione funzionale.
  • Mi parli della programmazione Higher-Order
  • Mi parli dell'implementazione della ricorsione
  • Mi descriva formalmente (tramite le regole di riduzione) la differenza fra valutazione eager e lazy
  • Mi faccia un esempio di un generatore della sequenza di tutti i numeri pari, usando un linguaggio lazy
  • Mi parli del concetto di Type System
  • Mi descriva il Type System del sottoinsieme di ML corrispondente al Lamda calcolo
  • Mi parli delle complicazioni che sorgono (per il Type System) quando si vuole introdurre il costrutto let
  • Mi parli delle differenze fra programmazione logica e funzionale
  • Mi enunci i teoremi di correttezza e completezza per la SLD-resolution
  • Mi scriva un programma (in un linguaggio dichiarativo a sua scelta) che prenda due alberi e controlli se il primo e' sottoalbero del secondo
  • Mi parli dei vantaggi del Lambda Prolog rispetto al Prolog
  • Mi parli del concetto di classe ed oggetto
  • Mi parli dell'inheritance nei linguaggi Object Oriented
  • Mi parli dei vantaggi della programmazione Object Oriented (in particolare, riguardo ai meccanismi di astrazione)
  • Mi descriva come implementerebbe una classe "lista" in C++
  • ...