Know Your Language: Brainfucked by Brainfuck

I'm not so sure Brainfuck is an actual brainfuck so much as it is exhausting. Nor was it meant to be a brainfuck, for that matter. By most accounts, the esoteric programming language's founder, Urban Müller, was interested in creating a Turing-complete language that had the smallest possible compiler, which is the in-between program that coverts high level languages like C to a given computer architecture's machine-representational assembly instructions. Müller wanted tiny, the complete minimum that a language could be and still be a "real" language.

The Brainfuck compiler is down to about 171 bytes now, which is about half the capacity of all of the processor registers in a canonical x86 architecture combined. That is, you could imagine running it without using any memory outside of the actual processor cores. That is truly an accomplishment, of sorts.

While Brainfuck is knotty as hell, there's a satisfying element. For one thing, any other programming language that I can think of takes assembly code and adds more structural and syntactical complexity while also adding new layers of abstraction. Which is the point of high-level languages. Things become simpler as code gets more specific and more abstract, but there's also a lot of extra stuff that comes with high-level languages and their myriad extensions and outgrowths. Below the surface, things become muddier, more opaque.

Brainfuck, meanwhile, takes assembly instructions and reduces them to the barest whisps of code, which more or less approximates a Turing machine. It's an abstraction, but hardly one that makes programming any simpler or more intuitive or, well, reasonable.

Surprisingly, coding in a highly unreasonable language is refreshing or perhaps even … soothing, especially if you happen to already be a fan of sparse and immediate programming (e.g. C or assembly itself). Brainfuck is that, though sparse and immediate hardly means easy.

Brainfuck consists of six commands. Assembly (or ASM) has at least a hundred different instructions, some that are completely primitive like "add" and some that are kind of just slight refinements of other instructions or instructions that could be represented in more primitive terms by combining other, more primitive instructions (like "jump if less than or equal" and "jump if less than"). The basic ASM pallete, however—things you'd most likely to be using again and again—is more like a couple dozen. Which is still a lot more than Brainfuck. Nor can I think of any other language that's nearly so limited; languages, the ones used to actually do things, usually expand.

Brainfuck does not expand. There are different versions of it implemented in different ways and corresponding to different compilers, but making Brainfuck larger and more functional is to miss the entire point of Brainfuck (though people certainly try).

The six commands are as follows. I'll explain what they mean afterward.

>: Increment the pointer.

<: Decrement the pointer.

+: Increment the byte at the pointer.

-: Decrement the byte at the pointer.

.: Output the byte at the pointer.

,: Input a byte and store it in the byte at the pointer.

[: Jump forward past the matching ] if the byte at the pointer is zero.

]: Jump backward to the matching [ unless the byte at the pointer is zero.

If you don't know what a pointer is, that's surely just a bunch of nonsense. It's worth a quick lesson.

A pointer in computer science/programming is basically a memory address. When I declare a variable within a given general-purpose programming language, I'm planting a flag for that variable in a specific memory location (or more likely a virtualized specific memory location). When I reference that variable in my code, I can refer to the contents of the memory location or I can refer to a pointer to that memory location.

Say I declared the following in the C programming language:

int i = 0

There's now a slot in memory corresponding to my variable. If I later take my i and add 1 to it, the value of i will be 1 (0+1). I can also reference the variable i by appending an ampersand symbol to it like this: &i. This will give me the physical memory address of that variable instead of the variable's contents. You can also take the memory address of a variable and add or subtract from it as you would any other value to give you a new memory address based on your variable's location in memory. This is a really good way to screw things up, actually.

So, the basic idea is that a pointer is a location within a huge list of memory addresses. OK?

Let's get back to Brainfucking.

Using Müller's original C implementation of Brainfuck—note: languages are only implemented in other languages, save for ASM itself—a Brainfuck program will be initially allocated 5,000 slots of memory. The "real" machine addresses of these slots are maintained by the C code as nornmal C pointers, but in Brainfuck we just imagine them to be indexed slots within a big array (a list, basically). So, at the start of a Brainfuck program, we imagine cell #0. (In programming, lists start at 0, not 1.) We have basically just one or two choices of how to proceed in writing our Brainfuck program. We can increment by one the value held within cell #0 (which is initialized to be 0) using the "+" command, or we can ignore cell #0 (which will then remain with a value of 0) and move on to the next memory address using the ">" command.

Say that I wanted to make cell #0 hold the ASCII character "H," as if we were planning to output "Hello, world." I need the numerical value within cell #0 to be 72, which is the ASCII code for the letter H. The most straightforward way of accomplishing this is to just type out "+" 72 times, incrementing the value of cell #0 72 times.

To get the next letter, we code a ">," which brings us to cell #1. Increment cell #1 101 times, for 101, the ASCII code for a lowercase "e." All we're ever doing is stepping forward and backward in memory while incrementing and decrementing the values we find by 1 and only 1 (per individual operation).

Brainfuck has two input/output commands. "." will print whatever value is at the current memory location, while "," will accept a single byte of input and place it in the current memory address. So, coding a period after having set cell #0 to 72, should output "H." In this respect, at least, Brainfuck starts to look a bit more normal.

There's one more thing. Brainfuck has a control structure. In programming, a control structure might be any number of different things that somehow affect the flow of program execution through a section of code. Examples include if … then statements (if this condition is met, execute this section of code, otherwise ignore it), for loops (execute this section of code some number of times), and while loops (execute this section of code until a given statement becomes untrue).

Brainfuck's control structure consists of a pair of "[]" brackets. When the code encounters the first opening bracket, it will test to see if the byte at the current memory location is equal to 0. If it is, the code will jump to the command after the closing bracket. Otherwise, the code will continue as normal. This would normally be used like a for or while loop where some memory location is initialized to a value and every time the loop executes that value is decreased by 1. When it hits 0, the loop stops looping and the code continues on.

Borrowed from this Brainfuck visualizer, here's the complete "Hello, World" code. You can see that it uses cell #0 as the counter, which is initialized to 10, so the loop (the stuff between the brackets) executes 10 times.

+++++ +++++ initialize counter (cell #0) to 10 [ use loop to set 70/100/30/10 > +++++ ++ add 7 to cell #1 > +++++ +++++ add 10 to cell #2 > +++ add 3 to cell #3 > + add 1 to cell #4 <<<< - decrement counter (cell #0) ] > ++ . print 'H' > + . print 'e' +++++ ++ . print 'l' . print 'l' +++ . print 'o' > ++ . print ' ' << +++++ +++++ +++++ . print 'W' > . print 'o' +++ . print 'r' ----- - . print 'l' ----- --- . print 'd' > + . print '!' > . print ' '

Now we get to ask So what? Fair enough, but there is actually a point. Brainfuck is amazingly tiny but it's also Turing-complete. This means that it's possible to write a Brainfuck program with the same capabilities of any other computer program written in any other programming language. The syntax and control structures of Brainfuck may be limited, but the language's abilities are as unlimited as any other programming language that exists or that will exist, which is sort of another way of saying that it can doing all of the stuff a Turing machine can do, which is itself a way of saying that it can do anything, or that it can find an answer to any computational problem given enough time and memory.

So, Brainfuck could be the only programming language that exists and we could have all of the technology we have now.

Weird, eh.

This has been proven several times, in fact. Daniel B Cristofani proved it directly by simulating a Turing-complete class know as a tag-system, which is used formally as a simulcrum of the Turing machine itself. Other proofs rely on showing reductions between Brainfuck and another esoteric language called P" that functions as a direct Turing machine simulator and has been shown to be Turing complete by proof. (A reduction is a way of showing that a certain language or problem represented as a formal language [don't ask] can be shown to be a subset of another language or problem represented as a formal language.) Frans Faase has similarly shown that Brainfuck can be rearranged such that it itself becomes a direct representation of a Turing-machine.

If you're into suffering, here's an online Brainfuck visualizer (same as above). It's worth screwing around with a bit.

Beyond that, you'll find that Brainfuck is parent to a vast family of derivative languages, some adding features like procedures/functions, multithreading, strings and repetition, Arduino capabilities, math functions, and built-in debugging capabilities. At least one Brainfuck extension, known as Smallfuck, actually removes capabilities, offering operations only on individual bits and limited data storage (which makes it Turing-incomplete). Meanwhile, A cursory Google search reveals a vast pit of different Brainfuck implementations (beyond the original C version mentioned above) and compilers. You're on your own for that.

Read more Know Your Language.