Experimentation Project

Below is a list of topics for experimentation projects in the general theme of programming/software technology. It is possible to do these projects even if you don't do the Programming Technology line, as long as you have the needed background. It is possible that after sometime the list becomes out-dated, but it should still give you a hint as to the general research areas of our researchers. You are welcome to approach them to ask if they have new projects.

Projects (in arbitrary order)

Using EHC's backend as a backend for Helium.

Currently, Helium's backend is an interpreter written in C and because the original developer left, hard to maintain. EHC has a backend of its own, and supports quite a bit more of Haskell than Helium currently does. In this project, you try to connect the two together via the core language. The main complication will be that the object files of Helium also store some type inference information, and this must be preserved in some way (probably through interface files).

Contact: AtzeDijkstra, Bastiaan Heeren, Jeroen Fokker, Jurriaan Hage

Using Nix for building EHC.

Contact: AtzeDijkstra

Implementing and testing a generic plagiarism detection tool for computer programs

Marble was written by JurriaanHage in Perl, mainly for plagiarism detection for Java programs. I'd like to extend this to other languages, but without copying Marble and making a new instantiation. You should investigate in what respect existing programming languages differ and how they can be parameterized to yield a system that also support plagiarism detection for languages similar or not so similar to Java.

Other extensions to the existing system are:

• dealing with programming assignments in which parts are supplied by the lecturer
• addition of new heuristics that can serve to add to the power and precision of the system (two heuristics know more than one).

If you think the tool can and should be implemented in a different language: this is certainly open to discussion. Haskell is a good option as far as I am concerned.

Deliverables: the source code for the system, a manual and an architectural description.

Prerequisites: Grammars and Parsing, and Compiler Construction.

Contact: JurriaanHage

Repetitive Reduction Patters in Lambda Calculus with letrec

A paper with that title is being worked on. It describes an optimisation on λ-calculus with letrec (which means that it is applicable to Haskell) that lifts certain 'constant' parameters out of recursive positions. This transformation leads to a form that needs fewer β-reductions to evaluate. This is, however, a rather theoretical result, since the amount of β-reductions is not a good measure for efficiency on practical evaluators such as the run-time systems of existing Haskell implementations. Therefore besides the primary task of this project to implement the optimisation (analysis + transformation) it would also be interesting to determine in which cases exactly the optimisation actually increases run-time efficiency.

Contact: JanRochel

Code generation for type classes in Helium

Jeroen Weijers has added type classes to Helium's frontend. We, however, still lack some facilities in the backend for executing programs that have type classes.

Prerequisites: at the very least Compiler Construction. Advanced Compiler Construction would be helpful.

Contact: JurriaanHage

Adding logging facilities to GHC

This is a relatively lightweight thing to do. The idea is that when a programmer compiles with --make then he may elect to log the results of the compile to a server somewhere. I do not think internal knowledge of the compiler is necessary, programming will be through the GHC API.

Since this is a relatively small task, there's bound to be a need for doing something extra, that may not be directly related to this particular project.

Contact: JurriaanHage

Develop a website for cross-comparing type error messages in Java

Nabil el Boustani and I developed a system for generating improved type error messages for generic method invocations. We would like to offer this as a service to programmers and students. The idea is to have people upload a Java program, we compile it with our own compiler, with Sun's javac and Eclipse's ejc and show all error messages. We log the programs we thus obtain, and ask the people who use the site to indicate what they think of the messages. Information should be stored in a database for later querying.

Contact: JurriaanHage

Further extensions to PHP Validator

Patrick Camphuijsen developed a tool to perform all kinds of analyses on PHP code, in Java. A new version was implemented by Henk Erik van der Hoek in Haskell, which was again extended by Marcelo Sousa. Your task is to further extend the system. For this you will need knowledge of dataflow analysis (which you may learn during the course Automatic Program Analysis).

Contact: JurriaanHage

Making type directives for Helium more mature

We introduced type inference directives in a paper at ICFP 2003. These have been implemented into the Helium compiler. In this project, you shall implement additional features to make type inference directives more user-friendly. These may include also the type class inference directives described in our paper at PADL 2005.

Contact: JurriaanHage, Bastiaan Heeren

Repair systems

One way to give feedback to a programmer when his program contains a type error, is to show possible ways to correct the program. Some years ago, Arjen Langebaerd made a first investigation into this issue, see the thesis. We want to take this further by offering a domain specific language to programmers to allow them to tune the repair process to their liking, for example by allowing them to tune the priorities, or by allowing them to specify repair heuristics themselves and providing a general method inside the compiler to find the best reparation and execute. The project takes place within the context of Helium and Top and a substantial part of your work will be to program an extension to the existing extension made by Arjen Langebaerd and to test it thoroughly to obtain experimental results. If succesful, this work can lead to a publication.

Contact: JurriaanHage and Bastiaan Heeren

Design/build a Wiki system using Haskell

Contact: AtzeDijkstra, DoaitseSwierstra

Experimentation projects in automated testing

Contact: Wishnu Prasetya

T2, the Next Generation

T2 is our homegrown automated testing tool for Java featuring sequence based testing, in-code specifications, and on-the-fly checking; more on T2 here. T2 generates tests in the form of sequences of method calls. These are represented with some internal data structures which are then saved through serialization. Saved tests are useful so that we can replay them later for analysis and for regression. In the recent years there have also been a lot of exciting projects build around T2, that add more capabilities to it:

• Prime path coverage, by Maaike Gerritsen, see her thesis.
• Genetic algorithm for test cases generation, by Christiaan Hees, see his thesis.
• Smart test-cases selection, by Jeiel Schalkwijk, see his thesis.

However the original design of T2 was intended to be simple. So, it was rather ad-hoc. Extensions such as the ones above were originally meant to be pure research experiments, but in the end we think it would be nice if they can be part of T2's release. This in itself is possible, but due to to T2's ad-hoc architecture the integration will be unmaintainable.

So, we need someone who can redesign T2, to make it more modular and extensible in an OO way. We want you to make the next release for T2. Here is an non-exhaustive list of wishes:

• A systematic way to control the randomness of T2
• A simple base test-sequences generator, which is extensible in an OO way, e.g. by using some design pattern
• Concept of coverage which is built-in from the start
• Concept of test-case selection and replay which is built-in from the start
• A more robust and clever way to serialize and de-serialize test-sequences
• A better way to express trace directors (for model-based testing)
• A less invasive way to write specifications and test interface

High Performance Log Analysis

We are currently involved in a European research project called FITTEST. The project seeks to improve automated testing techniques for future Internet applications. These future applications are expected to be much more dynamic that what we have today, to such an extent that the traditional pre-release testing approach is not going to work anymore. FITTEST proposes a continuous approach, where testing is done regularly along side the production. The approach relies a lot on analyzing logs to provide feedback information for testing. We have build a prototype of a new logging framework. It is already quite sophisticated, that it can automatically inject logging statements to the target application. In FITTEST, injection will be done systematically and in large scale, so that we can maximize the amount of feedback information we get.

On the other hand, this also means that a lot of information will be produced. To make high performance analysis of logs, we need compression. The idea is to store the logs in a compressed form, so that it is space efficient. But it has to be in such a way that at least basic queries on the logs can still be done efficiently without having to fully decompress them. Our current algorithm does not deliver enough compression rate. We need you to come up with a smart solution with this.

Design/build a web based interface for EHC

Contact: AtzeDijkstra, DoaitseSwierstra

Generate a pretty printed visualisation (LaTeX and/or Html) of type derivation trees for EHC

Contact: AtzeDijkstra, DoaitseSwierstra, ArieMiddelkoop

Parser Combinator Related

With the new parser combinator library (under development) several issues are to be implemented

Generate Syntax Diagrams

Give a redefinition of the combinators (and probably extend them) such that syntax diagrams (e.g. using Tikz) can be generated. Change the error messages in such a way that they contain a reference (url) to these digarams, such that students can see why their input is erroneous.

Re-implement the abstract interpretation part

for the new library, such that parsing speed increases. In order to keep the library modular this may be done by giving an attribute-grammar based description of the library.

Contact: DoaitseSwierstra

Program Animation

In principle we know how we animate the execution of a function. For this we have however to write code. Can we use the Hat tracer to avoid having to write the specialised cases over and over again?

Contact: DoaitseSwierstra