72940 - Computational Models And Languages M

Learning outcomes

At the end of this course unit, conceived according to a multi-paradigm and multi-language constructive approach, the student has a deep knowledge on the fundamental concepts of programming languages and related computational models, knows the foundations of computability, knows and is able to apply the basic interpreter and compiler techniques, and possesses the basic concepts of functional programming and is able to apply such concepts in typical practical situations.

More precisely, the student will know the main formal methods for language definition in terms of syntax and semantics, for both programming languages and specification languages, and will be able to apply the main LL and LR techniques for language evaluation and recognition for interpreters and compilers, including the use of the most common tools. Students will also be able to define reasonably simple languages understanding their properties, implementing the corresponding interpreters, and evaluating the pros and cons of different choices/computational paradigms in application design.

Course contents

The course aims to provide a rational view over the fundamental concepts of programming languages, relating them to the different computational models and to the problem of language translation and recognition: solid foundations are coupled to a strong experimental approach.

Contents:

• Computability and Turing machine (5hrs)
• Formal description of programming languages: grammars and Chomsky classification. Relationship between grammars and language interpreters/translators: lexical analysis, top-down and bottom-up techniques for the syntactical analysis of regular languages and context-free languages. Overview on methods for the formal description of the semantic aspects of a language. (18hrs)
• Structure and organisation of interpreters/compilers, and their run-time support: examples in Java. Parser generator tools. (14hrs)
• Introduction to Model-Driven approaches: the Xtext case. (3 hrs)
• Iterative vs. recursive computational models, tail recursion optimisation, basic concepts of functional programming, closures, models for function evaluation, intro to the basics of Lambda calculus (9hrs)
• Javascript as an example of (dynamic) functional language with a prototype-based object model (6hrs)
• Scala and Kotlin as notable examples of blended programming languages on the Java platform. (9hrs)

Readings/Bibliography

Please refer either to the course page at the site indicted below, or to the slides on the VirtuaLe site.

Teaching methods

The course adopts a constructive approach, where lectures (with slide projection) and foundational aspects are interleaved with practical examples, exercises, case studies - both during the lectures, in the form of live lab, and as proposal for autonomous exercises at home, according to the "individual continuous lab" formula.

Lectures and practical aspects are then intentionally brought forward in parallel, whenever possible for the specific subject. In addition to the above-mentioned individual lab, actual lab sessions are also organised when appropriate.

Assessment methods

The exams consists of an oral discussion, which includes written exercises, examples of the discussed concepts, demonstrations, and comparisons between different approaches.

If the student also selected the extra Work Project, a single comprehensive discussion can be settled. However, it is always possible to take the two exams separately.

Teaching tools

Slides and any other useful material is available on Unibo repository, VirtuaLe. 

A comprehensive list of possible books, manuals, etc. is available on the course web site, which also lists plenty of online tools for practical experiments.

 

Links to further information

http://enricodenti.disi.unibo.it/

Office hours

See the website of Enrico Denti