Here are some project suggestions I'm currently particularly excited about:
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:
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.
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:
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:
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:
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:
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:
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:
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:
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:
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:
References: