Experimentation Project

Master/Intern
<!--
%TOC%
-->

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.

<!--
In order to allow for more flexibility in the overall planning we have added an extra option to the curriculum: the experimentation project, which you can do _in any period_.

In this project you will, supervised by one of the lecturers, implement a piece of software. In order to start with such a project you have to find a member of the faculty who is willing to supervise you. In general we will choose the subjects from one of our research areas. So typically you can use this project for:

   * implementing some interesting idea you stumbled upon while doing a seminar
   * try out an idea without having to start with a full thesis project
   * build that small, but so extremely useful tool that everyone has been talking about, but did not find time  time to implement 
-->

---++ Projects (in arbitrary order)

---+++ Using [[Ehc.WebHome][EHC]]'s backend as a backend for [[Center.Helium][Helium]].
#EhcBackend

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: Main.AtzeDijkstra, Bastiaan Heeren, Jeroen Fokker, Jurriaan Hage

---+++ Using [[http://nix.cs.uu.nl/][Nix]] for building [[Ehc.WebHome][EHC]].

Contact: Main.AtzeDijkstra

<!--

---+++ Making lhs2TeX language-independent

lhs2TeX is a tool, written in Haskell, that transforms
literate Haskell code to LaTeX code. There is no strict
parser for Haskell, but only a clever lexer. As a result,
it is possible to run all sorts of files containing
Haskell extensions through lhs2TeX as well.

However, this only works well as long as the modified
language is sufficiently similar to Haskell. The more
the source language deviates from Haskell, the more hacks
and kludges are required to make lhs2TeX work as desired.

The task of this project is to abstract from the Haskell-
specific assumptions in the lhs2TeX tool, so that plugins
for several different source languages can be written.
The resulting tool should have at least three such plugins:

   * a backwards-compatible plugin to reproduce the current
     behaviour of lhs2TeX exactly
   * a plugin for EHC (or, alternatively, a current version
     of ghc including several syntax extensions such as
     functional dependencies or Template Haskell)
   * a plugin for Trinity, an ML-like hybrid functional and
     imperative language currently in development

This project involves:

   * studying the source code of lhs2TeX
   * defining what needs to be done to achieve the goal
   * implementing the changes and the plugins
   * documenting the solution

Depending on the progress, the quality of the solution,
and ideas on how to extend the task, this project could
be developed into a later master thesis.

Contact: Main.AndresLoeh

---+++ Improving the Trinity Debugger

Trinity is a functional/imperative/object-oriented hybrid language (similar
in style to SML and OCaml) that is intended for teaching concepts of
programming languages.

Trinity is implemented as a Haskell interpreter, and one feature of this
interpreter is that you can step through the evaluation of an expression
to see the formally described semantics of the language in action.
The goal of this project is to make this tracer/debugger as convenient
as possible to use.

This project involves:

   * understanding the implementation of the Trinity interpreter
   * identifying weaknesses in the current debugger
   * adding missing features and improving the user experience
   * reducing the mismatch between what is shown on screen and
      what is written on paper
   * improving the overall code quality of the Trinity interpreter where
      possible

If you are interested in Trinity, but not in this particular project:
other projects related to Trinity are probably available, just ask.

Contact: Main.AndresLoeh

---+++ Implementing proper and configurable dependency resolution for cabal-install

[[http://haskell.org/cabal][Cabal]] is a system for building and packaging Haskell
libraries and tools. It is by now used by most of the Haskell packages available.
[[http://hackage.haskell.org/packages/archive/pkg-list.html][HackageDB]] is an
online database of such packages.

Most packages have several dependencies
on other Haskell libraries, and a user who wants to use one package often has
to download and install several packages. Some operating systems package
Cabal packages. Then the OS package manager can track dependencies between
Cabal packages. However, not all OSs have capable package managers and
up-to-date package repositories at the same time. Furthermore, often OS package
managers don't allow the installation of packages for non-root users.

For these purposes,
[[http://hackage.haskell.org/trac/hackage/wiki/CabalInstall][cabal-install]]
is currently being developed. It is a Cabal-specific package manager that
tracks dependencies between such packages and can download and install
all required dependencies for a desired package. However, the current
algorithm that is used by cabal-install is [[http://hackage.haskell.org/trac/hackage/ticket/175][flawed]].
The task of this project is to implement a new algorithm. A framework for such
an algorithm is already present.

This project involves:

   * understanding the Cabal architecture and implementation
   * plugging in the new resolution algorithm
   * devising test cases and identify potential remaining problems
   * fixing problems as far as possible

Contact: Main.AndresLoeh

-->

---+++ Implementing and testing a generic plagiarism detection tool for computer programs
#PlagiarismProg

Marble was written by Main.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: Main.JurriaanHage

---+++ Repetitive Reduction Patters in Lambda Calculus with =letrec=
#RepetitiveReductions

A [[http://rochel.info/TERMGRAPH2011-repetitive-wip.pdf][paper]] with that title is being worked on. It describes an optimisation on &#955;-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 &#946;-reductions to evaluate. This is, however, a rather theoretical result, since the amount of &#946;-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: Main.JanRochel

---+++ Code generation for type classes in Helium
#TypeClassesHelium

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: Main.JurriaanHage

---+++ Adding logging facilities to GHC
#LoggingFacilityGHC

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: Main.JurriaanHage

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

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: Main.JurriaanHage

---+++ Further extensions to PHP Validator
#PhpValidator

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: Main.JurriaanHage

---+++ Making type directives for Helium more mature
#TypeDirectives

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.

<!-- Maybe also add resource files to Helium. -->

Contact: Main.JurriaanHage, Bastiaan Heeren

---+++ Repair systems
#RepairSystems

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 [[http://www.cs.uu.nl/wiki/bin/view/Hage/MasterStudents#Arjen_Langebaerd][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.WebHome][Helium]] and [[Top.WebHome][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: Main.JurriaanHage and Bastiaan Heeren

---+++ Design/build a Wiki system using Haskell

Contact: Main.AtzeDijkstra, Main.DoaitseSwierstra

%INCLUDE{WP.ExperimentationProject}% 
<!--
#TTInteractiveTestTraces
---+++ Interactive Test Traces

T2 is our homegrown automated testing tool for Java. [[WP.T2Framework][Check it out here]]. Unlike other java testing tools T2 performs the testing on-the-fly; so without first generating Junit scripts. T2 stores the tests in the form of a meta data structure called _trace_. Being just a data structure, it can be manipulated like one, including interpreting over it to build the actual testing execution that the trace represents. We need someone to build a GUI for viewing a trace. The user should be able to follow the trace step by step, and see the (intermediate) state of involved objects. Since you have access to the trace anyway, you can just as well allow the user to edit the trace and re-interpret it. Typically the traces come from the tool T2; these are violating traces: traces that end up in some error. After the programmer fix the error; retesting will show that the error indeed disapears. Now, with the help of your GUI the programmer can furthermore interactively try out various mutants of the original test trace to see if no new error pops up.

Contact: [[WP.WebHome][Wishnu Prasetya]]
-->

---+++ Design/build a web based interface for [[Ehc.WebHome][EHC]]

Contact: Main.AtzeDijkstra, Main.DoaitseSwierstra

---+++ Generate a pretty printed visualisation (!LaTeX and/or Html) of type derivation trees for [[Ehc.WebHome][EHC]]

Contact: Main.AtzeDijkstra, Main.DoaitseSwierstra, Main.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: Main.DoaitseSwierstra

---+++ Program Animation
In principle we know how we [[http://www.cs.uu.nl/wiki/bin/view/FP/SomeAnimation][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: Main.DoaitseSwierstra