Linguaggi e Compilatori I e II 2013/2014

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
    • proiezioni di Futamura
  • 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:
    • i capitoli 10 e 12 del libro Pascal Implementation , Pemberton&Daniels
    • Sezione 6.2 (Icode) del libro The GENTLE Compiler Construction System
    • Per sperimentare è disponibile l'implementazione (freeware) The P4 compiler, in particolare:
      • pint.pas Assembler and interpreter of Pascal code, K. Jensen, N. Wirth, Ch. Jacobi, ETH
      • pcode.pas
  • 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
  • Non-deterministic Programming
  • Il linguaggio Prolog (alcune implementazioni: GProlog, Swi-Prolog e Sicstus; in materiale didattico potete trovare file usato a lezione per le demo, ).
  • Warren Abstract Machine (testo di riferimento, slides sull'evoluzione della memoria mostrate a lezione, syllabus, istruzioni, alcuni esempi di compilazioni di programmi prolog in linguaggio WAM si possono trovare nei testi dei compiti)
• 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
  • 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
  • M. Hanus. The Integration of Functions into Logic Programming: From Theory to Practice, Journal of Logic Programming, 19&20:583-628, 1994.
  • S. Antoy, R. Echahed, M. Hanus. A Needed Narrowing Strategy, Journal of the ACM, 2000.

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
  • Ci sono ottime implementazioni freeware di Prolog, ad esempio gprolog e swi-prolog
• 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.
  • Nella Home di Curry potere trovare moltissima documentazione sul linguaggio e i links alle implementazioni MCC (Münster Curry Compiler, per MacOSX usate l'ottimo AquaCurry) e PAKCS (che si basa su Sicstus o su Swi-Prolog e si può usare via interfaccia web).

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:

1. tutti i membri di un gruppo devono iscriversi (mediante il sito S3) all'appello del progetto
2. 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

1. testo del compito del 27/01/2011 su Materiale Didattico
2. testo del compito del 22/02/2010 su Materiale Didattico
3. testo del compito del 01/02/2010 su Materiale Didattico
4. testo del compito del 07/09/2009
5. testo del compito del 17/07/2009
6. testo del compito del 01/07/2009
7. testo del compito del 26/02/2009
8. testo del compito del 02/02/2009
9. testo del compito del 17/09/2008
10. testo del compito del 11/07/2008
11. testo del compito del 10/04/2008
12. testo del compito del 20/12/2007
13. testo del compito del 05/12/2007
14. testo del compito del 17/09/2007
15. testo del compito del 13/07/2007
16. testo del compito del 13/04/2007
17. testo del compito del 23/03/2007
18. testo del compito del 12/01/2007
19. testo del compito del 18/12/2006
20. testo esercizio P-Code Pascal del 02/12/2004
21. testo esercizio P-Code Pascal del 08/09/2004
22. testo esercizio P-Code Pascal del 06/07/2004
23. testo esercizio P-Code Pascal del 23/06/2004

Esami di Linguaggi 2

1. testo del compito del 15/06/2010 su Materiale Didattico
2. testo del compito del 22/02/2010 su Materiale Didattico
3. testo del compito del 07/09/2009
4. testo del compito del 17/07/2009
5. testo del compito del 01/07/2009
6. testo del compito del 17/06/2009
7. testo del compito del 17/09/2008
8. testo del compito del 11/07/2008 (con soluzione WAM)
9. testo del compito del 10/04/2008
10. testo del compito del 28/03/2008 (con soluzione WAM)
11. testo del compito del 17/09/2007
12. testo del compito del 03/09/2007
13. testo del compito del 13/07/2007
14. testo del compito del 13/04/2007 (con soluzione WAM)
15. testo del compito del 23/03/2007 (con soluzione WAM)