For ant description we use the following language:

Syntax
~~~~~~


stmt ::=
   "label" "(" ID ")" 
   "goto" "(" assigns, ID ")" 
   "vars" "(" vars, stmts ")" 
   "mark" "(" INT ")" 
   "unmark" "(" INT ")" 
   "set" "(" assigns ")" 
   "drop" "("  ")" 
   "turn" "(" "left" ")" 
   "turn" "(" "right" ")" 
   "if" "(" expr ")"  stmts "else" stmts
   "when" "(" expr ")"  stmts
   "pickup" "("  ")" 
   "move" "("  ")" 

stmts ::=
	stmt
	"{" (stmt ";") * "}"

expr ::=
	expr "&&" expr
	expr "||" expr
	"!" expr
	const
	what "^" where		// sense condition
	"pickup"		// if picked up
	"move"			// if moved ...
	"rand" "(" INT ")"	// flip

const ::=
	ID
	INT
	const "+" const
	const "-" const
	const "<" const
	const ">" const
	const "<=" const
	const ">=" const
	const "==" const
	const "!=" const

what ::=
    "friend"
    "foe"
    "friend" "(" "food" ")"
    "foe" "(" "food" ")"
    "foe" "(" "marker" ")"
    "food"
    "rock"
    "marker" "(" INT ")"
    "home"
    "foe" "(" "home" ")"
                                                                                                               
where ::=
  "here"
  "front"
  "left"
  "right"



Semantics
~~~~~~~~~


   "label" (ID);
   	Define a new label.
	
   "goto" (assigns, ID);
   	Jump to a label setting specified variables.
	
   "vars" (vars, stmts);
   	Define local variables in scope of stmts.
	
   "mark" (INT);
   "unmark" (INT);
   "drop" ();
   	Should be obvious.
	
   "set" (assigns);
   	A shortcut for:
		goto (assigns, tmp);
		label (tmp);
		
   "turn" ("left");
   "turn" ("right");
   	Both commands in addition to turning the ant also update compass
	variable that must be declared in toplevel vars. So each ant program
	looks like vars (compass(6), { ... }).
	
   "if" (expr) stmts "else" stmts;
   	Evaluate given condition (either runtime or compile time) and execute
	stmts.
   
   "when" (expr) stmts;
   	Shortcut for if (expr) stmts else {};
	
   "pickup" ();
   	Shortcut for if (pickup) {} else {}

   "move" ();
   	Shortcut for if (move) {} else {}

In addition we have defined a few macros.

mark_compass:
	Puts encoding of current compass value on current field
	using markers.

mark_rev_compass:
	Likewise, but mark reverse of compass.

align_to_mark:
	Align ant so it heads in direction marked on the current field.

align_to_rev_mark:
	Likewise, but opposite direction.



Constants
~~~~~~~~~

Compilation of this language to DFA from the task isn't hard -- you just need
to translate linear structure of the program and the gotos to graph. Of course
it is important to optimize gotos to gotos, but it's rather trivial. The resulting
DFA linear with respect to program size.

The important part is how we use constants. Without constants we would need
to write 10000 lines of source program to fully exercise power of ant's brain.
Therefore we have added variable a.k.a. compile time constants. For example:

  vars (x(7), { ... })

Multiplies automata resulting from compilation of ... by 7, and inside the ...
variables x can be used -- that is it can be used in conditionals (it's then
constant folded) and modified using set and/or goto.

The compilation of source program to automata proceeds as follows:
  1. program is compiled to AST using standard Nemerle language parser
  2. special set of macros transforms Nemerle AST to ants AST.
  3. &&, || and ! are unfolded, special labels are added at the
     end of vars() blocks
  4. vars() and constant if expression are unfolded
  5. labels are bound and tree is changed to DFA form
  6. optimization of DFA [not done]
  7. serialization of DFA

As for 1. and 2., Nemerle parser is easily extensible using macros. Some
goes for semantics.  We were therefore able to reuse this important part
of the compiler

As for 3., for example:

  if (c1 && c2) {
    s1
  } else {
    s2
  }
  
is transformed to:

  if (c1)
    if (c2) {
      s1
    } else {
      goto (lab);
    }
  } else {
    label (lab);
    s2
  }

also:

  vars (a, { s })

is transformed to:

  vars (a, { s; goto (end); });
  label (end);

to aid in later vars() unfolding.

As for 4., for example:
  
  vars (x(3), y(2), { label (l); goto (x = 2, l); })

is transformed to:

  label (l_x=0_y=0);
  goto (l_x=2_y=0);
  
  label (l_x=0_y=1);
  goto (l_x=2_y=1);

  label (l_x=1_y=0);
  goto (l_x=2_y=0);

  ...

Of course if can lead to lots of unused labels -- these are removed from
the resulting DFA.

Additionally when "if(const) {...} else {...}" is encountered const is
evaluated and if it's really constant, special "if(1) {...} else {...}"
construct is generated. This one is later recognized by phase 5 --
first branch is generated as usual, but second is compiled, but can be
only referenced with labels from outside.