Academic Year 2019-2020


Marco Comini
Marina Lenisa
Total Course Credits: 9
Teaching Period: Second Period
Teaching Language: Inglese
Prerequisites. A course on programming languages. Basic knowledge of a modern functional programming language.
Teaching Methods. Lectures and exercises.
Verification of Learning. The exam consists of a project to be performed by groups, with exercises to be implemented at the computer, in the various languages introduced in the course. It also includes the development of a front-end of a compiler from a suitably simplified imperative language to three-address code.

Finally there will be an individual oral test in which to discuss the project and the topics presented in the lessons.


Specific learning objectives

This course aims to provide a knowledge of the features of the various programming paradigms, focusing on the “universal” principles that guide the design, development and implementation of modern programming languages, with special emphasis on the study of relations between project techniques, semantics and implementation of programming languages.

This course complements the basic courses on programming languages of the three-year degrees in computer science related to imperative and functional paradigms, introducing the theory and practice of programming in logic and functional-logic paradigms, where features such as high-order and non-determinism can be exploited to write compact, elegant and easily reusable code. It also analyzes the operational principles underlying the various declarative languages and how these guide the implementation of their corresponding abstract machines.

To complete the picture of the implementation of languages, the main issues, solutions and techniques regarding the front-end of a compiler are addressed: the algorithms for lexical and syntactic analysis, that are the base of tools such as Lex and Bison (for the language C) or Alex and Happy (for the Haskell language), are shown. In addition, the main methods for program’s static semantics analysis are illustrated, by means of attributed grammars and type systems. Finally, intermediate code generation (without optimizations) is presented.

The course has as its ultimate aim to develop a critical spirit that allows to arrive at a conscious programming in which one knows how to choose the most appropriate paradigm depending on the application problem to be solved, knowing what constructs of a language to use, and at what total cost (in terms of resources used throughout the implementation pipeline).

1.1 knowledge and understanding

The student knows the main concepts of programming in the main paradigms of programming languages. He also knows the operational principles underlying the implementations of the various languages. Finally he knows the main problems, solutions, and techniques relating to the front-end of a compiler.

1.2 applying knowledge and understanding

Students learn new declarative languages and learn to write code in the various paradigms by using appropriate styles and techniques. The also learn to know and to use the tools that are typically used to write a compiler but can have also many applications in other information technology areas.

The project activity allows students to consolidate the theoretical knowledge presented during lectures through its use in real cases, thus allowing them to independently develop a front-end of a simple imperative language.

2.1 making judgements

The course objective is primarily to develop a critical spirit that allows one to choose the most appropriate programming language depending on the application problem to be solved, knowing which constructs of a language to use, and at what cost. It also aims to improve the student’s ability to identify the most practical and simple solutions in the implementation of software systems.

2.2 communication skills

The student learns the exact meaning of the terms used in programming language coding and implementation.

Through the group project activity, students improve their communicative and interaction skills.

2.3 learning skills

The knowledge acquired allows students to move with ease among the myriad of programming languages, and to learn new langages in a short time by quickly framing new language features.

Thanks to the interaction with the other members of the project team, students learn to evaluate their degree of learning by comparing with others.


Functional Paradigm

* The language Haskell

* utilizzo della programmazione di ordine superiore per scrivere codice compatto e flessibile

* Execution models of functional languages: Term Rewriting Systems and Pattern Matching

Functional-logic Paradigm

* The language Curry

* Higher-order Non-deterministic Programming

* Notes on executions models of functional-logic kanguages: unification and needed narrowing.

Compilers basic theory

* Top-down parsing with error recovery

* Bottom-up parsing (SLR,LR,LALR) with error recovery

* Syntax Directed Translation

* Attributed Grammars

* S-attributed and L-attributed SDDs

* Statica semantics/type checking via Attributed Grammars

* Intermediate code generation (three address code)

– Translation of expressions with array access

– Translation of Control flow: eager/lazy conditionals

– Non-optimized Control flow. Fall-through technique. Back Patching. Translation of break/continue.

– Translation of declarations and calls of Procedures/Functions

* Continuation Passing-Style in functional languages

* Hints on intermediate code generation of functional languages


* M. Gabbrielli, S. Martini. Programming Languages: Principles and Paradigms. McGraw-Hill. ISBN 978-1848829138

* F. W. Schröer The GENTLE Compiler Construction System. R. Oldenbourg Verlag, 1997, ISBN 3-486-24703-4

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

* Terese. TERESE LITE. Vrije Universiteit, 2006. (excerpt from book Term Rewriting Systems. Cambridge Tracts in Theoretical Computer Science, Vol. 55, Cambridge University Press, 2003)