www.BrettDaniel.com

For some context, see parts one and two of my semester project rundown.

In the rare periods during which I was not thinking about the software engineering project, I worked on the semester project for my programming languages course. It was the most unique programming assignment that I think I have ever worked on. I got to play around with finite state machines, environment simulation, programming language design, and functional programming. It was a very interesting and enjoyable project, but I would have enjoyed it more had the software engineering project not consumed all of my time.

The project idea came from the 2004 ICFP programming contest. We had to "design an ant colony that will bring the most food particles back to its anthill, while fending off ants of another species." Ants were finite state machines governed by a simple machine language consisting of eight simple commands. To create a winning ant, we had to write a compiler that would take in a high-level ant language that we designed and output a series of ant commands. The twist was that for the class project we had to write our compiler in Scheme.

I had some experience with functional programming from using XSLT, but I had never used a "real" functional programming language. The majority of the course involved the Lambda Calculus, so the instructor wanted to give us applied experience with both the Lambda Calculus and functional programming by having us write a language compiler in Scheme.

The class had only six students, which made for very intimate lectures. Imagine six people sitting in the first three rows of a 90-person classroom. There were two women in the class. This is an astronomically high percentage for a CS course. The class split into two ant teams. At the end of the semester we would pit our ants against each other and see who won. About halfway through the semester, one of the women dropped the course. This cut our female attendance in half and reduced my team to myself and a guy named Phil who was on one of the software engineering mapping teams. I am glad he was not on the other Del.icio.us team. Having two software engineering students on a team was difficult enough; it would have been worse had we been competing against each other in the other class.

The first draft of our language looked like a normal procedural language containing loops, conditionals, variables, etc. I found out later that this was the direction that the other team as well as the winning ICFP team went. Phil and I, however, felt there had to be a better way to specify ant behavior.

Our second draft abandoned the procedural approach. We instead designed a language that could specify stimulus/response pairs similarly to the way we thought real ants could possibly think. Each stimulus "handler" specified a series of actions to take in response to the ant sensing something such as a wall, food, or other ant. The syntax expanded on the state-based nature of the ant neurology by allowing the programmer to specify superstates that could contain stimulus/response handlers as well as any number of substates. Handlers could jump between states based on certain stimuli. For example, sensing food could jump from the "searching" state to the "found_food" state. A state would loop indefinitely, performing its default actions, until some stimuli caused the ant to jump to a different state.

The following is an example of our final language. It exhibits several features of the language such as macro expansion, marker expansion, default actions, substates, and various stimuli. The syntax looks very Scheme-like, but this was simply to make it easier to read and parse.

(default
  (random forager soldier))

(macro SEE-FOOD
       (move)
       (pickup))

(marker TRAIL (1))

(state forager
       (state searching-for-food
              (sense ahead rock
                     (turn left))
              (sense ahead food
                     (move)
                     (pickup)
                     (jump return-home))
              (default 
                (move)
                (mark TRAIL)))
       
       (state return-home
        ; do stuff...
	)

       (default 
         (jump searching-for-food)))

(state soldier
	; do stuff...       
)

The initial default state is executed first. This randomly splits the ants into two main types: soldiers and foragers. Macro and marker definitions, such as the ones that follow the initial default state, are automatically expanded by the compiler when used in the code. The hierarchy of the states also defines the scope of macro and marker definitions. A macro or marker is valid in the current state as well as any substates. Therefore, because the two definitions are in the "root" state, they are valid for the entire program. The forager state contains the searching-for-food and return-home substates. A forager ant will initially fall into the searching-for-food state. The ant will move and mark until it senses either a rock or food. If it senses a rock, it will turn left and resume searching. If it senses food, it will execute the code in SEE-FOOD, then jump to the return-home state. The marker in this case does not do anything. A more complex program like the one we used in the competition could use markers to create trails and send messages to other ants.

This is a very stupid ant and far less complex than the ant we ran against the other team at the end of the semester. However, one can easily see how the state hierarchy and stimulus/response design can be used to define very complex and useful behavior.

Phil and I had our language design pretty early in the semester, but as software engineering picked up, our compiler and ant fell further and further down in the priority list. I am sorry to say we finished the last 75% of the project in the three days before the final presentation and competition. We put the finishing touches on our ant program during the hour before the class started.

Our final ant had forager and guard states. We made it so that there were three foragers for every guard. Foragers wandered around looking for food. Whenever one found food, it would carry its food along a directed path back to the home anthill. Other foragers, when they found a food trail would follow it in the opposite direction to the food. Guards stayed on the home anthill and guarded the food that the foragers brought back.

The competition took place on a very nice visual ant simulator that a classmate found. We lost, but I do not feel this is due to any weakness in the language. Given time, we could have created an incredibly powerful ant.