Functional Programming

Summary

These lectures providesan 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. Students must also have prior programming experience in a general purpose programming language.    Note - these lectures do NOT cover use of the Haskell language.

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-2020-lecture1.pdf
• Lecture 2 - Lambda Calculus  FP-2020-lecture2.pdf
• Lecture 3 - Lambda Calculus Continued  FP-2020-lecture3.pdf
• 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