BrainFunge

A BF interpreter written in Befunge!

• Funge-93 compliant!
• Turing complete (with minimal changes) in Funge-98!
• Tested and working here, here, and here!
• Also works in my own Python3 Befunge interpreter!

v
0++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+
0++.------.--------.>>+.>++.
v
v
v
v
v
>::44*5*1-%1+\44*5*1-/1+g02g68*-!v                                              
^                  v     !-*86g10_99*9+1+-:v                                    
^                 v_99*9+3+-:v                                                  
^                             <-1p20+g20!-2_$02g1-:02p68*-!!2*-v                
^              <+1 p10+g10!+2_$01g1-01p>                       v                
^                 >           76*1+-:v                         v                
^                                v:-1_$\:1+:0g1+\0p\>    #+    v                
^                            v:-1_$\:1+~84*+\0p\>        #,    v                
^                        v:-1_$\:1+:0g1-\0p\>            #-    v                
^                  v:-*27_$\:1+0g84*-,\>                 #.    v                
^              v:-2_$\1-\>                               #<    v                
^      v:-+1*56_$\1+\>                                   #>    v                
^  v:+2_$\:1+0g84*-!v                                          v                
^                 v\_\02g1+02p2->                        #]    v                
^ @_$\:1+0g84*-v  #                                            v                
^            v\_\01g1+01p>                               #[    v                
^+1<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<                

BF?

BF is an esoteric programming language consisting of 8 instructions (> < + - . , [ and ]) that is a fantastic introduction to writing interpreters / compilers or proving a system is Turing complete. The Wikipedia article is a great place to read more.

Befunge?

Befunge is an esoteric programming language designed to be incredibly difficult to compile - it features (in the funge-93 specification) an instruction pointer that can move in 2 cardinal directions, an 80x25 grid of instructions, and the ability to modify its own code - aka "reflection". Once again the Wikipedia article is a great place to learn more!

Is this actually turing complete then?

Almost. With the limited code and data space, running in a funge-93 compliant compiler / interpreter, this code is not turing complete. It could be if the program was fed in via stdin, but I didn't want to interleave program and user input.

It is, however, trivial to achieve turing completeness in a funge-98 compiler / interpreter while still using the Funge-93 instruction set. The text wrapping code should be removed, after which the BF program is written entirely on line 1. Funge-98 programs are not constrained to any size grid, so data and program space can stretch continuously, and turing completeness is achieved.

This doesn't look very space and/or time efficient

It probably isn't! :D

Architecture

There is not much to a BF interpreter. You need:

1. An array to hold onto your data
2. An instruction pointer, to point to the current instruction
3. A data pointer, to point to the current data

We also avail ourselves of two counters: one each for the amount of left and right brackets we are abiding by at a given moment. No other state is needed; all other commands are executed immediately, using the topmost row of the grid as the data storage.

Brackets?

BF accomplishes looping by using brackets: if a right bracket is encountered, and the data at the current data pointer is nonzero, the program loops back to the matching left bracket. Vice versa is also true, if a left bracket is found and the data at the data pointer is zero, we jump forward to the matching right bracket. At first blush this can look tricky to implement but luckily, bracket matching is O(n). When moving forward you keep a tally of how many left vs right brackets you've seen; when that number reaches 0, you have reached the end of the original bracketed data. When moving backward, the tally becomes right vs left brackets.

This bf interpreter uses two "static" counters to achieve this, that physically occupy a space on the board. These could be held in memory, but Befunge only supports swapping the topmost two values in the stack. By storing the bracket counters on the board itself we need only store the data and instruction pointer in memory, making swaps trivial. What's more, the bracket tallys reuse the original instruction and data pointer initialization instructions as a space-saving measure!

Code Overview

You don't need to know the entire instruction set of Befunge to make sense of this section, but do note that:

1. All Befunge programs start in the top left of the board and travel right unless directed otherwise
2. The instruction pointer's direction is changed via <, >, v and ^ - hitting a cell with one of these arrows in it will unconditionally change the direction of the instruction pointer
3. Befunge is a stack-based language - most functions either pop a value onto the stack, manipulate values on the stack, or do both

Initialization

We immediately redirect the instruction pointer downwards, and pop two 0's onto the stack; these are the data and instruction pointer x values. Both values are actually offset by 1, but we just accomplish this by adding 1 to a copy of the pointer value whenever we need to reference something. These two zeros are the instructions that get repurposed into the bracket tallies.

>::44*5*1-/1+\44*5*1-%1+

Yeah... Befunge is a bit of a write-only language.

This code used to be much simpler: :1+1g -> copy the instruction pointer, add 1 to it, add a y value of 1 to the stack, and get the value at the square [x+1,1]. However, the funge-93 specification clearly outlines a maximum board size of 80x25 instructions, and most Befunge interpreters / compilers dutifully comply. "Hello World" in bf is well over 80 characters, so I needed to write some text wrapping code in order to have any usable amount of program space. There is a Funge-98 specification which allows for arbitrarily sized program spaces, but it also allows for 3-dimensional program spaces, so it's a bit overkill.

This code copies the instruction pointer twice, then modulos and then divides the instruction pointer by 79 to find the x and y values of the instruction pointer from the instruction pointer value. We add 1 to both x and y because of the offset we've mentioned earlier. If you've ever represented a 2d array in a single array, that is exactly what we're doing here.

Befunge uses postfix arithmetic, so 44*5*1- means 4 * 4 * 5 - 1. \ is the swap command, and swaps two values on the stack; in this case we're swapping to a fresh copy of the instruction pointer value to find the x coordinate of the current instruction after finding the y.

g02g68*-!v

Our stack currently consists of the data pointer, the instruction pointer, and the x and y values of the next instruction, in that order. we use g to grab the ascii value of the next instruction. We then immediately grab the value of the right-bracket tally - if we are in "bracket searching" mode we only process brackets, so we need to short circuit here.

g returns the ascii value of the character at the given location, so 0 actually returns 48. We could use empty spaces instead of overwriting the two pointer initialization values, but most Befunge interpreters interpret blank instructions as space, or 32. You might be able to find an interpreter that lets you input a NULL character, but I opted to just subtract 48 from each tally instead.

! is the not instruction and is used here just to flip the direction of the branching conditional, explained below

v !-*86g10_99*9+1+-:v

This line is best read in two parts: everything before and everything after the underscore. Underscore (and pipe) in Befunge are branching conditionals; if the current value on the stack is 0 the instruction pointer moves right, if not it moves left. If the instruction pointer moves right it means we've seen a right bracket. We check if the instruction we just accessed is a left bracket (91 -> 9 * 9 + 9 + 1) by subtracting its value, and feeding into another conditional. We duplicate the subtracted value just before we compare, for reasons we will discuss below.

If we move left, it means we haven't seen any right brackets. We immediately check if we've seen any left brackets then, using the same logic as before. Because we're now moving right-to-left, the instructions to do so are reversed.

v_99*9+3+-:v

Continuing where we left off, if we move left from the underscore it means we haven't seen any left brackets either; we immediately exit the bracket-matching code.

If we move right it means we've seen a left bracket, so we check if the current instruction is a right bracket (93).

<+1 p10+g10!+2_$01g1-01p>

Finishing where we left off, if we move right it means we've seen a left bracket and the current instruction is a right bracket. We discard the duplicate subtracted value, and subtract one from the left bracket counter, then exit the instruction loop. We have effectively exited this bf loop!

If we move left, it means we've seen a left bracket but this current instruction is not a right bracket. We need to keep track of all the left brackets vs right brackets we see however, so we quickly add 2 t