COMPGC16 - Functional Programming

This database contains the 2017-18 versions of syllabuses. Syllabuses from the 2016-17 session are available here.

Note: Whilst every effort is made to keep the syllabus and assessment records correct, the precise details must be checked with the lecturer(s).

Code COMPGC16 (Also taught as: COMP3011)
Year MSc
Prerequisites

EITHER the completion of 2 years undergraduate level study in pure Computer Science at UCL

OR the completion of the first term of the MSc Computer Science curriculum at UCL

OR the following prior study at university undergraduate (Majors) or postgraduate level:

  • programming in one high-level programing language and one assembly language
  • formal systems of logic such as boolean algebra, propositional logic or predicate calculus
  • virtual machines, virtual memory and memory paging
  • compilers, including lexical analysis, parsing and code generation
  • dynamic data structures and abstract data types
  • models of storage in computer systems
  • algorithmic complexity
Term 2
Taught By Chris Clack (100%)
Aims

This course explores the functional programming paradigm and the implementation technology for functional programming languages. It aims to develop a broad understanding of the functional programming style and recursive programming techniques using the language Miranda, 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 lazy functional language.
  • write non-trivial functional programs.
  • understand the computation and memory management issues affecting the sequential implementation of lazy functional languages.
  • read and understand the research and technical literature on functional programming.

Content

Context

  • Classification of Programming Languages
  • Distinctive Features of Functional Programming Languages
  • Differences between Haskell and Miranda

The Lambda Calculus and Combinators

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

Types

  • A brief introduction to Hindley-Milner type inference

Miranda

  • 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

Automatic Memory Management

  • Memory Allocation and Garbage Collection
  • Garbage Collection Techniques

Method of Instruction

Lecture presentations.

Assessment

The course has the following assessment components:

  • Written Examination (2.5 hours, 100%)

To pass this course, students must:

  • Obtain an overall pass mark of 50% for the exam component.

Resources

Reading list available via the UCL Library catalogue.