Dipartimento di Informatica e Scienze dell'Informazione

Programma

Elementi di un linguaggio di programmazione

• Generalità, storia, diversi paradigmi (Sethi Cap.1, Ghezzi-Jazayeri Cap.1).
• Sintassi
  Stringhe e linguaggi, grammatiche libere da contesto, alberi di derivazione, ambiguità e tecniche per eliminarla, algebre sintattiche e sintassi astratta, grammatiche come definizioni induttive. Analisi lessicale e sintattica dei linguaggi di programmazione. Schema di implementazione di un analizzatore lessicale (scanner) e di un analizzatore sintattico (parser).
• Semantica statica
  Vincoli contestuali. Nozione di ambiente, scope, variabili libere e legate. Semantica statica di un semplice linguaggio funzionale e di un semplice linguaggio imperativo. Schema di implementazione di un analizzatore statico (type-checker).
• Semantica (dinamica)
  Principi di semantica denotazionale. Semantica operazionale a piccoli passi. Semantica di un semplice linguaggio funzionale e di un semplice linguaggio imperativo. Schema di implementazione di un interprete.

Paradigma Object Oriented

• Tipi di dato ed oggetti
  Paradigma ADT (moduli corrispondenti a tipi dai dato). Possibilità di implementare ADT in Pascal, C, Ada. Da tipi di dato ad oggetti.
• Oggetti e classi
  Classi, attributi e metodi. Diverse nozioni di uguaglianza tra oggetti e copia. Clientship. Uso di this. Campi e metodi di classe. Confronto con i puntatori. Esempi di programmazione "ad oggetti". Inizializzazione e distruzione di oggetti.
• Inheritance e sottotipo
  Classi eredi, overriding. Binding dinamico. Importanza dell'inheritance per lo sviluppo incrementale del software. Esempi di classi wrapper. Inheritance e visibilità. Interfacce e classi astratte. Un esempio di implementazione di tipo di dato (le liste). Regole di tipo nell'overriding e problemi collegati. Varianti della nozione di inheritance.
• Java
  Le nozioni precedenti nel caso di Java. Generalità. Blocchi di inizializzazione statici. Array. Uso di super. Costruttori. Hiding di campi. Risoluzione dell'overloading. Casting. Eccezioni. Package. Visibilità e modificatori. Cenni alle classi predefinite. Confronto con C e C++.
• Uso di asserzioni.
  

Paradigma Funzionale

• Generalità. Definizioni di funzioni, applicazione.
• Polimorfismo. Variabili di tipo, politipi, tipo principale. Tipo dell'uguaglianza.
• Funzioni higher order. Espressioni di tipo funzionale. Applicazione parziale. Currying.
• Definizioni per pattern-matching.
• Liste ed algoritmi relativi (append, reverse, flatten, algoritmi di sorting, etc.). Funzioni higher order su liste (map, itlist, filter, etc). Algoritmi su liste
• Uso di parametri di accumulazione. Simulazione di strutture di controllo imperative.
• Tipi user-defined (prodotto e somma). Tipi ricorsivi. Alberi. Visite. Binary Search Tree.
• Eccezioni in Caml.
• Correttezza di definizioni di funzioni e sua prova con tecniche induttive (induzione aritmetica, induzione aritmetica completa, induzione strutturale nel caso di liste ed alberi, ...).

Paradigma Logico

• Generalità. Sintassi dei programmi logici (termini, atomi, literal, clausole di Horn).
• Semantica model-theoretic: universo e base di Herbrand, interpretazione, modello e modello minimo di un programma logico. Programmi logici come definizioni induttive.
• Semantica di punto fisso (bottom up).
• Semantica operazionale (top down). Sostituzioni, unificatori, mgu. Derivazioni ed alberi SLD.
• Tecniche di programmazione logica. Database programming. Implementazione di strutture dati induttive (numeri naturali, liste, alberi) ed algoritmi relativi (somma, member, append, reverse, algoritmi di ordinamento, visite, Binary Search Tree, etc.).
• Correttezza di programmi logici e sua prova con tecniche induttive.
• Valutazione della complessità di programmi logici attraverso gli alberi di prova.
• Modello di esecuzione di Prolog e differenze con il modello dei programmi logici.

Testi consigliati

• R.Sethi. Programming Languages: Concepts and Constructs (Seconda Edizione). Addison-Wesley, 1996. Disponibile in biblioteca.
• C. Ghezzi, M. Jazayeri. Programming Language Concepts (Terza Edizione). John Wiley & Sons, 1997. Disponibile in biblioteca la prima edizione in italiano (1989).
• K. Arnold, J. Gosling. The Java Programming Language (Terza edizione). Addison-Wesley, 2000. Disponibile in biblioteca; disponibile anche la prima edizione in italiano (Java : didattica e programmazione, 1997).
• J. Gosling, B. Joy, G. Steele. The Java Language Specification. Addison-Wesley, 1996. Disponibile in biblioteca.
• J. Gosling, B. Joy, G. Steele, G. Bracha. The Java Language Specification (Seconda Edizione). Addison-Wesley, 2000. Disponibile in in biblioteca.
• JDK 1.2 API Documentation (documentazione delle classi predefinite)
• B. Eckel. Thinking in Java. 1998
  
• M. Mauny. Functional programming using Caml Light. Gennaio 1995.
• C. Reade. Elements of Functional Programming (Capitoli 1-3, 5). Addison-Wesley, 1989. Disponibile in biblioteca.
• L. Sterling, E. Shapiro. The Art of Prolog (Capitoli 1-9). MIT Press, 1994. Disponibile in biblioteca.
• Programming Systems Group, Swedish Institute of Comp. Sci. SICStus Prolog User's Manual.