Computational Models and Semantics, Autumn 2021

Course Setup

The course consists of weekly lectures, see schedule below, some practical assignments, self-study and some project work. The practical assignments are meant for deepening the understanding of lecture content. These are either pen-and-paper or implementation exercises.

You will also do some self-study of an advanced topic, which can be a chapter from the book Models of Computation by Bruni and Montanari, or another book or research paper. After developing some understanding of your topic, you will propose a project. The project can be, for example, the implementation of an aspect of your topic, a small research project that builds on what you studied, or a deeper literature research. This is up to you to propose.

At the end, you will then hand in a report and give a presentation of your studies and project. The length of the report depends on your project: a literature study or the development of a theory needs more details than the description of an implementation.

Course Schedule

Week 1: Organisation and Introduction

Lecture Tuesday, 07 September, 11:15

We discuss the general course organisation and will get a general overview over the course. Thereby we will get an idea of what programming languages and semantics are all about, and those ideas on the language Simp of simple arithmetic expressions.

Week 2: Denotational Semantics, Basic Terminology and Derivation Systems

Practicals Session Tuesday, 14 September, 09:15

We will go together through some basics of Haskell and you can start working on the implementation of the semantics of Simp.

Lecture Tuesday, 14 September, 11:15

We finish the introduction to the course with an extensive explanation of denotational semantics, parameters like environments and some important terminology. This also leads naturally to a discussion of the use of semantics. Moreover, we discuss general inference rules, derivation systems and their use in inductively defining relations.

Week 3: Uses of Derivation Systems and Big-Step Semantics of IMP

Practicals Session Tuesday, 21 September, 09:15

We will discuss your solutions to the programming exercise from previous week.

Lecture Tuesday, 21 September, 11:15

The language IMP of simple imperative programs together with its big-step semantics will be introduced.

Week 4: Elements of Domain Theory I: Posets, Bounds and Limits

Practical Session Tuesday, 28 September, 09:15

Pen-and paper exercises on big-step semantics of IMP

Lecture Tuesday, 28 September, 11:15

We discuss partially ordered sets and their role in denotational semantics. Moreover, we introduce some general kinds of bounds and limits (least upper bounds) that will be later refined for providing semantics.

Week 5: Elements of Domain Theory II: Monotone maps, directed sets, dcpos and continuity

Lecture Tuesday, 29 September, 11:15

In this second part on domain theory, we discuss monotone maps, directed sets, directed-complete partial orders (dcpos) and continuous maps with the goal of constructing fixed points that underlie the denotational semantics of languages like IMP.

Practical Session Friday, 02 October, 09:15

Week 6: Elements of Domain Theory III and Denotational Semantics of IMP

Practical Session Friday, 02 October, 09:15

Lecture Tuesday, 06 October, 11:15

We finish the discussion of fixed points of continuous maps and use those to give semantics to IMP.

Week 7: Domain Theory II

Lecture Tuesday, 13 October, 11:15

  • Fixed points in CPOs
  • Denotational Semantics of IMP

Practical Session Friday, 16 October, 09:15

  • Discussion of assignments

Week 8:

Picking Self-Study Topics

Pick or suggest study topic as group until Friday, 23 October, 23:59. Please suggest your favourite study topic as response to the assignment on Brightspace. There is a list with suggested available on Brightspace, from which you can pick papers or book chapters. In case you pick something from this list, please also provide an alternative in case we have some conflicts. We will sort out these conflicts then in the forum. Feel free to communicate your choice also beforehand in the Self-Study and Project forum.

We will finalise on Monday, 26 October the study topic assignment. Then you can start studying your chosen topic.

Assignments

  • Implementation of HOFL

Lecture Tuesday, 20 October, 11:15

  • Syntax HOFL
  • Free variables
  • Substitution
  • Operational Semantics

Practical Session Friday, 23 October, 09:15

Week 9:

Start Self-Study

We will finalise on Monday, 26 October the study topic assignment. Then you can start studying your chosen topic.

Lecture Tuesday, 27 October, 11:15

  • Constructions on domains: products, function spaces
  • Continuity theorems (lifting, composition, etc.)

Practical Session Friday, 30 October, 09:15

Assignments

Week 10:

Lecture Tuesday, 03 November, 11:15

  • Denotational Semantics of HOFL

Practical Session Friday, 06 November, 09:15

Week 11:

Project proposal

Please submit your project proposal by Friday, 13 November, 23:59. The proposal should be of reasonable length, say, around 200 - 400 words long. You need to mention in your proposal what your study topic is and what you plan to carry out as project. Keep in mind that you have about three weeks for completing the project, which means that your proposal should be realistic.

The project should have a clear research question and a clear outcome that will answer your research question. I will give you some feedback by Monday, 16 November in the Afternoon on whether your proposal is realistic.

Lecture Tuesday, 10 November, 11:15

  • Equivalence Between HOFL Denotational and Operational Semantics

Practical Session Friday, 13 November, 09:15

Week 12: Category Theory

Lecture Tuesday, 17 November, 11:15

  • Categories and functors
  • Cartesian closed categories
  • Categorical semantics of STL

Practical Session Friday, 20 November, 09:15

Week 13: Monad Semantics

Lecture Tuesday, 24 November, 11:15

  • Monads
  • Categorical semantics of a simple probabilistic language

No on-site activity

Week 14:

No lecture

Practical Session Friday, 04 December, 09:15

Week 15:

Project Report Deadline Friday, 11 December, 23:59

Please hand in the report for your project via Brightspace. This report should contain a summary of your study topic, with enough explanation to understand the description of your project.

I will make a LaTeX template for the project report available.

No lecture

Practical Session Friday, 11 December, 09:15

  • Project Presentation?