Next: Part II of the
Up: Easter Term 2003: Part
Previous: Project Briefing I
  Contents
Semantics of Programming Languages
Lecturer: Dr P.M. Sewell (pes20@cl.cam.ac.uk)
No. of lectures: 12
This course is a prerequisite for Types (Part II), Denotational Semantics (Part II) and Topics in Concurrency (Part II).
Aims
The aim of this course is to introduce the structural, operational
approach to programming language semantics. It will show how to
specify the meaning of typical programming language constructs, in the
context of language design, and how to reason formally about semantic
properties of programs.
Lectures
- Introduction. Transition systems.
The idea of structural operational semantics.
Transition semantics of a simple imperative language.
Language design options. [2 lecture]
- Types. Introduction to formal type systems.
Typing for the simple imperative language.
Statements of desirable properties. [1 lecture]
- Induction. Review of mathematical induction. Abstract
syntax trees and structural induction. Rule-based inductive
definitions and proofs. Proofs of type safety properties. [2 lectures]
- Functions. Call-by-name and call-by-value function
application, semantics and typing. Local recursive definitions. [2 lectures]
- Data. Semantics and typing for products, sums, records,
references. [1 lecture]
- Subtyping. Record subtyping and simple object encoding. [1 lecture]
- Low-level semantics. Monomorphic typed assembly language.
[1 lecture]
- Semantic equivalence. Semantic equivalence of phrases in a
simple imperative language, including the congruence property.
Examples of equivalence and non-equivalence. [1.5 lectures]
- Concurrency. Shared variable interleaving. [0.5 lectures]
Objectives
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
Recommended books
Hennessy, M. (1990). The Semantics of Programming Languages.
Wiley.
Pierce, B. C. (2002). Types and Programming Languages. MIT Press.
Winskel, G. (1993). The Formal Semantics of Programming
Languages. MIT Press.
Next: Part II of the
Up: Easter Term 2003: Part
Previous: Project Briefing I
  Contents
Christine Northeast
Wed Sep 4 14:43:05 BST 2002