Johan, Elmar, Niels, and Wouter.
John, Eric, Thomas, and Michiel.
Mark, Kasper, and Nabil.
Gerbo, Sander, Gideon, Jinfeng, and Xiaoyu.
See the results
of the ant tournament.
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
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).
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
The following zip file contains a simulator and visualizer to see your ants in action:
. 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).
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
flag to see all the available arguments (including
which simulates a match without
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
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
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
, 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.)
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).
The submission is split into two phases. Every team must submit one generated ant instruction file before April 11 (Tuesday, 17:00).
This is a strict deadline
. On Wednesday the 12th, 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 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).
Thursday, 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.