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.

You can find part one of my semester project rundown here.

Purdue's CS307 software engineering course is regarded as one of the most project-intensive courses that an undergraduate can take. Over the course of a semester, a team of students must design and implement a real-world project proposed by a corporate partner. This year Motorola sponsored two projects: a mapping application tailored to building-to-building campus navigation*; and a social networking and data visualization application built on top of Del.icio.us. There were four teams, two competing on each project. I was the team leader for one of the Del.icio.us teams.

As indicated by the length of this post, this project became my primary concern this semester. I could never have foreseen the hours and hours that I willingly poured into my team's application. We spent many evenings, nights and weekends putting together the largest project any of us have ever seen to completion.

The Team

My team consisted of myself and six other CS students: Brandon, Brett A., Kai, Han, Jon, and Matt. I knew I wanted to be the team leader before the class even started. I hope to make software engineering my career one day, so I wanted to gain experience leading team through the entire development process.

I am very pleased with how the team performed. Everyone worked hard throughout the semester and contributed positively to the entire project. Once builds got underway, each person adopted a particular part of the application. I was the jack-of-all-trades, laying the groundwork for future builds and helping in current builds wherever I could. This organization worked out incredibly well. We communicated well, and the individual parts of the application came together without too many problems.

It was amazing the project went as smoothly as it did considering...

• Three team members had part-time jobs
• Two team members were married
• One had a daughter and did not have a computer at home
• One was in the marching band (which is a huge time commitment)
• One was taking compilers (also a huge time commitment)
• None but myself had any experience with .NET programming or large application design.

Design and Implementation

The main idea of the project proposal was that Del.icio.us' existing tag and bookmark "space" defines social relationships between users. For example, two users that have many tags or bookmarks in common probably share similar interests. The project needed to make these implicit relationships explicit through more social networking and data mining functionality. The project would need to display these social and data relationships in some form of enhanced visual frontend. Because the project was sponsored by Motorola, we also needed some kind of mobile device interface to the application.

We spent the first half of the semester designing the application. The course required a formal requirements document, user manual, and design specification. The purposefully vague project description gave us a great deal of freedom to design creatively. Even so, it was difficult to know how the application would function before we had written any code.

It was during this design phase that Brandon thought of naming the application "Scrumptious". I thought this name fit perfectly because it implies Del.icio.us-ness, with a little bit extra added on. Brandon even registered the domain sc.rumptio.us** which I thought was a nice touch.

We had seven weeks during the second half of the semester in which to build the application we designed. Unlike most CS classes, we, rather than the teachers, determined exactly what we needed to turn in and when. I planned the sequence and duration of each "build module" before we started developing. Prior to each module, we had to turn in a build plan to specify what we were planning to develop, a test plan to show that the module met the functional requirements, and an inspection plan to verify that the code and tests were correct. We usually had three build modules under development at any given point. I am pleased, as the team leader, to say that we only had to modify our build schedule twice and made only minor changes to our design document.

It was not until we started building that we realized how large the project would be. We managed to meet all of our build plan goals, but it was not without a great deal of hard work and long nights. We had a short status meeting every Tuesday night to plan the week's tasks. Each team member did his part during the week in preparation for the build demo every Monday. Around the fifth build we also started meeting on Saturdays in the lab*** for long team development sessions. These long meetings made it feel like we were a small web startup getting ready to roll out our flagship product.

The Application

Despite having just seven builds, our application had a very long list of features. The following is a very short list of the application's core functionality.

Social Networking

Like other social networking applications, Scrumptious users could create personal profiles, form "buddy" links, and send public or private messages to other users. Pretty standard stuff.

Del.icio.us Integration

Users could do pretty much everything on Scrumptious that they could do in Del.icio.us. When a user added or modified a bookmark in Scrumptious, the changes were automatically mirrored back to Del.icio.us via the Del.icio.us API. Internally we had a DeliciousInterface class that was powerful enough to spin off into a standalone .NET library if we wanted.

The Scrumptious API

We tried to emulate Del.icio.us' open nature by creating a Scrumptious API similar to the Del.icio.us API. Like Del.icio.us, our API accepted HTTP GET requests and returned XML responses. It provided an interface to almost all of the functionality within the core system and drove both the visual and mobile interfaces (see below).

Data Relationships and Visualization

This was probably Scrumptious' killer feature. Internally, we wrote logic to retrieve users related by common tags and tags related by common bookmarks. Externally, we displayed these relationships in an interactive Flash interface.

The visual interface displayed a network of boxes connected by lines. The boxes could represent either users or tags depending on what the user wanted to browse. When a user clicked a box, a cloud of other boxes all related to the clicked box would spring outward and form links to the clicked box as well as related boxes already displayed on the network. When the user clicked the line connecting two boxes, he or she could see what made the two boxes related. For example, while browsing the tag network, clicking a line would display a list of bookmarks on which the two tags were used.

The boxes were positioned dynamically using a spring physics engine that I wrote. Related boxes would attract down to a certain threshold while all nodes would repel when below the threshold. It was engrossing to click a box and watch the network reach a new equilibrium.

Internally, the visual interface just pulled XML from the Scrumptious API and displayed the results.

I really wish the application was still running so I could link to a demo; words do not do the visual interface justice.

Mobile Interface

Kai became our "mobile guru". He designed and implemented a mobile thin client written in J2ME. Because it was driven completely by the Scrumptious API, the mobile interface only needed to handle the UI, sending the GET requests, and parsing the XML responses. Thanks to the power of the API, the mobile interface supported almost all of the functionality of the core system but on a tiny phone screen. Pretty impressive.

The big selling point of the mobile interface was that it illustrated how a third-party application could piggyback on Scrumptious in the same way that we piggybacked on Del.icio.us. I love how applications are starting to become more open and distributed making architectures like this possible.

Supporting Projects

In addition to the scheduled builds, the team put together several side projects to help support various parts of the application.

Database Refresher

Han became the "database guy" during the course of development. He wrote a quick app that would remove all of our test data from the database and refresh it to a normalized state.

.NET Mobile Interface

Before we had decided on an architecture for the mobile interface, Matt played around with the .NET Compact Framework. We did not get much farther than screen prototypes, but it did give us an indication of what to expect on other mobile architectures. The reasons behind our choice of J2ME are too convoluted to go through here.

Documentation Generator

To make build plans less painful, I wrote a quick application that generated the required documentation from the .NET documentation XML output after compilation.

Del.icio.us Scraper

In order to have meaningful data for testing and for displaying on the visual interface, I wrote a scraper that spidered across Del.icio.us' RSS feeds and saved the data directly back to our database. It may bend Del.icio.us' terms of service a bit, but it gave us some great data with which to demo the application.

Unit Tests

Our test plans for each build module simply consisted of the code for NUnit unit tests. It was a perfect way to demo the functionality of each module; when everything was green, we got the points.

Hardware Headaches

As is the case with any software project, we had our share of problems during the course of development. The most frustrating by far involved our server.

Brandon had a dual-processor, quadruple-RAID, redundant power supply, rackmount server lying unused in his apartment. This was extremely fortunate because Purdue does not offer any way to host .NET applications. He agreed to donate it to the project for the semester and installed everything we needed.

At first we were planning to run the server in my apartment. This proved infeasible because the redundant power supplies produced redundant noise. It sounded like a miniature jet everywhere in the apartment even with all the doors closed. Fortunately, the TA allowed us to run the server in his office, but we soon found this setup had its own problems.

We thought the first crash was a fluke. All of us were in the lab developing at the time, so Jon and I trudged over to TA's office to restart the server. The second crash, not 24 hours later, made us worry a bit more. We were again in the lab, so Brett A. and I dejectedly walked over to the TA's office. To our horror, the door was locked! As it was dawning on me that we might have a serious problem, the door opened and the graduate student that shared the office with the TA ushered us in. With a sigh of relief, I restarted the server. The graduate student, hearing our complaints, gave us his number for if we ever found the door locked again. We copied it down, naively expecting that we would never need to call it.

The third crash was the worst. It was the day before a build module was due and key parts were not yet complete. The server went down at about 10 PM, so I knew as soon as I got the "Unable to connect" error that the office would be locked. I drove over anyway and valiantly jiggled the handle. I reluctantly called the graduate student. By some miracle he was home and thinking about heading into the office anyway. I agreed to pick him up.

The drive over was epic. I drove up and down the street—the very street I live on—several times but was unable to find the grad student's apartment. I stopped at my apartment and sprinted up the stairs to look at an online map. It was no help. I called him again, apologized for the delay, and got better directions. A few minutes later I found him shivering at the entrance to his apartment complex. We drove back to the office, and I restarted the server.

The team and I speculated long and hard about what could be causing the crashes. Perhaps we had too many connections to the database; perhaps we had some critical bug in our application; perhaps Windows was being characteristically flaky... who knows? After Thanksgiving break, Brandon installed a remote power management card and set it to restart the server every night. That prevented further crashes. In the end we fixed the symptom without ever knowing the true cause of the problem.

The Final Presentation

My team gave our final presentation on Saturday, December 3 to the course administrators and a Motorola representative. Each team had to give a 25-minute "sales presentation" followed later in the day by a 45-minute "poster session" in which we demoed the application. Our presentation went very well, but the server had one final laugh during our demo: we got a full-page server error that none of us had seen before while showing the Scrumptious API to the professor. Oh well.

I consider the project a great success. We got an A on our presentation, an A on our documentation and builds, and we won the competition against the other Del.icio.us team. In addition, I learned how to better gauge the scope of projects and how to coordinate a team of developers.

* The winning mapping team's project can be found at BoilerMap.com. They did a superb job.

** Right now http://sc.rumptio.us does not resolve to anything. We had to take down the server after the final presentation.

*** Live webcam pictures of the lab can be found here and here.

I expected this to be a light semester. I knew it might get busy from time to time, but I certainly could not have foreseen the constant, unremitting load of work that I have borne like an overworked pack mule for the entire semester.

In previous semesters, I have been fortunate to have at most two major projects going at any one time. They might overlap for a week or two, but overall, I have had periodic bursts of heavy work separated by lighter—but certainly not empty—spells. This semester has been different. This semester I had three major projects spanning the entire three and a half months since summer ended.

It has been tough, but all three projects are complete, turned in, and/or demoed. I plan to write about each of them in the order they concluded, starting with...

Project One: Graduate School Applications

I have heard it said that applying to medical school is the equivalent of a three credit hour college course. If that is the case, then applying for a Computer Science graduate degree counts for at least a two credit hour seminar. I wish I could have hired a secretary to handle all the papers, requirements, forms, and pages and pages of thorough yet misleading instructions.

Of the three projects, this has lasted the longest. I knew I wanted to go to graduate school around sophomore year. Much of my CS work—such as undergraduate research and the CS honors program—has been to prepare for further study in addition to a career. Last summer I seriously started looking at schools and began researching what I would have to do to apply. I started the online applications about a month into the semester, and I took the GRE in October.

The GRE is a computer-adaptive test, meaning that the questions get harder as one progresses. The increase in difficulty was very noticeable because I started having to guess a lot about halfway through each section of the test. The adaptive nature of the test also makes it very short—only about three hours total—so time plays a large factor in completing the sections. These two things made the test much more stressful than a normal multiple choice test. Taking the test on the computer was beneficial, however, because I got my verbal and math scores as soon as I finished. I did reasonably well.

The application process sped up after I took the GRE. I completed my statement of purpose in an afternoon, and three current and former course instructors agreed to write letters of recommendations around that time.

I applied to the following six schools:

• Massachusetts Institute of Technology
• University of Illinois, Urbana-Champaign
• Carnegie Mellon University
• University of Texas, Austin
• University of Wisconsin, Madison
• Purdue

All are top-20 computer science graduate schools, and I am sure I would be happy wherever I end up. I plan to get my master's degree in computer science, but at the advice of several people, I am applying as a PhD. student. This will help my chances of getting accepted and will probably open up opportunities for working on more interesting projects. It will also make it easier to continue for four years if I decide to get my doctorate.

It was interesting to note the similarities and differences between the schools' application processes. I was pleased to find that every school had an online application. I only had to send my paper transcripts to each school and a paper application to the computer science department at UT.

Purdue and UIUC both used the same software for their applications. This is interesting because the schools are so similar in other respects: both are highly-respected, technological, Midwestern schools. Fittingly, the software was equally bad in both cases.

MIT had the best application. It was easy to use, it gave clear instructions, it did not use popups (UIUC's was three popups deep at one point), and it worked in Firefox. The only downside was that I had to manually type in every CS, math, and science course I have taken as an undergrad.

I submitted each of the applications and mailed the final paperwork about two weeks ago. Now I must leave it up to the faceless application machinery to decide what I am going to do with myself for the next two or more years.