BackFlip
From Esolang
BackFlip is a 2-D reversible programming language created by User:ais523 in 2006.
Contents |
[edit] Syntax
In BackFlip, there are only two essentially different commands (three counting NOP, which is a space):
< > V ^ Backtracking direction change (arrow) / \ Flipping mirror (mirror)
The instruction pointer starts to the left of the top-left corner of the program, going right. If it encounters a backtracking direction change, the IP moves in the direction suggested by that change, which changes to point to the direction the IP came from. If it encounters a flipping mirror, the IP bounces off the mirror like a ray of light would, and then the mirror changes to the other sort of flipping mirror.
The input is a file with one character per cell. The first line of the file must be the longest and all lines below it are padded to its length with spaces, if necessary. If the IP goes off the edge of the file, execution terminates. (Infinite loops are impossible in BackFlip, so this always happens).
If the IP never reaches a location, it is ignored. This makes commenting the code possible (locations never reached do not have to be valid commands).
Adding I/O to BackFlip would be easy (see Extensions below), but it is an extension, and not part of the original language.
[edit] Using BackFlip
The only way to store data in BackFlip is by changing commands. Here is an example:
\----------------------
V V V V V V V V
\ />/>/>/>/>/>/ \<
>\>\>\>\>\>\>\<
< ^ ^ ^ ^ ^ ^ ^
^
When the program starts, control flow bounces off the mirrors at the top-left and left of the program, then follows through the />/>/>/>/>/>/ section, bouncing off the Vs as it goes. This leaves all the mirrors in that section in their original orientation and all the arrows in that section pointing left. The top-right demonstrates a way to emulate a fixed mirror (even when the mirror is flipped, the section of code acts as if it hadn't). Control flow hits the arrow at the bottom of the program and proceeds to backtrack. The large block in the middle of the program acts as a loop counter, with the result that the control flow hits the arrow another 63 times. Finally, control flow reaches the lower mirror on the left (which was flipped right at the start of the program) and the arrow below it diverts flow out of the program, ending it.
An example of function calling and a register that holds integers:
\----------------------------
\
\\\\\\\\\\\\\\\\\\\\\\\\\\/
> > > > > > > > V
>> >> >> >> >> >> >> >> > V
0 >/<
1 ^/<
2 ^/<
3 ^/<
4 ^/<
5 ^/<
6 ^/<
7 ^/<
8 ^/<
^
The main program consists of the row of mirrors near the top. Each is a subroutine call, with the arrows keeping track of return addresses. The first function, called using the top row of arrows, increments the register at the bottom-right of the program modulo 9 (the 'current value' of the register is the one with the rightwards-pointing arrow next to it). The second function changes a stored 0 to 1, 1 to 0, 2 to 8, 8 to 2, 3 to 7, 7 to 3, 4 to 6, 6 to 4, and 5 to 5.
There is a considerable problem with the second program; although the register can be changed at will, there is no way to access the value stored in it. More complicated techniques are required to write a BackFlip program that can both store and retrieve data.
[edit] Possibly useful patterns
In order to create a turning path which is not essentially changed by following it, the one-sided fixed mirror patterns (as in the first example) may be used:
V V \< or /<
It is easy to build patterns from which anything bounces back:
> V V>< V/ ^ or >< or ^>< >^
Here, the essential property is that all possible exits contain arrows, none of which are initially pointing outward. The only way to exit is through the arrow that was turned outward by entering.
[edit] Parity
As noted above, a one-sided fixed mirror may be emulated by two patterns turning into each other. The flipping between \ and / is essential: it is impossible to change the line that the instruction pointer is moving along without changing the content of the program. This is because each execution step preserves, on each vertical and horizontal line, the total parity (i.e. whether there is an even or an odd number) of the following:
- Whether the instruction pointer is moving along the line
- Number of / (equivalently, number of \)
- Number of arrows pointing along the line
If the line contains arrows, it can be split at each of them and the parity is then preserved for each line segment.
[edit] BackFlip extensions
An extension (which is optional and not part of the language) allows for BackFlip programs to produce output.
0 1 2 3 4 5 6 7 8 9 Write this digit to standard output; IP rebounds. N Write a newline to standard output; IP rebounds.
These operations are reversible if there is some way of unoutputting the characters when the flow is reversed.
[edit] Computational class
As BackFlip cannot use unlimited memory, it cannot be Turing-complete. Since it is also reversible a computation must terminate. It is unknown what its computational class is or whether it is usable for computation. To make it Turing-complete it would be necessary to add some way to access unlimited memory, although it might still be reversible.
[edit] See also
- Flip is similar, but more stateful and multithreaded.
- ABCDXYZ, an object-oriented language that can be compiled into BackFlip if its I/O commands aren't used;
- :≠, an easier-to-use version of ABCDXYZ that can probably be compiled into BackFlip if its I/O commands aren't used.
