## 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:

- Type classes for C (Dylan Ede, Robinson, 2014/2015)
- A toy language parser builder using parser combinators (Niall Rutherford, Pembroke, 2014/2015)
- The implementation of a compiler from BASIC 78 to LLVM (David Hoare, Robinson, 2014/2015)

### 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:

- A game similar to VIM Adventures in which the player unlocks, for example, library functions as they progress through the game, in order to solve programming puzzles or to navigate the environment.
- A game such as Hack 'n' slash which allows players to manipulate the programming of the game in order to advance
- A graphical user interface for a Domain-Specific Language (similar to Scratch / Unreal Kismet) which allows users to experiment with, for example, music, parsers, or concurrency.

### 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:

You could go down the library/EDSL route and implement fuzzy logic for some language that doesn't have good support for it yet. The goal would be to allow programmers to use fuzzy logic for their applications. Possible extensions include support for type-2 fuzzy logic (where membership functions map to fuzzy sets, rather than normal sets) or, if you are working in a language with a powerful type system, you could try to encode as much information about the fuzzy sets / operations on the type level.

Another interesting approach could be to find a good application for fuzzy logic or another programming technique to mix it with. For example, since fuzzy logic is often used for control systems, it may work well with Functional Reactive Programming. If you wanted to apply it to some problem domain, anything including robots and games would work.

What would a type system based on fuzzy logic look like? Since types are (typically) based on sets, it seems like it should be possible to generalise types to fuzzy sets. How would such types be different from probability types? How would they be useful? This direction for the project would be very theoretical and involve a lot of research.