Programming Assignment

Teams

• 1: Alesya, Peter, Matthijs, Niek
• 2: Eelco, Niels, Reinier
• 3: Robert, Brian, Erik, Bas
• 4: Achiel, Jeroen Goudsmit, Remi, Mark
• 5: Maaike, Jeroen Leeuwestein, Martijn
• 6: Marcin, Xavier, Guangyu
• 7: Jeiel, Joost, Tim Breedveld, Tim Smienk

See the Discussion Forum for a patch on the simulator to display all markers.

Results

See the Course Schedule for the slides.

• score.txt: Scores (overall and for each team individually)

• results.log: Log file

• ants.zip: All 17 ant files (in case you want to rerun the tournament)

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).
• To minimize the start-up time, you are given a working simulator (to run a game) and visualizer written in wxHaskell.
• All parts must be implemented in Haskell.
• 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!

The Task

Create your own ant instruction file: use your creativity to achieve this. Obviously, one aspect 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 domain specific embedded language for generating ant code.

Start version

The following zip file contains a simulator and visualizer to see your ants in action: Ants-AFP06.zip. To build the executable, you must have installed

• GHC version 6.4.1, and
• wxHaskell version 0.9.4

on your computer, although it will probably also work with slightly older versions (with some modifications). Make sure that the version of wxHaskell is compatible with the version of GHC. Use the makefile for building the executable (or copy-paste the commands from the makefile). See the remarks on the Discussion Forum if you want to compile with ghc 6.6.

To start the visualizer, type the following command:

bin/Ants.exe -w worlds/sample1.world -r ants/sample.ant -b ants/sample.ant

Windows users should change all / separators into \. Use the --help flag to see all the available arguments (including --simulate which simulates a match without a GUI).

Adapt the code to your own needs. Bug fixes and suggestions are welcome.

MacOS users should call the macosx-app application on the produced executable (see comment in makefile).

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. You may reuse parts of the start version.
• 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 Instructions

The submission is split into two phases. Every team must submit one generated ant instruction file on April 10 (Tuesday, 17:00). This is a strict deadline. On Wednesday the 11th, every team has to give a short explanation (5 minutes) on their language, and discuss the design choices in particular (while playing the matches between the 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, April 13th, 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.