Ïã¸ÛÁùºÏ²Ê

Aims:

This module 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 module 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 module students are expected to use independent study to read extensively about implementation issues which are then discussed in the lectures.

Intended learning outcomes:

On successful completion of the module, a student will be able to (at a level commensurate with FHEQ level 6):

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 Miranda (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 any aspect of the module's syllabus, under examination conditions.

Indicative content:

The following are indicative of the topics the module will typically cover:

1. Classification of programming languages:
   • Distinctive features of Functional Programming Languages.
2. The Lambda Calculus and Combinators:
   • Versions of the Lambda Calculus.
   • Syntax and semantics.
   • Reduction orders, strong normalisation.
   • Combinators and computationally complete sets.
3. Introduction to Miranda:
   • Programming environment.
   • Types and simple polymorphic types.
   • Recursion.
   • Pattern-matching.
   • Lists.
   • Higher-Order functions.
   • User-defined types.
4. Type polymorphism and type systems.
5. Recursive programming techniques.
6. Introduction to implementation techniques:
   • Strict evaluation and lazy evaluation.
   • The need for automatic memory management.
7. Automatic memory management:
   • Garbage collection techniques.

Requisites:

To be eligible to select the module delivery for Undergraduate (FHEQ Level 6) as optional or elective, a student must be registered on a programme and year of study for which it is formally available.

To be eligible to select the module delivery for Postgraduate (FHEQ Level 7) as optional or elective, a student must both: (1) be registered on a programme of study for which it is formally available; and (2) have either taken all Term 1 modules of the MSc Computer Science programme at Ïã¸ÛÁùºÏ²Ê or have studied the following at FHEQ level 6 or higher:

• 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.

Students must be proficient in the English language to Ïã¸ÛÁùºÏ²Ê's Level 4 standard or better.