I'm currently away on a family vacation, and as soon as vacation is over, I'm off on a business trip for a week. And along the way, I've got some deadlines for my book. So to fill in, I'm recycling some old posts. I decided that it's been entirely too long since there was any pathological programming 'round these parts, so I'm going to repost some of my favorites.
As long-time readers know by now, in real life, I'm not a
mathematician; I'm a computer scientist. I'm still a math geek, mind
you, but what I really do is very much in the realm of applied math,
working on building systems to help people build programs.
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 150
different languages; and I've picked up more since then. I've written programs
most of them. Like I said, I'm nuts.
These pathological programming language posts are my way of inflicting
my obsession on you in a (hopefully) amusing way. You see, in this
screwed up world of ours, there are lots and lots of thoroughly crazy
people out there. In the world of geekery, many of those crazy people
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 ones whose work I'm writing about. The
ones who deliberately set out to design strange, warped, twisted, and
nearly unusable languages, and succeed brilliantly. Most of the people who
design them 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,
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 it's Turing complete. In fact, it's one-up on just being Turing complete - it's
actually been formally specified with a complete formal theoretical design,
called P''.
And it's even been implemented in hardware!.
BrainFuck is based on something very much like a twisted cross between a
href="http://scienceblogs.com/goodmath/2007/02/basics_the_turing_machine_with_1.php">Turing
machine and a
href="http://goodmath.blogspot.com/2006/05/minsky-machine.html">Minsky
machine: it's got a tape, like a turing machine. But
unlike the turing machine, each cell of the tape can store an arbitrary
number, which can be incremented or decremented --- like a Minsky machine's
registers. Also like a Minsky machine, it's got a notion of control
flow based on zero-tests.
The 8 brainfuck instructions are:
-
>: move the tape head one cell forward. -
<: move the tape head one cell backward. -
+: increment the value on the current tape cell. -
-: decrement the value on the current tape cell. -
.: output the value on the current tape cell as a character. -
,: input a character and write it's numeric value onto the current
tape cell. -
[: compare and jump forward: compare the current
tape cell to 0. If it's zero, jump forward to the first instruction after the
matching "]"; otherwise, go on to the next instruction. -
]: compare and jump backward: if the current tape cell is
not zero, then jump backward to the matching "[". - Any character which is not one of those eight instruction characters
is a no-op - that is, it does nothing - execution will skip forward to the next command character.
This means that you don't need any special syntax to write comments in brainfuck -
you just intersperse them with the program instructions. (But you need to do it
carefully; if you use punctuation, you'll probably accidentally create instructions
which break your program. So Brainfuck makes it impossible to write
grammatical comments!)
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".
After that, it continues in pretty much the same vein, using a couple of
tape cells, and running loops to generate the values of the characters.
It's quite beautiful in its way. But at the same time, that's an astonishingly complicated
way of just printing out "Hello world"! Remarkably, isn't it?
If that didn't seem impressive enough,
href="http://esoteric.sange.fi/brainfuck/bf-source/prog/fibonacci.txt"here
is a really gorgeous implementation of a fibonacci sequence generator, complete 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
[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-
]
- Log in to post comments
Ah, Brainfuck is great. I used it to solve a Project Euler problem: http://git.veekun.com/?p=project-euler.git;a=blob;f=heteroglot/005.bf;h…
Ah yes, I quickly upgraded my TRS-80 Model I Level 1 to Level 2 BASIC. Then it was the fact that I understood the memory map of the machine and so started poking things into memory.
I'd do page swaps, etc. using that method. Clunky but it worked. In essence it gave the TRS-80 multi-threading.
Friend of mine modified a TRS-80 Model III so it could have more than two RS-232 ports. He also modified TRS-DOS to have advanced comm routines and ISAM files.
I had it running on my Model I but the disk drives on that were flaky. Always had to have an o-scope around to re-align the things.
But I knew that Model I well. For example when the characters on the screen had a dropout I knew exactly which memory chip went bad, and went to RS, got the chip and replaced it myself.
Brainfuck will always have a special place in my heart. Unlike so many other esoteric languages, Brainfuck is not intentionally awful to program in. In fact, the purity of its command set is quite aesthetically compelling. The hideousness implied by its name only manifests itself when you try to do anything of any significance in the language (leaving you with the tiny suspicion that the fault is as much with you and your own limitations than with the language).
Nit pick: it is perfectly possible to write grammatical, punctuated comments in Brainfuck â in fact, with entirely arbitrary text, as long as you balance any []s in it. The only restriction is that it must go somewhere where the current cell is guaranteed to be zero, such as after a ], and be enclosed in []s, so itâs skipped.
I wrote an interpreter for brainf* in Python, which was too easy, but I'm not a real programmer, just an amateur, so I can't really program using it.
This looks so much like an entry for the IOCCC. Make the C program an interpreter and have the main program expressed in Brainfuck as a string. Maybe even change a few symbols. heh.
But can you write a bf interpreter in bf?
To the best of my knowledge a Brainfuck interpreter has won the IOCCC only once, although apparently Brainfuck-based entries show up pretty frequently.
And yes, you can write a Brainfuck interpreter in Brainfuck without difficulty. After all, Brainfuck's reason for being was to be easy to implement. Urban Müller's original purpose for inventing the language was to be able to create a compiler for a Turing-complete language in under 256 bytes. That's the size of the binary, not the source code. (That was for the Amiga. My Brainfuck compiler for Linux is 170 bytes.)
@Paul Murray: of course you can. :) In fact, one of my colleagues did: http://code.google.com/p/awib/.
In this year's google code jam qualification round (which is usually a day long), there was guy,bozzball, who did a dynamic programming problem in brainfuck.
He seems to have used bf2c convertor to convert the bf program to c and then use that for generating o/p for the given i/p.