Project (due Jan. 18, 2013)

Make sure you follow the rules when submitting your solution. You can work in a group of more than two persons for the project.

The main motivation for the project is to write a larger, self contained program in one of the languages of the course. Writing a program is significantly different from writing code in that it takes more planning and design before you start to write the code. The exercises and assignments have been about writing code to get deeper knowledge in some areas of the different languages.

You can work in groups of 1-4 persons. A larger group should of course take on a larger and more ambitious project.

The projects will be graded. The result of the project will influence your grade on the course. Among the things that will affect the grade of the project are: the level of difficulty, the size of the project, the size of the team, how well various difficulties were handled and the report.

The project is to be presented in a report written in English. The report should contain at least the following:

• The design. Explain how you arrived at your solution, how you use any given code, how you use standard libraries. Also describe different design decisions and motivate them.
• Any limitations (the size of the problem that can be solved, for example).
• Complexity, in the algorithm-theoretic sense.
• Difficult corner cases, anything that required deliberation on your part, or any unexpected solutions to sub-problems.
• Algorithms and representation of data.
• An argument to why you solution produces a correct result.

Below is a list of possible projects. You can also suggest your own project. Either way, please contact me with a short written description of what you plan to do and the members of your project before you start the project. I will then check that the project is appropriate and perhaps suggest modifications. The proposals below contain a varying degree of detail. The hope is to inspire ideas and there are large possibilities for creating your own project. Ask for more details if you find that there are too few details in the proposals.

It is easy to become over-ambitious and aim for something that is too large. Be careful and be sure to discuss goals and limitations so this doesn't happen.

The languages listed are to be seen as recommendations, so you can do the project in another language, but clear the details with Stavros first.

(1-2 persons) Erlang

Implement Conway's Game of Life in Erlang.

The universe of the Game of Life is a two-dimensional grid of square cells, each of which is in one of two possible states, live or dead. Every cell interacts with its eight neighbours, which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:

• Any live cell with fewer than two live neighbours dies, as if by under-population.
• Any live cell with two or three live neighbours lives on to the next generation.
• Any live cell with more than three live neighbours dies, as if by overcrowding.
• Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.
• The initial pattern constitutes the seed of the system. Each next generation is created by applying the above rules simultaneously to every cell in the grid. Births and deaths occur simultaneously, and the discrete moment at which this happens is sometimes called a tick (in other words, each generation is a pure function of the preceding one). The rules continue to be applied repeatedly to create further generations.

In your project, the size of the board should be given as two paramaters W and H at the start of the simulation. The board might either wrap around the edges or simply end there.

The initial pattern should be given as some Erlang data structure, say as a list of strings:

["  XX  ",
 " XX   ",
 "  X   "]

Implement each cell as a process that uses message-passing to communicate with its neighbours. The process should decide to live or die depending on the result of the communication with its neighbours. During start-up there might be a process that knows the location of each cell, but it should not be necessary during execution.

If you like, you can use this code as a simple web-based user interface.

This should be a relatively straight-forward project. However, note that solutions to this problem tend to be prone to race-conditions, especially for large number of cells. I would like you to discuss this problem in your presentation.

(2-4 persons) Erlang

Implement a simulation along the lines described here.

Again, you can use the web-based interface mentioned above.

Here, each animal and plant should be represented as a process.

The comment on race-condition (se section on Game of Life, above) applies here as well.

(1-4 persons) Common Lisp

One interesting aspect of Common Lisp is the combination of high-level expressiveness with low-level preformance. Implement some algorithm as efficiently as possible. You should pick some algorithm which you understand well and where performance is often a consideration (don't pick something as simple as sorting). It helps if you have access to a well-written implementation in C or C++ for performance comparison.

The challenge here should not be simply to implement the algorithm correctly but gaining an understanding of the language implementation (run-time and compiler) and using feedback from the compiler to obtain high low-level performance. You could also consider high-level optimizations of the algorithm.

(You might consider numerical algorithms or algorithms used in data mining.)

(1-4 persons) Common Lisp

Find some problem domain where you expect that Common Lisp's ability to introduce new syntax and reduce boilerplate and other forms of repeated code would help in the development. One (obvious) area is that of language implementation/extension (see later proposals).

(2-4 persons) Common Lisp, Erlang, Haskell

Implement an interpreter of a subset of the programming language Basic.

You can find example programs here (together with longer descriptions here http://www.vintage-basic.net/games.html) and translated to Common Lisp format here. I have not yet had time to finish the translation to Haskell data types but the data type is here. Even if you plan to implement the interpreter in Common Lisp, the Haskell data type might still be helpful.

A language manual: Basic. Contact me if you still have questions.

Please note that to write programs with I/O in Haskell you need to understand how to use monads. This would make the project harder. However, there are a number of interesting non-interactive test programs so an implementation without I/O is still interesting.

You don't need to implement the whole language, but make sure that you can run a few of the example programs. It is acceptable if you need to make small modifications to the test programs in order to make them run on your system.

Variation (harder): Write a translator to Common Lisp.

Some more programs in Haskell format: examples

Implementing a language is a great way to gain deeper understanding of it. Common Lisp or Haskell are the most reasonable choices for one of these projects.

1. Design and implement a functional programming language. It should have at least lambda abstraction, be able to cater for higher order functions and be statically scoped. Note that when writing an interpreter dynamic scoping is easier to implement, but this should be avoided. Including lazy evaluation makes it both more challenging and fun.
2. Implement a type inference system for a subset of Common Lisp, i.e., your program should be able to infer and check types of a subset of Common Lisp. This could also be an extension of the previous proposal.
3. Implement a partial evaluator for a subset of Common Lisp or as an extension of the first proposal.
4. Implement a compiler.

(1-2 persons) Haskell, Common Lisp, Erlang

The nine dots puzzle is often used by management consultants and executive coaches to illustrate creative thought.

The problem is: Given nine dots in a 3x3 pattern, draw 4 straight lines without lifting the pen, so that the lines pass through all dots.

Your project is to write a program that solves this problem. You might view this as an AI problem, in which case Common Lisp is the natural implementation language. You could also see it as a mathematical problem, in which case it might make sense to look for an elegant solution in Haskell.

The program might be called as follows, where n is the size of the solution we are looking for,

solve n [(0,0),(0,1),(0,2),(1,0), ...]
Your program should be able to solve the puzzle for other dot configurations. In your presentation you should say something about how large configurations you can solve and if there are other limitations.