FlipJump

From Esolang
Jump to navigation Jump to search

FlipJump is a 1-instruction language, with the goal of being the simplest / most-primitive OISC. It successfully shows that you need practically nothing to do anything.

As the name implies - It Flips a bit, then Jumps (unconditionally). The fj op has 2 operands:

a;b

a and b are both addresses of bits, and it is equivalent to:

not *a; jump b


Understanding the instruction

Take a look at the next (64bit) program:

1000;256  // addresses 000-127
32;446    // addresses 128-255
128;256   // addresses 256-383

The CPU starts executing at address 0, so it will flip the 1000th bit and will jump to address 256.
The CPU now executes the op 128;256, so it will flip the 128th bit (the 2nd op will be overridden to 33;446) and will jump again to address 256.
The CPU will get stuck in a self-loop here, as it jumps back to 256 forever.

The FlipJump CPU

The fj CPU has a built-in width, and starts executing from address 0.
It halts on a simple self-loop (jumps to itself, while not flipping itself).

There are variants of the CPU, let's assume the simplest form:

  • The jump address is always w-aligned.
  • The operation doesn't flip bits in itself.

Here is a 8bit-fj-cpu C emulator:

#define BAD_ALIGNMENT 1
#define SELF_FLIP 2
#define SUCCESS_FINISH 0

int fj8(u8* mem) {
    u8 ip = 0;

    while (true) {
        u8 f = mem[ip/8];
        u8 j = mem[ip/8+1]; 

        if (ip % 8)  
            return BAD_ALIGNMENT;
        if (f >= ip && f < ip+16) 
            return SELF_FLIP;
        if (...) {
            // handle IO  (will be explained next).
        }
        if (ip == j) 
            return SUCCESS_FINISH; 

        mem[f/8] ^= 1<<(f%8);   // Flip
        ip = j;                 // Jump
    }
}

The Assembly Language

Declaring constants & labels

x = 6;
// The fj program starts with 1 predefined constant - w, which is defined with the address-width (word-width). 2^w is the memory size in bits.

label:

Syntax sugar

F;J
 ;J  =>  0;J                                                  - Just jump (it does flip the address 0).
F;   =>  F;$     ($ is the address of the next instruction)   - Just flip.
F    =>  F;$                                                  - Just flip.
 ;   =>  0;$

Words-value

[len]val         - Places len-memory-words, all with the value of val.

Flipping a whole word

.wflip dst val   - Assembles to multiple dst+i; ops (for 0<=i<w which the i'th bit is 1 on val).
// .wflip 128 45 will be assembled to 128+0; 128+2; 128+6; (or something equivalent, it's the assembler's choice).

Macros

.def macro_name [param ..] : [temp_label ..]
    // macro body
.end


// For example:

.def not4 x
    x;
    x+1;
    x+2;
    x+3;
.end

.def skip_bits jump_bits : end_label
    ;end_label + jump_bits
  end_label:
.end

// Using macros
.not4 100
.skip_bits 2*w

Repititions

.rep n i macro_name [param ..]    // repeats the macro n times, each with i = [0, 1, .. n-1].

// For example, building not4 in a simpler way
.def not x
    x;
.end
.def not4 x
    .rep 4 i not x+i
.end

Segments & Reserve

// some code
.segment 0x10000    // The code below will start from address 0x10000
// some code

.reserve 0x400      // Will reserve a spot for 0x400 0-bits. They will be filled by the running environment.
// The .blm file (the assembled file) allows specifying segment-length > data-length, and fills the remaining memory with zeros.

Assembly-time expressions

Many mathematic and logic operations are allowed between numbers/constants/labels at assemble time:
temp + 2*(b-temp) - 13/4 ; temp & 0x67 + 0b00110   
    // You can use the labels (will be resolved to numbers at assemble-time) and many operations to make the flip/jump addresses:
    //  Mathmatical:  +- */% ()  
    //  Logical:  &|^  operations
    //  Shifts  << >>
    //  C-like trinary operator  ?:
    //  Bit-width operator  #  (minimal number of bits needed to store this number.  #x == log2(x)+1).
    // Also you can use hexadecimal (0x) and binary (0b) numbers, and get the ascii value of chars ('A' == 0x41).

temp:  ;
b:
c:

b+'A';b+0x41    // The flip and jump addresses are identical in this line.

c+('A' > 'B' ? 1 : 'B');temp+(1<<(c-b))   // Is equivalent to c+0x42;temp+1

Memory - how can we implement variables?

A bit can be built using 1 fj operation. Specifically, ;0 or ;dw (defined in the standard library as 2*w).

Here the magic happens. The flipjump operation inherently can't read. It also can't write a specific value. All it knows is to flip a bit, and then jump. but where to?

The flipjump hidden-power lies exactly in this delicate point. It can jump to an already flipped address. In other words, it can execute an already modified code.
I based the main standard library functions, and the implementation of variables, on this exact point.

Follow the next example:

// Lets assume a 64 bits cpu, and that the label branch_target is evaluated to 0x400 (1<<10).
// Follow the {1}, {2} numbers to follow the execution flow.

    ;code_start // {0} code starts at address 0
    ;
    ;
    ;
code_start:

// {1} We can flip the address in the bit_a opcode by the branch_target address (0x400):
    bit_a+64+10;    // The +64 is to get to the 2nd word (the address word), and the +10 is to flip the bit corrospondig to 0x400.
// {2} If we jump to execute the opcode in bit_a, it will flip address 0 and then jump to the address written in it. 
//      So it will jump to 0x400, which is branch_target.
    ;bit_a

try_second_bit:
// {4} We will flip the address in the bit_b opcode by 0x400:
    bit_b+64+10;
// {5} Now we jump to execute the opcode in bit_b. It will flip address 0 and then jump to the address written in it. 
//      So it will jump to 0x480 (was 0x80 from the start), which is second_branch_target.
    ;bit_b


branch_target:          // This is address 0x400
    // {3} Now we get here, and then continue jumping.
    ;try_second_bit
second_branch_target:   // This is address 0x480
    // {6} Another jump.
    ;end


end:  ;end  // {7} The code will get here and then finish (self loop).

bit_a:  ;0
bit_b:  ;0x80


The same flip/jump combination on bit_a/bit_b did different things. We successfully jumped to different addresses depends on the value of the said bits. In that way, we can read the value of such a bit-variable.

This is very nice, but it only worked because we knew the address of branch_target in advance. We usually don't, but it is resolved during assemble time.

That's why the assembly language provides the .wflip operation.

.wflip bit_a+w branch_target    // This will work for every branch_target address, not just 0x400.

Of course, it is important to make the same .wflip again just after the jump to bit_a.
We assume that the jump-part of these bit-instructions is 0 / dw, so after each wflip we must wflip again, to make it back to 0 / dw.


Input / Output

Output

Output is done by flipping a special address.

2*w;    => will output 0
2*w+1;  => will output 1

To output an ASCII character - output the 8 bits of it in lsb-first order.

For example, the next code will output 'T' (0b01010100):

2*w;
2*w;
2*w+1;
2*w;
2*w+1;
2*w;
2*w+1;
2*w;

The standard library defines a simpler output macro:

dw = 2*w
.def output_bit bit
    dw+bit;
.def output char
    .rep 8 i output_bit (char>>i)&1
.end

// Output becomes easy as:
.output 'T'

Input

The next input bit is always loaded at address 3\*w + #w (3w+log(w)+1), when needed.

You can use this bit by jumping to a flip-jump opcode that contains it. The best way is to jump to ;dw.

In that way - this bit will reflect either 0x0 or 0x80 in the jump-part of the flip-jump op.
If we .wflip dw some_padded_address before the ;dw - the dw-flip-jump-op will make a jump to some_padded_address / some_padded_address+0x80, based on the input, just like in the Memory section.

// For example:

    .wflip dw+w padded_address  // we assume dw+w is 0.
    ;dw

.pad 2    // standard-library macro used to assure that padded_address is divisible by 2*dw.
padded_address:
    ;handle_0
    ;handle_1

handle_0:
    .wflip dw+w padded_address  // we make sure dw+w stays 0.
    // do some 0's stuff

handle_1:
    .wflip dw+w padded_address  // we make sure dw+w stays 0.
    // do some 1's stuff


The runlib.fj standard library defines macros to make IO as simple as possible.


The Standard Library

I Implemented the standard library for the language, found in the Github Page under stl/
It features some constants (runlib):

* dww  = #w       // double-w-width (log2(2w))
* ww   = dww-1    // w-width (log2(w))
* dw   = 2 * w    // double word size
* dbit = w + dww  // bit-distance from variable start to bit value (w+dww)

But mostly, it features useful macros, starting with the basic (runlib/bitlib):

* .if x l0 l1  - reads the instruction-bit x, and jump to l0/l1 based on its value (0/1).
* .xor dst src - flips the dst instruction-bit if the src instruction-bit is on.
* .mov dst src - copies the value of src instruction-bit into the dst instruction-bit.
* .pad n       - pads the memory with zeros until it is divisible by n*dw.
* .startup     - the first macro in your code - creates the IO label, and handles the initial flow.

Mathematical/Logical macros (veclib):

* .add n dst src  - adds the n-bit number (n consequative intruction-bits) src to dst.
* sub / inc / dec / neg
* xor / and / or  / not
* shr / shl / ror / roll

Andvance mathematical macros (mathlib):

* mul10 n x       - multiply the n-bit x by 10.
* mul n dst src   - multiply the n-bits src by dst, and save the result in dst.
* div n a b q r   - divide the n-bit a by b, save the result in q, and the reminder in r.
* idiv / div_loop / idiv_loop / imul_loop  - the loops implementations are smaller in size, but a bit slower.

Memory/Comparison (veclib):

* .var n value    - initialize a n-bit number with value value. 
* .zero n x       - zero's n-instruction-bits, starting from x.
* .mov n dst src  - copies the n-bits src into dst.
* .cmp n a b lt eq gt  - compares the n-bits a/b, and jump to right address (lt for a<b, eq for a==b, gt for a>b).
* .if n x l0 l1        - jumps to l0 if the n-bit x is just zeros, and to l1 otherwise.

IO (iolib):

* .string str     - Init a string by stating .string "Hello, FJ!".
* .input dst      - read a char (8-bits) from input, and save it in dst.
* .output ascii   - output a constant, like .output 'T'.
* .print x        - output a char (8-bits) from the 8-bit variable x.
* .print_str n x  - output n characters starting from x, stops if reaches a null byte ('\0'). 

Casting and formated-printing (iolib):

* bin2ascii / dec2ascii / hex2ascii
* ascii2bin / ascii2dec / ascii2hex
* print_hex_int / print_hex_uint
* print_dec_int / print_dec_uint

Pointers, Stack, and Functions (ptrlib) - handles w-bit variables as pointers to the memory:

* .init_ptr       - declare once to use the next macros:
* .ptr_jmp  ptr   - ;*ptr
* .ptr_flip ptr   - *ptr;
* .xor_to_ptr / xor_from_ptr
* .ptr_flip_by
* .stack n        - initializes a stack with n bit-variables.
* .push_bit / .pop_bit / .pop_res_bit  
                  - push a bit to the stack / pop an unchanged-bit from the stack / pop a general bit from the stack.
* .call address   - calls a function (pushes the return address to the stack, takes only 1 bit-variable space).
* .return         - returns from a function (pops the return address from the stack, and jumps to it).

Hello World

Using the stl:

.startup 
.print_str 20 str
.loop

str:
    .string "Hello, World!\n(:"
Hello.fj.png

Using nothing:

.def startup
    ;code_start
  IO:
    ;0
  code_start:
.end


.def output_bit bit
    IO + bit
.end
.def output ascii
    .rep 8 i output_bit ((ascii>>i)&1)
.end

.def end_loop : loop_label
    loop_label:
    ;loop_label
.end

    .startup
    
    .output 'H'
    .output 'e'
    .output 'l'
    .output 'l'
    .output 'o'
    .output ','
    .output ' '
    .output 'W'
    .output 'o'
    .output 'r'
    .output 'l'
    .output 'd'
    .output '!'
    
    .end_loop

The FlipJump Power

FlipJump is the product of searching for the simplest / most-primitive / weakest instruction set, and see what can be done with this power.

It seems like a lot can be done!

A screenshot from the calc.fj program, making multiple mathematical calculations, and printing integers:

Calc.jpg

A screenshot from the func.fj program, making multiple function calls:

Func.fj.png

A compiler from a RiscV 32bit machine code to fj 64bit code is planned.

Comparison to similar languages

BitBitJump

BitBitJump is the closest language to FlipJump, with its unconditional jump.

Yet, FlipJump Is more basic/primitive than BitBitJump.

  • BitBitJump can copy a bit from a general address to another.
  • BitBitJump can write zeros and ones directly to an address, without knowing the old value.

Both can't be trivially done with FlipJump, and no implementation ever succeeded in doing that (try to wonder about how to implement it..).
Flipping a general memory bit in BitBitJump is possible, and jumping unconditionally is possible as well (with 0 0 jump_address).

TOGA computer

Toga is close to FlipJump as well. It flips a bit but then has a conditional jump.

FlipJump is clearly more basic/primitive than Toga, as the conditional jump has the power of reading any bit in memory (and so is writing). Also, an unconditional jump can be easily implemented in TOGA using 2 instructions.

External resources

Github - Macro Assembler and Standard Library, and 2 interpreters.

See Also