Ideas

Architecture:

• define a language of code fragments, where each fragment is labelled and can be "called" from other fragments
• a program consists of a collection of fragments and the name of the starting fragment
• a compiler takes a program and lowers that to low-level ant instructions (note: lowering doesn't always mean inlining the fragments... otherwise cyclic references would be disallowed... how do we tackle this?)

Verification steps in the compiler:

• all used labels exist (could we enforce this statically, by using something else than strings for the labels?)
• the produced code is within the bounds (10.000)

Optimization passes: no idea what we could do... probably remove redundant code somehow.

Primitive functions:

• turn [LeftLeft, Left, Right, RightRight, Back]
• sense [LeftLeft, Left, Right, RightRight, Back]
• turn [Left, Right] until condition is met

Notes:

• Because there are no local variables, some loops may become unrolled and functions are always inlined. This could cause an explosion in code size.

Discarded ideas

Cell markers to implement variables

• A cell can have 6 different markers, which gives a total of 64 combinations.
• Not realistic: letting a single ant read the value of the variable stored in a cell would require having 64 different branches in the code, for each read (that is the only way to keep state through reads).

Our DSL allows the user to freely define and compose multiple program fragments. This feels similar to functions in other languages, but requires a very different approach when compiling. Below is an overview of the problem.

Normal programming languages: In a normal programming language, the program counter is stored in the stack before calling a function, so when the function ends we can pop the stack and restore the program counter. This way, it is possible to jump back to the place where the function was called.

Our DSL: program fragments are quite different than normal functions, since there is no stack in our low level representation. However, we would still like to come back to the call site after calling a fragment. Therefore, each time a fragment is called, we need to generate a goto at the end of the code so we can come back. This acts like a poor man's program counter.

Problems

1. It is possible that the same program fragment is called from different places. Therefore, the goto at the end needs to be different depending on the call. This means that we must generate code two times, one with each goto. I think this is somewhat similar to the problem of instantiating generic function (also known as monomorphization). There also seems to be room for optimization: by detecting multiple instantiations of the code fragment that have the same goto at the end we can merge them into one instantiation.
2. Recursively calling program fragments seems troublesome. This also applies to cases when recursion is indirect (A calls B calls C calls A). Since there is no stack, we cannot track how deep we are in the recursion. I can't find a sensible way to deal with recursion or other kinds of cycles.

Conclusions

Forbidding cycles should make things doable again. Otherwise we will need to think more about this issue. I have the feeling that it is impossible, but maybe there is literature on the subject that we could investigate.

User story:

I as writer of an Ants program want to write: Not Condition to test if something does not have a certain condition. Branches can be inverted to execute this on the low level. This should make it easier to use functions like turnCond.

Example:

turnCond Left (Not Home) notHomebranch middleOfHomeBranch

We need to check the following properties (see Language.Fragment.hs at the bottom):

• All gotos target existing labels. Possible implementation: collect all goto targets into a set, collect all labels into a set, take the difference between gotos and labels (it should be empty)
• There is no dead code (eventually, we can pass a flag to allow it). It would be great to mention which labels are dead. Possible implementation: collect all gotos into a set, collect all labels into a set, take the difference between labels and gotos (it should be empty).
• There are no unused labels (ie labels without a corresponding fragment). Possible implementation: make an ordered list from the labels attached to each fragment, check if there are gaps between them (e.g. in [0, 1, 2, 5] we can see that labels 3 and 4 have been declared but don't have a corresponding fragment)