◧◨
Designed by | User:C++DSUCKER |
---|---|
Appeared in | 2025 |
Memory system | tape |
Dimensions | one-dimensional |
Computational class | Turing complete |
Major implementations | ◧◨/Interpreters |
◧◨ Is a programming language with only ◧ and ◨.
it has a infinite array of bits, a pointer, and obviously a program counter.
It has two commands:
◨◧◨ Toggles the bit at the pointer and then move the pointer right
◧◧ followed by n ◨'s is a relative jump instruction, jumping (-1)^n * ceil(n/2) instructions if the bit at the pointer is 1 and then always moving the pointer left.
Disambiguity
The specification seems like it could result in multiple valid interpretations for a single program. Since ◧◧ (00) can be followed by any amount of ◨ (1) to index a relative address, and after the string of ◨ (1) a ◨◧◨ (101) or ◧◧ (00) command can follow. However, if upon encountering ◧◧ (00) we start greedily consuming ◨ (1) until we hit the first ◧ (0) we can check if there is just the one we encountered ◧ (0) or two in a row ◧◧ (00). If just one, we consumed one too many and started eating a ◨◧◨ (101) command. If two, then we consumed the correct amount. In either case, we can unambiguously parse the input. Here is a PEG grammar for the language (which can be run on PeggyJS online demo) that can convert a program into a series of mnemonic commands:
program = (toggle / jump_instruction)* toggle = "◨◧◨" { return 'toggle, right;' } jump = "◧◧" target = n:(!toggle !jump "◨")* { return ((n.length % 2 == 1) ? -1 : 1) * Math.ceil(n.length / 2) } jump_instruction = jump t:target { return `if (*ptr) {jump ${t}}, left;` }
Computational class
The language is Turing complete, all of the Smallfuck commands can be constructed. The conditional looping can be implemented in a straightforward manner using a pair of conditional jump instructions as well as idempotent rightward moves (which are constructible). See below for the movement constructions.
Examples
Find zero to the left
◧◧
00
if (*ptr) {jump 0}, left;
If the pointer is over a one, then this will move left and repeat the command until a zero is encountered. Once a zero is encountered the program ends.
Move left
◧◧◨◨
0011
if (*ptr) {jump 1}, left;
If the value under the pointer is 0, then the jump does not execute. If the value is instead 1, the jump executes and sets to jump to the next instruction. In either case a left is issued and the immediate next instruction is executed, no effective branching occurs.
This will be called LEFT;
in later mnemonic decompositions.
Toggle
◨◧◨◧◧◨◨
101 0011
toggle, right; LEFT;
Toggle, then move right, then move left. The moves always cancel, except on a side-bounded machine. Since the language is implicitly unbounded on both sides, this always returns to the same position.
This will be called TOGGLE;
Move right
◨◧◨◧◧◨◨◨◧◨
101 0011 101
TOGGLE; toggle, right;
Toggle, toggle, then move right. The cell under the pointer does not change.
This will be called RIGHT;
Find zero to the right (invalid)
◧◧◨◨◨◧◨◧◧◨◨◨◧◨◧◨◧◨◧◧◨◨◨◧◨◧◧◧◨◨◨◨◨◨◨◨◨◨◨
0011 101 0011 101 0101001110100011111111111
LEFT; RIGHT; <invalid code>
This example is invalid.
Reset current bit
◧◧◨◨◨◨◨◨◨◨◨◨◨◨◨◧◨◧◧◨◨◨◧◨◨◧◨◧◧◨◨◧◧◨◨◨◧◨◧◧◨◨◨◧◨◨◧◨◧◧◨◨
00111111111111 101 0011 101 101 0011 0011 101 0011 101 101 0011
This is actually incorrect, the author of this example must have partially forgotten that the initial jump moves left.
if (*ptr) {jump 6}, left; RIGHT; TOGGLE; LEFT; <- RIGHT; TOGGLE;
The command marked with the arrow is the target of the first jump. This can be interpreted as two programs, one which runs if the current cell is 0 and the other for 1:
0 branch:
LEFT; (part of conditional) RIGHT; TOGGLE; LEFT; RIGHT; TOGGLE;
Cancels to a no-op
1 branch:
LEFT; (part of conditional) LEFT; RIGHT; TOGGLE;
Cancels to just LEFT; TOGGLE;