  We present a modular neural network architecture Main that learns algorithms
given a set of input-output examples. Main consists of a neural controller that
interacts with a variable-length input tape and learns to compose modules
together with their corresponding argument choices. Unlike previous approaches,
Main uses a general domain-agnostic mechanism for selection of modules and
their arguments. It uses a general input tape layout together with a parallel
history tape to indicate most recently used locations. Finally, it uses a
memoryless controller with a length-invariant self-attention based input tape
encoding to allow for random access to tape locations. The Main architecture is
trained end-to-end using reinforcement learning from a set of input-output
examples. We evaluate Main on five algorithmic tasks and show that it can learn
policies that generalizes perfectly to inputs of much longer lengths than the
ones used for training.
