Docente

Prof. Marco Comini marco.comini@uniud.it

Crediti

9 CFU

Finalità

Questo corso, in congiunzione con il corso di Linguaggi e Compilatori, intende fornire una conoscenza delle caratteristiche dei vari paradigmi di programmazione, cercando il più possibile di evitare di concentrarsi su uno specifico linguaggio, andando bensì a presentare i principi che guidano la progettazione, realizzazione e implementazione dei moderni linguaggi di programmazione. Con solida conoscenza delle caratteristiche “universali” si potrà così in futuro imparare nuovi linguaggi in pochissimo tempo.
A questa visione generale si giunge attraverso la descrizione dei principali paradigmi di programmazione: imperativo, funzionale, logico e logico-funzionale. Questi paradigmi, oltre a essere esaminati nei loro aspetti pragmatici più immediati, sono analizzati e confrontati sulla base dei principi generali, in modo tale da permettere una comprensione critica della maggior parte dei linguaggi di uso comune. In questo modo s’intende sviluppare uno spirito critico che permetta di arrivare a una programmazione consapevole in cui saper scegliere il paradigma più adatto a seconda del problema da risolvere e sapere quali costrutti di un linguaggio usare, e a quale costo.
I due corsi intendono inoltre fornire una conoscenza relativamente approfondita (soprattutto dell'aspetto programmativo) dei paradigmi di programmazione dichiarativa (funzionale, logico e logico-funzionale) che, grazie alla loro espressività, si prestano naturalmente quale base di sviluppo di software corretto. Grazie a ciò si forniscono i concetti fondamentali per valutare come sfruttare al meglio la programmazione in uno specifico paradigma, vedendone anche le problematiche di implementazione, e per saper valutare il linguaggio più adatto in un paradigma di programmazione rispetto al problema applicativo da risolvere.
Questo corso, in particolare, tratterà i concetti generali, il paradigma imperativo e quello funzionale. Nello specifico si occuperà di: comprendere i concetti di macchina astratta, compilazione ed interpretazione di linguaggi di programmazione; implementazione dei moduli di analisi lessicale e sintattica di un compilatore mediante i più diffusi strumenti come flex/alex e bison/happy; studiare le relazioni tra tecniche di progetto, semantica ed implementazione dei linguaggi di programmazione; studiare i modelli e le principali tecniche classiche per l’implementazione di linguaggi del paradigma imperativo ed orientato agli oggetti; studiare le tecniche di programmazione mediante funzioni di ordine superiore tipiche del paradigma funzionale.
Il corso di Linguaggi e Compilatori completerà la presentazione dei paradigmi dichiarativi, illustrando i paradigmi logico e logico-funzionale. Inoltre introdurrà le principali problematiche, soluzioni e tecniche concernenti il front-end di un compilatore, da sorgente a codice intermedio.

Programma

Aspetti Generali e Paradigma Imperativo
• Macchine astratte, Interpretazione e Compilazione (proiezioni di Futamura)
• Descrivere un linguaggio di Programmazione (Sintassi e Semantica)
• Introduzione alla struttura dei compilatori (e tecnica bootstrapping)
• Labelled BNF Grammar Formalism e il tool BNFC
• Analisi lessicale
o Grammatiche Regolari ed Espressioni Regolari
o Generatori di Analizzatori Lessicali (Flex e Alex)
o Automi riconoscitori (NFA, DFA, minimizzazione)
• Analisi Sintattica
o Grammatiche libere da contesto
o Generatori di Analizzatori Sintattici (Bison e Happy).
o Vincoli di semantica statica
• I nomi e l'ambiente
• La gestione della memoria
• Strutturare il controllo
• Astrarre sul controllo (Metodi di passaggio dei parametri)
• Un esempio di Macchina Astratta completa: P-code Machine.
• Strutturare i dati
• Sistemi di Tipi monomorfi e polimorfi
o Semplice linguaggio imperativo tipizzato
o Il sistema di tipi (indecidibile) dei linguaggi funzionali e la regola di ML
o cenni all'implementazione di Type checking e type inference
Paradigma Funzionale
• Introduzione alla Programmazione Funzionale.
• High-order Programming.
• Il linguaggio Haskell
o list comprehensions, partial applications of curried functions, sections, non-strict functions, infinite data structures, case expressions, pattern matching
o Types, Classes and Overloading
o Haskell's monadic I/O
o Standard Haskell Classes
o Monads
o Modules

Bibliografia

• M. Gabbrielli, S. Martini. Linguaggi di Programmazione - Principi e Paradigmi. McGraw-Hill. ISBN 88-386-6261-4
• Hudak, Fasel. A gentle introduction to Haskell, 1992
• B. Wadler, Introduction to Functional Programming using Haskell. ISBN: 0134843460, Prentice Hall PTR, 1998
• N. D. Jones, C. K. Gomard, P. Sestoft. Partial Evaluation and Automatic Program Generation. Prentice-Hall, Englewood Cliffs, NJ, 1993.

Modalità d'esame

Progetto a gruppi, scritto e orale individuali