Code

COMPGC16 (Also taught as: COMP3011)

Year

MSc

Prerequisites

n/a

Term

2

Taught By

Chris Clack (100%)

Aims

This course introduces the functional programming paradigm and the implementation technology for functional programming languages. It aims to develop a broad understanding of the benefits of the functional programming style, together with an understanding of implementation issues that are relevant not only to functional languages but also to other systems that require automatic dynamic memory management.

Learning Outcomes

To be able to: understand the basics of the lambda calculus and combinators and how they are used in the implementation of functional languages; understand the main features of a modern lazy functional language; write non-trivial functional programs; understand the computation, synchronisation and memory management issues affecting the sequential and parallel implementation of lazy functional languages; read and understand the research and technical literature on functional programming.

Context

Classification of Programming Languages
Distinctive Features of Functional Programming Languages

The Lambda Calculus and Combinators

Versions of the Lambda Calculus - syntax and semantics
Reduction orders, strong normalisation
Combinators - computationally complete sets

A Modern Functional Language

Programming Environment
Types
Recursion
Pattern-Matching
Lists
Higher-Order Functions
User-Defined Types
Recursive Programming Techniques

Introduction to Implementation Techniques

Strict Evaluation and the SECD Machine
Lazy Evaluation and Graph Reduction
The Need for Automatic Memory Management
Parallel Graph Reduction

Automatic Memory Management

Memory Allocation and Garbage Collection
Memory Allocation Techniques
Garbage Collection Techniques

Lecture presentations with associated class problems.

The course has the following assessment components:

• Written Examination (2.5 hours, 95%)
• Coursework Section (1 piece, 5%)

To pass this course, students must:

• Obtain an overall pass mark of 50% for all sections combined

The examination rubric is:
Answer 3 questions out of 5. All questions carry equal marks.

Programming with Miranda, Clack, Myers and Poon, Prentice-Hall 1994 ISBN 0-13-192592-X.

The Implementation of Functional Programming Languages, Peyton-Jones, Prentice-Hall 1986

Garbage Collection: Algorithms for Automatic Dynamic Memory Management, Jones and Lins, Wiley 1996 ISBN 0 471 94148 4

Research Directions in Parallel Functional Programming, Hammond and Michaelson (Eds.), Springer, ISBN 1-85233-092-9, 1999

Supporting information