Project for the Advanced functional programming course. (draft)

Sven-Olof Nyström
Advanced functional programming, fall -11
Information technology
Uppsala University

General information

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 presentation.

The projects are to be presented December 8 and 12. In the presentation of your project you should give the following information:

I also want you to write a brief report where you summarize the main points of your presentation.

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.

Game of Life

(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:

  1. Any live cell with fewer than two live neighbours dies, as if by under-population.
  2. Any live cell with two or three live neighbours lives on to the next generation.
  3. Any live cell with more than three live neighbours dies, as if by overcrowding.
  4. 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.

Pasture

(2-4 persons) Erlang

Implement a simulation along the lines described here: pasture.html.

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.

Performance

(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 (no, 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.)

Use of macros in Common Lisp

(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 helo in the development.

Basic

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

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

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

A language manual: status/project/BASIC-Reference-Manual.pdf. 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.

(Added 111122): Some more programs in Haskell format: bcg.hs

Creative thinking

(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.