Linguaggi e Compilatori I e II 2015/2016
(LC1=Linguaggi di Programmazione laurea triennale, LC2=Linguaggi e Compilatori
laurea magistrale)
pagina aggiornata il
08-10-2015
There are two ways of constructing a software design: one way is to make it
so simple that there are obviously no deficiencies, and the other way is to
make it so complicated that there are no obvious deficiencies. The first
method is far more difficult.
[C. A. R. Hoare]
Nota sui contatti via email: vi prego di non mandare
email doppie/triple a tutti gli indirizzi email a mia disposizione, son tutti
alias e le email arrivano nella stessa casella. Fate invece attenzione a non
mandare email al Prof. Gianni Comini. Potete recuperare l'email "master"
dal cercapersone o nel sito di eLearning
(non la riporto qui per non dare
feedback ai robot cerca e-mail)
Indice
Finalità del corso
I corsi di Linguaggi e Compilatori I e II, intendono 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 potranno 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 si intende sviluppare uno
spirito critico che permetta di arrivare ad 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
(soprattutto) a quale costo.
I due corsi inoltre intendono 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. Si mostrerà come caratteristiche
quali high-order e non-determinismo possano essere sfruttate per scrivere
codice compatto, elegante e flessibile (riutilizzabile).
Il corso di Linguaggi e compilatori I, in particolare, tratterà
innanzitutto i concetti generali, fornendo una conoscenza “language
independent” delle caratteristiche di tutti i paradigmi. Si vedranno
poi il paradigma imperativo e i meccanismi di supporto a
“run-time” dei linguaggi imperativi. Dopodiché si
illustreranno le caratteristiche del paradigma funzionale (specialmente
l'high-order programming).
Il corso di Linguaggi e compilatori II, in particolare,
illustrerà i modelli d'esecuzione dei linguaggi funzionali e poi
completerà la presentazione dei paradigmi dichiarativi: logico e
logico-funzionale (specialmente il non-deterministic high-order
programming).
Programma
Linguaggi e Compilatori 1
- Aspetti Generali e Paradigma Imperativo
- Macchine astratte, Interpretazione e Compilazione
[Gabbrielli-Martini]
- Descrivere un linguaggio di Programmazione (Sintassi e
Semantica) [Gabbrielli-Martini]
- Introduzione alla struttura dei compilatori (e tecnica
bootstrapping)
- Labelled BNF Grammar Formalism
- il tool BNFC
(nel sito di eLearning
potete trovare esempi fatti a lezione, IMPY, un prototipo per
OCL 2.0)
- Analisi lessicale
- Grammatiche Regolari
- Espressioni Regolari
- Generatori di Analizzatori Lessicali (Lex + esempi,Alex + esempi
visti a lezione nel sito di eLearning).
- Automi riconoscitori (NFA,DFA,minimizzazione)
- Generatori di Analizzatori Sintattici
(Happy + esempi
visti a lezione nel sito di eLearning,
Yacc +
esempi).
- I nomi e l'ambiente [Gabbrielli-Martini]
- La gestione della memoria [Gabbrielli-Martini]
- Strutturare il controllo [Gabbrielli-Martini]
- Astrarre sul controllo (Metodi di passaggio dei parametri) [Gabbrielli-Martini]
- Un esempio di Macchina Astratta: P-code Machine.
Per informazioni dettagliate e approfondimenti si vedano:
- Strutturare i dati [Gabbrielli-Martini]
- Type Systems monomorfi e polimorfi
- Semplice linguaggio imperativo tipizzato
- Il sistema di tipi (indecidibile) dei linguaggi funzionali
e la regola di ML
- cenni all'implementazione di Type checking e type inference
- Paradigma Funzionale
- Introduzione alla Programmazione Funzionale.
- High-order Programming.
- Il linguaggio Haskell (tutorial, libro
online, prelude, nel sito di eLearning
potete trovare file usato a lezione per le demo e miei esempi).
[Si vedano inoltre i corsi
online della Microsoft]
- list comprehensions, partial applications of curried
functions, sections, non-strict functions, infinite data
structures, case expressions, pattern matching
- Types, Classes and Overloading
- Haskell's monadic I/O
- Standard Haskell Classes
- Monads
- Modules
Linguaggi e Compilatori 2
- Paradigma Logico
- Paradigma Logico-Funzionale
- High-order Non-deterministic Programming.
- Il linguaggio Curry (tutorial,
un implementazione: MCC/AquaCurry, nel sito di eLearning
potete trovare file
usato a lezione per le demo, miei
esempi).
- Modelli di esecuzione dei linguaggi dichiarativi
- Paradigma funzionale: Sistemi
di riscrittura, Pattern Matching e Unificazione
- Paradigma logico:
Unificazione, SLD-derivations
- Semantica denotazionale della Programmazione Logica.
- Paradigma Logico Funzionale: narrowing
(needed
narrowing).
- Teoria base dei compilatori
- Parsing top-down (Esempi
Haskell)
- Parsing bottom-up (SLR,LR,LALR)
- Syntax Directed Translation
- Grammatiche ad Attributi
- S-attributed e L-attributed SDD
- Semantica Statica
- Type Checking via Attributed Grammars
- Generazione di Codice Intermedio (three address code)
- Traduzione espressioni con accessi in array
- Traduzione Control flow: eager/lazy conditionals
- Control flow non ottimizzato. Tecnica fall-through. Back
Patching. Gestione
break/continue.
- readuzione di Procedure/Funzioni e chiamate
- Continuation Passing-Style con linguaggi funzionali.
- Cenni alla generazione di codice intermedio di linguaggi funzionali
Bibliografia (Libri e Testi di consultazione)
- Linguaggi in generale
-
M. Gabbrielli e S. Martini. Linguaggi di Programmazione
- Principi e Paradigmi.
McGraw-Hill. ISBN 88-386-6261-4
- Paradigma imperativo
- D.W. Barron (Ed). PASCAL: The Language and Its Implementation.
John Wiley & Sons Ltd, 1981
- F. W. Schröer The
GENTLE Compiler Construction System. R. Oldenbourg Verlag, 1997, ISBN 3-486-24703-4
- L. Cardelli. Type
Systems. Handbook of Computer Science and Engineering. CRC Press, 1997.
- Paradigma funzionale
- P. Hudak, J. Peterson, J. Fasel. A Gentle Introduction
to Haskell 98.
1999
- B. O'Sullivan, D. Stewart, J. Goerzen. Real
World Haskell. O'Reilly Media, 2008.
- B. Wadler. Introduction to Functional Programming using Haskell.
ISBN: 0134843460, Prentice Hall PTR, 1998
- Terese. TERESE
LITE. Vrije Universiteit, 2006. (estratto
dal libro Term
Rewriting Systems.
Cambridge Tracts in Theoretical Computer Science, Vol. 55, Cambridge
University Press, 2003)
- Paradigma Logico
- L. Sterling, E. Shapiro. The art of Prolog, MIT Press, 1986.
- K. R. Apt, From Logic Programming to Prolog, International
Series in Computer Science, Prentice Hall, 1997.
- Hassan Aït-Kaci. Warren's
Abstract Machine: A Tutorial Reconstruction,
MIT Press, 1991, ISBN 0-262-01123-9. FUORI STAMPA
- Paradigma Logico-Funzionale
Esercizi di Programmazione
Per chi volesse esercitarsi a programmare in uno dei paradigmi visti a lezione
ho scritto alcuni
esercizi a difficoltà (più o meno) crescente. Vi consiglio
fortemente di non scriverli solo su carta ma provare ad eseguirli (ci sono ottime
implementazioni freeware disponibili sia di Prolog che di Haskell). Quando poi
siete ragionevolmente sicuri di aver fatto un programma funzionante secondo la
specifica (che implica averlo provato a calcolatore), se volete avere i miei
commenti su quanto avete fatto (e, se siete a buon punto, avere le mie soluzioni)
mandatemi via mail quanto avete fatto oppure (anche meglio) portatemi tutto a
ricevimento. Didatticamente reputo controproducente mettervi on-line le mie soluzioni
perché altrimenti restereste influenzati dalla mia soluzione prima di metabolizzarne
una vostra. Inoltre vi sconsiglio di fare tutti gli esercizi e mandarmi tutto
in blocco alla fine: meglio fare 2/3 esercizi e poi, prima di affrontare quelli
più complessi,
verificare quanto appreso per poi trarre profitto dall'esperienza fatta nell'affrontare
i nuovi esercizi ed evitare di ripetere gli stessi errori.
- Haskell: Il file aggiornato contenente la lista di Esercizi
di programmazione Hakell si può scaricare dal sito di eLearning
- Nella Home
di Haskell potere trovare moltissima documentazione sul linguaggio
e i links a varie implementazioni
freeware, fra cui GHC.
- Consiglio l'uso di hlint
sui vostri programmi per imparare ad evitare certi tipi di errori
- Per non impararsi molte informazioni tecniche a memoria si
può usare
il comodissimo Hoogle (sia on-line
che in locale)
- Prolog: Il file aggiornato contenente la lista di Esercizi
di programmazione Prolog si può scaricare dal sito di eLearning
- Curry: Per iniziare si possono riadattare gli esercizi
di programmazione Hakell, avendo cura di evitare il non-determinismo (implicito)
non voluto. Poi si possono affrontare gli esercizi
di programmazione Curry che
sfruttano le caratteristiche peculiari del paradigma logico-funzionale, testo
scaricabile dal sito di eLearning.
Implementazioni free
Modalità d'esame corsi attuali
Si veda nel sito di eLearning.
Modalità d'esame corsi anni accademici precedenti
Con le stesse modalità che erano previste quando si é seguito il corso
Testi degli esami passati
Potete inoltre scaricare in formato elettronico (parte dei) testi
dei compiti passati nel sito di eLearning.