Introduction to Befunge
Befunge is a programming language in which the program is written on a 2D grid. Each grid square contains a maximum of one instruction or element of data. The grid is initialized with the instruction pointer in the top-left grid square. To run a program, the instruction currently under the pointer is executed and then, by default, the instruction pointer moves to the right by one grid square and the process repeats.
Instructions however exist to move the instruction pointer in any compass direction and hence the programmer can utilize fully the two dimensions of the grid. To differentiate between instructions and data, a special string mode is used, yet there is nothing to stop the programmer from writing a string across the grid and then executing the characters as instructions. Most instructions operate on the stack. The instructions available are as follows:
COMMAND INITIAL STACK (bot->top) RESULT (STACK)
------- ------------- -----------------
+ (add) <value1> <value2> <value1 + value2>
- (subtract) <value1> <value2> <value1 - value2>
* (multiply) <value1> <value2> <value1 * value2>
/ (divide) <value1> <value2> <value1 / value2> (nb. integer)
% (modulo) <value1> <value2> <value1 mod value2>
! (not) <value> <0 if value non-zero, 1 otherwise>
` (greater) <value1> <value2> <1 if value1 > value2, 0 otherwise>
> (right) PC -> right
< (left) PC -> left
^ (up) PC -> up
v (down) PC -> down
? (random) PC -> right? left? up? down? ???
_ (horizontal if) <boolean value> PC->left if <value>, else PC->right
| (vertical if) <boolean value> PC->up if <value>, else PC->down
" (stringmode) Toggles 'stringmode'
: (dup) <value> <value> <value>
\ (swap) <value1> <value2> <value2> <value1>
$ (pop) <value> pops <value> but does nothing
. (pop) <value> outputs <value> as integer
, (pop) <value> outputs <value> as ASCII
# (bridge) 'jumps' PC one farther; skips
over next command
g (get) <x> <y> <value at (x,y)>
p (put) <value> <x> <y> puts <value> at (x,y)
& (input value) <value user entered>
~ (input character) <character user entered>
@ (end) ends program</pre>
(Instruction set description taken from here)
The first program I will inflict on you is the mandatory Hello World program: hello_world.bf. The program can be seen below:
You will have probably noticed that Hello World! is written backwards in the program, between two sets of quotes, this is because Befunge’s main data structure is the stack. Most of the commands affect the stack contents and it is considered purer by certain groups to avoid the use of the memory commands in favor of perverse stack manipulation :) The first double-qoute enables string mode, Hello World! is then pushed to the stack backwards so when we pop it later it is forwards, string mode is necessary for befunge not to try and interpret the letters as commands, infact, Befunge will do nothing to those characters if they are not viable commands.
The next character we see is >, this tells us we want to go to the right, we move up,down,left and right in Befunge with the respective characters ^, v, «/font> and >. The , tells us to output the top value of the stack ‘H’, the # tells us to skip over the character immediately following it. The next character : just duplicates the top value on the stack so we end up with two copies, this is done because certain commands pop the stack to use the top value, so if we don’t desire this action we must make a copy first. We now encounter _, this is a horizontal IF statement, if the top of the stack is 0 (or empty) we travel to the right, any other value sends us to the left. Because we have just done a comparison on ‘e’, integer value 101, we go to the left, we then encounter our copy command again, since we do not wish to duplicate the character, the command after is $ which tells Befunge to pop the stack and scrap the value. Now we hit a # which skips us over the , and we smash into a >, this sends us flying back to the right where we encounter , and the top of the stack ‘e’ is output, if instead of a ,, we had used . the program would have output the integer value 101 instead. Now we are back where we started, this is our loop. We jump again, compare again and so on until we output ’!’, jump; copy then do our final comparison, 0 is on the stack (since it is empty) so we go right instead of left and encounter the character @, this tells us to terminate the program.
Our next venture into the world of Befunge will be a factorial calculator: factorial_calc.bf, the program is shown below:
Ok, this one is a little more complicated and exploits the stack nicely, I will assume you have gained a little insight from the description of the previous program. Essentially we get our user input using the & command, lets assume it is 4; we are usherred on by > to a : which is the copy command, we need an extra copy because we want to preserve the value. Next, 1 is pushed onto the stack and then we come across: -, a subtract, this performs the operation second_from_top_of_stack - top_of_stack. We hit another duplicate (:) and then collide into a # which jumps us over the v into a horizontal IF, represented by _. The top of the stack is currently 3, so because we are not 0 or empty we branch to the left, we encounter v which tells us to go down then «/font> sends us left to ^, we then end up back at >, this is effectively the start of our loop. This little loop, assuming a starting value of 4, pushes 3, 2 and 1 now when 1 is subtracted from 1 we get 0;) which means when we get to
_ we branch right instead of left. Now, we still have a copy of zero on the top of the stack so we kill this with the $ command.
Finally, for that straight out of the packet freshness, is my program which converts integers in radix 10 to binary representations, the wonderful binary_conv.bf. If you found befunge fun, there are plenty of other nice languages like Unlambda, malbolge, brainfuck, and wierd out there, the Cats-Eye Technologies webpage has them all.
Finally, check this out for elite: quicksort in befunge: http://kotisivu.mtv3.fi/quux/index.html