Masters Projects

We are always looking for master's students. There are many topics on which you can write a thesis. Some lean towards the theoretical while others are more practical. The lists below should give you an idea of what we've done and what we may potentially do.

Potential Projects

In this section we list a couple of topics on which you can write a Master's thesis. This is not a complete list, contact Johan Jeuring if you want to know more about writing your Master's thesis on the topic of generic programming.

• Generic programs often use type-indexed datatypes: datatypes that are obtained from other datatypes in a generic way. Some example are a datatype extended with variables, with holes, or the datatype you define when implementing a zipper for a datatype. A common problem with such type-indexed datatypes is that values of these datatypes have to be constructed using the constructors of the type representation, instead of the constructors of the original datatype. We have some ad-hoc solutions for particular cases, but in this project it is the idea to solve this problem once and for all...
• Model-driven development. Model-driven development (or engineering, architecture, ...) has received a lot of attention lately. Generic programming is a kind of model-driven development. In this assignment you will have to investigate the various kinds of applications of model-driven development, and determine which of use would profit from generic programming. Of course you have to provide the implementation as a generic program as well.
• From datatype-specific to datatype-generic programs. A number of applications would profit from `generalisation'. Examples are computer algebra packages, exercise assistants, or compilers. A generic program can be applied to more domains, but it might also be possible to obtain a more efficient program by choosing a different datatype representation, and generating all of the boilerplate code from generic programs.
• Generic bidirectional programming. Turn generic programs into bidirectional programs, for example the generic programs in the library of EMGM. Investigate if these bidirectional programs can be used to replace some of the work in the bidirectional programming literature.
• Optimise Haskell compilers to compile generic programs into more efficient code.
• Turn the exercise assistants we are developing into a generic program. In principle we know how to turn most components of the exercise assistants into generic programs, but turning the complete program into a generic program is challenging because of concepts such as abstract datatypes, domains with a special semantics, etc.

Current Projects

Previous Projects

These are projects previously undertaken by master's students. Browse the included abstract or follow the link for more information.

Generic selections

Martijn van Steenbergen, Utrecht University, May 27, 2010.

Tools for computer languages need position information: compilers for providing better error messages, structure editors for mapping between structural and textual views, and debuggers for navigating through a term, for instance. Manually adding position information to an abstract syntax tree is tedious and requires pervasive changes: the original tree becomes verbose and every function operating on it needs to be adapted.

In this thesis, we describe how to automatically extend datatypes with position information using datatype-generic programming techniques. Furthermore, we show examples of how to use this position information: parsers that automatically construct trees annotated with positions, catamorphisms that deal with failure by reporting error locations, and zippers that efficiently navigate annotated trees. The generic programming technique we describe is applicable to a wide range of domains.

Generic programming with fixed points for parametrized datatypes

Erik Hesselink, Utrecht University, December 10, 2009.

Generic Views for Generic Types

Thomas van Noort, Utrecht University, January 24, 2008.

Generic programming allows us to capture uniform behaviour for a family of types in a single defi- nition. In this thesis, we focus on Generic Haskell, a preprocessor to Haskell that enables us to define generic functions and generic types. Such definitions are applicable in almost any context since their result depends on a structural representation of types. Several representations exist, which together are called generic views. These generic views include a standard view using sums of products, a balanced view to improve efficiency, and a fixed-point view that makes the recursive occurrences in a type explicit. In contrast to generic functions, Generic Haskell allows us define generic types only using the standard view.

This thesis studies to what extent generic views, other than the standard view, are useful on the type level. We illustrate the use of generic views for generic types by giving several examples, in- cluding a finite map library with improved efficiency, a generic rewriting library with automated extension of the object language with meta variables, and the zipper for efficient traversal of data structures, with improved usability. Additionally, we present a formal approach to the translation of generic views for generic types and discuss the implementation in the Generic Haskell compiler.

Comparing Haskell libraries for generic programming

Alex Gerdes, Open University (supervision at Utrecht University), October 27, 2007.

There are numerous approaches to generic programming in Haskell. Until now there hasn’t emerged a clear winner. The time is right to join all the scattered effort and to converge into one common generic programming library. This master’s thesis takes the first step in that process and develops a set of criteria that can be used to evaluate and compare the known generic programming libraries in Haskell. Besides the criteria, a set of test functions has been developed to test whether a generic programming library satisfies a particular criterion. A first preliminary evaluation of a few libraries is conducted. This master’s thesis paves the way for the design of a common generic programming library in Haskell.

Generic Views

Stefan Holdermans, Utrecht University, January 5, 2005.

Structural polymorphism allows for generic functions to be defined by induction over the structure of types. In Generic Haskell, the structure of a type is perceived as a nested sum of products. Over the last few years it has been shown that a great amount of generic programs can be defined in terms of this perception. Still, there are applications for which viewing data types as sums of products limits the expressiveness of Generic Haskell. As it turns out, different perceptions of the structure of types enable the definition of generic programs that are more efficient, more elegant, and more expressive. We show how these different perceptions, which we call generic views, can be implemented and used in Generic Haskell.

And before...

We have studied generic programming since 1995, and besides the Master's students mentioned above, other Master students were:

• Paul Hagg, UU, MSc (2002): A framework for developing generic XML tools
• Joost Halenbeek, UU, MSc (1998): Comparing Approaches to Polytypic Programming
• Patrik Jansson, Chalmers, MSc (1995): Polytypism and polytypic unification.
• Jan de Wit, UU, MSc (2002) A technical overview of Generic Haskell