Linguaggi e Compilatori I e II 2013/2014
(LC1=Linguaggi di Programmazione laurea triennale, LC2=Linguaggi e Compilatori
laurea magistrale)
pagina aggiornata il
13-11-2013
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]
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 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 II, in particolare,
illustrerà i modelli d'esecuzione dei linguaggi funzionale 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
- Descrivere un linguaggio di Programmazione (Sintassi e
Semantica)
- Introduzione alla struttura dei compilatori (e tecnica
bootstrapping)
- Labelled BNF Grammar Formalism
- il tool BNFC
(in materiale didattico 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 nella pagina privata del corso).
- Automi riconoscitori (NFA,DFA,minimizzazione)
- Generatori di Analizzatori Sintattici
(Happy + esempi visti a lezione nella pagina privata del corso,
Yacc + esempi).
- 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: P-code Machine.
Per informazioni dettagliate e approfondimenti si vedano:
- Strutturare i dati
- 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, in materiale didattico 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, in materiale didattico potete trovare file
usato a lezione per le demo, miei
esempi).
- 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
- 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).
Bibliografia
-
M. Gabbrielli e S. Martini. Linguaggi di Programmazione
- Principi e Paradigmi.
McGraw-Hill. ISBN 88-386-6261-4
- P. Hudak, J. Peterson, J. Fasel. A Gentle Introduction
to Haskell 98.
1999
- L. Sterling, E. Shapiro. The art of Prolog, MIT Press, 1986.
Libri e Testi di consultazione
- 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
- 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
- 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 da Materiale
Didattico
- 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 da Materiale
Didattico
- 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 da Materiale
Didattico.
Implementazioni free
Modalità d'esame corsi attuali
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 su Materiale Didattico (non la riporto qui per non dare
feedback ai robot cerca e-mail)
L'esame di Linguaggi e compilatori 1 si compone di:
DA DEFINIRE
L'esame di Linguaggi e compilatori 2 si compone di:
DA DEFINIRE
- Progetto:
- Il progetto si svolge a gruppi e, dal momento della consegna del testo,
entro il tempo stabilito sopra si richiede di:
- svolgere degli esercizi a calcolatore
- scrivere una succinta relazione
- inviare i sorgenti dei programmi e il PDF della relazione via e-mail
entro la scadenza.
Si tenga presente che
-
In ogni caso alla scadenza si deve consegnare quanto
prodotto, anche nel caso si volesse riprovare.
- Ogni componente del gruppo che
ritira il testo di un progetto per la prima volta gode
di un bonus d'ingresso, che consiste in un incremento percentuale della propria valutazione.
- La relazione può contenere immagini passate a scanner
di grafici o figure (oppure si può concordare, al momento del ritiro,
per una consegna del cartaceo delle figure invece di includerle nel file
PDF ). L'utilizzo di sofisticati typesetting per grafici o figure non
influisce sulla valutazione (eventualmente indirettamente in negativo
se vi togliesse
tempo utile a svolgere meglio il resto del lavoro)
Chi non avesse già dei colleghi con cui formare
un gruppo può lasciarmi un recapito via mail che io provvederò a girare agli
altri nella stessa situazione
(son aperto a suggerimenti su come agevolare la costruzione dei gruppi)
Per
poter rititrare il testo dell'elaborato, preferibilmente il prima possibile
e comunque
almeno 10gg prima del ritiro:
-
tutti i membri di un gruppo devono iscriversi (mediante il sito S3)
all'appello del progetto
- uno dei membri deve inviarmi via mail
- gli indirizzi e-mail di tutti i membri
- i numeri di matricola e i nominativi di tutti i membri
- per ciascun membro, il tipo di esame da sostenere (LC1,2 da 9CFU
oppure LC
da 12CFU, LP1/2 da 6CFU, Comp da 6CFU)
- una proposta di appuntamento per il ritiro a cui, preferibilmente
ma non necessariamente, tutti i membri si presenteranno per leggere
e chiarire il testo, dopodiché scatterà il tempo d'inizio e, di conseguenza,
il tempo massimo
di consegna.
Tale proposta non può essere a meno di 10gg dal momento
di invio.
- Scritto:
- La prova scritta richiede di:
- svolgere degli esercizi analoghi a quelli presentati nelle esercitazioni
e a quelli dati per casa (inclusi quelli qui)
- rispondere ad alcune domande sugli argomenti trattati nelle lezioni.
Le prove vanno redatte secondo le seguenti modalità (pena la non
validità della
prova):
- il testo dell'esame deve essere consegnato con
scritte le proprie generalità nell'apposito spazio
e non dove capita!
- le soluzioni devono essere motivate/giustificate in modo preferibilmente sintetico
ma comunque necessariamente completo (in particolare quanto
presente nelle bozze delle soluzioni messe on-line sicuramente non basta)
Ogni qualvolta si consegna uno scritto per la correzione si
annulla un eventuale scritto precedente (ovviamente se all'ultimo non si
consegna rimane il precedente).
Iscrizioni Necessarie!!! Si ricorda che sia per potersi
presentare alle prova scritta è necessaria
l'iscrizione elettronica (mediante il sito S3)
all'appello dello scritto. Mi riserverò la facoltà di non
ammettere i non iscritti.
- Orale (se necessario) e Registrazione Voto Esame:
- La prova orale consiste nella discussione di alcuni degli argomenti trattati
a lezione e/o dello svolgimento di esercizi.
Per poter sostenere la prova orale o registrare il voto dell'esame (se
la prova orale non fosse necessaria e non si intendesse sostenerla), è necessario
aver superato una prova scritta e un progetto da meno di
un anno.
Se durante la prova scritta non fosse stata fissata una data per l'orale
basta accordarsi (anche via mail).
Faccio presente che non eseguo la procedura di verbalizzazione dei voti accettati
settimanalmente, ma principalmente quando ho completato dei "blocchi", quindi
qualora ci fossero urgenze siete pregati di comunicarlo via email.
N.B. Ogni volta che si consegna per la correzione una prova scritta o un progetto
si cancella il voto precedente corrispondente.
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:
Esami di Linguaggi 1
- testo del
compito del 27/01/2011 su Materiale
Didattico
- testo del
compito del 22/02/2010 su Materiale
Didattico
- testo del
compito del 01/02/2010 su Materiale
Didattico
- testo del
compito del 07/09/2009
- testo del
compito del 17/07/2009
- testo del
compito del 01/07/2009
- testo del
compito del 26/02/2009
- testo del
compito del 02/02/2009
- testo del
compito del 17/09/2008
- testo del
compito del 11/07/2008
- testo del
compito del 10/04/2008
- testo del
compito del 20/12/2007
- testo del
compito del 05/12/2007
- testo del
compito del 17/09/2007
- testo del
compito del 13/07/2007
- testo del
compito del 13/04/2007
- testo del
compito del 23/03/2007
- testo del
compito del 12/01/2007
- testo del
compito del 18/12/2006
- testo
esercizio P-Code Pascal del 02/12/2004
- testo
esercizio P-Code Pascal del 08/09/2004
- testo
esercizio P-Code Pascal del 06/07/2004
- testo
esercizio P-Code Pascal del 23/06/2004
Esami di Linguaggi 2
- testo del
compito del 15/06/2010 su Materiale
Didattico
- testo del compito del 22/02/2010 su Materiale
Didattico
- testo del
compito del 07/09/2009
- testo del
compito del 17/07/2009
- testo del
compito del 01/07/2009
- testo del
compito del 17/06/2009
- testo del
compito del 17/09/2008
- testo del
compito del 11/07/2008
(con soluzione WAM)
- testo del
compito del 10/04/2008
- testo del
compito del 28/03/2008
(con soluzione WAM)
- testo del
compito del 17/09/2007
- testo del
compito del 03/09/2007
- testo del
compito del 13/07/2007
- testo del
compito del 13/04/2007
(con soluzione WAM)
- testo del
compito del 23/03/2007
(con soluzione WAM)