Functional Programming
Summary
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
- Lecture 1 - Overview and Introduction. FP-2024-lecture1.pdf
- Lecture 2 - Lambda Calculus FP-2024-lecture2.pdf
- Lecture 3 - Lambda Calculus Continued FP-2024-lecture3.pdf
2024: Lectures beyond here not yet released
- Lecture 4 - Miranda FP-2020-lecture4.pdf
- Lecture 5 - Patterns, functions, recursion and lists FP-2020-lecture5.pdf
- Lecture 6 - Designing simple programs FP-2020-lecture6.pdf
- Lecture 7 - Designing simple programs continued FP-2020-lecture7.pdf
- Lecture 8 - Recursion in the Lambda Calculus FP-2020-lecture8.pdf
- Lecture 9 - Designing Functional Programs FP-2020-lecture9.pdf
- Lecture 10 - Combinators and Higher Order Functions FP-2020-lecture10.pdf
- Lecture 11 - Higher Order Functions FP-2020-lecture11.pdf
- Lecture 12 - PRACTICAL SESSION - discussing the "challenge" FP-2020-lecture12.pdf
- Lecture 13 - Challenge, Foldr and Foldl FP-2020-lecture13.pdf
- Lecture 14 - Algebraic Types FP-2020-lecture14.pdf
- Lecture 15 - Recursive Algebraic Types FP-2020-lecture15.pdf
- Lecture 16 - Programming Examples FP-2020-lecture16.pdf
- Lecture 17 - Programming Examples Continued FP-2020-lecture17.pdf
- Lecture 18 - Lists, Trees and Graphs FP-2020-lecture18.pdf
Section 2: Language Implementation
- Lecture 19 - Introduction to Implementation FP-2020-lecture19.pdf
- Lecture 20 - Graph Reduction FP-2020-lecture20.pdf
- Lecture 21 - Graph Reduction continued FP-2020-lecture21.pdf
- Lecture 22 - Automatic Memory Management FP-2020-lecture22.pdf
- Lecture 23 - Memory Allocation Techniques FP-2020-lecture23.pdf
- Lecture 24 - Garbage Collection Mark Scan FP-2020-lecture24.pdf
- Lecture 25 - Garbage Collection Copying FP-2020-lecture25.pdf
- Lecture 26 - Garbage Collection Reference Counting FP-2020-lecture26.pdf