Skip to main content

Functional Programming


These lectures provide an introduction to Functional Programming, including both the functional programming language Miranda and functional language implementation techniques such as graph reduction and garbage collection.  The lectures are suitable for undergraduates and generalist MSc students. No prior experience of functional programming in Miranda is assumed.     Note - these lectures do NOT cover use of the Haskell language.

Pre-requisites include:

  • important
    • prior programming experience in a general purpose programming language including dynamic data structures and abstract data types, 
    • some understanding of formal systems of logic such as Boolean logic, propositional logc or predicate calculus, 
    • some exposure to the concepts of compilers such as lexical analysis, parsing and code generation, and 
  • preferably:
    • some prior experience of an assembly language, 
    • some prior exposure to models of stoprage in computer systems and the concepts of virtual machines, virtual memory and paging, 
    • a basic understanding of algorithmic complexity.

Student Objectives

Understand the basics of the lambda calculus and combinators and how they are used in programming and in the implementation of functional languages. Understand the main features of a lazy functional language. Understand type checking, type-inference and the operation of the Hindley-Milner type system as implemented in Miranda. Write, understand and analyse non-trivial functional programs in Miranda. Understand the computation and memory management issues affecting the sequential implementation of lazy functional languages. Be able to solve problems relating to all of the above, under pressure.

Sections and Lectures

The lectures comprise two unequal sections:

  • SECTION 1: Lambda Calculus, Combinators and Functional Programming
  • SECTION 2: Language Implementation, including garbage collection, graph reduction and memory management

The PDFs are password protected - passwords are provided to my students and occasionally to others on request.  Each Lecture is normally presented live (online or in person).

Section 1: Lambda Calculus, Combinators and Functional Programming

2024: Lectures beyond here not yet released


Section 2: Language Implementation