Re:direction
Re:direction is an esoteric programming language created by User:ais523 in 2018. It is a two-dimensional language, consisting only of the direction-changing arrows and a command to repeat a previous direction change.
Although it was created independently of Andromeda, the two languages have some clear similarities; it is reasonable to interpret Re:direction as a simplification of Andromeda.
Specification
A Re:direction program is a 2D matrix, where each cell contains one of the following six commands:
- No-op (space, or any character not listed below): do nothing
◄: set the IP direction to "left", and push "left" onto the tail of the queue▲: set the IP direction to "up", and push "up" onto the tail of the queue►: set the IP direction to "right", and push "right" onto the tail of the queue▼: set the IP direction to "down", and push "down" onto the tail of the queue♦: shift a direction off the head of the queue; set the IP direction to that direction
The instruction pointer starts in the top-left corner moving right. It executes each command it comes across (which may cause it to change direction); if it goes off one side of the matrix, it wraps to the opposite side and continues from there. The only data storage (other than the position of the instruction pointer) is a queue that remembers previously run direction commands; each direction command is pushed onto the queue as it runs, and the ♦ command will repeat a previous command shifted off the queue. (Each direction command thus typically runs twice each time the IP reaches it; once immediately, and again when it reaches the front of the queue and the the IP reaches a ♦ instruction.)
The program halts when it reaches a direction command on a row or column by itself, that points along that row or column; the command runs once, execution wraps around the program to the location of that command again (without running any commands in between), and the program exits rather than running the command twice in a row. Queue underflow causes an alternative, "error", exit.
The initial state of the direction queue is taken from user input; the user input is a list of non-negative integers, each of which is encoded as that many ► followed by ▼. Likewise, the final state is decoded from the direction queue using the same encoding (with any ◄ or ▲ ignored), and used as user output. The integers may be input and output in decimal or as character codes, depending on the implementation (ideally, implementations should support a switch or command-line option to change between these modes).
When Re:direction programs are stored in a file, the lines of the matrix are joined with newlines, and trailing space on lines of the matrix can optionally be removed. Implementations that read the program from a file should be able to handle at least the following three encodings for the file: UTF-8; codepage 437; or an ASCII substitution using <^>v+ for ◄▲►▼♦.
Examples
Hello world program
Here's an example of what a program that prints a constant string could look like (there are almost certainly terser ways to write this, but this is one of the clearest):
◄ ▼
♦♦◄
▲
▼►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►
▼►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►
▼►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►
▼►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►
▼►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►
▼►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►
▼►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►
▼►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►
▼►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►
▼►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►
▼►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►
▼►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►
▼►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►►
◄
The start of the program pushes "left" and "down" on the queue, and then neutralises unwanted input via changing every "right" to a "left" and "down" to an "up", using a loop on the rightmore ♦. Once the queue cycles back round to the additions made at the start of the program, it will move left from the rightmore ♦, hitting the leftmore ♦, which then goes down and hits the start of the data section. For the rest of the program, we never read from the queue, simply blindly push the characters of the string onto the queue. The final ◄, which (allowing for the wrapping) points to itself, halts the program.
Computational class
Re:direction is Turing complete. A simple way to show this is to observe that it's easy to translate 2-tag systems with an explicit halt state into Re:direction.
For example, the 2-tag system (1→3321H,2→331,3→33) translates as follows (using 0 as the halt state):
♦♦ ♦ ♦
◄
►►►▼►►►▼►►►▼
▼ ▼ ▼
►►►▼►►►▼►►►▼
▼ ▼
►►▼ ►▼
▼
►▼
▼
▼
♦ ◄ ◄ ◄
♦
♦
▼
Each state n from the tag system is represented in the Re:direction queue as n rights, a down, any number of lefts and rights, and a down. (That means that the input to the tag system is expressed as input to the Re:direction program via interspersing zeroes; if we wanted to give the above tag system the input 211, we'd write that as (2, 0, 1, 0, 1, 0) in the Re:direction program.)
The tag system rules themselves are easy to implement given this encoding of the queue. The first row acts as a branch table that branches to one of four locations based on a value read from the start of the queue. The first goes to a ◄ on its own line, i.e. halts. The others each follow a chain of ► and ▼ that push the representations of the appropriate elements onto the queue, minus the final ▼. Then we merge control again using a chain of ◄ (which push to an "any number of lefts and rights" position); discard three sequences of lefts and rights via using ♦s on lines by themselves; and add the final ▼.
Note that this construction can't handle an empty production, but that isn't an issue: you could add an extra state that expands to two copies of itself, and then use two copies of that state as a substitute for an empty production.