REVERSE

REVERSE is an esoteric programming language devised by Brian C. Smith. It supports control flow only by reversing direction, top to bottom (moving South) or bottom to top (moving North). Decision making is done by reversing as well. Data is manipulated within integers, floating points, and characters. Integers are signed and have no limits.

Cat in REVERSE is:

 SKIP REVERSE GETXA SKIP PUTXA REVERSE<XA

It works like this:

• First, the SKIP will skip over the REVERSE command.
• GETXA will get one character from the standard input and store it in the variable XA.
• Another SKIP will skip over the PUTXA command.
• REVERSE<XA will reverse the program flow if the variable XA is larger than 0 (i.e. no EOF)
• If the program flow was reversed, the PUTXA command will now write the variable XA to the standard output.
• SKIP will skip over the GETXA command.
• REVERSE will reverse the program flow again.

One proof for Turing-completeness

Here is one proof for the Turing-completeness of REVERSE, via simulation: a Finiteless Cyclic Tag interpreter written in REVERSE. FCT is a variation of the Turing-complete language Cyclic Tag. The only difference is that FTC does not allow terminating programs (the data string may not become empty), nor initially empty program or data strings. Despite these limitations FTC is Turing-complete as well, and being able to run it, REVERSE proves to be Turing-Complete as well. The Cyclic Tag instructions "0", "1", and ";" are identical in FTC.

One may get the FCT-in-REVERSE program here: http://yiap.nfshost.com/esoteric/reverse/fct.rev Then, one may use partialREVERSE REVERSE interpreter to run it. While not supporting every feature of REVERSE (such as floating points and input), partialREVERSE does support arbitrary integers, which appear to be quite important in REVERSE programming. One may get it here: http://yiap.nfshost.com/esoteric/reverse/preverse.py

The FCT interpreter is initially loaded with a program "101;1" and data "10". The important lines are the three in the beginning of the program:

VPROG+23212
VDATA+12
VSIZE+10

Due the nature of the FCT program, the program and data strings are encoded -- and reversed. Encoding the CT program is easy: simply substitute "0" with "1", "1" with "2", and ";" with "3". Then reverse the string. Data is handled similarly; "0" becomes "1", "1" becomes "2" (notice that the data string is binary, and can not have 3s in it). An important thing to note is the VSIZE variable. It must, initially, be given a value that begins with a 1 and is 'padded' with 0s to match the length of VDATA above it. Say, if VDATA was "122112", VSIZE would be:

VDATA+122112
VSIZE+100000

Once the program and data strings are what is wanted, the interpreter can be run. The FCT interpreter prints the state of the data string on every cycle. Below what can be seen with the "101;1" and "10" combination:

 12        ; 21    -> 10
 212       ; 212   -> 101
 1212      ; 2121  -> 1010
 21212     ; 21212 -> 10101
 2121      ; 1212  -> 0101
 2121      ; 1212  -> 0101
 ...

Reading the output requires reversing the encoding (which is done on the commented ';' lines).

External resources

• REVERSE website (from the Wayback Machine; retrieved on 6 August 2009)
• Implementation
• Keymaker's REVERSE stuff features REVERSE programs, partialREVERSE (an interpreter in Python)