Befreak is a purely reversible two-dimensional programming language. It was inspired by the Chris Pressey's Befunge programming language. Like Befunge, all Befreak instructions are written as a single character, and execution can flow north, south, east, and west.
The thing that makes Befreak special is its reversibility. Every instruction in Befreak is by its very nature reversible. At any point during execution, if you'd like, you can pause the system, toggle the "reverse" flag, and then upon resuming, the program will run itself backwards from its current state, eventually ending up at the very beginning, where it started. This feature is not accomplished by keeping a history of past states, but simply by virtue of the fact that each individual instruction is reversible. This means that Befreak contains no instructions that can destroy information; this can make programming in the language both challenging and interesting.
/"Hello world!"01\
\(13v 'wsv)@(/
\(=13=13)/
In Befreak, execution always begins at the @ symbol and proceeds east. Thus, the first instruction encountered is "(", which pushes a zero onto the stack (in Befreak, data is manipulated through a stack, a la FORTH). The next instruction, "/", is a mirror that causes the IP (the instruction pointer) to change direction; in this case, it will make IP go north; next is "\", which is another mirror, and in this case causes IP to go west. Next we have the instruction "01", or rather "10" since we're coming from the east: this causes the top item on the stack to be XOR'd with 10 (decimal); since the top of stack was zero, this makes the top of stack 10, which is the ASCII code for newline.
Next, the " instruction is encountered, which causes the program to go into string mode until the next " is reached. In string mode, the ASCII value of each character encountered (not including the quotes themselves) is pushed onto the stack. In Hello World above, when we reach the second ", the top item on the stack is 'H', and the other characters are underneath.
Next, we hit "/" which makes the IP go south. Then we hit "\" which makes the IP go east. Then we hit "(" and "13", which together push 13 onto the stack ("(" pushes a 0 and then 13 XORs it with 13); 13 is the number of characters in our string; this "13" will serve as a counter telling how many times our main loop will execute; it will be decremented each time through the loop, and when it reaches 0, the loop will be exited.
So, we next hit "v", which is the entrance to our main loop. The "v" here is not exactly the same as in Befunge; it makes the IP go south, but it also pushes a value onto an auxiliary stack, called the "control stack", telling where we came from. In this case, it pushes a 1, since we made a right turn (if we'd made a left turn, e.g., came from the east, a 0 would have been pushed). This value, called a "control bit", is needed for reversibility: imagine we're past the "v", going south, and then we want to reverse, making the IP go back north. What happens when we hit the "v"? How do we know if we came from the right or the left? (we don't need to consider the possibility that we came from the north, as will be explained in the control flow section.) By the control bit on the control stack, of course...
The next instructions "(=13=13)" serve as the condition of the loop, which will determine whether the loop will continue or not. Recall that at this point we have a 1 on the control stack, because we turned right entering the "v". Notice that if this 1 remains how it is, then when we hit the next "v" coming up in a few instructions, we'll turn right again, exiting the loop. Thus, the instructions coming up had better change the 1 to a 0, so that the loop will continue. In fact, they do:
First we push a zero onto the stack, with "(". Then we execute "="; this tests to see if the top two items on the stack are equal, and if so, the top item on the control stack will be XOR'd with 1 (effectively toggling it between 0 and 1). "=" has no effect if the top two items are unequal. In this case, the top two items are indeed unequal (13, our counter, is not equal to 0) and thus nothing happens. But, next we have the sequence "13=", which changes the 0 to a 13 (by an XOR) and then checks to see if the loop counter is equal to that, which it is. Thus the 1 on the control stack is toggled to a 0. Finally, we execute "13)" which cleans things up, changing the 13 back to a 0, and removing it (the ")" instruction removes a zero from the stack; it is an error for the top item to be non-zero with this instruction; if it happens, the interpreter will block, refusing to execute the offending instruction).
Then we hit the mirror "/" which bounces us up into the "v", and we remove the "0" from the stack and turn left. Here we have the body of the loop, which is fairly simple. The "s" instruction swaps the top two items on the stack; in this case, it swaps the loop counter out of the way, pulling up a character ("H"). Then, we write the character to stdout using "w" (this removes the character from the stack). Then we decrement the loop counter with "`", pass over some spaces (which are no-ops) and hit the "v" and re-enter the loop; but this time, a 0 is pushed, instead of a 1, since we're turning left. That means that the upcoming conditional code need not change that 0, since as it is, it will cause a left turn at the next "v", making the loop continue.
Indeed, as you may have figured out, our code only changes the control bit when the loop counter is either 0 or 13, so the loop will keep executing in the same fashion, until the counter reaches 0, at which point the condition will be toggled from a 0 to a 1, causing a right turn at the "v", which makes us exit the loop.
It may seem peculiar that, in essence, we are forced to put both an entrance condition and an exit condition in loop code, instead of just an exit condition. This is a natural phenomenon in reversible programming, since if we were running the loop backwards, we need to know at what point we are done so we can "exit" the loop (through the entrance).
Anyhow, eventually the loop exits, and then removes the loop counter, which is now zero, with ")". Then we ram into the left side of the "@", which the proper way of terminating a Befreak program.
You might be wondering why we used a counter in our Hello World, instead of just using a null-terminated string like one would do in Befunge. The answer is that trying to naively print out a null-terminated string won't work in Befreak becauses its inherently irreversible; if we try to run the program backwards, to unprint the string, how will the program know when the beginning of the string has been reached? But, there are in fact other solutions to the problem besides using a counter: for example, we could fix the first character of the output to be a newline, which would act as a signal when going in reverse (although the output may not look the way we want), or we could preserve a copy of the string as we write.
(5+5)
It works by pushing a zero with "(", changing it to a 5, performing the addition, and then removing the 5 which was left there by "+" (remember, "5" is an XOR; since 5 is already at the stack at this point, XORing it with 5 changes it back to a zero, so it can be removed with ")").
Befreak also has a similar subtraction operator; to subtract 5 instead of adding, use the exact same code as above except replacing "+" with "-". Also, Befreak has the instructions ' and ` which increment and decrement the top item, respectively.
By the way, if an overflow occurs on an addition or subtraction, Befreak will happily wrap around, since this type of overflow is reversible.
On the other hand, multiplication and division gets a bit trickier. Befreak's division instruction "%" works like so: it takes the dividend on bottom and a divisor on top (which must be non-zero). It performs the division, replacing the dividend with both the quotient and the remainder (the quotient is on bottom, and the remainder is above that, with the original divisor staying untouched on the very top). Thus, division takes 2 items and leaves you with 3 items.
Befreak's inverse to the divide instruction is called "*", however this can be misleading, because it is not a normal multiplication operator. It takes 3 items, multiplies the first (e.g., top item, which is the multiplier, and must be non-zero) by the third and adds in the second (which must be less than the first), and leaves you with that result on bottom, with the original top item unchanged. So you might say this is sort of a restricted "multiply-and-accumulate" instruction; to do a normal multiplication, simply use a 0 as the second item.
By the way, in Befreak it is an error to cause an overflow in a multiplication, because, if the multiplier is even, bits are shifted off the high-end and lost, thus being irreversible. Technically, multiplying by an odd number is reversible even through overflows, because of the number theory fact that odd numbers have inverses modulo 2^n; however, Befreak does not use this. (Another fact is that if we did multiplication modulo a prime, then all multiplication, except by zero, would be reversible).
Similarly, there is "|" which takes the bitwise OR of the top two items, XOR'ing the result into the third.
Next, there's "#", which performs XORs. This is a bit simpler than "&" and "|", since XOR'ing is reversible. The top item is simply XOR'd onto the second item, leaving the top item unchanged. This is similar to how "+" and "-" work.
And then, there's "~", which performs a bitwise NOT on the top item. As a handy fact, you can push a -1 by doing "(~" (Befreak assumes two's complement arithmetic).
Finally, there's "{" and "}" which perform left and right bitwise rotations; they rotate the second item by the amount specified in the top item, leaving the top item untouched.
There's "d", which digs up the third item, bringing it to the top of the stack (causing the original first and second items to become second and third). The inverse to this is "b", which buries the top item underneath the next two, making it the third item.
There's "c", which swaps the second and third items, leaving the top untouched. And, there's "f", which flips (e.g., reverses the order of) the top three items, effectively swapping the first item with the third.
That's it for the permutators. Befreak also has the equivalent of "DUP"; it's called ":", as in Befunge. This simply duplicates the top item, leaving you with two items that are the same. The inverse is ";", which unduplicates two things, leaving you with one (it is an error if the two things are not the same).
As an interesting fact, it's possible to construct ":" as "(s#" or "(s+".
Finally, as mentioned earlier, Befreak uses an extra stack called the "control stack"; it is is mainly used as a place to put control bits for loops or conditionals; however, it may also be used like the "return stack" of FORTH, as a convenient place to temporarily shove stack items that won't be needed for a while. The instruction to transfer an item from the main stack to the extra stack is "["; to bring it back, use "]" (notice that "[" and "]" move, not copy, the items). Also, there's the "$" instruction, that swaps the top item on the main stack with the top item on the control stack.
Notice, these comparisons can be conveniently combined; for example, to do a lesser-than-or-equals-to comparison, simply do "l=". For not-equals, do "lg".
One of the neat things about a reversible programming language is the ability to run code backwards. In Befreak, sometimes it is expedient to run a portions of code backwards. There is a way to do that: that "?" instruction toggles the system's "inverted mode". If inverted mode is on, then the inverse of each individual instruction is used, instead of the normal instruction. However, the IP keeps moving the same way that it normally would.
There's one particular pattern of coding that "?" is very handy for; often in reversible coding, you want to do some code that sets up some information, then do some code "FOO", and then go back and undo the code that did the setup. That is, you want to do "SETUP FOO UNSETUP". However, if "SETUP" is large, then it can be inconvenient to have to write it again backwards for "UNSETUP". In Befreak, using "?", you can solve the problem this way (here, "SETUP" and "FOO" represent arbitrary blocks of code; they may be much larger than just 5 or 3 characters):
@v? S E T U P / ^?\ \FOO/
Recall that the IP starts at "@" and goes east. We hit the "v", turn right, and do the "SETUP". Then, we hit "^", turn right again, and do FOO. We hit "?" which puts the system into inverted mode; then we hit the "^" again, and turn right, going north, and undo "SETUP", and hit "v", turn right again, and hit "?", which restores the system to normal mode. Thus, looking at the whole thing, we've done "SETUP", done "FOO", and then undone "SETUP".
In inverted mode, the roles of 0 and 1 are interchanged, in that 0 then corresponds to a right turn and 1 to a left turn, both in entering and exiting the branch. This is neccessary for it to run backwards properly.
Befreak also has "^", ">", and "<", which are north, east, and west branches. They function exactly symmetrically to "v". For example, ">" makes the IP go east (and push a 0 or 1 onto the stack), when coming from the north or south, and makes the IP branch when coming from the east. In all four kinds of branches, 0 corresponds to a left turn, and 1 to a right turn (except that in inverted mode, this is reversed).
One helpful way to think about branches is to avoid thinking too much about the control bits, and simply realize that if we enter a loop or branch by turning right, then it will also exit by turning right, (unless the control bit or the inverted mode is toggled in between), and if we enter by turning left, then it will exit by turning left. You can take a portion of code (that includes branches) and flip it on it horizontally or vertically (i.e., along an x-axis or y-axis), and it will normally function exactly the same way, although all the control bits will be reversed.
Now, we have too look at what happens if a branch is entered from the "wrong" side (for example, if "v" is entered from the north). Here's what happens: the top item on the control stack is toggled, the system enters inverted mode (or rather, inverted mode is toggled), and IP reverses direction (in the case of "v", IP goes back north). This may seem a bit peculiar, but in fact this is a useful behavior in many situations; it gives a slick way of doing backtracking, or aborting due to an exceptional condition. Here's an abstract code example:
@ v? HANDLE_EXCEPTION
C
O
D
E / KEEP_GOING
> IS_THERE_AN_EXCEPTIONAL_CONDITION <
v
Here's what happens: we hit the first "v" and go south (and push a bit onto the control stack), do "CODE", and then hit ">", which sets up a bit on the control stack to be potentially toggled by the "IS_THERE_AN_EXCEPTIONAL_CONDITION" (note, we could have set up that bit by manually pushing zero using "([", but that would be less proper, because if we reflected the whole program vertically, it would then no longer function correctly, because then a 1 would be needed to be pushed, instead of a zero; also, the ">" is visually a structural match to the upcoming "<").
Now, as long as that exceptional condition doesn't happen, the IP will turn left again at the "<" and execute "KEEP_GOING", and the program will go on its merry way. However, if there is an exceptional condition, then IP turns right and we hit "v" the wrong way, which causes the top item on the control stack (the bit pushed by the original "v") to be toggled, inverted mode to be entered, and IP to go back north. At this point, the program backtracks until we reach the original "v" (i.e., whatever was done by "CODE" and "IS_THERE_AN_EXCEPTIONAL_CONDITION" is undone). If it wasn't for the fact that the abort (hitting "v" the wrong way) toggled the top item on the control stack, then the abort would be permanent, causing us to backtrack all the way to the beginning of the program, with no way to stop it. However, since it does toggle the top item on the control stack, we end up going east when we hit that original "v", and then hit the "HANDLE_EXCEPTION" stuff (first restoring the system to normal mode using "?"). One last and important thing to notice here is that from the perspective of the "HANDLE_EXCEPTION" stuff, it is as if the "CODE" had never been executed at all, since it was unexecuted in the backtracking process.
Also, Befreak has the "r" instruction, which reads a character from stdin onto the top of the stack.
We might question the reversibility of these instructions. In fact, writing to stdout is irreversible since we cannot, within the constraints of an irreversible operating system, take back the characters that we've written. Also, we cannot give back characters that we've read from stdin.
However, the interpreter handles this problem by keeping a stack of characters that have been outputed, and a stack of characters than can be input ("uninputing" something puts a character back on the top of that stack, whereas input from the keyboard comes in at the bottom of the stack). Thus, within the cozy bubble of the interpreter, everything, including input/output, is completely reversible. However, if Befreak is interacting with the outside world, then we'll have to accept this degree of irreversibility.
As a final note, for kicks, here's a program that prints out the prime numbers (the bottom half of the program outputs an integer in decimal form, character by character, since Befreak has no special instruction to do this):
/1)@(1\
>)1=1(<
\'(v?)/
>'%s(\
^ >*s)=/
>=<
(
/s'0v^?w23(v`s]:(48\
[ ( ) +
) = = 4
0 c c 8
1 = = )
% ) ( w
\01(^ ^)01*01(/
1-9 XOR top item with a value 1 thru 9 (multidigit also works) . [x] -> [x']
( Push a zero onto the stack ..................................... -> [0]
) Pop a zero from the stack .................................. [0] ->
[ Transfer the top of main stack to control stack ............ [x] ->
] Transfer the top of control stack to the main stack ............ -> [x]
$ Swap the top item with the top of control stack ............ [x] -> [y]
w Write the top item to stdout as a character ................ [x] ->
r Read a character from stdin to the top of stack ................ -> [x]
' Increment the top item ..................................... [x] -> [x']
` Decrement the top item ..................................... [x] -> [x']
+ Add the top item to the next item ...................... [y] [x] -> [y+x] [x]
- Subtract the top item from the next item ............... [y] [x] -> [y-x] [x]
% Divide x by d, leaving a quotient and remainder ........ [y] [x] -> [y/x] [y%x] [x]
* Undo the effects of %, using multiplication ........ [z] [y] [x] -> [z*x+y] [x]
~ Bitwise NOT the top item ................................... [x] -> [~x]
& Bitwise AND top two items, XOR'ing to the third ... [z] [y] [x] -> [z^(y&x)] [y] [x]
| Bitwise OR top two items, XOR'ing to the third ..... [z] [y] [x] -> [z^(y|x)] [y] [x]
# Bitwise XOR the top item to the next item .............. [y] [x] -> [y^x] [x]
{ Rotate "y" to the left "x" bits ........................ [y] [x] -> [y'] [x]
} Rotate "y" to the right "x" bits ....................... [y] [x] -> [y'] [x]
! Toggle top of control stack (i.e., XOR it with 1) .............. ->
= If y equals x, toggle top of control stack ............. [y] [x] -> [y] [x]
l If y is less than x, toggle top of control stack ....... [y] [x] -> [y] [x]
g If y is greater than x, toggle top of control stack .... [y] [x] -> [y] [x]
s Swap the top two items ................................. [y] [x] -> [x] [y]
d Dig the third item to the top ...................... [z] [y] [x] -> [y] [x] [z]
b Bury the first item under the next two ............. [z] [y] [x] -> [x] [z] [y]
f Flip the order of the top three items .............. [z] [y] [x] -> [x] [y] [z]
c Swap the second and third items .................... [z] [y] [x] -> [y] [z] [x]
o "Over": dig copy of second item to the top ............. [y] [x] -> [y] [x] [y]
u "Under": the inverse of "over" ..................... [y] [x] [y] -> [y] [x]
: Duplicate the top item ..................................... [x] -> [x] [x]
; Unduplicate the top two items .......................... [x] [x] -> [x]
" Enter string mode ..............................................
? Toggle reverse mode ............................................
@ Halt. Also signals the entrance point for the program ..........
\ If going east or west, turn right; otherwise, turn left ........
/ If going east or west, turn left; otherwise, turn right ........
> If going north, go east and push 1 (in reverse mode, push 0) ...
If going south, go east and push 0 (in reverse mode, push 1) ...
If going west, pop and go south if 0, north if 1. (opposite in reverse mode)
If going east, toggle top of control stack, toggle inverted mode, and go west.
< If going north, go west and push 0 (in reverse mode, push 1) ...
If going south, go west and push 1 (in reverse mode, push 0) ...
If going east, pop and go north if 0, south if 1. (opposite in reverse mode)
If going west, toggle top of control stack, toggle inverted mode, and go east.
v If going east, go south and push 1 (in reverse mode, push 0) ...
If going west, go south and push 0 (in reverse mode, push 1) ...
If going north, pop and go west if 0, east if 1. (opposite in reverse mode)
If going south, toggle top of control stack, toggle inverted mode, and go north.
^ If going east, go north and push 0 (in reverse mode, push 1) ...
If going west, go north and push 1 (in reverse mode, push 0) ...
If going south, pop and go east if 0, west if 1. (opposite in reverse mode)
If going north, toggle top of control stack, toggle inverted mode, and go south.