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

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

• Are you interested in graphics and games? Consider a project on games as described below. I'd be particularly interested if the game involves Haskell or FRP, or if it's a game for a mobile device. Even better if Haskell, FRP, and mobile device! Or consider one of the robot simulator projects.
• Are you interested in compilers and compiler- related technology? Consider doing a compiler-related project as described below, or the one on EONF Parser and AST Generator.
• Are you interested in low-level programming and compilers? Again, consider doing a compiler-related project as described below, or consider doing a project on a portable backend for a lazy functional compiler. The compiler exists (but may need some work to compile with modern Haskell compiler: most of this by far was done a couple of years ago, though). The challenge would be to tie it in with a library for generating retargetable machine code (of which there are a few around, e.g. LLVM), and to port the existing runtime system to that setting.
• Do you want to combine a theoretical development with a concrete, useful, application? Consider the project on testing for Functional reactive Programming. The theoretical side concerns developing a way to express suitable properties using some version of temporal logic. The practical side concerns implementing something akin to QuickCheck for FRP based on this.
• Are you interested in computers and music? So am I. Get in touch!

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.

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:

• Replace HGL with an up-to-date graphics library. Maybe OpenGL.
• Extend the functionality of the simulator (e.g. with an interactive world editor) and make it look better. Maybe even 3D?
• Extend the simulator to work well with a GUI toolkit (menus, dialogue boxes) to facilitate interaction with the simulator.
• Or combine with aspects of the robot simulator project above.

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:

• Complete compiler: all the way from source to executable code
• Implemented in Haskell
• Very well documented
• Probably a Happy-generated [1] frontend, but other options possible.
• Principled design, using the right level of abstractions (e.g. Monads and the like) but without going overboard and making it too hard for student's with limited Haskell background to understand what is going on.
• Modular and extensible design. It must be easy to define various projects around the compiler, e.g. by extending the language or by replacing various sub-modules with alternative (and possibly more sophisticated) implementations. In particular, this implies well defined and describe interfaces and internal representation.

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

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