Heapfuck

heapfuck

Paradigm(s)	imperative
Designed by	User:K.avi
Appeared in	2023
Memory system	Cell-based
Dimensions	one-dimensional
Computational class	Turing complete
Reference implementation	heapfuck interpreter
Influenced by	Brainfuck
File extension(s)	.heapf

Heapfuck is a brainfuck like Esolang. It's goal is to be a brainfuck where the environment is a binary heap instead of a list/array. The language's lexic and syntax are very similar to brainfuck. Heapfuck also supports a few instructions to make manipulating a heap easier/possible. Some brainfuck instructions are also redefined to make sense in the context of a heap (cf documentation of , , > and <)

Environment

The environment of heapfuck is a binary heap. 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 heap is always maintained and that the heap is updated after each instruction.

Instructions

Heapfuck accepts brainfuck like instruction adapted to the binary heap structure. The behavior of some is slightly changed to be more adapted to a heap. Noe that after every instruction the environment will restructure itself to remain a binary heap. If the heap is empty, every instruction other than the creation of nodes will be 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
!	removes 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 the heap as an array as well as informations on the heap (size, number of elements, index of node pointer)

Example programs

• cat :

,[.!,]

• heapfuck: (prints heapfuck)

%%%%%%%%
<<<
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
^
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
^>
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
^
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
^>>
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
^<
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
^
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
^
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
^<.^><.^^.<<.^^>>.^^<<<.^^^>.^<>.

Turing completeness

Attempt at a proof by reduction of heapfuck's turing completness : The general goal of this proof is to define a subset of heapfuck behaving like brainfuck. We will not map the I/O instruction of brainfuck because they are not necessary for turing completness. The self preserving properties of a binary heap makes the behavior of the data structure hard to predict. It is thus important to structure the heap in a way that makes it possible to emulate brainfuck (or P for that matter).

• In order to do so we will assume that we have a heap of arbitrary large size at our disposal and that every node of this heap is initialised at 257.
• The second step is to set every node in the rightmost branch of the heap (starting from the root and going to the right every time) at -1.
• The third step is to set the left child of each of the rightmost nodes to 0 (the idea is that those nodes are the ones that will emulate the brainfuck cells). For the remainder of this proof these nodes will be called Tnodes (tape nodes).
• With this construction these nodes can accept every value between 0 and 256 without the heap restructuring itself.
• This means that the brainfuck - and + operators trivially behave the same as the heapfuck ones in this context (as long as we assume that you don't overflow the cell's value, in order to prevent that we could assume that the negative cells are set to an arbitrary low value and the positive ones to an arbitrary high one).
• The idea is now to find equivalent to the brainfuck > and < instructions. This is where the Tnodes will come in handy. We assume that the pointer is at an arbitrary Tnode (this allows to emulate the infinite tape).In order to reach the next Tnode the Heapfuck sequence of instruction will ALWAYS be ^>< this sequence of instruction allows us to emulate the brainfuck > instruction.
• In order to reach the previous Tnode. We use the same idea. The sequence of Heapfuck instruction will always be ^^<. This thus emulates the brainfuck < instruction.
• Assuming we only use the previously described movement instructions. The node pointer is constrained on the Tnodes. This means that the Heapfuck loop construction will now behave the same way as the brainfuck one (this is because no zeroes can be reached outside of the Tnodes).

Using a similar construction (with Tnodes and constrained movement) we could emulate any brainfuck derivative ( by adding other constraints if necessary).

Brainfuck	Heapfuck equivalent
+	+
-	-
[	[
]	]
>	^><
<	^^<

the idea of this proof was found by Pacidus

External resources

interpreter written in C with flex/bison parser

wiki page on binary heaps

Pacidus (the person that came up with the turing completness proof) github page