Part II projects & ideas for 2015/2016

I am happy to supervise Part II projects which are related to my research interests, general software engineering, or my personal interests (games, education, food/cooking, and aviation). While I would encourage you to come up with your own idea, this page contains some suggestions for projects below.

If you are interested in one of the projects on this page, a variation of one, or your own, feel free to send me an email. I would also be more than happy to answer any questions about the proposals on this page or to have an informal chat in person.

I have had the pleasure to supervise the following projects in the past:

Adding type classes to low-level languages

Types classes in Haskell enable ad-hoc polymorphism. Consider the following typing:

double :: a -> a

It says that double is a function which, given some value of an arbitrary type a, returns a value of the same type a. We can see that this function must be the identity function, which simply returns what it is given, because there is nothing else we can do with a value of an arbitrary type.

However, this is not our intention with double. We want a generic function which doubles a numeric argument. We could specialise a to a numeric type, but there are many different numeric types in Haskell (Int, Double, etc) and we want double to work with all of them. Type classes provide a solution:

double :: Num a => a -> a

Num a is a type class constraint that constrains a from an arbitrary type to those which are instances of the Num type class. A type class, such as Num, specifies a collection of typings for which there must be specialised implementations for types which wish to be instances of the type class.

The definition of Num, for example, includes the * operator. Therefore, every type that is an instance of Num has an implementation of *, allowing us to give the following definition for double:

double x = x * 2

Note that Haskell can infer the type of this function automatically, including the need for the Num constraint. This is a nice way of writing generic and reusable code and other languages with parameteric polymorphism could also profit from it. The goal of this project would be to extend a language such as C or C++ with type classes, either by extending an existing compiler or writing one from scratch.

You can read more about type classes in this paper. Note that there have also been various extensions to them over the years which may be worth exploring, such as multi-parameter type classes, functional dependencies, and (associated) type families.

Games that teach programming/Computer Science

Computer Science education is becoming increasingly important in today's world and, with Computer Science now being part of the GCSE curriculum, it is important to think of good, entertaining ways to teach Computer Science which are accessible to all children. Some existing projects, such as Scratch, aim to provide a fun platform for learning about programming. The aim of this project would be to develop a game which teaches a programming language or Computer Science theory through its gameplay. There are many ways in which this could be done, but here are some possibilities:

Libraries/Languages for Fuzzy Logic

In classical set theory, values either belong to a set or they don't. In other words, membership for a set \(A\) can be decided by a function \(\mu_A \in U \to \mathbb{B}\) for some universe \(U\). In fuzzy logic, values belong to sets to some degree. Membership of elements from some universe \(U\) for a fuzzy set \(B\) is therefore decided by a function \(\mu_B \in U \to [0..1]\).

For example, if \(\mathit{a}\) is an element of a fuzzy set \(\mathit{X}\) to a degree of \(0.1\) and an element of a different fuzzy set \(\mathit{Y}\) to a degree of \(0.9\), it belongs to \(\mathit{X}\) a little bit and to \(\mathit{Y}\) a lot.

Fuzzy sets are used primarily for linguistic variables in Fuzzy Inference Systems (FIS). A FIS consists of Fuzzy Inference Rules which may, for example, state that

\[ \ \mathbf{IF}~\mathit{Lie}~\mathbf{is}~\mathit{believable}~\mathbf{AND}~\mathit{Deliciousness}~\mathbf{is}~\mathit{high}~\mathbf{THEN}~\mathit{TestPerformance}~\mathbf{is}~\mathit{favourable} \]

where \(\mathit{Lie}\), \(\mathit{Deliciousness}\), and \(\mathit{TestPerformance}\) are linguistic variables. \(\mathit{Lie}\) and \(\mathit{Deliciousness}\) are the inputs to this system and \(\mathit{TestPerformance}\) is the output. These may correspond to, for example, numeric inputs and outputs. \(\mathit{believable}\) is a fuzzy set that is part of the linguistic variable \(\mathit{Lie}\). If \(\mathit{Lie}\) corresponds to, for example, a numeric input, then the membership function for \(\mathit{believable}\) will assign it a degree to which it belongs to \(\mathit{believable}\). There may be other fuzzy sets in \(\mathit{Lie}\) as well, each of which will assign a truth value to an input.

Fuzzy Inference Rules determine how outputs should be computed. Given the above rule, we would take the truth value of \(\mathit{believable}\) and of \(\mathit{high}\) to calculate the truth value for \(\mathit{favourable}\) using some arithmetic.

There are multiple, possible directions this project could take: