COMP0020: Functional Programming
Christopher D. Clack
University College London
Academic Year 2019-2020
COMP0020: Functional Programming
Course Objective
Explores the functional programming paradigm and the implementation technology for functional programming languages.
Uses the functional language “Miranda”.
NB : this module does not aim to teach Haskell (though we may discuss Haskell in passing).
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 2 / 18
COMP0020: Functional Programming
Student Objectives
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 as
implemented in Miranda.
4 Write, understand and analyse 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.
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 3 / 18
COMP0020: Functional Programming
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.
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 4 / 18
COMP0020: Functional Programming
Approximate Schedule of Lectures
Tuesdays : Wednesdays : Fridays :
10am 10am 1pm
Bentham House LG26 Lecture Room Bentham House LG26 Lecture Room Cruciform Building B404 – LT2
Monday 13th January 2020
Lambda Calculus, Miranda Programming, Advanced Concepts
Advanced Concepts, Implementation Techniques
Start of Term :
5 weeks of lectures : (Reading Week)
4-5 weeks of lectures :
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 5 / 18
COMP0020: Functional Programming
Moodle page : COMP0020 : Functional Programming (previously COMP3011COMPGC16) — essential reading !
There is no marked coursework, but students must complete formative exercises during and between lectures. The book and the Moodle page have simple self-study exercises and answers. There are many past paper questions, without answers. Feedback is given on attempted solutions to past paper questions.
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 6 / 18
COMP0020: Functional Programming Section 1 : Introduction
Introduction to Functional Programming
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 7 / 18
COMP0020: Functional Programming Section 1 : Introduction
Many people think of Alan Turing as ‘the father of computing”, but there are many other important figures in computer science. In particular, Alonzo Church (Turing’s PhD supervisor).
Church and Turing promoted two different (and provably equivalent) approaches to programming :
Turing was interested in building machines and understanding how to control them using a small set of rules.
Church was interested in how to express problems in a precise way, to be solved by automatic transformation using a small set of rules.
These approaches have much in common, but they lead to two radically different styles of programming.
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 8 / 18
COMP0020: Functional Programming Section 1 : Introduction
Consider the notion of programming languages in general :
How many programming languages currently exist ? 1 and how many can you use ? Does the choice of language matter ?
Are older programming languages irrelevant ?
should we only use the most recent language ?
are the rest just “junk” ?
1. See “The next 700 programming laguages”, P.J.Landin, 1965 at https ://homepages.inf.ed.ac.uk/wadler/papers/papers-we- love/landin-next-700.pdf
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 9 / 18
COMP0020: Functional Programming Section 1 : Introduction
Can you just use (say) Java for every programming task ?
if a language (and associated compiler and runtime system) provides a computational system that is Turing-equivalent, 2 is it the only language you need to learn ?
Since many problems can be solved without the full power of a Turing Machine, why should we care ? What else do programming languages gives us ? expressivity (e.g. type systems), abstraction,
protection from common errors (e.g. type systems), different ways to think about solving problems Different languages, different computational models, change the way we think
2. Turing-equivalence and Turing-completeness are outside the scope of this module.
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 10 / 18
COMP0020: Functional Programming Section 1 : Introduction
It can be helpful to group programming languages into different categories (though it can be difficult to do this precisely, since some languages incorporate more than one computational model).
There are many ways to do this ; one way is to identify
the “imperative” languages (typically based on the concept of giving instructions to a machine) ⋆ e.g. Java, C++, Fortran
the “declarative” languages (typically based on the concept of solving a problem) ⋆ e.g. Haskell, Miranda, Prolog
The class of “declarative” languages contains both “functional” languages (e.g. based on Church’s λ-calculus) and “logic” languages (e.g. based on first-order predicate calculus)
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 11 / 18
COMP0020: Functional Programming Section 1 : Introduction
A simple example of the difference in programming style
Assume “results” is the name of a variable that contains a sequence of 100 integers, and write code to select all those with a value less than 10
Imperative style :
int small[100] ;
int j,k ;
for (j = 0, k = 0; j < 100; j + +)
if (results[j] < 10){ small[k] = results[j]; k + +; } return (small );
Functional style :
filter (< 10) results
Concise, low syntactic “clutter”, reduced need to specify storage of intermediate results
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 12 / 18
COMP0020: Functional Programming Section 1 : Introduction
An example of literate programming style using Miranda
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 13 / 18
COMP0020: Functional Programming Section 1 : Introduction
A practical example of functional programming style
Functional Programming languages are renowned for their “elegance”
But are they like Japanese Haiku poetry (elegant, but not very practical) ?
Or are they like Karate (elegant, and useful in a fight) ?
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 14 / 18
COMP0020: Functional Programming Section 1 : Introduction
Prototyping a large object-oriented design using a functional programming language
A commercial project (a very large international settlement bank)
The world’s largest IT Consultancy
A “mission-critical” financial system
Over 100 programmers
C++ required by client
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 15 / 18
COMP0020: Functional Programming Section 1 : Introduction
Component-based system design : a network of components (“nodes”) communicating via streams of data (”arcs”). One or more inputs (“arcs”), one output (“arc”).
Project requirements :
Discrete-event simulation of component network.
Prototyping of central optimisation and approximation algorithms
The main constraint was C++
⋆ Too slow for rapid prototyping work (execution speed was very fast, but development time and debugging effort too great for prototyping many different designs)
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 16 / 18
COMP0020: Functional Programming Section 1 : Introduction
IT Consultancy’s dilemma :
C++ required by client, but “not viable” for prototyping/simulation ⋆ Would take too long to develop the underlying components
Rapid prototyping object-oriented language (e.g. Smalltalk) “not desirable”
⋆ Smalltalk known to client — raised issue of suitability of client’s choice of C++ (consultancy did not
wish to “insult” client)
Alternative approach — use a functional language (Miranda)
Higher Order, Statically Typed, Lazy, with Garbage Collection, no pointers, no assignment
Unknown to client ( !)
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 17 / 18
COMP0020: Functional Programming Section 1 : Introduction
Selling points :
Speed and Clarity with which algorithms can be ⋆ expressed
⋆ validated
Can simulate key object-oriented designs in detail
⋆ With minimal detail for other components ! Access to expertise :
A “champion”
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 18 / 18
COMP0020: Functional Programming Section 1 : Introduction
Note : Speed of execution was almost totally irrelevant !
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 19 / 18
COMP0020: Functional Programming Section 1 : Introduction
Modelling the component network
Figure : A network of component (nodes) sending streams of data (arcs) to each other.
Recursive (looping) functions a, b, c and d
c1, c2 etc. are streams of (time, value) events — represented by potentially-infinite lists of 2-tuples
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 20 / 18
COMP0020: Functional Programming Section 1 : Introduction
Assume recursive (looping) functions a, b, c and d are defined elsewhere Define the streams of (time, value) tuple :
c1
c5
c9
(c2, c3) (c4, c6) (c7,c8)
= read ”file1” = read ”file2” = b(c2, c6, c8) = a(c1, c4)
= c(c5, c7) =d(c3)
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2019-2020
21 / 18
COMP0020: Functional Programming Section 1 : Introduction
Simulating behaviour
Simple, behavioural and executable specification
Expression-based (ordering of sub-expressions is easier than ordering of commands)
Synthetic (statistical) data generation
Used Miranda algorithms as specification for subsequent implementation in C++
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 22 / 18
COMP0020: Functional Programming Section 1 : Introduction
Results
Rapid development
About 5 times faster than C++ Concise expression
6 pages of Miranda = about 25 pages of C++
Simulation and specification of complex processes
Design optimised early in lifecycle
Confidence increased through validation on real data
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 23 / 18
COMP0020: Functional Programming Section 1 : Introduction
Results
Almost NO errors in prototype code
Vast reduction in errors in final C++ code
Viewed as a commercial advantage
Promoted worldwide within the IT Consultancy — “champion” promoted to Manager
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 24 / 18
COMP0020: Functional Programming Section 1 : Introduction
END OF LECTURE
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 25 / 18