This course is being assessed by an unusual form of examination: a practical exercise. The object of the exercise is to show that you have learned to use lazy functional programming as a practical programming tool. The exercise is deliberately open-ended, in order to form a good basis for setting a grade.
You may if you wish choose your own programming problem for assessment, or you may solve one of the problems proposed below. If you choose your own problem, be careful to choose one of appropriate difficulty: too hard, and you will not be able to solve it by the deadline; too easy, and you will not have sufficient scope to show that you have understood the course.
You earn credit by showing that you can use Haskell as a practical problem-solving tool, and that you can exploit higher-order functions and the ideas on program structuring that have been fundamental to the course.
The course will be examined by an oral presentation for the entire class, a written report, and a brief discussion with me.
Since this exercise will be used to set individual grades you must work independently.
I will organise a day of presentations in January, the date is not set yet. Each of you is expected to give a talk of around 20 minutes for the rest of the class. An overhead projector and black- or white-boards will be available.
Your report should be submitted by Friday February 4th. It should cover the following points:
I will discuss the report briefly with each of you, at times that we decide on an individual basis.
Simulation programs predict the behaviour of, for example, a physical system. In discrete event simulation, this behaviour can be thought of as a series of discrete events, each occurring at a particular time. For example, in a car wash simulation the events of interest might be
Simulation programs that simulate complex systems can themselves become very complex, and difficult to structure well. This led early on to the design of special purpose simulation languages (such as Simula), and thus was one of the driving forces behind the development of object-oriented programming. This goal of this exercise is to develop a package to support simulation programming in Haskell.
There is more than one way to approach this problem. You might choose to follow Simula and structure related events into processes. A process is a computation that can hold (wait until a specified simulated time), wait to be activated (for example in a queue), and activate other processes. For example, a car might place itself in a carwash queue, activate the car wash if necessary, and then wait for washing to be complete. A car wash might wait for a car to arrive, and then until the queue is empty, take a car from the queue, hold it for 10 minutes, and then activate it (to allow it to drive away). With the right combinator definitions, such processes can be expressed simply in Haskell, and a simulation library based on the idea.
On the other hand, you might choose to build up simulations as event transformers, that transform input events to output events, rather as stream processors transform input messages to output messages. With this approach, a car wash transforms `car arrival' events to `car departure' events with a suitable delay. The car wash queue receives `car arrival' events from the road, and transmits `car arrival' events to the car wash when it is ready. (So the car wash had better send `green light' events back to the queue so it can tell this!)
No doubt there are other possibilities also.
The user will probably want to explore the simulation interactively, for example varying the number of cars or car washes, observing the results in various ways (average waiting time, utilisation of the washes etc). A graphical user interface could be extremely useful here.
N.B. the problem here is to design a package to support the development of simulations, not to program one particular simulation. You should develop at least two different simulations, using your package, to demonstrate that it is not rigidly focussed on one particular problem. Your design will be assessed on how easily new simulations can be developed, and secondly on elegance and efficiency.
If you are already familiar with simulation, you probably need no further introduction. If not, I suggest reading Chapter 9 of [BDMN79]. It contains an introduction to simulation, with more or less detailed examples starting with a car wash and working up to an airport passenger flow simulation. You should find the examples helpful to exercise your package with. The presentation is heavily oriented towards Simula, but I hope will be comprehensible even if the programming language is unfamiliar.
You might want to simulate the activity at ``Creperiet''. Interesting parameters that one might want to vary include the customer arrival frequency, eating time, number of seats, and the tendency for the customers to book a seat before they enter the meal ordering queue. Interesting variables to watch include the number of meals served per hour and how high proportion of the seats are occupied by customers waiting in the meal ordering queue.
Or you could create a monkey world, which contains monkeys and banana trees. Each monkey has an age, a sex, a pecking order level, and a hunger factor. The behaviour of a monkey will depend on these three attributes; hungry monkeys go in the direction of banana trees. Male monkeys are attracted by female monkeys but avoid other male monkeys, especially those that are higher in the pecking order. Mature female monkeys cub baby monkeys after encountering a mature male monkey. Old monkeys die. These simple rules are allegedly a realistic abstraction of real-life monkey behavior! Again, a graphical visualisation could be highly valuable.
The problem is interesting since an ICQ client should be a reactive program, i.e., it should react on stimuli from the user and from the world, and we do not know the order in which things will happen so some form of concurrency is needed.
Information (unofficial) about the ICQ protocol can be found here.