TOGA computer

From Esolang
Jump to: navigation, search

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 byte is stored and program address. The size of an instruction is therefore the sum of the data space size and the program space size. Although a unique instruction is used, the language form by this instruction is demonstrated to be Turing complete. The TOGA is an esoteric or academic computer. as many instructions are needed to do simple operation. However, the TOGA has a very simple architecture and the number of transistor to make a TOGA is extremely limited. Therefore, its performance relative to the number of transistor might still be interesting.

Architecture and instruction set[edit]

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. Although a unique instruction is used, the language form by this instruction is demonstrated to be Turing complete, i.e. it has the ability to solve any arbitrary computable function.

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) allowing to address the program memory (pm).

Additional special register mapped in the data space may be needed to implement additional hardware features such as timer, interrupt, general purpose IO, computed goto, indirect addressing…

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++;

At reset the pc register is reset. Any code is an arbitrary suite of TOGA(a,b).

Emulator[edit]

The TOGA machine can easily be emulated in software. The following c++ code will emulate the TOGA machine. In this example, The TOGA computer has a 10 bit data address size and 12 bit program address size that 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[edit]

Toga Enhanced (TE) is an extension to Toga computer language in the following ways:

  1. TE has a uniform address space, i.e. does not distinguish code from data.
  2. TE has input and output registers.
  3. TE execution halts when the instruction jumps to a negative address.
  4. TE has an advanced assembly language.

Introduction[edit]

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[edit]

Having an assembly helps writing more complex and not word size dependent code. The assembly replaced numeric with symbolic representation. 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 semicolon separator

F:S T; S:F'1 F; T:F'1 -1

In the assembly notation the second operand can be left out. In this case its value means the next word address. The same can be specified with '?' character:

X; X

is the same as

X ?
X ?

and is the same as

X N1
N1:X N2
N2: ...

Another useful assembly feature is a definition of macro commands:

.def test1 A b L
A'b; A'b L
.end

The above definition defines a macro test1, which when used as

.test1 X 3 G

replaces with 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[edit]

Due to limited Toga instruction functionality, the only way to communicate with external ports is to toggle bits with artificially assigned addresses. Let us assume that toggling by the address (-1) outputs bit 1 to some output stream; and toggling by the address (-2) outputs bit 0. Assume also that toggling by those addresses has the effect of setting bit to 1, meaning that the B-operand is used.

When 8 bits are accumulated in the output stream, a byte - ASCII character is printed. The bits are ordered from lower to higher. So

0; 0
-1;-2;-2;-2;-2;-2;-1;-2
0 -1

outputs 'A' - ASCII code 65 and binary 01000001.

The first line in the above example leaves 0th bit set to 0. It is useful to have a data pocket 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 three times '?', or the 3rd word from this address; so '3?' jumps over the next instruction. It is also possible to use negative coefficient. For example, this macro command

.def set0 A b
A'b -1?
.end

sets a bit to 0. This instruction is executed once or twice depending on the initial value of the bit.

Set and Copy[edit]

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 is 1 jumps over the second instruction.

Different macros can be collected together into a library included in a program by .include directive. The following 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 have been 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 must be defined as

.def goto L : Temp
Temp; Temp L
.end

Colon in the headline of the macro definition separates formal arguments from external arguments. Temp is a variable defined somewhere else.

Since there is a way to copy one bit, it is possible to copy the whole word. The macro copying a word must know about the word size. It is useful to hide the size from the interface of the library by assembly substitution a special symbol with a numeric value of the word size. Such symbol is '??':

.def copy X Y
.copy_?? X Y
.end

Now the macro definition can use a specific name depending on the memory model. For example, for 32-bit model it is

.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 as

.include lib.te
.out Y
.copy X Y
.out Y
0 -1
X:65 Y:66

This program prints: 'BA'.

Arithmetic[edit]

All arithmetic is based on the following primitives: shift, roll, increment, and inversion. Macro shift shifts bits to lower or to higher direction in a word. Macro roll shifts bits but copies the popped out bit back into the opposite side bit. Macro increment does arithmetic increment by 1 treating all bits in a word as a signed binary representation of a number. And inversion inverts all the bits in a word. Their implementation is 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 particular chosen algorithms. Examples can be seen inside the TE library (see link below).

Indirection[edit]

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 C language statements X=*Y and *X=Y.

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 (same as p+=32 in a 32-bit system).

Input[edit]

To input anything from the external world, a port has to be defined. Assume that the instruction accessing address (-3) returns 1 or 0 depending on the bit value in the input stream. Then the macro 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

See Also[edit]

References[edit]