Brainpocalypse II
Brainpocalypse II is a modified version of Brainpocalypse, created by User:ais523 in 2023. Unlike Brainpocalypse, in Brainpocalypse II the position of the tape pointer is statically known at every point in the program (i.e. for every command, it is known which tape element it will act on); the intention is that this should make it easier to write compilers from Brainpocalypse II into other programming languages, in order to prove those languages Turing complete. Brainpocalypse II is otherwise very similar to its predecessor (although the "decrement" instruction needed to be tweaked slightly in order to allow the program to zero-test cells without completely forgetting what it was doing at the time).
Data storage
Like in brainfuck and Brainpocalypse, Brainpocalypse II stores data on a tape of cells, each of which holds an unbounded non-negative integer, initially 0. Although the tape is conceptually infinite (like in brainfuck), only a finite number of cells on the tape can ever be read or written by any given program (because for any given location in the program, it is possible to statically calculate which cell it is referring to).
Commands and syntax
There are three different syntaxes available for Brainpocalypse II. These are equivalent to each other, and effectively different ways of viewing the same language.
Standard version
The standard version of the language uses a pointer that points to a cell on the tape, and has the following commands:
< |
Move the tape pointer one cell to the left. |
> |
Move the tape pointer one cell to the right. |
+ |
Add 1 to the cell that the tape pointer is pointing to. |
- |
Subtract 1 from the cell that the tape pointer is pointing to, if it's nonzero. If the cell was 0 (and thus the subtraction was not performed), instead set the cell to 1, reset the tape pointer to its initial location, and goto to the start of the program. |
The commands generally run in sequence, from the start to the end of the program. The - command can be an exception, if it attempts to decrement zero; in this case, the program runs again from the start (and with the tape pointer reset to its initial location, and the cell that was to be decremented being incremented instead).
When execution falls off the end of the program, execution halts. If there are any nonzero values on the tape at the time, this is a "standard halt"; if all the tape values are zero, this is a "perfect halt".
It is possible to statically determine the position of the tape pointer, at any given point in the program, by counting the number of < and > commands up to that point; because a jump to the start of the program also resets the tape pointer to its initial location, the tape pointer will be in the same place any time a given command runs.
Minimized version
Just as with its predecessor Brainpocalypse, it is possible to minimize Brainpocalypse II down to two commands:
( |
Add 1 to the cell that the tape pointer is pointing to. Reset the tape pointer to its original location. |
) |
If the cell that the tape pointer is pointing to is nonzero, subtract 1 from it, then move the tape pointer one cell to the right. Otherwise add 1 to that cell, reset the tape pointer to its initial location, and goto the start of the program. |
By treating every second cell as a bit bucket whose value is never relevant (and instead just used to reset the tape pointer location by incrementing it), it is possible to compile the standard version of the language into this minimized version; after a pointer location reset, it is possible to move to a known cell (without changing any cell values) that's n spaces to the right of the reset position by doing 2n-1 (, then 2n-2 )(, then 2n-3 ))(, and so on, finishing with n copies of ). For example, to reach cell 3, you can do (((()()())())):
initial [0] 0 0 0 (((( [4] 0 0 0 ) 3 [0] 0 0 ( [3] 1 0 0 )( [2] 2 0 0 ) 1 [2] 0 0 ) 1 1 [0] 0 ( [1] 1 1 0 ) 0 [1] 1 0 ) 0 0 [1] 0 ) 0 0 0 [0]
The ability to move the tape pointer to a known cell from its starting location, and to reset it to its starting location, make it possible to move it anywhere. Then, ( and ) can be used to implement the + and - instructions by moving the tape pointer to the appropriate cell, running ( or ) as appropriate, and moving the tape pointer back to a known location (in the case of ); ( does this automatically).
Numerical version
In the numerical version of Brainpocalypse II, instead of having a tape pointer, commands instead specify which tape cell they are working on directly. There are two commands, each of which takes a numerical argument:
+n |
Add 1 to the cell n. |
-n |
Subtract 1 from cell n, if it's nonzero. If the cell was 0 (and thus the subtraction was not performed), instead set the cell to 1 and goto to the start of the program. |
This version of the program is harder to parse, but a little easier to read because the affected cells are explicitly stated (so there's no need to count instructions to work out which cell is affected by any given command). It is up to the implementation whether cell numbers are 0-based or 1-based (programs can be written to work regardless of which convention the implementation uses simply by choosing not to use the cell n=0 regardless of whether or not it exists).
Because for all three versions of the syntax, any given command always operates on a statically known cell, it is possible to compile the other versions of the syntax into this one via changing a + or ( into +n (where n is the cell it operates on), and a - or ) into -n in the same way.
Computational class
Although Brainpocalypse II starts out with a tape of all-zeroes, it is trivial to compile "Brainpocalypse II but programs specify initial values for the tape cells they use" into the official version of the language. The idea is to reserve one additional cell as a marker that specifies whether or not the tape has been initialised (0 for uninitialised, 1 for initialised). The compilation adds additional code at the start of the program, which increases every tape element by its initial value, then decrements the "tape initialised" marker, increments the "tape initialised" marker again, and decreases every tape element by its initial value again. If the tape has been initialised, this entire block of code cancels itself out and is a no-op. However, if the tape has not been initialised, the attempt to decrement the "tape initialised" marker will restart the program, whilst setting the "tape initialised" marker to 1, and every tape element will be left with the correct initial value when this occurs.
Given the ability to initialise cells as desired, it is fairly simple to compile The Waterfall Model into Brainpocalypse II. The idea is to use two cells for each waterclock. The first of these cells, z, is used to control the zeroing trigger; it usually has the value 1, but instead has the value 0 if the waterclock has zeroed but its zeroing trigger has not been run yet. The second of these cells, v, stores the waterclock's value.
The basic structure of the program (after initialisation) is to start by testing all the z cells, in a very similar way to the initialisation: for each cell n, each cell's v (including n's) is increased by the appropriate value from the zeroing trigger, then n's z is decremented and incremented, then all the adjustments to the v cells are undone. If any cells had become zero, but their zeroing trigger had not run yet, then this will implement the effects of the zeroing trigger, whilst setting the z cell in question back to 1. (One slight tweak: the adjustment to n's v will be 1 smaller than the zeroing trigger value, because n will have incremented itself to 1 when it was successfully tested for zeroness.)
After the tests of the z cells comes the steady decrement (implemented simply by decrementing all the v cells – they should all be at least 1 at this point, so the program's control flow does not reset), and then tests of all the v cells. These are done by decrementing the corresponding z cell, decrementing and incrementing the n cell, and incrementing the z cell again.
At the end of the program, the "tape initialised" marker is decremented twice. This sets its value from 1 to 0 back to 1 and restarts the program.
Halting can also be implemented easily in this construction: a halt counter's zeroing trigger can be defined to add 2 to every counter (including itself), and also to increment the "tape initialised" marker. The change to the "tape initialised" marker will have no immediate effect on the initialisation code, and will not change the behaviour of the bulk of the program (nor will any waterclock zero, because they all had 2 added to them). At the end of the program, the double-decrement of the "tape initialised" marker will not restart the program, and so the program will run off the end and do a standard halt. (If the values of every waterclock are known at this point – which is possible if the Waterfall Model program was originally compiled from a state-machine-plus-counters model such as a Minsky machine, and the state machine zeroed its counters before halting – every cell will have a known value at this point, so it is possible to decrease every cell by its known value and do a perfect halt.)
See also
External resources
- An implementation in Jelly, runnable online at Try It Online; implements only the 1-based numerical syntax
- Short Scratch implememtation, with numerical syntax