Befucked is a programming language inspired by Brainfuck and Befunge. Befucked programs are written in a two-dimensional grid of ASCII characters, where the flow of the program is mostly linear with the exception of branches and control flow characters. A program ends when no character can be followed, or when a character that requires branches doesn't receive any branches. Instructions outside the flow of a program are interpreted as comments (unless these contain the character N, which would cause an error, as N is the character that determines where a program starts.)
Befucked's memory has two arrays of memory cells, a mutable one called data space, and an immutable one called value space. It also has a pointer, which can contain a value and move in the memory table. The pointer's position in data space is at all times the same position it has in memory space. The pointer can grab a value from any space, which interchanges the value it contains with that of the space. If a value space cell is grabbed, its value does not change.
The cells in value space are always set to be an integer number line, extending countably infinitely in both directions. The pointer starts at the data space value under the value space 0.
In theory, a cell can contain any integer number.
Befucked has a set of instructions that control the pointer's actions on the data table and the flow of the program. These instructions are:
|N||Start||The beginning of the program. There can only be one.|
|G||Grab||Swap the pointer's contained value and the value it's pointing to.|
|>||Move Right||Move pointer 1 cell to the right|
|<||Move Left||Move pointer 1 cell to the left|
|^||Move Up||Move pointer between data and value space|
|R||Repeat||Repeat bottom branch as many times as indicated by top branch, then proceed|
|O||Output||End the current branch and return whatever is under the pointer|
|X||If||If top left branch equals bottom left branch, do top right branch, else, do bottom right branch|
|T||Unify||Proceed through bottom branch no matter what|
|A||Absolute||Move pointer horizontally until it's closest to the absolute value under the current value it points to|
|#||Input||Take a number from the user (or a character's ascii value)|
|E||Print the value contained by the pointer|
|P||Character||Print the value contained by the pointer as a character if it's a valid unsigned 8-bit integer|
|-||Horizontal flow||Only flow horizontally|
||||Vertical flow||Only flow vertically|
Some of the instructions are hard to explain in the constraints of a table, so they will be explained below:
The repeat instruction executes its bottom branch as many times as outputted by its top branch. The top branch creates a separate pointer that starts identical to the pointer of the branch that created it. The bottom branch moves the current branch's pointer.
Repeat can only be ran from its left or right. When iteration is done, it proceeds through the opposite of the side that it was entered from.
This program prints every number from 1 to the number inputted by the user, as long as that number is positive.
O ^ N#^R > EG
The if instruction checkes whether its bottom left branch outputs the same as its top left branch. If it does, then it proceeds through the top right branch, and if it doesn't, then it proceeds through the bottom right branch. The left branches create their own pointers which start in the same state as the pointer of the branch that created them.
The following program checks if two numbers are equal, prints 1 if they are, and 0 if they are not.
O < | ^GEO N#>#-X | <^GEO O
If what the user inputted can be understood as an 64-bit signed integer, then the value of the cell under the pointer will be set to that integer value. Otherwise, if it is a single-byte character, it will set it to its ascii value.
Instructions normally look at their orthogonal neighbors to find where to go next. If more than one neighbors are found besides the instruction where the program already came from, the program will panic because the instruction won't know here to go. Control flow characters don't check for neighbors, instead, they check from where they were called and proceed on the opposite side. If a vertical control flow is called from below, it will continue above, and it's a similar case for horizontal control flow.
When characters are outside of the flow of a program, they cannot be called, and as such they are comments. Comments cannot contain the character N
The author of Befucked has theorically proven it to be turing complete by showing that it is capable of running other turing complete systems.
It is possible to create a NAND code block that can be composed using memory space to store values temporarily when nesting gates. Since a NAND gate is all it takes to create all logic gates, and logic gates are turing complete, Befucked is also turing complete.
[*] -----------| | -| [*2] | O ...-X | -----T -^GR<^G^>>G^<<AG| | ------X --| < | | | ---| | | | -| O | | O | O ------^GR<^G^>G^<AGT | ^ | ^ < --... ---R^O |---R^O < <
This NAND takes two "inputs" set by the programmer and sets the value under the current pointer to be either 1 or 0 accordingly. It treats everything that isn't a 0 as a 1. It only works on positive spaces, but can be adapted for negative spaces if necessary.
The inputs would go at [*] and [*2], and are to be set by the programmer, which requires making this gate a lot less compact. The inputs of the gates can be set by the user by using the # instruction and the R instruction.
Storing data is easy since Befucked's behaviour already has random access memory.
By setting up some restrictions, it is possible to run a turing machine whose behavior is described by a Befucked program. In the following list, the word "pointer" refers to the Turing machine's pointer, not the Befucked pointer, unless specified otherwise.
- Data cell 0 will be used to represent the pointer's position
- Data cell -1 will be used to represent the Turing machine's state
- After adding one to the pointer's position, if the current pointer's position is -1, and if it is, add two to it.
- After subtracting one from the pointer's position, if the current pointer's position is 0, and if it is, subtract two from it.
- Data cell 0 must be set to 1 before the loop starts
- Befucked's pointer's position must be at data cell 0 before the loop starts and when the loop ends.
Adder and Subtracter
This program adds two integers together and prints the result. The first integer must be positive, but the second one can be a negative. The code also features a comment.
^-O A N#>#G<AGR^GE | O | | G>G -----X <--- this conditional checks if | G<G the number is positive by comparing it | to its absolute value A^O
A Hello World program is very hard to write because one must find the ascii values in value space manually. It's theorized that condensing the repetitive parts of the program is be possible.
N^>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>| | |-------------------------------------------------------------- | >>>>>>>>>>>>GP>>>>>>>>>>>>>>>>>>>>>>>>>>>>>GP>>>>>>>GPP>>>GP<<| | |-------------------------------------------------------------- | <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<| | |-------------------------------------------------------------- | <<<<<<<<<<<<<<<GP>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>| | |-------------------------------------------------------------- | >>>>>>>>>>GP>>>>>>>>>>>>>>>>>>>>>>>>GP>>>GP<<<<<<GP<<<<<<<<GP