's success at evolving computer programs inspired the creation of Biota, a language and interpreter with a two-dimensional memory model and adjacency as its only addressing mode.
Here is a sample Biota program, called flagellum, which incrementally rotates a series of digits, 1 to 5, such that the 5 remains connected to the 1 by the intervening digits and travels around the 5 in an approximation of a circle that completes after 1688 instructions:
. . c .
. . s . . initial program counter
t g / (facing right)
t t / initial data counter
t . t . . d / (facing right)
t s . . /
b . b . s s . 1 2 3 4 5
. s s . b . b
. . s t
u d t t t t
. . s . .
. c . .
Many instructions just move the data counter (DC)
- s -- straight: move DC in the current direction. Fail if that cell is empty.
- b -- backup: move DC opposite the current direction. Fail if that cell is empty.
- t -- turn DC right 45 degrees
- u -- unturn: turn DC left 45 degrees
- g -- go to a non-empty character ahead (tries to move DC straight ahead, then right and left 45 degrees, then 90, then 135, then back).
Other instructons write to the memory at or near the data counter
- c -- clear character at DC. Fails if already empty.
- d -- duplicate the current data into the cell left of the DC. Fails if source cell is empty or target cell is non-empty.
One instruction exists only to connect instructions into loops that the program counter follows
- . -- no-op, a non-empty do nothing.
The Biota evaluator maintains program and data counters, both of which reference a character in the two-dimensional space and maintain a direction, up, down, left or right, which determines how they will advance. An instruction can turn the data counter, as with TurtleGraphics
. The program counter turns when it finds an empty location or a failing instruction. Therefore, any instruction that can fail can be used as a conditional by simply placing an alternate sequence beside it. The dot (.) is a non-empty non-operation often used to complete loops. Complex programs are assembled by duplication and modification of functional domains. The flagellum program is a triply-nested loop where the midlevel loop is repeated twice. Biota includes a visualization module. Both single stepping and high speed execution are a joy to watch.
Biota was packaged and sold publicly online in 1991. This disclosure predates BefungeLanguage
by several years. The Smalltalk source code for Biota has been located along with the release notes for the package. -- WardCunningham
I've had success with an implementation of SnuspLanguage
on a web page. I think I've got a working implementation (a rotating flagella) on http://www.quirkster.com/js/biota.html
. Tested on Safari and IE. A more object-oriented implementation in on biota-proto.html. -- IanOsgood
Yes, this is a faithful reimplementation of Biota. What a thrill it was to see flagellum run again. I hope you felt some of the excitement I did when I got such a small and unusual program to do such an unusual activity as rotating a string of characters in place. I encourage others to give it a try. (Try reloading the page if you think initial conditions might not be right.) -- WardCunningham
, I agree with Tom that the removal of embedded addresses in the instruction stream is the primary means to improve robustness under mutation. I disagree that a single dimension is the natural environment for evolving programs. I take my inspiration from membranes. I must admit, however, that I have yet to construct or evolve a self-duplicating program in Biota, so I am in no position to criticise his work. -- WardCunningham