Ideas for Individual Projects (G53IDS, MSc projects, etc.)

Here are some project suggestions I'm currently particularly excited about:

Most of these, along with others, are described in more detail below. Feel free to get in touch with me to get more information.


Games

This is a standard project, possibly a bit of a last resort, although I have seen really good ones, so it does not have to be so. What is important is that the project isn't trivial, and preferably it should also have some novel, interesting and maybe even research-oriented aspects to it. Thus, there needs to be a "twist" (or two).

For example, a while back, one student programmed a backgammon game that used genetic algorithms for training a neural network allowing it to learn how to play backgammon well. Other interesting possibilities might be novel multi-player mobile phone or Internet games.

I'm personally quite interested in the functional programming language Haskell, and I would thus welcome people who are interested in writing games in Haskell, especially if there is a graphical aspect to them. wxHaskell (a Haskell binding for wxWidgets) [1,2] would probably be a suitable library. To make things more interesting, the game might use Yampa [3,4,5,6] at its core. For example, a 3D first person shooting game first-person shooter game called Frag [7] has been developed using Yampa and Haskell OpenGL bindings, see http://www.haskell.org/haskellwiki/Frag.

References:

  1. http://wxhaskell.sourceforge.net/
  2. Daan Leijen. wxHaskell - A portable and concise GUI library for Haskell. http://www.cs.uu.nl/~daan/pubs.html
  3. The Yampa web site: http://www.haskell.org/yampa
  4. Paul Hudak, Antony Courtney, Henrik Nilsson, and John Peterson. Arrows, Robots, and Functional Reactive Programming. In Summer School on Advanced Functional Programming 2002, Oxford University http://www.haskell.org/yale/papers/oxford02/index.html
  5. Henrik Nilsson, Antony Courtney and John Peterson. Functional Reactive Programming, Continued. In Haskell Workshop 2002. http://www.haskell.org/yale/papers/haskellworkshop02/index.html
  6. Antony Courtney, Henrik Nilsson, John Peterson. The Yampa Arcade. In Haskell Workshop 2003. http://www.haskell.org/yale/papers/haskell-workshop03/index.html
  7. Mun Hon Cheong. Functional Programming and 3D Games. Master Thesis, November 2005, University of New South Wales, Sydney, Australia. http://www.haskell.org/haskellwiki/Frag.


Music

I'd be interested in supervising any project combining Computer Science and Music in one way or another. Could be pretty much anything, from some interesting signal processing application, to languages for writing music or describing sound, algorithmic composition, evolving music or sounds using genetic algorithms, etc. Other possibilities includes programs to help learning or teaching music.


EONF Parser and AST Generator

This is a compiler-oriented project. Pablo Nogueira, former PhD student in the FoP group, were involved in developing an innovative tool that allows a parser, declarations for a suitable Abstract Syntax Tree (AST) representation, along with libraries supporting traversal of such ASTs to be generated from a single, virtually unannotated, high-level specification of a language in Extended Object Normal Form (EONF) [1].

The existing tool is implemented in Java, and it generates Java code. The goal of this project would be to develop a similar tool that generates Haskell. The implementation language of that tool would probably also be Haskell.

References:

  1. Angel Herranz, Pablo Nogueira. Data types, parsers, and traversals from first-order context-free grammars. Unpublished manuscript.


Delta Debugging for functional languages

Delta Debugging [1] is an automated debugging approach based on systematic testing. The basic idea is simple: assuming that there is an automatic way of determining whether a program exhibits a particular failure, the program is run over and over again under changed circumstances until a minimal set of relevant failure inducing circumstances have been identified [2]. For example, given a program and some input that causes this program to crash, delta debugging could permute the input systematically until it has found some smallest possible input that still causes the crash [2]. Or suppose, during program development, yesterday's version of a program worked, but today's does not, then by systematically trying all permutations of the differences between the two versions, Delta Debugging could pinpoint exactly which changes that are responsible for the problem [3]. Of course, Delta Debugging can be a very computationally intensive process. The rationale is that computer time is increasingly cheap, whereas human time is increasingly precious.

The aim of this project is to investigate to what extent Delta Debugging techniques are applicable in the context of functional languages like Haskell or ML (or possibly other classes of declarative languages), and implement some Delta Debugging-based tool for a particular language.

Some applications of Delta Debugging, such as identifying the minimal difference between two versions of a program that causes a failure, are clearly applicable to functional languages. In fact, one could apply the Delta Debugging method naively and write a general tool that would be applicable for any language. So the challenge in that case would be to to exploit domain knowledge, e.g. knowledge about Haskell's syntax and semantics, in order to speed up the testing process as well as making the tool easy to use (think real code spanning multiple modules and source files) [4].

Other applications of Delta Debugging, such as isolating the entire cause-effect chain [5], seem rather more tied to the imperative (including Object oriented) programming paradigm. Carrying over such ideas to a functional setting could thus be rather challenging. This is particularly true if the target language is lazy, such as Haskell, in which case just comparing values during evaluation is a challenge since things in general are not fully evaluated. Other complications would include functional data. On the other hand, since functional languages are more high-level than imperative languages like C, some aspects would be simpler (comparing data structures in C is a nightmare). If some thing could be done here, then the likely concrete result for this particular Delta Debugging application would be an interpreter for a small (possibly lazy) functional language augmented with support for computing cause-effect chains as a proof of concept.

Yet another possibility might be to apply Delta Debugging to aid in finding type errors. Again, the challenge here would be to permute the source code in a sensible way.

A general Python framework for simple Delta Debugging is available. With adaptation, it could probably be used for some of the possible applications above. But one could also imagine developing stand-alone applications. For example, implementing a Delta Debugging framework in a functional language could in and of itself be an interesting part of the project.

References:

  1. The Delta Debugging web site: http://www.st.cs.uni-sb.de/dd/
  2. Andreas Zeller. From Automated Testing to Automated Debugging http://www.infosun.fmi.uni-passau.de/st/papers/computer2000/
  3. Andreas Zeller. Yesterday, my program worked. Today, it does not. Why? http://www.infosun.fmi.uni-passau.de/st/papers/tr-99-01/
  4. Using Delta Debugging: A short tutorial. http://www.st.cs.uni-sb.de/dd/ddusage.php3
  5. Andreas Zeller. Isolating Cause-Effect Chains from Computer Programs http://www.st.cs.uni-sb.de/papers/fse2002/


Improved syntactic support for Yampa

Functional Reactive Programming (FRP) is a conceptual framework for programming reactive systems using ideas from functional programming. It has been used in a number of domains, including robotics, vision processing, graphical user interfaces, interactive games, and hybrid modelling. Yampa [1,2] is the latest Yale implementation of FRP. Yampa is a domain-specific language embedded in the lazy functional language Haskell (i.e., it is a Haskell combinator library). It is structured using arrows [3] and it provides constructs for programming systems with highly dynamic interconnection structure [4,5].

Writing arrow-structured programs, including Yampa programs, is greatly facilitated if one uses a special arrow notation, similar to the do notation for monads [6]. This notation is supported directly in the latest versions of the Haskell compiler GHC. Otherwise, one has to use a preprocessor that translates Haskell program with the arrow notation to plain Haskell programs.

However, Yampa provides constructs that go beyond arrows. For example, the switch constructs that allow systems with dynamic structure to be described. Moreover, Yampa programs posses a certain property, a property related to commutativity for monads [7] and that do not hold for arrows in general, that might allow an even more concise and readable syntax than what the arrow notation provides.

The aim of this project is to devise better syntactic support for writing Yampa programs and to implement this support through a pre-processor (the current arrow preprocessor would presumably be a good starting point). A keen student may also want to widen the area of study to include syntactic support for commutative arrows and perhaps monads [7] in general.

Referenences:

  1. The Yampa web site: http://www.haskell.org/yampa
  2. Paul Hudak, Antony Courtney, Henrik Nilsson, and John Peterson. Arrows, Robots, and Functional Reactive Programming. In Summer School on Advanced Functional Programming 2002, Oxford University http://www.haskell.org/yale/papers/oxford02/index.html
  3. John Hughes. Generalising Monads to Arrows. Science of Computer Programming, 2000, volume 37, pp. 67-111.
  4. Henrik Nilsson, Antony Courtney and John Peterson. Functional Reactive Programming, Continued. In Haskell Workshop 2002. http://www.haskell.org/yale/papers/haskellworkshop02/index.html
  5. Antony Courtney, Henrik Nilsson, John Peterson. The Yampa Arcade. In Haskell Workshop 2003. http://www.haskell.org/yale/papers/haskell-workshop03/index.html
  6. Ross Paterson. A New Notation for Arrows. In Proceedings of the 2001 ACM SIGPLAN International Conference on Functional Programming.
  7. Simon Peyton Jones. Wearing the hair shirt: a retrospective on Haskell. http://research.microsoft.com/Users/simonpj/papers/haskell-retrospective/ index.htm


Graphical Front-End for Yampa

This is, in some sense, a variation on the project above. See [1-6] for background material. The basic idea is to develop a GUI allowing a user to develop Yampa code in a very user-friendly manner through block-oriented composition. Ideally, such a GUI would on the one hand facilitate for experts to construct arbitrary Yampa programs, and on the other allow novices without much if any experience of functional programming to construct at least simple programs. However, it might be that these goals are irreconcilable, in which case one would have to focus on one of the user groups.

However, developing such a GUI may not be as straightforward as it first appears. Key issues would be to come up with suitable graphical notation for the Yampa switch construct, which, being a higher-order construct, also means that there has to be graphical notation for functions, or at least some kind of "parametrised box", and to somehow handle recursion. If that turns out to be too hard, or, if the goal is to support people with little experience of functional programming, and any solution just seem too complex, then one might try to sidestep the whole issue by only supporting certain simple, predefined patterns of switching and recursion. For example, a system might be described as an agglomeration of modes, where each mode is described graphically through a block diagram, and then one would device some suitable graphical notation for switching among the modes and transferring of initial values for the state variables.

Another issue would be type checking. Ideally, it should not be allowed to compose ill-typed systems. In a simple setting, one might get away with allowing just a few base types, and then perhaps representing those types using colour encodings. For example, a block output of one colour cannot be connected to an input of a different colour. But if arbitrary types are allowed, a more dynamic approach would be needed where the types of inputs and outputs would be gradually determined as connections are made, and connections of incompatible ports are refused (with some suitable graphical feedback).

Related to type checking, it might, at least in simple cases, be possible to ensure that systems do not lock up due to ill-formed feedback loops. Again, one could imagine that the GUI simply does not allow ill-formed feedback loops to be made by refusing such connections.

Finally, there would also have to be some ways of entering Haskell code fragments here and there, e.g. for expressing various state-free computations and logical conditions.

As a fully-fledged GUI would be a very demanding project, a reasonable goal might be a GUI that only supports the construction of only fairly basic Yampa programs, like simple physical simulations of, say, a bouncing ball or a breaking pendulum.

References:

  1. The Yampa web site: http://www.haskell.org/yampa
  2. Paul Hudak, Antony Courtney, Henrik Nilsson, and John Peterson. Arrows, Robots, and Functional Reactive Programming. In Summer School on Advanced Functional Programming 2002, Oxford University http://www.haskell.org/yale/papers/oxford02/index.html
  3. John Hughes. Generalising Monads to Arrows. Science of Computer Programming, 2000, volume 37, pp. 67-111.
  4. Henrik Nilsson, Antony Courtney and John Peterson. Functional Reactive Programming, Continued. In Haskell Workshop 2002. http://www.haskell.org/yale/papers/haskellworkshop02/index.html
  5. Antony Courtney, Henrik Nilsson, John Peterson. The Yampa Arcade. In Haskell Workshop 2003. http://www.haskell.org/yale/papers/haskell-workshop03/index.html
  6. Ross Paterson. A New Notation for Arrows. In Proceedings of the 2001 ACM SIGPLAN International Conference on Functional Programming.

Improved Yampa-based robot programming language and simulator

Functional Reactive Programming (FRP) is a conceptual framework for programming reactive systems using ideas from functional programming. It has been used in a number of domains, including robotics, vision processing, graphical user interfaces, interactive games, and hybrid modelling. Yampa [1,2] is the latest Yale implementation of FRP. Yampa is a domain-specific language embedded in the lazy functional language Haskell (i.e., it is a Haskell combinator library). It is structured using arrows [3] and it provides constructs for programming systems with highly dynamic interconnection structure [4,5].

The current Yampa distribution comes with a robot simulator that allow users to write Yampa programs that control simulated robots. It even allows a simple version of Robocup robot soccer to be played. However, the simulator is still incomplete in many ways. For example, the physical realism of the simulation, as well as the capabilities of the simulated robots, could be greatly enhanced. It would also be desirable to provide an interactive editor that allows a user to set up various simulated worlds with ease. Finally, there is a layer on top of Yampa that provides abstractions intended to facilitate robot programming, essentially another FRP-flavoured domain-specific language. This layer could also be greatly improved, perhaps taking ideas from existing robot programming languages. Or combine with aspects of the robot simulator project below.

References:

  1. The Yampa web site: http://www.haskell.org/yampa
  2. Paul Hudak, Antony Courtney, Henrik Nilsson, and John Peterson. Arrows, Robots, and Functional Reactive Programming. In Summer School on Advanced Functional Programming 2002, Oxford University http://www.haskell.org/yale/papers/oxford02/index.html
  3. John Hughes. Generalising Monads to Arrows. Science of Computer Programming, 2000, volume 37, pp. 67-111.
  4. Henrik Nilsson, Antony Courtney and John Peterson. Functional Reactive Programming, Continued. In Haskell Workshop 2002. http://www.haskell.org/yale/papers/haskellworkshop02/index.html
  5. Antony Courtney, Henrik Nilsson, John Peterson. The Yampa Arcade. In Haskell Workshop 2003. http://www.haskell.org/yale/papers/haskell-workshop03/index.html

New Yampa Robot Simulator

Functional Reactive Programming (FRP) is a conceptual framework for programming reactive systems using ideas from functional programming. It has been used in a number of domains, including robotics, vision processing, graphical user interfaces, interactive games, and hybrid modelling. Yampa [1,2] is the latest Yale implementation of FRP. Yampa is a domain-specific language embedded in the lazy functional language Haskell (i.e., it is a Haskell combinator library). It is structured using arrows [3] and it provides constructs for programming systems with highly dynamic interconnection structure [4,5].

There is a framework for robotics programming developed on top of Yampa called YFrob. It comes with a graphical (2D) robot simulator. The simulator allows various robot behaviours to be programmed and tested. It is even possible to set up games of robot soccer! Unfortunately, the graphical library it is based on, HGL, is rather dated, poorly supported, and is increasingly hard to get to work. The purpose of this project would be:

References:

  1. The Yampa web site: http://www.haskell.org/yampa
  2. Paul Hudak, Antony Courtney, Henrik Nilsson, and John Peterson. Arrows, Robots, and Functional Reactive Programming. In Summer School on Advanced Functional Programming 2002, Oxford University http://www.haskell.org/yale/papers/oxford02/index.html
  3. John Hughes. Generalising Monads to Arrows. Science of Computer Programming, 2000, volume 37, pp. 67-111.
  4. Henrik Nilsson, Antony Courtney and John Peterson. Functional Reactive Programming, Continued. In Haskell Workshop 2002. http://www.haskell.org/yale/papers/haskellworkshop02/index.html
  5. Antony Courtney, Henrik Nilsson, John Peterson. The Yampa Arcade. In Haskell Workshop 2003. http://www.haskell.org/yale/papers/haskell-workshop03/index.html


Evaluation of Yampa for developing reactive systems

Functional Reactive Programming (FRP) is a conceptual framework for programming reactive systems using ideas from functional programming. It has been used in a number of domains, including robotics, vision processing, graphical user interfaces, interactive games, and hybrid modelling. Yampa [1,2] is the latest Yale implementation of FRP. Yampa is a domain-specific language embedded in the lazy functional language Haskell (i.e., it is a Haskell combinator library). It is structured using arrows [3] and it provides constructs for programming systems with highly dynamic interconnection structure [4,5].

The hope, of course, is that Yampa provides a good way to develop reactive systems, at least in principle. The aim of this project is to critically evaluate that hope. One possibility might be to develop some sufficiently substantial but not overly complex application(s) (like video games) in Yampa as well as in other suitable systems, and compare the resulting codes in order to identify strengths and weaknesses. In addition, it might be interesting to set up some simple experiments involving other people to evaluate usability aspects.

References:

  1. The Yampa web site: http://www.haskell.org/yampa
  2. Paul Hudak, Antony Courtney, Henrik Nilsson, and John Peterson. Arrows, Robots, and Functional Reactive Programming. In Summer School on Advanced Functional Programming 2002, Oxford University http://www.haskell.org/yale/papers/oxford02/index.html
  3. John Hughes. Generalising Monads to Arrows. Science of Computer Programming, 2000, volume 37, pp. 67-111.
  4. Henrik Nilsson, Antony Courtney and John Peterson. Functional Reactive Programming, Continued. In Haskell Workshop 2002. http://www.haskell.org/yale/papers/haskellworkshop02/index.html
  5. Antony Courtney, Henrik Nilsson, John Peterson. The Yampa Arcade. In Haskell Workshop 2003. http://www.haskell.org/yale/papers/haskell-workshop03/index.html

Testing for Functional Reactive Programming

Functional Reactive Programming (FRP) is a conceptual framework for programming reactive systems using ideas from functional programming. It has been used in a number of domains, including robotics, vision processing, graphical user interfaces, interactive games, and hybrid modelling. Yampa [1,2] is the latest Yale implementation of FRP. Yampa is a domain-specific language embedded in the lazy functional language Haskell (i.e., it is a Haskell combinator library). It is structured using arrows [3] and it provides constructs for programming systems with highly dynamic interconnection structure [4,5].

The aim of this project is to develop a testing framework for Yampa, maybe similar to QuickCheck [6,7], maybe even using QuickCheck. Part of the project would probably be to identify/develop a temporal logic that would allow desirable properties for Yampa programs to be expressed in a QuickCheck-like way. Both a framework that would facilitate testing of the Yampa implementation itself (e.g. regression testing), and a frame oriented toward end users are of interest.

References:

  1. The Yampa web site: http://www.haskell.org/yampa
  2. Paul Hudak, Antony Courtney, Henrik Nilsson, and John Peterson. Arrows, Robots, and Functional Reactive Programming. In Summer School on Advanced Functional Programming 2002, Oxford University http://www.haskell.org/yale/papers/oxford02/index.html
  3. John Hughes. Generalising Monads to Arrows. Science of Computer Programming, 2000, volume 37, pp. 67-111.
  4. Henrik Nilsson, Antony Courtney and John Peterson. Functional Reactive Programming, Continued. In Haskell Workshop 2002. http://www.haskell.org/yale/papers/haskellworkshop02/index.html
  5. Antony Courtney, Henrik Nilsson, John Peterson. The Yampa Arcade. In Haskell Workshop 2003. http://www.haskell.org/yale/papers/haskell-workshop03/index.html
  6. Koen Claessen, John Hughes. Testing Monadic Code with QuickCheck. In Haskell Workshop 2002. http://www.math.chalmers.se/~koen/Papers/quick-monad.ps
  7. Koen Claessen, John Hughes. QuickCheck: A Lightweight Tool for Random Testing of Haskell Programs. Published at ICFP 2000. http://www.math.chalmers.se/~koen/Papers/quick.ps

Compiler-related Project

The aim of this project would be to develop a compiler for e.g. a small imperative compiler with an emphasis of making it suitable for teaching, e.g. a replacement for or extension of the (Mini)Triangle compiler used in the G53CMP module.

Basic requirements:

Possible projects or parts of projects around the existing compiler (or in the context of a new one) include:

  • Better support for visualisation and debugging. E.g. better pretty printing, graphical visualisation of key data structures.
  • Better debugging support for the generated code. E.g. a TAM debugger. Something like GDB?
  • Additional language features. E.g. higher-order procedures and functions. (And the necessary extensions to make their use safe, e.g. by imposing certain constraints, either syntactically or through the type system, or by heap-allocating closures (probably implying automatic memory management).
  • More interesting type system. E.g. overloading, subtyping, references, making sure the type system catches references that escape their scope.
  • Automatic memory management (garbage collection).
  • More realistic TAM backend. E.g. define a binary TAM-code format and implement an external TAM in a language like C.
  • Alternative back ends. E.g. an LLVM backend.
  • Support for testing. Testing is very important, and students need to learn this. Thus there should be support for students to test their (modified) compilers. Maybe in the form of a traditional test suite + automated regression testing. Maybe using a tool like QuickCheck [3]. Or maybe both.
  • References:

    1. http://www.haskell.org/happy/
    2. http://www.cminusminus.org/
    3. Koen Claessen, John Hughes. QuickCheck: A Lightweight Tool for Random Testing of Haskell Programs. Published at ICFP 2000. http://www.math.chalmers.se/~koen/Papers/quick.ps


    Last updated 8 December 2011.