Obiettivi formativi
Il corso intende fornire le nozioni di base sulla programmazione dichiarativa, illustrandone alcuni degli aspetti fondamentali tramite la presentazione e l'applicazione pratica del linguaggio di programmazione logica Prolog.
Prerequisiti
Le nozioni e le tecniche di base della programmazione convenzionale (ad esempio in C). Le nozioni di base riguardanti strutture dati fondamentali come liste, alberi e grafi. Le nozioni di base su funzioni e insiemi e su connettivi ed espressioni logiche. Familiarietà nell'uso del calcolatore.
Contenuti dell'insegnamento
I parte – Introduzione alla programmazione dichiarativa
II parte – Un linguaggio per la programmazione dichiarativa: il Prolog
III parte – Programmazione dichiarativa in Prolog
IV parte – Programmazione logica a vincoli
Programma esteso
Introduzione alla programmazione dichiarativa. Definizione, vantaggi, linguaggi di programmazione dichiarativa, forme di programmazione dichiarativa.
Principali caratteristiche dei linguaggi di programmazione dichiarativa.
Un linguaggio per la programmazione dichiarativa: il Prolog. Cenni allo sviluppo del Prolog.
Variabili e tipi di dato (termini semplici e composti). Clausole e programmi (sintassi).
Semantica. Interpretazione logica. Interpretazione procedurale. Invertibilita' predicati.
Unificazione e sostituzione.
Semantica operazionale. Derivazione. Albero di derivazione SLD. Insieme di successo.
Nondeterminismo e strategie di ricerca. Backtracking. Incompletezza.
Strutture dati: liste. Rappresentazione. Operazioni su liste. Stringhe.
Rappresentazione e manipolazione numeri.
Controllo backtracking ("cut"). Negazione per fallimento (cenni).
Programmazione dichiarativa in Prolog. Variabili logiche e unificazione. Strutture dati parzialmente specificate. Nondeterminismo e ricorsione.
Predicati built-in (extra-logici). Input-output: di termini, di caratteri, su file. Modifica dinamica del programma (cenni). Manipolazione di termini (cenni). Insieme delle soluzioni ('setof').
Meta-interprete Prolog (puro).
Sviluppo ed esecuzione di programmi in SWI-Prolog.
Programmazione logica a vincoli. Limitazioni del Prolog (dichiarativita', efficienza).
Nozione di vincolo e di risolutore. Esempi di Domini di vincoli.
Il CLP. Programma, computazione CLP, risoluzione di vincoli: propagazione e controllo di consistenza.
Interprete CLP scritto in Prolog.
Un esempio di CLP: CLP(FD). Vincoli FD. Risoluzione vincoli FD ("arc-consistency"). Regole di riduzione dei domini. Completezza. Calcolo delle soluzioni ("labeling")
Esempio della "colorazione di una mappa".
CLP(FD) in SWI-Prolog.
Bibliografia
L. CONSOLE, E. LAMMA, P. MELLO, M. MILANO: Programmazione logica e Prolog, II edizione (2012), UTET Università, pp. 432.
Metodi didattici
Lezioni frontali con esercitazioni assistite.
Modalità verifica apprendimento
L'esame consiste nella preparazione e discussione di esercizi di programmazione Prolog assegnati nella parte finale del corso e sviluppati in modo autonomo (con l'assistenza del docente) da ciascun studente, e in un esame orale su tutto il programma del corso, con eventuale discussione degli esercizi assegnati.
Altre informazioni
Pagina web del corso su ‘elly’, con informazioni aggiuntive su programmazione dichiarativa e Prolog e sugli esercizi assegnati.
