School of Computer Science

Module 06-02552 (2014)

Principles of Programming Languages

Level 3/H

Uday Reddy Semester 1 10 credits
Co-ordinator: Uday Reddy
Reviewer: Paul Levy

The Module Description is a strict subset of this Syllabus Page.

Outline

It can be argued that the development and study of high-level programming languages is a central task for computer science research, and enormous progress has indeed been made from the machine-level coding of the 40s to today's functional and object-oriented languages. In this module, we will study the features that have emerged as recurring themes in high-level languages, though they are expressed in a variety of ways. We will use the lambda calculus as a meta language to express theses features concretely and precisely. At this level of abstraction, 'computation' becomes 'evaluation' of expressions, rather than the execution of machine instructions. We will look at ways to specify this process in a precise fashion and thus discover some key design decisions that have to be made when developing a concrete language. Types can be used to constrain the range of valid programs and thus help the programmer to develop well-structured code. We will see how polymorphism and subtyping extend the expressivity of simple type disciplines without sacrificing semantics.


Aims

The aims of this module are to:

  • introduce the central ideas and techniques in the theory of programming languages
  • exhibit some of the building blocks from which high-level programming languages are constructed
  • illustrate how concrete languages realise abstract programming language ideas
  • explain ways for defining the semantics of programming language constructs in a rigorous fashion

Learning Outcomes

On successful completion of this module, the student should be able to:

  1. demonstrate fluency in reading, constructing, and manipulating expressions in the lambda calculus
  2. execute specific evaluation strategies for lambda calculi with effects
  3. relate features of concrete programming languages to abstract principles
  4. assign types from various type disciplines to program expressions

Restrictions

No co-requisites but 06-02578 (Compilers & Languages) will be an ideal complement


Pre-requisites


Teaching methods

2 hrs of lectures and one exercise class per week, one revision lecture

Contact Hours: 34


Assessment

Sessional: 1.5 hr examination (80%), continuous assessment (20%)

Supplementary (where allowed): 1.5hr examination only


Detailed Syllabus

  1. History and overview
  2. The lambda calculus

* abstraction and application * alpha equivalence * substitution * reduction 3. Evaluation strategies * Call-by-name, call-by-value, call-by-need * Operational semantics * Abstract machines * effects 4. Types * simple types * polymorphic types * subtyping 5. Modularity * data encapsulation * object-orientation * abstract data types


Programmes containing this module