In real life, I’m not a mathematician; I’m a computer scientist. Still a math geek, mind you, but what I really do is very much in the realm of applied math, researching how to build systems to help people program.
One of my pathological obsessions is programming languages. Since I first got exposed to TRS-80 Model 1 BASIC back in middle school, I’ve been absolutely nuts programming languages. Last time I counted, I’d learned about 130 different languages; and I’ve picked up more since then. I’ve written programs most of them. Like I said, I’m nuts.
Anyway, I decided that it would be amusing to inflict my obsession on you, my readers, with a new feature: the friday pathological programming language. You see, there are plenty of *crazy* people out there; and many of them like to invent programming languages. Some very small number of them try to design good languages and succeed; a much larger number try to design good languages and fail; and *then* there are the folks who design the languages I’m going to talk about. They’re the ones who set out to design *bizzare* programming languages, and succeed brilliantly. They call them “esoteric” programming languages. I call them evil.
Today, the beautiful grand-daddy of the esoteric language family: the one, the only, the truly and deservedly infamous: [Brainfuck!][bf], designed by Urban Müller. (There are a number of different implementations available; just follow the link.)
Only 8 commands – including input and output – all written using symbols. And yet Turing complete; and not just Turing complete, but actually based on a *real* [formal theoretical design][pprimeprime]. And it’s even been implemented [*in hardware*!][bf-hard]
BrainFuck is based on something very much like a twisted cross between a [Turing machine][turing] and a [Minsky machine][minsky]. It’s got the idea of an input tape, like the turing machine. But unlike the turing machine, each cell of the tape stores a number, which can be incremented or decremented, like a Minsky machine. And like a Minsky, the only control flow is a test for zero.
The 8 instructions:
1. **>**: move the tape head one cell forward.
2. **<**: move the tape head one cell backward. 3. **+**: increment the value on the current tape cell. 4. **-**: decrement the value on the current tape cell. 5. **.**: output the value on the current tape cell as a character. 6. **,**: input a character and write it's numeric value onto the current tape cell. 7. **[**: Jump forward to the first instruction after the matching "]" *if* the value on the current tape cell is 0. 8. **]**: jump backward to the matching "[" *unless* the value on the current tape cell is 0. Here's a hello-world program in BF: ++++++++[>+++++++++<-]>.<+++++[>++++++<-]>-.+++++++..+++.< ++++++++[>>++++<<-]>>.<<++++[>——<-]>.<++++[>++++++<-]>
Let’s pull that apart just a bit so that we can hope to understand.
* “++++++++”: store the number “8” in the current tape cell. We’re going to use that as a loop index, so the loop is going to repeat 8 times.
* “[>+++++++++<-]": Run a loop: using the tape cell *after* the loop index, add "9" to it. Then go back to the loop index, decrement it, and branch back to the beginning of the loop if it's not zero. So we wind up with the number 72 in the second cell. That's the ascii code for "H". * ">.”: go to the cell after the loop index, and output what’s there. That outputs the “72” as a character: “H”.
* “<+++++": back to the loop index. This time store 5 in it. * "[>++++++<-]": same idea as the loop to generate the "H": this time, we're going to add 5 * 6 to the value in the second cell. (Remember that we didn't get rid of the value in that cell - so it's *still* 72.) So now the second cell contains 102. * ">-.”: Advance past the index, subtract one, and output. That’s 101, or “e”.
Continues in pretty much the same vein, using a couple of tape cells, and running loops to generate the values of the characters. Beautiful, eh?
If that didn’t seem impressive enough, [here][bf-fib] is a really gorgeous implementation of a fibonacci sequence generator, with documentation. The BF compiler used to write this ignores any character other than the 8 commands, so the comments don’t need to be marked in any way; they just need to be really careful not to use punctuation.
+++++++++++ number of digits to output > #1 + initial number >>>> #5 ++++++++++++++++++++++++++++++++++++++++++++ (comma) > #6 ++++++++++++++++++++++++++++++++ (space) <<<<<< #0 [ > #1 copy #1 to #7 [>>>>>>+>+<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-] < divide #7 by 10 (begins in #7) [ > ++++++++++ set the divisor #8 [ subtract from the dividend and divisor -<- if dividend reaches zero break out copy dividend to #9 [>>+>+<<<-]>>>[<<<+>>>-] set #10 + if #9 clear #10 <[>[-]<[-]] if #10 move remaining divisor to #11 >[<<[>>>+<<<-]>>[-]] jump back to #8 (divisor possition) << ] if #11 is empty (no remainder) increment the quotient #12 >>> #11 copy to #13 [>>+>+<<<-]>>>[<<<+>>>-] set #14 + if #13 clear #14 <[>[-]<[-]] if #14 increment quotient >[<<+>>[-]] <<<<<<< #7 ] quotient is in #12 and remainder is in #11 >>>>> #12 if #12 output value plus offset to ascii 0 [++++++++++++++++++++++++++++++++++++++++++++++++.[-]] subtract #11 from 10 ++++++++++ #12 is now 10 < #11 [->-<] > #12 output #12 even if it's zero ++++++++++++++++++++++++++++++++++++++++++++++++.[-] <<<<<<<<<<< #1 check for final number copy #0 to #3 <[>>>+>+<<<<-]>>>>[<<<<+>>>>-] <- #3 if #3 output (comma) and (space) [>>.>.<<<[-]] << #1 [>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<- ]