OwenWiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== ISAs in ArchEvo ======

===== What is an ISA? =====

An //ISA//, short for Instruction Set Architecture, is the convention that allows programmers to talk to computers. The programmer can write a string of bits, give it to a CPU, and the CPU will do something. It is the most basic form of programming language. In fact, all programming languages are eventually turned into a series of bits based off of the ISA. (The series of bits is sometimes called Assembly Language, but that isn't important here.)

===== Brittleness =====

ISAs that are practically used are generally //brittle//. This means that if a random bit flips in an instruction, the results will likely be catastrophic (for the execution of the program, that is). Although this isn't a purposeful choice on the parts of the designers of these ISAs, it isn't necessarily a bad thing. Consider, for example, an ATM. If a "cosmic ray" hits the CPU, and an instruction has a bit flip, we (or, at least, the bankers) don't want it to continue running as if nothing had happened, as this could lead to a loss of money. Instead, they would rather the program fail, and just be rebooted.

Brittleness is caused by two main factors. 

  * The first factor is what I call //structural fragility//. The most important aspect of an ISA is control flow. This is because a program is really only useful when it can make decisions. Since programs are written as a 1D string of commands, decisions are made by jumping to certain locations in the program. This is no problem for normal programs written by normal people, but when mutation occurs, the changes can be drastic. 
  * The second factor is what I call //fault intolerance//. In a normal computer, errors do happen. Someone will open up calc.exe and divide 5 by 0. For modern computers, this is no problem. When an error, or fault, occurs, the operating system will step in and deal with it, and give the program a slap on the wrist. This means that mutations to source code occur, they are quickly stopped if they happen to cause a fault.

===== Evolvable ISAs =====
Evolvable ISAs are simply ISAs that lack the fragility of normal ISAs. They do this at a cost to human comprehension - it is generally extremely difficult for a human to program in these languages.

==== Template Jumps ====
One way to avoid the problems with structural fragility is to use //template jumps//. Template jumps were introduced in [[https://www.cc.gatech.edu/~turk/bio_sim/articles/tierra_thomas_ray.pdf | TIERRA]]. The TIERRA paper explains the motivation behind templating in this quote:

> A second feature that has been borrowed from molecular biology in the design of the Tierran language is the addressing mode, which is called “address by template”. In most machine codes, when a piece of data is addressed, or the IP jumps to another piece of code, the exact numeric address of the data or target code is specified in the machine code. Consider that in the biological system by contrast, in order for protein molecule A in the cytoplasm of a cell to interact with protein molecule B, it does not specify the exact coordinates where B is located. Instead, molecule A presents a template on its surface which is complementary to some surface on B. Diffusion brings the two together, and the complementary conformations allow them to interact. (( See [[https://www.cc.gatech.edu/~turk/bio_sim/articles/tierra_thomas_ray.pdf|TIERRA]], page 7 ))

The basic idea of template jumps is that instead of jumping to an absolute location in the program, the program jumps to a certain pattern. In [[ projects:archevo:ASIA ]], the two instructions that form these patterns are called NOP_A and NOP_B. Consider the following program:

<code>
> 0 JUMP
  1 NOP_A
  2 NOP_B
  3 ...
  4 ...
  5 NOP_A
  6 NOP_B
  7 ...
</code> 

When the JUMP instruction is executed, it will go to the end of the template to line 7:

<code>
  0 JUMP
  1 NOP_A
  2 NOP_B
  3 ...
  4 ...
  5 NOP_A
  6 NOP_B
> 7 ...
</code> 

There are several caveats to template jumping, like what happens when there is no perfect match? These will be addressed in a separate article, as they are frankly rather boring.

==== Ghost Bits ====

In ArchEvo, I want cells to be able to look into the registers of adjacent cells, but not to change the value of these registers. That is, cells have read/write privileges on their own registers, but only read privileges on their own. So what happens when a cell attempts to write to a register it does not have access to?

To motivate this example, I will use the ASIA instruction set. In this example, REG_A is an internal register referenced by code 0b0011, and I_REG_A is an external register referenced by code 0b1011. Finally, MOVE_REGISTER is 100. If we put these together, we can make an instruction that seems to move REG_A into I_REG_A, overwriting the contents of that register.

<code>
MOVE_REGISTER REG_A I_REG_A
100           0011  1011
</code>

All seems lost, until the magical Ghost Bit appears! 👻 The Ghost Bit changes MOVE_REGISTER to UNASSIGNED, which tells the cell to pause.
<code>
   UNASSIGNED REG_A I_REG_A
[1]100        0011  1011
</code>

So where did the Ghost Bit come from? Well, consider that whether or not a register is writable is true or false, so it can be expressed as a bit. This is the Ghost Bit. So, when the result register is writable, the ghost bit is 0, but when it is not writable, the ghost bit is 1. The operation that would have caused a fault is swapped out for an operation that cannot cause a fault.

The Ghost Bit system makes ISAs faultless by making it impossible for a fault to arise. It does this by interpreting any instruction that //could// lead to a fault as an instruction that will not cause a fault. 

===== Other ISA features in ArchEvo =====

==== IPLOC ====
In order for cells to be able to observe other cells' registers, they must be able to manipulate an offset to that cell. We can limit this to the eight adjacent squares around a cell to make this easier.

The naïve approach would be to store each offset as a number in a register. There are two problems with this. Firstly, interpreting the register as an unsigned int, the possible range for observation becomes a square of size 256 around the cell. This is not what we want. Secondly, this requires two registers, which is not ideal.

The IPLOC (**I**nspection **P**ointer **LOC**ation) convention circumvents this by encoding each of the eight offsets as a bit in a single register. The actual offset is the most significant bit in the register. 

<code>
1xxxxxxx => ( 1,  1)
01xxxxxx => ( 0,  1)
001xxxxx => (-1,  1)
0001xxxx => ( 1,  0)
00001xxx => (-1,  0)
000001xx => ( 1, -1)
0000001x => ( 0, -1)
00000001 => (-1, -1)
00000000 => ( 0,  0)
</code>

===== ISAs in ArchEvo =====
The following is a list of the ISAs in ArchEvo:
  * [[projects:archevo:asia|ASIA]]