{"id":802,"date":"2009-09-06T18:08:21","date_gmt":"2009-09-06T18:08:21","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2009\/09\/06\/the-one-the-only-brainfck\/"},"modified":"2020-02-24T09:12:05","modified_gmt":"2020-02-24T14:12:05","slug":"the-one-the-only-brainfck","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2009\/09\/06\/the-one-the-only-brainfck\/","title":{"rendered":"The One… The Only… Brainf*ck"},"content":{"rendered":"

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.<\/em><\/p>\n

As long-time readers know by now, in real life, I’m not<\/em> a mathematician; I’m a computer scientist. I’m still a math geek<\/em>, 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.<\/p>\n

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\u00a0 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.<\/p>\n

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 <\/em>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<\/em> 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.<\/p>\n

Today, the beautiful grand-daddy of the esoteric language family: the one, the only, the truly and deservedly infamous: Brainfuck<\/a>, designed by Urban M\u00fcller. (There are a number of different implementations available; just follow the link.)<\/p>\n

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”<\/a>. And it’s even been implemented in hardware!<\/a>.<\/p>\n

<\/p>\n

BrainFuck is based on something very much like a twisted cross between a
Turing machine<\/a> and a Minsky machine<\/a>: 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.<\/p>\n

The 8 brainfuck instructions are:<\/p>\n

    \n
  1. ><\/code>: move the tape head one cell forward.<\/li>\n
  2. <<\/code>: move the tape head one cell backward.<\/li>\n
  3. +<\/code>: increment the value on the current tape cell.<\/li>\n
  4. -<\/code>: decrement the value on the current tape cell.<\/li>\n
  5. .<\/code>: output the value on the current tape cell as a character.<\/li>\n
  6. ,<\/code>: input a character and write its numeric value onto the current tape cell.<\/li>\n
  7. [<\/code>: compare and jump forward: compare the current tape cell to 0. If it’s zero, jump forward to the first instruction after the matching “]<\/code>“; otherwise, go on to the next instruction.<\/li>\n
  8. ]<\/code>: compare and jump backward: if the current tape cell is not<\/em> zero, then jump backward to the matching “[“.<\/li>\n
  9. Any character which is not<\/em> 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<\/em> to write grammatical comments!)<\/li>\n<\/ol>\n

    Here’s a hello-world program in BF:<\/p>\n

    ++++++++[>+++++++++<-]>.<+++++[>++++++<-]>-.\n+++++++..+++.<++++++++[>>++++<<-]>>.\n<<++++[>------<-]>.<++++[>++++++<-]>.\n+++.------.--------.>+.\n<\/pre>\n
    Let’s pull that apart just a bit so that we can hope to understand.<\/p>\n