Brainpocalypse
Brainpocalypse is an esoteric programming language created by User:ais523 in 2018, as a cross between brainfuck and Subtractpocalypse. The idea is to produce a language that's simpler than each of the original languages in terms of the complexity of its command set. It can also be fairly easily minimalized down to two instructions; unlike some other languages with the same property, it does not require an implicit loop around the program (i.e. the commands of the program itself handle both data manipulation and control flow).
The name "brainfuck" is written mid-sentence every time it appears in the specification (thus making it unclear how its name is capitalised at the start of a sentence, although it's lowercase if it appears mid-sentence). Brainpocalypse has the opposite issue; in its specification, the name only appears at the start of a sentence, thus making it unclear how it would be capitalised mid-sentence.
Data storage
Like brainfuck, data is stored in a tape of cells, each of which holds an integer that's initially 0. Brainpocalypse, however, uses only nonnegative integers in its cells (like Subtractpocalypse does with its counters); by default, the cells are unbounded (although a version of the language with bounded cells might be interesting). Because the cells are unbounded, the tape length can be bounded; the default is for the tape to be 256 cells wide and to wrap from the start to the end (just like the default for brainfuck's cells is for them to wrap between 255 and 0); again, a version of the language with a tape that's unbounded in both directions might be interesting. There is also a tape pointer, just like in brainfuck, which can point to a cell, and initially points to the "first" cell (although because the tape is either unbounded or wrapping, the decision of where to start the pointer is invisible and entirely arbitrary).
Commands and syntax
Brainpocalypse's syntax is like brainfuck: each command is a single character long, and every character other than those that name commands is ignored and can be used to write comments. The commands likewise work in a similar way to brainfuck; the program starts with the first command and by default runs commands in order, halting if an attempt to execute "beyond the last command" is made, with flow control commands able to change this basic behaviour.
Standard version
Brainpocalypse has four commands in its standard version:
| Command | Meaning |
|---|---|
< |
Move the tape pointer to the left |
> |
Move the tape pointer to the right |
+ |
Add 1 to the tape cell that the pointer is pointing to |
- |
Subtract 1 from the tape cell that the pointer is pointing to, if it's nonzero. If the subtraction fails because the cell was zero, instead goto the start of the program (i.e. rewind the IP address to the first command in the program). |
Minimized version
When the tape is bounded, < is unnecessary, as you can replace it with enough > commands to wrap around to the other end of the tape.
It's also possible to merge > and + into a single instruction, } (with the same semantics as >+). This command allows you to simulate > as }-. Once you have >, you can use it to implement <, and then + can be written as <}. This brings the language down to just two commands, } and -, at the expense of a rather large explosion in the code size.
Computational class
Brainpocalypse is Turing-complete, given a sufficiently long tape (and it is likely but not proven that 256 cells is sufficient). This can be proven via compiling into it a version of The Waterfall Model in which every cell adds 5 to itself upon zeroing. (There's a Turing-completeness construction on Talk:The Waterfall Model which can trivially be adapted to have this property.)
The first step of the compiled program is to initialise the tape appropriately via adding the elements of the initial state to those on the tape, which can be done with + and < instructions. The first, third, fifth, etc. tape elements are each initialised to 1; the second is initialised to 0, with others being initialised as explained below. Then the program moves to the second tape element (i.e. the element to the right of where it started) and does -+, followed by undoing the tape initialisation by subtracting the same amount from each tape element as was initially added, and moving the pointer back to its original location. The first time this sequence runs, the subtraction in this -+ will fail and reset the program, thus initialising the tape appropriately (with the pointer on the second element). For the rest of the program, the pointer is always moved two elements at a time (i.e. we use << and >> for movement and treat all the 1-valued cells as nonexistent); this means that the -+ will always succeed (the pointer would start on an element in between the 1s, so the cell to its right – the cell where -+ is run – would be 1-valued), so the entire initialisation sequence cancels itself out.
From now on we only focus on the tape elements in between the repeated 1s. Whenever the instruction pointer returns to the start of the program (and thus immediately after the tape is initialised), these follow a repeating pattern:
- 0 (usually; this is a 1 for one specific cell, the cell after the unused "waterclock" cell, which mustn't be the original second cell on the tape); or 6 if it's one of the two cells immediately before the tape pointer
- 0; or 6 if it's one of the two cells immediately before the tape pointer
- an arbitrary positive number
- a cell that holds the same value as a waterclock in the original The Waterfall Model program (except that one such cell is unused)
This gives us a number of waterclocks equal to ⅛ the total number of cells on the tape minus 1 (¼ minus 1 after ignoring the 1s that appear everywhere).
The next piece of code to appear in the compiled program is ++++++ >> -+ << ------ << ------ >> >> >> >> -+. This code effectively starts by looking for the next nonzero cell after the point at which it started running (which is probably a waterclock that's just been zeroed); this will be the positive number just before the next waterclock (or unused waterclock). Each zero cell we find when we're looking will be set to 6. When we find the arbitrary positive number, the code subtracts 6 from the two cells before the pointer (thus maintaining our invariant that whether the first two cells in the sequence of four are 0 or 6 depends on their position relative to the pointer, as the pointer's about to move away). Note that, however, that when this sequence starts with a zeroed waterclock cell, it will be set to 6 while we're looking for a nonzero cell, and (unlike the two 0-or-6 cells) not set back to 0 when we find it.
The code then jumps the tape pointer past the waterclock after the arbitrary positive cell we found, and checks to see if the cell where it ends up (the cell after the waterclock/unused waterclock we found) is nonzero. If it isn't, it'll restart, effectively repeating these steps to check the cell after each waterclock in turn (setting the maintained zeroes to 6 and back to 0 in the process). Eventually, it'll find the cell after the unused waterclock. And thus, the purpose of the code in question is that when it runs after at this point in the code, we've made no changes to the tape (except for setting a waterclock from 0 to 6 if the instruction pointer started there), but the tape pointer is now in a known position (specifically, on the 1 just after the unused waterclock).
Now that the tape pointer is in a known position, we can start talking about moving the pointer to specific cells (as for the rest of the program we always know where the pointer is) and performing specific adjustments to them (or more colloquially, adjusting specific cells). The basic idea is to apply the expected cell value adjustments for the first waterclock zeroing, then decrement it and undo the decrement, then undo those adjustments and apply the expected cell value adjustments for the second waterclock zeroing, then decrement it and undo the decrement, and so on. If any waterclock is at 0 (and thus "decreased to -1"), it'll end up getting reset to 6, and every other cell being set to 1 more than its expected value (because it should have been decremented, but with this algorithm, none of the cells are other than the waterclock that zeroed). The result thus leaves every waterclock 1 higher than in the The Waterfall Model program that's being simulated, which is a correct result (as adding 1 to the value of every waterclock in a The Waterfall Model program is a no-op). Similarly, zeroing triggers run on waterclocks being decreased from 0, rather than decreased to 0, but this likewise has no effect on the semantics of the program.
If the program hasn't restarted yet, it must be because all the waterclocks have positive values. As such, we can subtract 1 from every waterclock (thus maintaining The Waterfall Model semantics), via moving the tape pointer there and decrementing it. Finally, we just have to restart the program, which can be done by going to the original second cell (which should be 0 at this point) and attempting to decrement it. (It's possible to slightly modify this construction to add a halt state; if the unused waterclock is the second-last on the tape, but the last is also unused, then the code won't be able to observe an increment of the second cell except when the "subtract 1 from everything" effect happens. Thus, this cell can be incremented by a waterclock zeroing trigger, even though it isn't a waterclock, to serve as a signal that the program should halt.)
See also
- Brainpocalypse II
- Subtractpocalypse and brainfuck
- The Waterfall Model
- OISCalypse, an OISC inspired by Brainpocalypse