BackFlip
BackFlip is a 2-D reversible programming language created by User:ais523 in 2006.
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.
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.
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.
The ABCDXYZ storage device
A storage device has been invented, which has four states (A, B, C and D) and three commands (X, Y and Z).
- In state A, X and Y change to state B, and Z remains in state A.
- In state B, X and Y change to state C, and Z changes to state D. X will also cause the event function to run.
- In state C, X and Y change to state D, and Z changes to state B. Y will also cause the event function to run.
- In state D, X and Y change to state A, and Z changes to state C.
Unfortunately, it behaves in an undefined manner if you try to send it commands recursively (intuitively, this is because otherwise you could create an infinite loop if the event function called X four times). The #s round the edge are purely comments to set this register off.
This should actually be able to store something; using just states A and C, XY is a negate instruction like @ in Smallfuck, and YYXY calls the event function in state C but not in state A). The code example below is one possibility for state A. (There is another arrangement of arrows and mirrors it sometimes reaches that acts exactly like state A.)
###### VV # Input from the left on this row does X. \ V# Input from the left on this row does Z. V # Input from the left on this row does Y. # V # #>\< # #^/^ # #V < # # >\<# # ^/^# #> V # \ < # Outputs to the left for the event function, #^ # which should return by backtracking. ######
This device has been made into an esoteric programming language of its own, ABCDXYZ.
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.
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.
Computational class
As BackFlip cannot use unlimited memory, it cannot be higher than Finite state machine. 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.
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.