3 May 2014

The Life of (an) Ant

I already mentioned that Daniel impressed me by implementing Conway's Game of Life in MSBuild with MSBTest. Being a Java developer for most of my career, Apache Ant was the proper choice to build the cellular automaton using a build tool. I have worked with Ant before, so I was confident I would be able to pull it off.

Bring Out Your DeadIdiomatic Ant
I wanted a challenge and decided to avoid Ant extensions whenever possible. For example there are if and for tasks in Ant-Contrib which enable an imperative, procedural coding style. Obviously embedding any kind of script was also considered cheating.

An Ant's Universe
Wikipedia says that the universe of the Game of Life is an infinite two-dimensional orthogonal grid of square cells. How could I represent such a grid using basic Ant data structures? Which types does Ant support at all? Ant offers immutable properties and property sets, files, directories and paths and supports text file filtering using regular expressions. Which data structure could I use for the universe? How about directories? The universe is a two-dimensional grid, containing rows and columns, which might be defined by the names of nested folders. A single row in the grid is a folder which contains the folders of all its columns, e.g.
That looks promising. But how to find the previous and following columns given a current column (folder) name? There are no arithmetic functions available in Ant, so there is no way to increase or decrease a number by one. But it is possible to append a character to a property creating a new one, allowing to reach the cells (folders) right and down of the current one, e.g.
To access the left and upper neighbours of a cell the name has to be shortened. Ant is not able to shorten String properties but the basename task is able to strip the extension off a file or directory name. So the row and column folders are called '.y' and '.x'.
Testing Framework
To do it "right", I needed a testing framework. Although there is Apache AntUnit, I used a simpler solution to test my build files. Inspired by my former colleague Andy Balaam's Test-Driven Ant macros I created the necessary assertion macros on the way. For example the following code asserts that a certain property is set:
<macrodef name="assert-propery-set">
    <attribute name="propertyname" />
        <fail message="property '@{propertyname}' not set."
              unless="@{propertyname}" />
Tell me about your neighbours
Having the data structure and assertions in place, it was time for the first test. I started with tests for counting the neighbours of a given cell, expecting its implementation in target count_neighbours of cell-build.xml.
<import file="lib/asserts.xml" />
<import file="cell-build.xml" />

<target name="test-count-neighbours-in-middle-when-no-neighbours">
    <make-tmp-dir />
    <antcall target="create_3x3_grid" />
    <touch file="${test.temp_dir}/.y.y/.x.x/cell" />

    <antcall target="assert-number-of-neighbours">
        <param name="p_cell_location" value="${test.temp_dir}/.y.y/.x.x" />
        <param name="p_expected_neighbour_count" value="0" />

<target name="create_3x3_grid" if="test.temp_dir">
    <mkdir dir="${test.temp_dir}/.y/.x" />
    <mkdir dir="${test.temp_dir}/.y/.x.x" />
    <mkdir dir="${test.temp_dir}/.y/.x.x.x" />
    <mkdir dir="${test.temp_dir}/.y.y/.x" />
    <mkdir dir="${test.temp_dir}/.y.y/.x.x" />
    <mkdir dir="${test.temp_dir}/.y.y/.x.x.x" />
    <mkdir dir="${test.temp_dir}/.y.y.y/.x" />
    <mkdir dir="${test.temp_dir}/.y.y.y/.x.x" />
    <mkdir dir="${test.temp_dir}/.y.y.y/.x.x.x" />

<target name="assert-number-of-neighbours" depends="count_neighbours">
    <assert-propery-equals propertyname="cell.neighbour_count"
                           expected="${p_expected_neighbour_count}" />
First I fulfilled the test with a fake solution.
<target name="count_neighbours">
    <property name="cell.neighbour_count" value="0" />
After eight more tests,
<target name="all-test-targets" description="run all test targets">
    <antcall target="test-count-neighbours-in-middle-when-no-neighbours" />
    <antcall target="test-count-one-neighbour-left" />
    <antcall target="test-count-one-neighbour-right" />
    <antcall target="test-count-one-neighbour-up" />
    <antcall target="test-count-one-neighbour-down" />
    <antcall target="test-count-one-neighbour-up-left" />
    <antcall target="test-count-all-neighbours-around" />
    <antcall target="test-count-neighbours-in-left-up-when-no-neighbours" />
    <antcall target="test-count-neighbours-in-lower-right-when-no-neighbours" />
count_neighbours was finished.
<property name="cell.marker_alive" value="cell" />

<target name="count_neighbours" if="p_cell_location"
      description="sets property 'cell.neighbour_count' to the count of living
                   neighbours of a cell in the given location 'p_cell_location'.">

    <dirname property="cell.base_row" file="${p_cell_location}" />
    <dirname property="cell.base" file="${cell.base_row}" />

    <pref_self_next dim="y" folder="${cell.base_row}" /> <!-- (1) -->
    <pref_self_next dim="x" folder="${p_cell_location}" /> <!-- (2) -->

    <resourcecount property="cell.neighbour_count"> <!-- (3) -->
        <fileset dir="${cell.base}">
            <include name="${cell.prev_y}/${cell.prev_x}/${cell.marker_alive}" />
            <include name="${cell.prev_y}/${cell.self_x}/${cell.marker_alive}" />
            <include name="${cell.prev_y}/${cell.next_x}/${cell.marker_alive}" />

            <include name="${cell.self_y}/${cell.prev_x}/${cell.marker_alive}" />
            <include name="${cell.self_y}/${cell.next_x}/${cell.marker_alive}" />

            <include name="${cell.next_y}/${cell.prev_x}/${cell.marker_alive}" />
            <include name="${cell.next_y}/${cell.self_x}/${cell.marker_alive}" />
            <include name="${cell.next_y}/${cell.next_x}/${cell.marker_alive}" />
Line (1) defines the properties for the previous, current and following row, i.e. in the y dimension and line (2) does the same for columns, i.e. in the x dimension. Both sets of properties are similar, so I extracted a macro to remove duplication. (Remember: Red - Green - Refactor)
<macrodef name="pref_self_next"
      description="defines properties 'cell.self_X', 'cell.pref_X' and 'cell.next_X' for
                   given dimension/orientation 'dim' from center of current 'folder'.">

    <attribute name="dim" />
    <attribute name="folder" />

        <basename property="cell.self_@{dim}" file="@{folder}" />
        <property name="cell.next_@{dim}" value="${cell.self_@{dim}}.@{dim}" />
        <basename property="cell.prev_@{dim}" file="@{folder}" suffix=".@{dim}" />
After determining the names of the previous and following neighbouring cells (folders), counting the live ones (files) was be done with Ant's resourcecount. Line (3) counts the number of files called 'cell' in the neighbouring folders.

To Be or Not To Be
With the number of living neighbours I was ready to implement the rules of the game right away. The target apply_rules uses this number to determine if a cell lives on or dies. With four tests,
<target name="all-test-targets" description="run all test targets">
    <antcall target="test-rules-with-two-neighbours-lives-on" />
    <antcall target="test-rules-with-one-neighbour-dies-on" />
    <antcall target="test-rules-empty-with-two-neighbours-stays-dead" />
    <antcall target="test-rules-empty-with-three-neighbours-comes-alive" />
apply_rules evolved to
<target name="apply_rules" depends="count_neighbours" if="p_cell_location"
      description="sets property 'cell.will_live' only if a cell in the given
                   location 'p_cell_location' will live on for the next generation.">

    <condition property="cell.will_live">
              <available file="${p_cell_location}/${cell.marker_alive}" />
              <equals arg1="${cell.neighbour_count}" arg2="2" />
            <equals arg1="${cell.neighbour_count}" arg2="3" />
Target apply_rules expects the property p_cell_location to point to a given cell (folder) in the universe. It first calls the target count_neighbours via depends and uses the cell.neighbour_count to determine if the given cell will be reborn, live on or die. This implements the rules of the game and ends this post. The next one will use apply_rules to run a full Game of Life on arbitrary universes. Stay tuned!

No comments: