Foundations of Computing - LINGUAGGI (2016/2017)

Course code
Name of lecturer
Massimo Merro
Number of ECTS credits allocated
Academic sector
Language of instruction
I sem. dal Oct 3, 2016 al Jan 31, 2017.
Web page

To show the organization of the course that includes this module, follow this link * Course organization

Lesson timetable

I sem.
Day Time Type Place Note
Tuesday 10:30 AM - 12:30 PM lesson Lecture Hall I  
Thursday 8:30 AM - 10:30 AM lesson Lecture Hall I  
Friday 11:30 AM - 1:30 PM lesson Lecture Hall I  

Learning outcomes

The aim of the course is to present the structural operational approach to programming language semantics. A number of paradigmatic untyped and typed languages will be introduced. The entire course will focus on the concepts of operational semantics and type system. Formal techniques for verifying the behavior of programs will be introduced.

At the end of the course students should
• be familiar with rule-based presentations of the operational semantics and type systems for some simple imperative, functional and interactive program constructs
• be able to prove properties of an operational semantics using various forms of induction (mathematical, structural, and rule-based)
• be familiar with some operationally-based notions of semantic equivalence of program phrases and their basic properties


Classes and exercises (56 hours)

• Introduction.
Transition systems. The idea of structural operational semantics. Transition semantics of a simple imperative language. Language design options. Exercises.
• Types.
Introduction to formal type systems. Typing for the simple imperative language. Statements of desirable properties.
• Induction. Exercises.
Review of mathematical induction. Abstract syntax trees and structural induction. Rule-based inductive definitions and proofs. Proofs of type safety properties. Exercises.
• Functions.
Call-by-name and call-by-value function application, semantics and typing. Local recursive definitions. Exercises.
• Data.
Semantics and typing for products, sums, records, references. Exercises.
• Subtyping.
Record subtyping and simple object encoding. Exercises.
• Semantic equivalence.
Semantic equivalence of phrases in a simple imperative language, including the congruence property. Examples of equivalence and non-equivalence. Exercises.
• Concurrency.
Shared variable interleaving. Semantics for simple mutexes; a serializability property. Exercises.

Reference books
Author Title Publisher Year ISBN Note
Peter Sewell Semantics of Programming Languages (Edizione 6) Cambridge University Press 2019 Note a cura del Prof. Sewell.
G. Winskel The formal Semantics of Programming Languages MIT Press 1993
Benjamin Pierce Types and Programming Languages (Edizione 1) MIT Press 2002 ISBN-10: 0262162091 Guida ineguagliabile per lo studio dei sistemi di tipi per i linguaggi di programmazione.

Assessment methods and criteria

The exam consists of a written test containing 4 or 5 exercises. The correct conduct of all exercises allows for a 30/30 vote.