Tomas Petricek @ Computer Lab

Part II Project Ideas

Update 2012/2013

I already have enough students for the year 2012/2013, so I'm not able to supervise more Part II projects at the moment. However, if you like some of the proposals below, you can try contacting others from our research group and hopefully you'll find someone.

Dominic Orchard (dao29) is doing things related to functional programming and Haskell, so he might be a good person for functional programming related topic. Pete Calvert (prc33) might be a good person for concurrency or distributed programming. Raoul-Gabriel Urma (rgu20) might be a good person if you want to do something in Java/Scala or web-related.

Functional programming, tools, functional languages and libraries:

Working with data and F# type providers, type systems and other:

OCamlLabs: Types for cross-compilation

Increasing number of applications are targetting heterogenous execution environments such as server-side, client-side, GPU, embedded and web. This is supported by a number of OCaml compiler backends (JavaScript, Java, ARM, LLVM) and libraries allowing interoperability. In such a scenario, certain parts of code may be compiled only for certain platform-specific environments, but some can be safely shared. This project should extend the OCaml type system in order to track execution environments for which an expression can be compiled, and simplify writing code that cross-compiles for multiple platforms and diverse execution environments.

This project idea comes from the OCamlLabs web site, but I'd be happy to supervise it. As the name suggests, this should be done as an extension to the OCaml compiler, but if you're interested in other tools and languages, let me know.

Related articles:

Functional data-binding (Taken)

At the basic level, data-binding is a mechanism (known from various JavaScript or .NET libraries) that is used to specify how to display data in a user-interface. It is possible to bind various user-interface elements to properties from some data source. More interestingly, two-way data binding can be used to create connection that works in both ways - the data are displayed in the UI, but when they are changed in the UI, the change is propagated back to the data source.

In functional programming, functional reactive programming (FRP) serves a similar purpose, but it is generally focused on just one way information flow (i.e. how data from robot sensors flow and influence the behaviour of a robot).

There is a number of interesting problems here. For example, how could we implement data-binding library that is less ad-hoc than those used in JavaScript or .NET and is inspired by functional programming ideas? Could the FRP concepts be extended to work bothways?

Related articles:

Visual editor for domain specific languages

Domain specific languages (DSLs) give a powerful technique for writing reusable libraries (not just) in functional languages. Given a problem (i.e. processing lists), we design a set of reusable combinators (mapping, filtering, etc.). A specific problem (such as a task to multiply elements of two lists by some number and then combine them in some way) can then be easily solved just by using the available combinators.

The approach is used not just for list processing, but in many other areas - for composing user interfaces, specifying event handling, modelling financial contracts, etc. Here is an example of list processing (using F#):

List.zip (list1 |> List.map (fun x -> x * 10))
         (list2 |> List.map (fun x -> x * -10))
|> List.iter (fun (a, b) -> printfn "left %d, right %d" a b)

The code can be quite nicely represented visually, showing how the data flow through the combinators:

The idea of this project is to design some editor (or, at least, visualizer) that can take code written using DSL and display it visually and allow the user to edit it. This should work for any DSL (although it may need to be annotated in some way).

Related articles:

Refactoring tool for functional languages (Taken)

Any modern IDE like Eclipse or Visual Studio provides a number of automated refactoring ranging from simple ones (like rename) to fairly complicated operations (extract part of a class into a superclass, etc.)

The goal of this project would be to implement some advanced refactorings for a functional programming language (probably using open-source compiler for Haskell, F# or some other). The interesting question is, what kind of advanced refactorings would be useful in functional languages?

  • Turn purely functional code to monadic code (i.e. asynchronous in F# or to support I/O in Haskell)
  • Turn a tuple type into a data type such as record
  • Group function parameters into a data type or un-group a data type
  • Extract common parts of two functions into a higher-order function
  • ...

Web programming with alternative formlets

Formlets provide an interesting abstraction for web programming - they represent a web "form" that can be rendered (on the server-side) to get HTML representing a form. When the user fills in form information and submits the result, the "formlet" can process the incoming data to get a data-structure representing the result of the form (such as customer information).

Formlets are designed for old-fashioned web programming where most of the processing happens on the server-side, so the question is, could we adapt them to make them more useful on the client-side too?

One interesting option is using the Alternative type, which extends the core concept behind formlets and adds a notion of choice. This means that one could build forms with multiple different options and the option could be chosen on the client-side dynamically. However, there are probably many other interesting approaches!

Related articles:

F# type providers

F# 3.0 makes it possible to write "compiler plugins" called type providers that provide access to external data sources, such as web services, databases, or other online information sources. The plugin takes the schema of the external data source and maps it to F# types. The programmer can then easily access any external data source (for which there is a type provider). Here is an example:

There is a number of interesting data sources that do not have a type provider yet, so one project would be to implement a type provider for accessing some interesting data source. Other interesting projects could deal with unstructured data - for example, how to extract reasonable structure from HTML pages or how to easily describe REST services (so that the provider can map them to programming language).

Related articles:

Combinators for schematized data

When working with external data sources, there is a number of common operations that one needs to perform. For example, you can:

  • Merge two data sources that provide similar information (for example, two movie databases) and combine the overlapping information (i.e. ratings)
  • Add data source as an extension to another - for example, if you have a directory with software companies, you could enhance it by adding their stock prices from data source such as Yahoo Finance.
  • And there are probably many other options...

The goal of this project would be to find more interesting operations that can work on schematized data and to implement them as a library. Ideally, this could be integrated with F# type providers (so that you could easily create type providers that combine different data sources).

Fuzzy type-checking

In statically typed programming languages, the type system is used to check that types of expressions are used correctly and are correctly composed (i.e. you call a function with an argument of a correct type).

However, sometimes we do not quite surely know what the type of an expression is. This may be because we're calling some dynamically typed code or because we're loading data from an external data source that does not have a clear type.

The goal of this project is to create a "fuzzy" type system that can deal with such uncertainty in programs. For example, if the type system can tell us that the property "Name" is a string in 99% of the cases, then that's quite useful information!

This is probably more theoretical or experimental project, but it could be implemented as a simple language (i.e. for data processing) or it could be written as an additional checker for dynamic programs or programs in Haskell, F# or other language.

Related articles:

  • Fuzzy Logic - type systems for functional languages are connected to logics, so the new type system would be probably related to fuzzy logics in some way

Other projects

I'm happy to supervise other interesting projects related to functional programming, F# language (and other functional languages), programming with data, web programming and JavaScript, as well as distributed, concurrent and reactive programming. This is not a complete list, just a list of areas that I know more about (and might be able to supervise better). If you have some idea that you'd like to discuss,