Linguaggi e Compilatori I e II 2011/2012

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 (IMPY, esempio simile a quello fatto a lezione [11 nov 09], un prototipo per OCL 2.0)
    • Analisi lessicale
      • Grammatiche Regolari
      • Espressioni Regolari
      • Generatori di Analizzatori Lessicali (Lex + esempi,Alex + esempi, esempi a lezione 1, 2, 3).
      • Automi riconoscitori (NFA,DFA,minimizzazione)
    • Generatori di Analizzatori Sintattici (Happy, Yacc, ...).
  • 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, file usato a lezione per le demo, miei esempi 2008/01/03).
    [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 (file usato a lezione per le demo, alcune implementazioni: GProlog, Swi-Prolog e Sicstus,).
  • 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, file usato a lezione per le demo, nqueens, miei esempi 2006/03/24).
• 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 (Parser con controlli di semantica statica ad attributi per IMPY)
  • 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

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:

• un mini progetto da realizzare in gruppi
  • gruppo da 2 persone 9*24 ore di tempo
  • gruppo da 3 persone 8*24 ore di tempo
  • gruppo da 4 persone 6.5*24 ore di tempo
• una prova scritta individuale ed
• (eventualmente) di una prova orale (soprattutto per discriminare le situazioni "di confine" o, in ogni caso, "sospette" e/o dare la possibilità di alzare il voto rispetto allo scritto).

L'esame di Linguaggi e compilatori 2 si compone di:

• un mini progetto da realizzare in gruppi
  • gruppo da 2 persone 11.5*24 ore di tempo
  • gruppo da 3 persone 10*24 ore di tempo
  • gruppo da 4 persone 8.5*24 ore di tempo
• una prova orale da decidere se individuale o collettiva

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. 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 ).

Per poter rititrare il testo dell'elaborato, preferibilmente il prima possibile e comunque almeno 7gg 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 7gg 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)

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/o un progetto da meno di un anno.
Se durante la prova scritta non fosse stata fissata una data per l'orale basta accordarsi via mail.
Nel caso la prova orale non venga superata o si decida di non accettare il voto, lo scritto rimane valido al fine di sostenere un secondo esame orale.
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.

Sia alla prova scritta, quanto quella orale, è ammesso l'uso di qualsiasi materiale didattico (libri, appunti,..., soluzioni di vecchi compiti) purché cartaceo.

Vecchi corsi

In base agli esami già sostenuti o da fare individuate in tabella cosa fare. Notare che per

• Magistrale INFORMATICA iniziata nel 2009/10 si ha:
  • LP1 = Linguaggi di Programmazione (necessariamente fatto alla triennale)
  • LP2 = primo modulo del corso Linguaggi e Compilatori
  • Comp = secondo modulo del corso Linguaggi e Compilatori
• Magistrale INFORMATICA iniziata nel 2008/09 o prima si ha:
  • LP1 = Linguaggi di Programmazione 1
  • LP2 = Linguaggi di programmazione 2
  • Comp = Compilatori
• Triennale con Linguaggi di Programmazione da 6CFU e Magistrale TECNOLOGIE DELL'INFORMAZIONE si ha:
  • LP1 = Linguaggi di Programmazione
  • considerare l'ultima entry con i=1

vista la sufficiente richiesta sto organizzando un appello scritto straordinario di LP1 6CFU con le vecchie modalità. Per decidere la data ho organizzato un poll su Doodle, andateci quanto prima ed inserite le vostre preferenze, usando il campo 'no' solo quando davvero impossibile (usando '(yes)' in alternativa).

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)