The Usefulness of Mutant Code
In The Usefulness of Broken Glasses, I speculated on using the topological concept of continuity to design a language in which small deformations would do less harm to programs than they do in existing languages — or at least, would make the effects of the harm easier to predict. I don't think anybody has tried this (it would be a fascinating exercise in topological semantics). But there is a machine code designed to adapt to mutation. You can spray bit-flips through its memory, and often, programs will still do the right thing, more or less. It's the machine code of Thomas Ray's Artificial Life simulator, Tierra.
Tierra simulates a virtual world whose inhabitants are blocks of machine code. The Tierra machine's memory can be "seeded'' with a simple code block that copies itself many times in one run. It loops over its own code, copying it instruction by instruction into a new area of memory.
But Ray designed the Tierra machine to make copying errors, and so mutant blocks arise.
Whereas Earthly organisms compete for resources like food and light, Tierran evolution is driven by a relentless struggle for processor time. The Tierra machine gives each creature a fixed time-slice. So the faster a creature can copy itself, the more offspring it will have. Because of the copying errors, and because Ray designed his machine code to adapt to mutation, some offspring will differ from their parents, but will still function. Some will be more efficient than their parents. So efficient code-blocks evolve at the expense of inefficient ones.
When Ray started experimenting with Tierra, he noticed that in most runs, parasites soon emerged. These were mutants which lacked certain instructions. Their bodies were therefore smaller and faster to copy. But they continued to function, because the code that jumped to these instructions had also mutated so as to jump to code in the body of a creature that still had these instructions. It's as if I could telepathically link to the brain of the person sitting next to me and think with it, thereby avoiding the need to supply my own brain with oxygen and glucose, and so get by with 20% fewer calories.
Later, some hosts developed immunity. Others became hyper-parasites. Such a creature forces parasites to copy itself, stealing their time ration for its own reproduction. And the evolutionary arms race continued, yielding — in one run — over 29,000 species, all from a single parent. Some runs saw oddities such as social creatures that could only reproduce in groups.
Ray was originally an ecologist and evolutionary theorist, and wrote Tierra to experiment with evolution. For example, consider parasites, immunity to parasites, and sociality. Are these peculiar to life on Earth, or could they arise on other planets? That they happened in Tierra suggests the latter.
I said that Tierran machine code adapts to mutation. This is due partly to a novel addressing mode, "address by template". The Tierran GOTO instruction takes a pattern of instructions as its operand, not a numeric address. To obey it, the Tierra machine searches outwards from the GOTO for the first piece of code that matches this pattern, and jumps to it. Ray designed this to mimic the way protein molecules in the cell recognise one another by complementary patterns on their surfaces.
Address by template is one reason for the success of those parasites that jumped to code in another one's body. I wonder whether one could design a logic- or functional-programming equivalent. At any rate, Thomas Ray's home page is here. It links to info on Tierra — which runs on Unix and Windows — and to Ray's subsequent work on digital evolution. This includes Virtual Life, derived from Karl Sims's wonderful Evolved Virtual Creatures. Take a look at the videos!