Programming Assignment

Groups

Group 1: Rinse van Hees, Gerrit van den Geest, Huib van den Brink, Lee Provoost.

Group 2: Raymon van Wanrooij, Arie Middelkoop, Jacob Kleerekoper, Reinier Vis.

Group 3: José Pedro Magalhães, Bogdan Dumitriu, Huanwen Qu, Jinfeng Zhu.

Introduction

Every year, the ICFP (International Conference on Functional Programming) organizes a programming contest. Teams from all over the world are challenged to submit a solution within 72 hours. Although the contest is hosted by the ICFP, which has a desire to promote functional languages, submissions implemented in non-functional programming languages are accepted as well. In 2004, the programming contest was organized by members of the PLClub in the Computer and Information Science Department at the University of Pennsylvania. Andres Loeh from Utrecht University was a member of the winning team in the main division: they implemented all their tools in Haskell (congratulations Andres!).

In this years programming assignment for AFP, student teams have to tackle the problem as described by the 2004 programming contest. A detailed description of the task can be found here. In order to complete this assignment, several topics that are covered in the course have to be dealt with.

Diner with Ambiants

(from the Task Description)

The object of this year's programming contest is to design an ant colony that will bring the most food particles back to its anthill, while fending off ants of another species. To win the contest, you must submit the neural wiring for the ants in your colony---a text file containing code for a simple, finite state machine that is run by all of your ants. In principle, your entry can be written by hand, but for complex behaviors you will probably find it useful to write tools that generate ant code in some way. You may use any programming language you like for this purpose.

Your ants will compete in a tournament with all the ants submitted by other teams. In each match, two species of ants are placed in a random world containing two anthills, some food sources, and several obstacles. They must explore the world, find food and bring it back to their anthill. Ants can communicate or leave trails by means of chemical markers. Each species of ants can sense (with limited capabilities), but not modify, the markers of the other species. Ants can also attack the ants of the other species by surrounding them. Ants that die as a result of an attack become food. The match is won by the species with the most food in its anthill at the end of 100,000 rounds. The overall winner is the ant that wins the most matches.

Restrictions and rules for the AFP student teams

The focus of this assignment is different from the main goal of the contest (namely submitting clever ant code). There are some additional restrictions, and modifications to the rules.

• A team consists of 3-4 students (depending on the number of students).
• The time frame in which the solutions have to be submitted is ten weeks (instead of 72 hours).
• The programming task is split into three parts: a simulator (game engine), a visualization of a match (a GUI), and an ant code generator. Each of these parts is described in detail below.
• All parts must be implemented in Haskell.
• Each of the parts has its own deadline.
• Programs are also judged on elegance, style, and clarity. Submitting a program that only does the job is insufficient.
• Apply techniques from the lectures whenever it seems appropriate.

The last slot of the course is reserved to present your solution to the other teams. Submissions of the student teams will compete against each other in a small tournament. The winning student team may challenge the winning submission of the ICFP contest (if we have enough time).

Enjoy!

Part 1: Simulator

The first part of the programming assignment will be to implement an ant simulator (or game engine). Basically, your simulator has to perform the following tasks:

• Read a world file (for instance, tiny.world) in which the ants have to compete.
• Read a file with ant instructions (for instance, sample.ant). You may want to allow different instruction sets for the red and the black team.
• Simulate the progress of the ants during 100,000 rounds, in accordance with the rules.
• Determine the winner by counting the food particles collected by the two teams.

Testing your simulator

For the rest of the assignment, it is crucial that your simulator is implemented correctly. To test whether your implementation is correct, you have to be able to show that your simulator produces exactly the same dump file as the one given on the programming contest website (and within a reasonable amount of time). To get a positive grade for this part, a correct implementation is an absolute necessity. (As a result, you will have to implement the pseudo-random number generator as described in Section 2.10 of the task description).

Tips and Tricks

The best hint for success is to make use of the topics and techniques that are discussed during the lectures. Here are some more tips and tricks.

• Besides the necessary operations in the IO monad, other monads may be useful as well. Perhaps you also want to use mutable references to speed up your implementation (see for instance Data.IORef in the hierarchical libraries).
• When designing your own data structures, keep in mind the lectures on Functional Data Structures, and don't forget to take a look at the available (and efficient!) data structures in the hierarchical libraries.
• Do some profiling on your code, and discover which parts of your program consume most of the time. In fact, you will have to submit profiling information as part of the assignment (see submission).
• The Glasgow Haskell Compiler (GHC) offers some flags for optimization. Study those, and make use of them.
• You may want to use records, which allow you to name the fields of a data structure.
• Let main have type IO (). Use getArgs from System.Environment to obtain the program's command line arguments. Furthermore, you might want to have a look at System.Console.GetOpt, which greatly reduces the work needed to process the arguments. Note that ghci lets you explicitly set the arguments returned System.getArgs.

Submission (Part 1)

Submit your Haskell source (this may consist of more than one file), together with a clear set of instructions how it should be compiled with GHC (version 6.2.2), and how to run it to obtain the dump file for N rounds. Typically, your simulator will be tested with N = 1,000 and N = 100,000. Furthermore, you have to include:

• some profiling information about time and memory allocation of your simulator (about the submitted program only, no earlier versions).
• a rough estimation of the time required to generate the dump file.
• a description of your implementation on a global level (in particular those parts of your code that are not straightforward).

Because of the size of the dump files, do not include these in your submission.

Part 2: Visualizer

Once your simulator is working, you need to get a clear picture what is happening during the 100,000 rounds. For this purpose, you will have to design and implement a visualization of a match. Of course, we will use wxHaskell to build the GUI. Although you are free to choose your own layout, you have to support at least the following features:

• A simulation of a match without intervention from the user (for instance, showing the match from begin to end by clicking a start button).
• A step-wise visualization offering a user to inspect what is happening in one round.

In addition to these two mandatory features, you are encouraged to add more functionality to your visualizer (this may be helpful for the third part of the assignment in particular). Just to inspire you, here are some ideas:

• Display the state of a particular ant. Remember that each instruction can be accompanied with some comment. You may want to introduce some conventions in writing comments to allow for a more descriptive presentation of some ant's state.
• Once you know how the chemical markers (the 6 bits, both for the red team and the black team) should be interpreted, you can visualize them more precisely. Of course, you can only guess the interpretation of the markers set by the other teams.
• Gather statistics about the pace in which food particles are collected by your ants, and brought to the anthill.

Tips and Tricks

• wxHaskell comes with a large collection of examples. Studying these examples is likely to save you some time.
• You also have to be able to visualize a game that takes place in a 100x100 world. You may assume that larger worlds do not exist (although your visualizer should deal with tiny.world, which is a 10x10 world, in a correct manner).
• Make the number of steps that are visualized per second a parameter of your system. This will guarantee that your simulator also runs on other machines.

Submission (Part 2)

The submission should contain:

• your Haskell source, and a description how to compile and run it.
• the version of wxHaskell you are using.
• a brief manual-like explanation of the GUI you designed.
• a (technical) explanation of special implementation techniques used for visualization.
• optional: submit some nice screen shots of your visualizer.

Part 3: Generator

You have to create your own ant instruction files to complete the third part of the programming assignment. Use your creativity to achieve this. Obviously, one aspect of this part of the exercise is to obtain the best ant code. The quality of an ant instruction file can be measured easily by the number of matches it wins, for instance against the other teams. However, this should not be your main challenge.

Needless to say, writing an instruction file by hand is both cumbersome and error-prone, and submitting a hand-written instruction file is therefore not permitted. A much more interesting approach is to see how ant code can be generated from a high-level specification language. Such a high-level specification language should allow you to implement all kinds of strategies relatively easy. Hence, the main challenge for you is to design your own embedded domain specific language for generating ant code.

Tips and Tricks

Introduce a data type for high-level ant instructions. As a starting point you may take some of the low-level ant instructions given in the task description. Next, invent and add your own ant instructions. Keep in mind that you have to be able to translate a set of high-level instructions into a set of original instructions, for instance by providing a function

compile :: [HighLevelInstruction] -> [LowLevelInstruction]

The idea of translating a high-level language into a language on a lower level is the essence of a compiler! You may want to apply other well-known techniques from compiler technology, such as code analysis or code optimization. Furthermore, you may want to include some imperative language constructs to your ant language, such as gotos and labels.

In addition to the high-level instruction language, you may also want to design a library of combinators to construct often occurring patterns in your language. For instance, you could offer a function goHome, which instructs an ant to seek for his own ant hill. (This function serves as an example only: it is not necessary to include it in your library.) Ofcourse, goHome is nothing but an abbreviation of a series of instructions.

As a language designer, it is your task to find the right balance between the level of abstraction (how easy is it to implement a certain strategy) and expressiveness (which ideas can be formulated). Try to keep the following aspects separated in your code at all time (i.e., provide them in different modules):

• The high-level instruction language.
• The low-level instruction language (as given in the task description, and implemented for Part 1).
• Compilation techniques, including a translation from high-level to low-level.
• A combinator library on top of the high-level instruction language.
• Examples of ant programs written in your high-level instruction language (using your combinators).

Submission (Part 3)

The submission for Part 3 is split into two phases. Every team must submit one generated ant instruction file before June 29 (Wednesday, 17:00). This is a strict deadline. On Thursday the 30th, every team has to give a short presentation (20 minutes) on their language, and discuss the design choices in particular. Afterwards, we will play the matches between the three AFP teams.

Note that teams can submit ant instruction files during the whole course: only the last submission will be used for the tournament. Submitting ant instruction files early on prevents you from submitting a syntactically incorrect file (it gives me the opportunity to run them beforehand).

Friday, July 1st, will be the last day on which you can submit your final version. This should include:

• The ant code generator.
• A detailed description of your high-level ant instruction language.
• The slides of your presentation.
• At least one example program written in your ant language.
• A description of how to compile your examples. It is strongly recommended to include the generated files for all your examples.
• An updated (or the same) submission for Part 1 and Part 2 of the programming assignment. Please use a readme file to indicate clearly which parts have changed.