Subtractpocalypse

From Esolang
Jump to: navigation, search

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 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.

Subtractpocalypse to Minsky Machine

Subtractpocalypse is quite simple to translate into Minsky Machine. Here is a commented example for translating this

x = 3  y = 2  z = 3

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

to MM:

;; initial:  x = 3  y = 2  z = 3
i1 inc X i2
i2 inc X i3
i3 inc X i4
i4 inc Y i5
i5 inc Y i6
i6 inc Z i7
i7 inc Z i8
i8 inc Z c1s1 ; go to command 1


;; command 1:  x + 3, y - 2;
; 'x+3' - will always succeed
c1s1 inc X c1s2
c1s2 inc X c1s3
c1s3 inc X c1s4
; 'y-2'
c1s4 dec Y c1s5 c1s7 ; if fails, y was 0, no need to fix y value since it didn't change, go to fix x (c1s7)
                     ; otherwise, y was decreased by one successfully, continue to c1s5 to decrease it further
c1s5 dec Y c2s1 c1s6 ; if fails, y was 1 (previous instruction c1s4 changed it from 1 to 0), so go to c1s6 to correct it back to 1
                     ; if decreased, y was originally at least 2 and was decreased by 2 successfully (by c1s4 and c1s5), go to next command's simulation (c2s1)
; y correction
c1s6 inc Y c1s7 ; now y is 1 again. if here, command failed, so x must be fixed too, so do that (c1s7)
; x correction
c1s7 dec X c1s8 c1s8 ; if here, always succeeds, so both branches can just be c1s8
c1s8 dec X c1s9 c1s9
c1s9 dec X c1s1 c1s1 ; now both registers are fixed. restart program (go to command 1)


;; command 2:  z + 5;
; 'z+5' - will always succeed
c2s1 inc Z c2s2
c2s2 inc Z c2s3
c2s3 inc Z c2s4
c2s4 inc Z c2s5
c2s5 inc Z end ; go to end of program


;; the program halts if running through the commands successfully, here a halt instruction simulates reaching that point
end halt

Generally, a command increases and decreases registers. If a register would become less than 0, it means the command fails, so all the changes done at that point by the command's simulation are reversed (increments decreased, decrements increased) and the control flow moves to the first command of the program.

Interpreter

One can find an interpreter written in Python here: http://yiap.nfshost.com/esoteric/subtractpocalypse/subt.py It will not detect all faulty programs and does not handle output at all but otherwise it should be fine.