Subtractpocalypse

Subtractpocalypse is an esoteric programming language created by User:ais523 in 2016.

Data storage

Like a Minsky machine, Subtractpocalypse stores data using a number of counters, each of which has a name (which is a string of letters, case-insensitive), and each of which can store a nonnegative integer. A Subtractpocalypse program starts by listing the counters it uses and their initial values in the format name=value (with the values in decimal); whitespace is ignored. For example:

x = 5  y = 6  z = 7

Commands

A Subtractpocalypse command is a series of changes (additions or subtractions of a constant) to one or more counters. The individual changes to counters within a command are listed using the format name+value or name-value (again, values are in decimal, and consist entirely of digits, with a + or - sign not being part of the value); a complete command is made via listing one or more changes separated by commas, followed by a semicolon. As usual, whitespace is ignored. The same counter cannot be changed twice within a command. For example, here are two commands:

x + 3, y - 2;
z + 5;

When running a command, two things can happen. One possibility is that all the counters listed will change by the amounts, and in the directions, specified; this happens whenever possible. If, however, a command tries to subtract more from a counter than its current value, changing all the counters by the amounts specified is impossible, because a counter can't hold a negative value. In this case, the command restarts the entire program (without resetting counters to their initial values), and has no other effect.

A program is just a list of commands, which run in sequence, and exits if the last command completes running without restarting the program in the process. If a program exits naturally like this, the value of the first counter to be defined is interpreted as a base-256 integer and output as a sequence of octets, apart from its first digit.

Computational class

(The main thing holding back Subtractpocalypse from being obviously Turing-complete is its rather idiosyncratic control flow. Reversing the control flow – so that a program restarted after successfully running a command – would make the language clearly equivalent to Fractran. But such a thing is not needed...)

Here is a method (by User:Keymaker) for translating Minsky machine to Subtractpocalypse, thus showing that the language is Turing-complete.

A translator can be found here: http://yiap.nfshost.com/esoteric/subtractpocalypse/mmtosubt.py (The translator's output could be more optimized but the author was not in the mood for programming that. Presently, the output offers maximum clarity.)

A simple MM program like this:

1 inc A 2
2 inc A 3
3 dec A 3 4
4 halt

produces the following Subtractpocalypse program:

regA=0 addA=0 ok=0 cur=0 next=0

ok+1, next+1;
next-2, cur+1, ok-1;
ok-1;
cur-1;

ok+1, addA+1;
addA-2, regA+1, ok-1;
ok-1;
regA-1;

regA+1;
next+1;
cur-1;
regA-1;
next-1;

regA+1;
next+2;
cur-1;
regA-1;
next-2;

next+3;
addA+1;
regA-1;
next-3;
addA-1;
next+2;
cur-1;
next-2;

The beginning of the program declares the counters. Then follows a couple of loop constructions, which are used to add the arbitrary contents of certain counters to another ones - essentially transferring data from the end of the program to its beginning; from one 'cycle' to the next. The most used of these is the pair 'next' and 'cur', which are used to represent which simulated instruction of the MM will be simulated next. Counters with names like 'addA' are used to increase the simulated MM counters - why that is done, see below...

The execution of a simulated MM instruction is based on manipulating a counter - and then annulling the change unless the current instruction is the one (indicated by 'cur' with its value as 0) whose change is meant to remain. To execute, for instance, the 5th instruction, instructions 1, 2, 3, and 4 must be executed before that - and their effects annulled. Annulling an INC instruction is simple; simply decrease the counter right after. DEC is a more complicated case; because the jump is used in the case of branching, and the jump always happens whenever a command attempts to decrease something below zero, a simple "decrease by one, then increase by one" is not sufficient here since a counter might have 0 as its value and cause unintentional branching. That is why, when an instruction sets the next one (by manipulating 'next'), it will also set proper addX-counters - they add (in the beginning of the next cycle) to the relevant counters, so that the DEC instructions before the current (new) instruction will not cause any unintentional jumps to happen. The counters will be back to normal by the time the current instruction is reached.

The command "cur-1;" transports control flow to the beginning of the program if cur is 0 - that means the current instruction is one whose effect will remain. In case a DEC branches, the jump happens because of "regX-1;". In both cases, the 'next' is already set, and that instruction will be simulated next.

If HALT is used - it should be the very last instruction of the MM program for this translation method - the program will simply continue past all instruction simulations and end there, as Subtractpocalypse does on its own.