COMP0020 Functional Programming

This database contains the 2018-19 versions of syllabuses.

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

Academic session

2018-19

Module

Functional Programming

Code

COMP0020

Module delivery

1819/A6U/T2/COMP0020 Undergraduate

Related deliveries

1819/A7P/T2/COMP0020 Postgraduate

Prior deliveries

COMP3011

Level

Undergraduate

FHEQ Level

L6

FHEQ credits

15

Term/s

Term 2

Module leader

Clack, Chris

Contributors

Clack, Chris

Module administrator

Ball, Louisa

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. The course explores the underlying mechanics of strict and lazy functional languages; it does not use Haskell or F# or OOCAML and does not aim to provide training in such languages, though an introduction to Miranda is provided and students are expected to improve their functional programming skills through independent study. In the second half of the course students are expected to use independent study to read extensively about implementation issues which are then discussed in the lectures.

Learning outcomes

On successful completion of the module, a student will be able to do the following at a level suitable for a Year 3 undergraduate:

  1. understand the basics of the lambda calculus and combinators and how they are used in the implementation of functional languages;
  2. understand the main features of a lazy functional language;
  3. understand type checking, type-inference and the operation of the Hindley-Milner type system;
  4. write and understand non-trivial functional programs in Miranda;
  5. understand the computation and memory management issues affecting the sequential implementation of lazy functional languages;
  6. solve problems relating to all of the above, under examination conditions.

Availability and prerequisites

This module delivery is available for selection on the below-listed programmes. The relevant programme structure will specify whether the module is core, optional, or elective.

In order to be eligible to select this module as optional or elective, where available, students must meet all prerequisite conditions to the satisfaction of the module leader. Places for students taking the module as optional or elective are limited and will be allocated according to the department’s module selection policy.

Programmes on which available:

  • BSc Computer Science (Year 3)
  • MEng Computer Science (Year 3)
  • MEng Mathematical Computation (Year 3)

Prerequisites:

In order to be eligible to select this module, student must have:

  • passed BSc/ MEng Computer Science (Years 1 and 2) at UCL; or
  • undertaken the following prior study at university undergraduate (Majors) or postgraduate level:
    • programming in one high-level programming 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

Content

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

Introduction to Miranda

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

Types

  • A brief introduction to Hindley-Milner type inference as implemented in Miranda.

Recursive Programming Techniques

Introduction to Implementation Techniques

  • Strict Evaluation and Lazy Evaluation
  • The Need for Automatic Memory Management

Automatic Memory Management

  • Memory Allocation and Garbage Collection
  • Garbage Collection Techniques

A full reading list is available on the module’s Moodle page. Further indicative reading material may be available via http://readinglists.ucl.ac.uk/departments/comps_eng.html.

Delivery

The module is delivered through a combination of lectures and guided reading.

Assessment

This module delivery is assessed as below:

#

Title

Weight (%

Notes

1

Written examination (2hrs 30mins)

100

 

In order to pass this Module Delivery, students must:

  • achieve an overall weighted Module mark of at least 40.00%;

AND, when taken as part of BSc Computer Science; MEng Computer Science, and MEng Mathematical Computation:

  • achieve a mark of at least 30.00% in any Components of assessment weighed ≥ 30% of the module.

Where a Component comprises multiple Assessment Tasks, the minimum mark applies to the overall component.