Computer Laboratory Home Page Search A-Z Directory Help
University of Cambridge Home Computer Laboratory
Computer Science Tripos Syllabus - Semantics of Programming Languages
Computer Laboratory > Computer Science Tripos Syllabus - Semantics of Programming Languages

Semantics of Programming Languages next up previous contents
Next: Easter Term 2005: Part Up: Lent Term 2005: Part Previous: Operating Systems II   Contents


Semantics of Programming Languages

Lecturer: Dr P.M. Sewell

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. [1 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]

  • Semantic equivalence. Semantic equivalence of phrases in a simple imperative language, including the congruence property. Examples of equivalence and non-equivalence. [1 lecture]

  • Concurrency. Shared variable interleaving. Semantics for simple mutexes; a serializability property. [1 lecture]

  • Subtyping. Record subtyping and simple object encoding. [1 lecture]

  • Low-level semantics. Monomorphic typed assembly language. [1 lecture]

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. Out of print, but available on the web at http://www.cogs.susx.ac.uk/users/matthewh/semnotes.ps.gz
* Pierce, B. C. (2002). Types and programming languages. MIT Press.
Winskel, G. (1993). The formal semantics of programming languages. MIT Press.


next up previous contents
Next: Easter Term 2005: Part Up: Lent Term 2005: Part Previous: Operating Systems II   Contents
Christine Northeast
Wed Sep 8 11:57:14 BST 2004