IMC011 Semantics and Domain Theory Spring 2018

Teacher

Herman Geuvers: home page

Introduction

Denotational Semantics is about assigning a mathematical meaning to syntax (in particular, that of programming languages) which is, in some sense, independent of how the syntax is presented, or what computational rules it may obey (which are properly the subject matter of Operational Semantics).

Domain Theory is the mathematics of the objects, sets-with-structure, and mappings between them, which serve as a vehicle for denotational semantics.

Material

  1. Lecture Notes on Denotational Semantics by Andy Pitts and Glynn Winskel, abbreviated to DENS for now. (Available via internet: PDF file)
  2. Grondslagen van de Informatica 2 course notes by Erik Barendsen, August 1988, abbreviated to GI2 for now
  3. Selected sections from From computation to foundations via functions and application: The lambda-calculus and its webbed models by Chantal Berline, Theoretical Computer Science 249 (2000) pp. 81-161.

Fresh up material for those who haven't followed Semantiek en Correctheid or have forgotten some of that:

  1. Material on operational semantics can be found in Hanne Riis Nielson en Flemming Nielson: Semantics with applications, Wiley 1999 (freely available).
  2. For a recap of lambda calculus, here is a set of selected pages from Introduction to Lambda Calculus by Barendregt and Barendsen. As exercises you may try 2.5 -- 2.10.

Further reading material:

  1. Ch. 3.1 and 3.2 of Domains and Lambda Calculi by Roberto Amadio and Pierre-Louis Curien, Cambridge University Press, 1998, pp: 484
  2. Ch. 13 of Formal Semantics of Programming Languages by Glynn Winskel, MIT Press, Cambridge, Massachusetts, 1993.
  3. Ch. 2 and Ch. 8 until page 260 of Semantics of Programming Languages: Structures and Techniques, by Carl Gunter, MIT Press, Cambridge, Massachusetts, 1992.

Structure

The course is divided roughly into 3 parts:

Examination

There is a written exam, which is "open book", so you can take the course notes and your own notes to the exam. Apart from that there is a small assignment, where you are required to apply your knowledge on denotational semantics to a concrete programming language or programming concept. (Of your own choice.) This will be explained in week 16. This should result in a short note (max 10 pages). See the assignment explanation. The deadline for the assignment is July 1

The final grade is 3/4 of your written exam grade + 1/4 of your assignment grade.

Set up

The course consists of 2 hours hoorcollege Wednesday, 15:45--17:30 in HG00.071 or HG00.114, plus "self study" and a "werkcollege" (exercise class) on Friday, 10:45--11:30 in HG00.114.

Look below for updated information on the weekly schedule!

The course by week

The following is the weekly schedule. Every lecture on Wednesday is followed by an exercise class on Friday, 10:45-11:30.
Year-week Order Date and Location Material Exercises
6 1 7/2, HG00.071 Chapter 1 of DENS and notes exercises, 9/2, HG00.114
7 No lectures, carnaval week
8 2 21/2, HG00.071 Chapter 1 of DENS exercises, 23/2, HG00.114
9 3 28/2, HG00.071 Section 2.1 of DENS exercises, 2/3, HG00.114
10 4 7/3, HG00.071 Chapter 2-3 of DENS until Section 3.2 (p. 23) exercises, 9/3, HG00.114
11 5 14/3, HG00.071 Section 3.2, 3.3, Chapter 4 of DENS until slide 21 exercises, 16/3, HG00.114
12 6 21/3, HG00.071 Chapter 4 of DENS until page 36 exercises, 23/3, HG00.114
13 7 28/3, HG00.071 Chapter 5 of DENS, until page 45 exercises, no werkcollege: goede vrijdag
14 No lectures
15 8 11/4, HG00.114 end of Chapter 5 + Chapter 6 of DENS until page 54 exercises, 13/4, HG00.114
16 9 18/4, HG00.114 end of Chapter 6 + Chapter 7 (not everything) of DENS exercises, 20/4, HG00.114
17 10 25/4, HG00.114 Chapter 8 of DENS + presentation of the assignment exercises, no werkcollege: koningsdag
18 No lectures, May break
19 11 9/5, HG00.114 Stable models: notes and exercises exercises, no werkcollege: hemelvaartsdag
20 12 16/5, HG00.114 Stable models continued: notes and exercises + exercises, 18/5, HG00.114
lambda calculus revisited
21 13 23/5, HG00.114 Models of lambda calculus: the notes of Berline exercises, 25/5, HG00.114
22 14 30/5, HG00.114 Sections 3.1, 3.2 and 3.3 of GI2 exercises, 1/6, HG00.114
23 15 6/6, HG00.114 Chapter 4 of GI2 exercises, 8/6, HG00.114
24 16 13/6, HG00.114 Recap + questions no class on 15/6
25 Work on the assignment, No lectures
27 3/7, 13:30-14:30, Mercator ground floor Question hour
27 4/7, 12:30-15:30, HG00.062 EXAM

Written Exam

The written exam is "open book", so you can take the course notes and your own notes to the exam. Dates:

The deadline for the assignment is 1/7

The final grade is 3/4 of your written exam grade + 1/4 of your assignment grade.

herman at cs dot ru dot nl