# FlipJump

Paradigm(s) imperative Tomhe 2021 Cell-based one-dimensional Bounded-storage machine github BitBitJump, TOGA computer `.fj`

FlipJump is a 1-instruction language, intending to be the simplest / most-primitive programming language.
Yet, it can do any modern computation (#The FlipJump Power, #The Standard Library).

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
```

The CPU now executes the op 128;256, so it will flip the 128th bit (so, 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)
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 at the end.

// The wflip op is promised to take 1 op-size in its local area (and if more ops are needed - they will be at padded spots and at the end of the current segment).
```

```pad n          // a special assembly-op that fills the current address with arbitrary fj ops, until the address is divisible by (n*dw)
label:         // label % (n*dw) is 0
```

#### 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 upwards, inc. the current).
}
// 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.
```

The end of the previous segment will be followed by the fj ops needed to complete that segment's wflip ops.

#### 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).
// The value of a string is the number built of its bytes ("TomH" == 'T' + 256*'o' + 256^2 * 'm' + 256^3*'H')

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?

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:

```//Let's 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.
;bit_a

try_second_bit:
// {5} We will flip the address in the bit_b opcode by 0x400:
bit_b+64+10;
//      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).

```

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.
Yep. By jumping to different addresses (based on the bit-variable's value) - we indeed, read its value.

In that same way, we can also implement hexadecimal variables in a single op (implemented in hexlib.fj).
Instead of two options (;0 or ;dw) we will have a bit more (0dw,1dw,2dw,3dw,...,15dw / 0dw,1dw,2dw,3dw,...,9dw).

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 char {
rep(8, i) output_bit (char>>i)&1
}

// Output becomes easy as:
output_char 'T'
```

### Input

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.

```// For example:

;handle_0
;handle_1

handle_0:
// do some 0's stuff

handle_1:
// do some 1's stuff
```

The iolib.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):

```* startup       - the first macro in your code - creates the IO label and handles the initial flow.
* fj f, j       - a basic macro for the FlipJump op - f;j
* comp_if expr, l0, l1      - jump to l1 if expr!=0 else jumps to l0
* comp_flip_if bit, expr    - flip bit if expr!=0
* skip          - skip the next instruction.
* loop          - self-loop (finish executing right here).
```

The standard library uses 3 main namespaces. The *bit*, *hex* and *dec* namespaces.
Each namespace offers many macros related to that variable type.
For example, the stl offers the bit.mov macro for moving bit-variables, hex.mov for moving hex-variables, and dec.mov for moving dec-variables.
We will mainly mention the bit versions, but the hex/dec versions of many of these macros also do exist.
The stl uses the _ namespace (and several _ inner namespaces) for its inner-macros, used only by the stl.

basic macros (defined under bit and hex namespaces):

```* if x, l0, l1  - reads the variable x, and jumps to l0/l1 based on its value (0/not0).
* xor dst, src  - flips the dst variable by the src value.
* mov dst, src  - copies the value of src into dst.
```

Mathematical/Logical macros (bitlib, under the bit namespace):

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

Andvance mathematical macros (mathlib):

```// The bit namespace:
* mul10 n, x         - multiply the n-bit x by 10.
* mul n, dst, src    - multiply the n-bit 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.
// The hex namespace ([x] is the hex-width (1/4 of the bit-width) of the number):
* add_mul n, res, a, b   - res[n] += a[n] * b[1]
* mul n, res, a, b       - res[n]  = a[n] * b[n]
```

Memory/Comparison (bitlib, under the bit namespace):

```* vec n, value             - initialize a n-bit number with value value.
* zero n, x                - zero's n-bit-variables, starting from x.
* mov n, dst, src          - copies the n-bits src into dst.
* swap n, a, b             - swaps the n-bits a with b.
* xor_zero n, dst, src     - xor's the n-bits dst by src, then zero's the n-bits src.
* 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):

```* bit.str str        - Init a string by stating str "Hello, FJ!".
* output_char ascii  - output an 8-bit constant, like output_char 'T'.
* output str         - output a string constant, like output "Hello, World!".
```

IO for variables (iolib/hexlib, under the bit/hex/dec namespace):

```* input dst           - read a char (8-bits) from input, and save it in dst.
* output x            - output the bits in that variable (1 for bit, 4 for hex/dec).
* print x             - output a char (8-bits) from the 8-bit variable x.
* print_as_digit x    - output an ascii representation of this variable.
* print_str n, x      - output n characters starting from x, stops if reaches a null byte ('\0').
```

Hexadecimal math/logic macros (hexlib, under the hex namespace) - still in development:

```* hex.init (required exactly once to use many of the macros below)
* vec, xor, zero, xor_zero, mov, swap, xor_by, set
* not, or, and, shl_bit, shr_bit, shl_hex, shr_hex, count_bits
* inc, dec, neg, add, sub
* if_flags, if, cmp, sign
* print_int, print_uint
```

Casting and formated-printing (iolib):

```* bit2hex, hex2bit
* bin2ascii / dec2ascii / hex2ascii
* ascii2bin / ascii2dec / ascii2hex
* print_hex_int / print_hex_uint
* print_dec_int / print_dec_uint
```

Pointers, Stack, and Functions (ptrlib, under the bit namespace) - 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 / pop / pop_res
- 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).
* fcall / fret    - fast call / fast return (with a constant place to store the return address, other than a stack).
```

### Lookup Tables

The hex/dec macros are based on "lookup-tables" (take a loop at hex.exact_xor in stl/hexlib.fj).
Some of these tables are small enough to be inside a macro definition, but others are just too big (hex.or.init in stl/hexlib.fj for example).
The latter are initialized by using the hex.init / dec.init macros.
The idea is simple. Based on the parameters - jump to the right entry in the table, which will set the result variable to hold the right value.

The use-flow of the big-tables is as follows:

```1. Set the jump part of a fj op (dst) to the start of the padded table, flipped by the parameters' values, to reflect the right table-entry.
For example - flip dst+dbit+{0-3} by the first hex-param, and flip dst+dbit+{4-7} by the second hex-param.
3. The table-entry will cause bits to flip, such that a result variable (res) will have the right result.
4. Set the flipped dst-bits back to 0, and jump to ret.
(small tables are the same, except that the return address is known in advance - so no need in ret).
```

The big-tables are initialized once, and can be used anytime and anywhere - it's a way to save up some memory.

## The .fjm Format

The FlipJump executable file is saved as a .fjm file. It holds all the memory segments and data. In some versions, the data is compressed.

The format itself can be found under src/fjm.py.

The .fjm file currently has 4 versions:

```0. The basic version
1. The normal version (more configurable than the basic version)
2. The relative-jumps version (good for further compression)
3. The compressed version
```

## Hello World

Using the stl (source):

```startup
output "Hello, World!\n(:"
loop
```
Hello World

Using nothing (source):

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

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

def end_loop @ loop_label {
loop_label:
;loop_label
}

startup

output_char 'H'
output_char 'e'
output_char 'l'
output_char 'l'
output_char 'o'
output_char ','
output_char ' '
output_char 'W'
output_char  'o'
output_char 'r'
output_char 'l'
output_char 'd'
output_char '!'

end_loop
```

## How To Run?

As simple as (src/fj.py)

```>>> python src/fj.py hello.fj
Hello, World!
```

You can also assemble and run separately:

Assembly
Run

You can also debug:

Debugging

And test:

Running tests

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 screen recording that was taken from the calc.fj program, making multiple mathematical calculations, and printing integers:

Calculator

A screen recording that was taken from the series_sum.fj program, calculating an arithmetic series:

Arithmetic Series

A screenshot from the func.fj source, making a function call:

Function Call

A quine (a program that prints itself) using only 99 ops of code + 448 ops of data, fully documented

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

## 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 one 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.