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?