TOGA computer
The TOGA is a one instruction set computer (OISC), sometimes called an ultimate reduced instruction set computer (URISC), is an abstract machine that uses only one instruction – obviating the need for a machine language opcode. It uses two operands: a memory address where a data of one bit is stored, and program address. Although a unique instruction is used, the language formed by this instruction is demonstrably a bounded-storage machine (failing to be Turing complete only because it cannot reference memory that does not appear as an operand of a source instruction). The TOGA is an esoteric or academic computer, as many instructions are needed to do even a simple operation. However, the TOGA has a very simple architecture and the number of transistors to make a TOGA is extremely low. Therefore, its performance relative to the number of transistor might still be worth note.
Architecture and instruction set
The TOGA computer is a minimalist and esoteric computer. It uses two operands: a memory address where one byte of data is stored, and a program address. The size of an instruction is therefore the sum of the data space size and the program space size.
The data address size and program address size can be selected arbitrarily and should be adjusted to the available memory.
The TOGA has one register. This register is a program counter register (pc) which allows addressing in the program memory (pm).
An additional special register mapped in the data section may be needed to implement additional hardware features, such as a timer, interrupts, general purpose IO, computed gotos, indirect addressing etc.
The unique instruction is TOGA(a,b). It stands for TOGgle a And branch to b if the result of the toggle operation is true (1). It translates into
dm[a]=!dm[a]; if(dm[a]) pc=b; else pc++;
When the system is rebooted the pc register is reset. Code is an arbitrary sequence of TOGA(a,b).
Emulator
The TOGA machine can easily be emulated in software. The following C++ code will emulate the TOGA machine. Here the TOGA computer has a 10 bit data address size and 12 bit program address size, which can address 1024 bit of data and 4096 instructions.
#define PC_SIZE 12
#define W_SIZE 10
typedef struct {unsigned int a,b;} Instruction;
int main(void){
Instruction pm[1<< PC_SIZE]={{0,0},{1,0},{1,0}};
bool dm [1<< W_SIZE];
unsigned int pc=0;
for(;;){
pc&=(1<< PC_SIZE)-1;
pm[pc].a&=(1<< W_SIZE)-1;
pm[pc].b&=(1<< PC_SIZE)-1;
dm[pm[pc].a]=!dm[pm[pc].a];
if(dm[pm[pc].a]) pc=pm[pc].b; else pc++;
}
return(0);
}
Toga Enhanced
Toga Enhanced (TE) extends the Toga computer language in the following ways:
- TE has a uniform address space, i.e. does not distinguish code from data.
- TE has input and output registers.
- TE execution halts when the instruction jumps to a negative address.
- TE has an advanced assembly language.
Introduction
TE model has an array of memory of bits grouped into words. Each word can be interpreted as an address of a bit in the memory. TE code consists of a sequence of instructions. Each instruction has two operands:
A B
Operand A is the address of a bit in memory which is to be inverted. Operand B is the address where the process passes the execution if the result of inversion of the bit addressed by A is 1. If the result is 0, then the next instruction is executed. For example, in a 32-bit model
64 128 1 0 1 -1
with three instructions (64,128)(1,0)(1,-1) are executed as follows.
( 64 128 )* ( 64 128 ) ( 65 128 )* ( 65 128 ) ( 67 128 ) ( 1 0 ) -> ( 0 0 )* -> ( 0 0 ) -> ( 2 0 ) -> ( 2 0 ) ( 1 -1 ) ( 1 -1 ) ( 1 -1 ) ( 1 -1 )* ( 1 -1 ) halt
The first instruction inverts the bit of address 64, which is the 0th bit of the A-operand of the second instruction. The A-operand of the second instruction becomes 0. Thus the execution is passed to the next instruction, which is the second one. The second instruction now (0,0) inverts the bit of address 0, which is the 0th bit of the A-operand of the first instruction. This word becomes 64 -> 65. Since the result set the bit to 1, the execution is passed by the B-operand of the second instruction, which is 0, i.e. back to the first instruction. The first instruction now (65,128) sets 65th bit, which is the second bit of the A-operand of the second instruction, making 0->2. Since the bit inversion sets to 1, the execution passed to the address 128, i.e. to the third instruction (1,-1). This instruction sets the bit addressed 1 (the second bit in the A-operand of the first instruction) and jumps to the address (-1), which means halt.
Assembly notation
Having an assembly helps writing more complex and word-size-independent code. The assembly replaces the numeric representation with a symbolic one. Let
L:X'b
signify the word addressed L, with a value X+b, where X is a label and address of some other word, and b is a bit offset. The above example can be rewritten as
F: S T S: F'1 F T: F'1 -1
or using semicolons as separators
F:S T; S:F'1 F; T:F'1 -1
In the assembly notation the second operand can be omitted. In this case its value means the next word's address. The same can be specified with the '?' character:
X; X
is the same as
X ? X ?
and
X N1 N1:X N2 N2: ...
Another useful feature of the assembly is the ability to define macro commands:
.def test1 A b L A'b; A'b L .end
The above definition defines a macro test1, which when called as
.test1 X 3 G
is equivalent to
X'3 X'3 G
This test1 macro tests a bit and jumps if the bit is 1. The bit is always set to the previous state, so the test works as a non-modifiable test.
Output
Due to limited Toga instruction functionality, the only way to communicate with external ports is to toggle bits with specific addresses. Let us assume that toggling the address (-1) outputs bit 1 to some output stream; and toggling the address (-2) outputs bit 0. Assume also that toggling those addresses has the effect of setting the respective bit to 1, meaning that the B-operand triggers.
When 8 bits are accumulated in the output stream, a byte - ASCII character - is printed. The bits are ordered from lowest to highest. So
0; 0 -1;-2;-2;-2;-2;-2;-1;-2 0 -1
outputs 'A' - ASCII code 65, binary 01000001.
The first line in the above example leaves 0th bit set to 0. It is useful to have a space left at the beginning of the program as:
0 start ... anything start:0 -1;-2;-2;-2;-2;-2;-1;-2 0 -1
The output in the above example is hardcoded. If it is required to send a lower byte from any word, the test1 macro has to be used. It is even handy to make the byte output its own macro command:
0 start A:65 start:0 .out A 0 -1 .def out H .test1 H 0 l0 -2 3?; l0: -1 .test1 H 1 l1 -2 3?; l1: -1 .test1 H 2 l2 -2 3?; l2: -1 .test1 H 3 l3 -2 3?; l3: -1 .test1 H 4 l4 -2 3?; l4: -1 .test1 H 5 l5 -2 3?; l5: -1 .test1 H 6 l6 -2 3?; l6: -1 .test1 H 7 l7 -2 3?; l7: -1 .end
Note: '3?' means perform '?' three times, or the 3rd word from this address; so '3?' jumps over the next instruction. It is also possible to use negative coefficients. For example, this macro command
.def set0 A b A'b -1? .end
sets a bit to 0. The instruction is executed once or twice depending on the initial value of the bit.
Set and Copy
As shown above set0 sets a bit to 0 with just one instruction. Setting a bit to 1 requires two:
.def set1 A b A'b 3?; A'b .end
The first instruction inverts the bit and if it's a 1, it skips over the second instruction.
Different macros can be collected together into a library, included in a program by the .include directive, unsurprisingly. This program prints "ACBC":
.include lib.te .out X .set1 X 1 .out X .set0 X 0 .out X .copyb X 1 X 0 .out X 0 -1 X:65
Macros out, set0, and set1 are defined. Macro copyb copies a bit from one place to another:
.def copyb A a B b .set1 B b .test1 A a 3? .set0 B b .end
And goto has to be defined as
.def goto L : Temp Temp; Temp L .end
A colon in the heading of the macro definition separates formal parameters from external variables used as arguments. Temp is a variable defined somewhere else.
Since you can copy one bit, it is possible to copy the whole word. The macro for copying a word must know about the word size. It is useful to hide the size from the library interface; the assembler can substitute a special symbol with the numeric value of the word size. The symbol for that is '??':
.def copy X Y .copy_?? X Y .end
Now the macro definition can use a specific name that depends on the memory model. For example, for the 32-bit model it would be
.def copy_32 A B .copyb A 0 B 0 .copyb A 1 B 1 .copyb A 2 B 2 .copyb A 3 B 3 ... .copyb A 29 B 29 .copyb A 30 B 30 .copyb A 31 B 31 .end
Then this macro can be used like so:
.include lib.te .out Y .copy X Y .out Y 0 -1 X:65 Y:66
This program prints 'BA'.
Arithmetic
All arithmetic is based on the following primitives: shift, roll, increment, and inversion. The macro shift is a bitshift, shifting bits left or right in a word. The roll macro shifts bits but copies any bits that fall off one end back into the opposite side. The macro increment does arithmetic incrementation (by 1), treating all bits in a word as a signed binary representation of a number (such as in 2's-complement fashion). Lastly inversion inverts all the bits in a word. Their implementations are straightforward. For example,
.def rollR_32 X : _T .copyb X 0 _T 0 .shiftR_32 X .copyb _T 0 X 31 .end
Implementations of add, mul, sub, and div depend on the particular algorithms chosen. Examples can be seen inside the TE library (see link below).
Indirection
To write a simple program printing "Hello, World!" string using iterations arithmetic is not enough. The program has to be able to access memory indirectly - by reference. There has to be a way to copy a bit defined by addresses of the addresses. That can be done by code self-modification:
.def copyb_ref A B .copy A A1 .copy A A2 .copy B B1 .copy B B2 .copy B B3 B1:0 3?; B2:0 A1:0; A2:0 3? B3:0 -1? .end
Depending on whether referencing used with the first or the second argument, it is possible to construct macros deref and toref, equivalent to the commands X=*Y and *X=Y in C.
An example of a "Hello, World!" program
.include lib.te start: .deref p X .testH X -1 .out X .next p .goto start p:H X:0 H:72 101; 108 108; 111 44 32 87; 111 114; 108 100 33 10; -1
where testH tests the highest bit of the word, and next advances the pointer (the same as p+=32 in a 32-bit system).
Input
To input anything from the outside world, a port has to be defined. Assuming that the instruction accessing address (-3) returns 1 or 0 depending on the next bit in the input stream, the macro for inputting a byte can be
.def in R .set1 R 0; -3 5?; .set0 R 0 .set1 R 1; -3 5?; .set0 R 1 .set1 R 2; -3 5?; .set0 R 2 .set1 R 3; -3 5?; .set0 R 3 .set1 R 4; -3 5?; .set0 R 4 .set1 R 5; -3 5?; .set0 R 5 .set1 R 6; -3 5?; .set0 R 6 .set1 R 7; -3 5?; .set0 R 7 .end