Fibofuck
| Paradigm(s) | imperative |
|---|---|
| Designed by | User:K.avi |
| Appeared in | 2023 |
| Memory system | Cell-based |
| Dimensions | one-dimensional |
| Computational class | Turing complete |
| Reference implementation | fibofuck interpreter |
| Influenced by | Brainfuck Heapfuck |
| File extension(s) | .fbf |
Fibofuck is a language based on brainfuck that replaces the tape with a Fibonnaci heap (fibo heap). 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 syntax is very similar to brainfuck, with some instructions redefined to make sense in the context of a heap (cf documentation of , , > and <)
Environment
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 heaps. This means that no node has more than two children. The trees are implemented this way to simplify the language, as n-ary tree support would make the syntax more complicated. 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. While 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 trees follow the merge operation of skew heaps. This means that their right and left branches are swapped after each merge.
Behavior of operations
The specific behavior of the different operations on the heap is a mix of the skew heap operations and those of fibonacci heaps. This makes the internal structure of the environment somewhat unique.
- 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, inserts its children in the heap as new trees and then calls merge.
- delete tree: Deletes a tree from the heap.
- decrease key : Comes from skew heap. Decreases a key in a tree and then heapifies it.
- increase key : Comes from skew heap. Increases a key in a tree and then heapifies it.
Instructions
Note 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 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 parent 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 character |
:
|
Prints the value of the node under the pointer as a decimal integer |
♯
|
Prints each tree in the heap as an array as well as information on the heap (size, number of elements, index of node pointer, number of trees,...) |
Example programs
- cat :
,.[!,.]
- Helloword :
%%%%%%% creates cells for each distinct letter in 'hello world' +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ W >/ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ R ^ +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ O >// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ L ^\ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ H .^^\ +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ E .^ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ D //..^^</<>.<.>/.^>//.^^.
Turing completeness
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 (greater than 256). A way to achieve that is to initialize trees of sizes from 1 to n. Once such a heap is initialized, the behavior of the +, -, [, ], <, >, and . instructions are identical to their brainfuck counterparts.