FlipJump

From Esolang
Jump to navigation Jump to search
FlipJump
Paradigm(s) imperative
Designed by Tomhe
Appeared in 2021
Memory system Cell-based
Dimensions one-dimensional
Computational class Bounded-storage machine
Major implementations github
Influenced by BitBitJump, TOGA computer
File extension(s) .fj

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.
 ;   =>  0;$

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, 69 will be assembled to 128+0; 128+2; 128+6; (actually, something equivalent, it's the assembler's choice).
wflip dst, val, jmp_addr  - Same as above, but jumps to jmp_addr in the end.

// The wflip op is guaranteed to take 1-op-size in its local area. If more fj ops are needed - they will be at the end of the current segment)

Macros

def macro_name param1, param2.. @ temp_label1, temp_label2.. < globals.. > externs.. {
    // macro body
}


// For example:

def not4 x {
    x;
    x+1;
    x+2;
    x+3;
}

def notnotjump x y jumper {
    x+y;jumper
}

def skip_bits jump_bits @ end_label {
    ;end_label + jump_bits
  end_label:
}

// if BLA1,BLA2 where not labeled as externs - a warning would come up.
def declarations > BLA1, BLA2 {
    BLA1:
    ;
    BLA2:
}

// if C was not labeled as a global - a warning would come up.
def flipC < C {
    C;
}

// Using macros
not4 100
notnotjump a, w, b
skip_bits 2*w

Repetitions

rep(n, i) macro_name arg1, arg2, ..    // repeats the macro n times, each with i = [0, 1, .. n-1].
                                       // n is an expression and may contain constants and labels of previous addresses.

// For example, building not4 in a simpler way
def not x {
    x;
}
def not4 x {
    rep(4, i) not x+i
}

Namespaces

ns namespace_name {
    // Any variables, labels, macro definitions declared here - will have the namespace prefix.
    // Access inner definitions with the "." prefix.
    ns nested_namespace {
        // Nested namespaces (to any level) are allowed!
        // Access nested_namespace definitions with the "." prefix, namespace_name definitions with the ".." prefix, 
        //  and so on (the number of leading dots, the number of namespaces to go upwords).
    }
    // A namespace can also contain code.
}
ns namespace_name {
    // You can append things to an already defined namespace!
}
// Access namespace_name definitions from outside with the "namespace_name." prefix

// For example:

ns my_ns {
    X = 7
}
ns my_ns {
    def foo dst {
        dst+.X;
    }
    ns inner_ns {
        Y = 8
        Z = .Y + ..X
        def inner_foo dst {
            ..foo dst+.Z
        }
    }
}

startup
my_ns.foo v
my_ns.inner_ns.inner_foo v
v + my_ns.inner_ns.Z + 2*my_ns.X;
loop: ;loop
v: var w, 446

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 .fjm 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 to get the important understanding of this concept:

// Lets assume a 64 bits cpu, and that the label branch_target is evaluated to 0x400 (1<<10).
// Follow the {0}, {1}, ... {9} 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:
// {5} We will flip the address in the bit_b opcode by 0x400:
    bit_b+64+10;
// {6} 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
    // {4} Now we get here, and then continue jumping.
    ;try_second_bit
second_branch_target:   // This is address 0x480
    // {8} Another jump.
    ;end


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

bit_a:  ;0      // {3} Jump to branch_target
bit_b:  ;0x80   // {7} Jump to second_branch_target


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.

In that same way, we can also implement hexadecimal and decimal variables in a single op (implemented in hexlib.fj & declib.fj).

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 set it back again 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
}

// 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+w, some_padded_address, 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, dw  // we assume dw+w is 0.

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 jumps 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'). 

Hexadecimal math/logic macros (hexlib) - still in development:

* xor, zero, xor_zero, print, mov, swap, set, not, inc, dec, neg, if_flags, if

Decimal math/logic macros (declib) - still in development:

// nothing implemented yet

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 ptr, value  - wflip *ptr, value
* 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 (source):

    startup

    print_str 20, str
    loop

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

Using nothing (source):

def startup @ code_start > IO {
    ;code_start
  IO:
    ;0
  code_start:
}


def output_bit bit < IO {
    IO + bit;
}
def output ascii {
    rep(8, i) output_bit ((ascii>>i)&1)
}

def end_loop @ loop_label {
    loop_label:
    ;loop_label
}

    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

How To Run?

As simple as (src/fj.py)

>>> fj.py hello.fj
Hello, World!

Current list of FlipJump assemblers:

Current list of FlipJump interpreters:

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