fibofuck docu

I: Introduction

Fibofuck is a brainfuck like Esolang. It's goal is to be a brainfuck where the environment is a fibonnaci heap instead of a list/array. However for the sake of minimalism and simplicity the language doesn't use n-ary trees like regular fibonacci heaps would. Instead each tree in the heap is a Skew heap. The language's lexic and syntax are very similar to brainfuck. Some brainfuck instructions are also redefined to make sense in the context of a heap (cf documentation of , , > and <)

II: Environment

II.1: General presentation

The environment of fibofuck is a heap similar in concept to a fibo heap. The key difference being that trees in the heap are implemented as binary skew heap. Which means that no node has more than two children. The tree is implemented this way to make the language more simple (n-ary tree support would have made a more complex syntax necessary). At the beginning of the program, the heap is empty. The maximal size of the heap is theoretically infinite. Each node of the heap contains a signed integer. Note that the structure of the fibo heap is always maintained and that the heap is updated after each instruction. This means that the heap is really "merge heavy". This is one of the differences between a regular Fibo heap and the heap in fibofuck. In a regular fibo heap, the merge call is often only done after deletion of an element. Here it's done after every instruction making the whole environment very chaotic. Another important detail is that the tree follow the merge operation of skew heaps. This means that their right and left branch will get swapped after a merge.

II.1: Behavior of operations

The behavior of every operation on the fibo heap will be documented here:

merge : Mix of skew heap AND fibo heap. Applies the skew heap merge operation on 2 trees of the same size (number of nodes) until every tree in the heap is of different size
insert node: comes from fibo heap. Adds a node to the heap and then calls merge
delete node : comes from fibo heap. Deletes a node from a tree. If it has children insert it's children in the heap as new trees and then call merge
delete tree: deletes a tree from the heap
decrease key : comes from skew heap. Decrease a key in a tree and then heapifies it
increase key : comes from skew heap. Increase a key in a tree and then heapifies it

What I find interresting about this is that the environment is merge heavy which means that it's hard to predict how it's gonna evolve after insertion or deletion.

III: Instructions

fibofuck accepts brainfuck like instruction adapted to the fibonacci heap structure. The behavior of some bf-like instruction is changed to be more suited for heap manipulation. Noe that after every instruction the environment will restructure itself to remain a fibonacci heap. If the heap is empty, every instruction other than the creation of nodes will be ignored. NB: Every character that isn't an instruction is ignored.

Command	Description
`%`	Initialises a node in the heap at 0
`,`	Reads a character and initialises a node in the heap at the character's value
`^`	moves the node pointer to the parent of the current node if it exists
`/`	moves the node pointer to the left child of the current node if it exists
`\`	moves the node pointer to the right child of the current node if it exists
`<`	moves the node pointer to the root of the previous tree in the heap if the current tree is not the last
`>`	moves the node pointer to the root of the next tree in the heap if the current tree is not the last
`!`	removes the node under the pointer from the heap
`*`	removes the tree containing the node under the pointer from the heap
`+`	increments the node under the pointer by 1
`-`	decrements the node under the pointer by 1
`[`	jumps past the matching `]` if the value of the node under the pointer is 0
`]`	jumps back to the matching `[` if the value of the node under the pointer is nonzero
`.`	prints the value of the node under the pointer as a char
`:`	prints the value of the node under the pointer as a decimal int
`♯`	prints each tree in the heap as an array as well as informations on the heap (size, number of elements, index of node pointer, number of trees,...)

IV: Turing Completness

This paragraph attempts to show that brainfuck can be simulated in fibofuck. To do so we have to setup a specific heap where the root of each tree is set to 0 and each of their children is set to an arbitrary high number (superior to 256). A way to achieve that is to initialise a tree of size 1 , one of size 2 ,.... one of size n
By creating such a heap of arbitrary size. The behavior of the + , - , [ , ] , < , > , . is the exact same as the behavior of their brainfuck counterpart.