GENETIC 2005 VIRTUAL MACHINE

				Henry Strickland
				<strick> in the domain <yak.net>

				July 2006

Genetic2005 (or g2005 or g5) is a bytecode-based virtual machine designed for 
evolving simple genetic programs. 

The machine has a Harvard Architecture with a 256-byte read-only program memory,
nine 32-bit integer registers, and a subroutine stack with room for 256 return points.

	uint8	P[256];	// program memory, indexed by
	uint8	PC;	// program counter.

	uint8	S[256];	// subroutine call stack for saving PC, indexed by
	uint8	SP;	// stack pointer.

	int32	A;	// accumulator
	uint32	G[8];	// general purpose global registers

Programs are expressed as 256 bytes, the contents of the program memory P.
All other registers are initialized to 0.

All opcodes are exactly 1 byte, so PC is incremented by 1 after ever instruction,
unless the instruction changes PC otherwise.  (Both PC and SP wrap from 255 to 0,
or 0 to 255, when needed.)

The low 4 bits of each opcode determine the instruction; the high 4 bits are
argument.  The opcode can decode these argument fields, used by various
instructions:

	D = (opcode >> 7) & 1;  // the highest bit can be the direction bit
	R = (opcode >> 4) & 7;  // The lower 3 argument bits can choose a register R
	N = (opcode >> 4) & 15;  // N uses all four argument bits

	I = opcode & 15;        // the instruction

There is one instruction to output a byte (PUTC), but no instructions for reading input.

These are the instructions:

switch (I) {

  case 0:  // RTN		// return from subroutine

	--SP;
	PC = S[SP];

  case 1:  // CALL N*16		// call subroutine

	S[SP] = PC;  
	++SP;
	PC = N * 16;

  case 2: // DBNZ N*16		// Decrement and branch if not zero

	--A;
	if ( A ) PC = PC * 16;

  case 3: // PUTC		// output a character

	putchar( (uint8) A );

  case 4: // LDC N-8		// load A with constant N-8

	A = N - 8;

  case 5: // INC N-8		// increment A by N-8
	
	A += N - 8;

  case 6: // INC		// increment A

	++A;

  case 7: // STO D,R		// store or recall with register R

	if (D) {
		G[R] = A;
	} else {
		A = G[R];
	}

  case 8: // ADD D,R		// add

	TMP = G[R] + A;
	goto store;

  case 9: // SUB D,R		// subtract

	TMP = G[R] - A;
	goto store;

  case 10: // MUL D,R		// multiply

	TMP = G[R] * A;
	goto store;

  case 11: // NOP		// no operation (future: divide?)
  case 12: // NOP		// no operation (future: modulo?)
		
  case 13: // ULE D,R		// unsigned Less Than Or Equal

	TMP = (uint32) G[R] <= (uint32) A;
	goto store;

  case 14: // OR D,R		// Bitwise OR

	TMP = G[R] | A;
	goto store;

  case 15: // NAND D,R		// Bitwise NAND

	TMP =  ~ ( G[R] & A );
	goto store;

  store:
	if (D) {
		G[R] = TMP;	// if D is true, store to Global Register
	} else {
		A = TMP;	// else, store to accumulator
	}

}

APPENDIX A:  Programming Tricks

  -- Notice there are only 16 points to CALL or DBNZ (branch) to.
     Think of these as 16 blocks of code, for subroutines or
     branch points.

  -- If one block is getting full while it is evolving, insert a CALL
     to extend it with a subroutine, which uses RET.

  -- Since S is initialized to 0s, if you RET more than you CALL,
     that's an easy way to jump to instruction 0.

  -- If you CALL but never RET, that's an unconditional JMP.



APPENDIX B:  How to expand the machine

If this is too limiting, expand the opcode size to 9 or 10 or more bits.
This will increase the size of N (so more subroutine and branch points)
and the size of R (so more registers).

Opcodes 11 and 12 are NOPs.  That's a good place to put new functionality.
Opcodes 13, 14, and 15 might be good choices for redefining.