Docente

• Prof. Marco Comini

Indirizzo Pagina Web Personale

http://www.dimi.uniud.it/members/marco.comini/

Crediti

9 CFU

Finalità

Questo corso, in congiunzione con il corso di Linguaggi di Programmazione, intende fornire una conoscenza delle caratteristiche dei vari paradigmi di programmazione, concentrandosi sui principi “universali” che guidano la progettazione, realizzazione e implementazione dei moderni linguaggi di programmazione.
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 applicativo da risolvere, sapendo quali costrutti di un linguaggio usare, e a quale costo (in termini di risorse).
Questo corso, in particolare, complementa il corso di Linguaggi di Programmazione, relativo ai paradigmi imperativo e funzionale, mostrando i paradigmi logico e logico-funzionale. Si completa quindi la presentazione dei paradigmi dichiarativi che, grazie alla loro espressività, si prestano naturalmente quale base di sviluppo di software corretto. Si mostrerà come caratteristiche quali ordine superiore e non-determinismo possano essere sfruttate per scrivere codice compatto, elegante e flessibile (direttamente riutilizzabile in diversi contesti, agevolmente manutenibile e facilmente estensibile).
Inoltre in questo corso vengono introdotte approfonditamente le principali problematiche, soluzioni e tecniche concernenti il front-end di un compilatore. Innanzitutto, si presentano gli algoritmi per l’analisi lessicale e sintattica, fondamenti concettuali della realizzazione dei più diffusi strumenti come flex/alex e bison/happy. Successivamente, si presentano i principali metodi per l'analisi statica dei programmi, mediante grammatiche con attributi e sistemi di tipi. Infine viene introdotta la generazione del codice intermedio.

Programma

Paradigma Logico
• Non-deterministic Programming.
• Il linguaggio Prolog.
• Warren Abstract Machine.
Paradigma Logico-Funzionale
• High-order Non-deterministic Programming.
• Il linguaggio Curry.
Modelli di esecuzione dei linguaggi dichiarativi
• Paradigma funzionale: Sistemi di riscrittura e Pattern Matching
• Paradigma logico: Unificazione, SLD-derivations, semantica denotazionale della Programmazione Logica.
• Paradigma Logico Funzionale: full narrowing e needed narrowing.
Teoria dei compilatori
• Parsing top-down (implementazione a programma e parser LL).
• Parsing bottom-up (parser SLR, LR, LALR).
• Syntax Directed Translation.
• Grammatiche ad Attributi.
• S-attributed e L-attributed SDD.
• Semantica Statica.
• Type Checking via Grammatiche ad Attributi.
• 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; backpatching; gestione break/continue.
• Traduzione di dichiarazioni e chiamate di procedure/funzioni.
• Continuation Passing-Style con linguaggi funzionali.
• Cenni alla generazione di codice intermedio di linguaggi funzionali.

Bibliografia

• 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
• M. Hanus, S. Antoy. Curry: A Tutorial Introduction, 2004
• 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.

Modalità d'esame

Progetto a gruppi, orale individuale

**********************************************************************************

Aims

This course, together with the Programming Languages course, aims to give knowledge on the characteristics of the various programming paradigms. It tries hard not to focus on a specific language but to present the general principles that guide project, development and implementation of modern programming languages.
To achieve this general vision the main programming paradigms are presented: imperative, functional, logic and functional-logic. Besides examining the most immediate pragmatical aspects of these paradigms, they are analyzed and compared basing on general principles in order to achieve a critical comprehension of most popular languages. This is needed to reach a conscious programming style, where one knows which paradigm is better to chose to solve a specific problem, and knows which language constructs to use, and at which cost (in terms of resources).
This course, in particular, complements the Programming Languages course, which presents the imperative and functional paradigms, by presenting the logic and functional-logic paradigms. This completes the presentation of the declarative paradigms that, thanks to their expressiveness, can be naturally used as basis for development of correct software. It will be shown how characteristics like high-order and non-determinism can be fruitfully used to write compact, elegant and flexible (directly reusable, effortlessly maintainable and simply extensible) code.
Moreover in this course are introduced in detail the main problems, solutions and techniques on the front-end of a compiler. First, we present algorithms for the lexical and syntactical analyses, conceptual foundations for the realization of the most popular tools like flex/alex and bison/happy. Next, we present the main methods for static analysis by employing attributed grammars and type systems. Finally, we introduce the intermediate code generation.

Program

Logic Paradigm
• Non-deterministic Programming
• The Prolog language.
• Warren Abstract Machine
Functional-Logic Paradigm
• High-order Non-deterministic Programming.
• The Curry language
Execution Models of the Declarative Languages
• Functional Paradigm: Term Rewriting Systems and Pattern Matching
• Introduction to Logic Paradigm: Unification, SLD-derivations, Denotational Semantics of Logic Programs.
• Functional-Logic Paradigm: full narrowing and needed narrowing.
Theory of Compilers
• top-down parsing (direct implementation and LL parsers)
• bottom-up parsing (SLR, LR, LALR parsers)
• Syntax Directed Translation
• Attributed Grammars
• S-attributed and L-attributed SDD
• Static Semantics
• Type Checking via Attributed Grammars
• Intermediate Code Generation (three address code)
• Translation of expressions addressing array elements
• Translation of Control flow: eager/lazy conditionals; non-optimized control flow; fall-through technique; backpatching; break/continue translation.
• Translation of declarations and calls of procedures/functions.
• Continuation Passing-Style with functional languages.
• Outline of Intermediate Code Generation for functional languages.

References

M. Gabbrielli, S. Martini. Linguaggi di Programmazione - Principi e Paradigmi. McGraw-Hill. ISBN 88-386-6261-4
Imperative Paradigm
• 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.
Logic Paradigm
• 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
Functional-Logic Paradigm
• M. Hanus, S. Antoy. Curry: A Tutorial Introduction, 2004
• 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.

Exams

Group project, individual oral exam