Writing a Brainfuck Quine
I was drinking with some coworkers and mentioned I’d never written a brainfuck quine. So, of course, as soon as we got back to computers, they start timing me.
It took me just over 30 minutes to produce this incredibly-verbose quine. I figured I’d do a quick writeup of how it works.
If you’re not familiar with Brainfuck, you can get a quick refresher here. It’s incredibly simple, so I won’t go into detail here.
Most simple quines can be divided into two parts, which I’ll refer to as the code and the data (obviously they’re all code in the sense that they appear as part of the source, but they’re conceptually very different).
The data is just a representation of the source code for the “code”, in some machine-readable way. The job of the code is then to print out the data twice: The first time, in the same form the data was formatted in the input, and the second time, to use the data to print out the source code of the code itself. We can see this structure in the classic English “quine”:
Print the following sentence, followed by its quotation: “Print the following sentence, followed by its quotation.”
The second sentence, the quoted one, is the “data” – it is not interpreted by the person following the instructions, just copied around. The first sentence is the “code,” and contains the key two parts: “print the following sentence” prints the code, and “followed by its quotation” prints a representation of the data.
So, in order to write a brainfuck quine, we’re going to represent brainfuck code as data generated by other brainfuck code, in such a way that:
We can use that data to print out the brainfuck code that generated the data.
We can use that data to print out the brainfuck code described by that data.
I’ve posted an annotated version of the source code, to help following along as we walk through the code.
The easiest (if awfully verbose) representation is trivial: We’ll represent a character of brainfuck as a cell containing its ASCII value, and we’ll generate that cell by N +s in a row.
In order to leave room for scratch computation, I decided to represent each value by N followed by three empty (0) cells. This turned out to be more than I needed, but was convenient.
So, in order to represent, say, a + in the code, we’ll emit this:
+++++++++++++++++++++++++++++++++++++++++++>>>>
We’ll also start with an extra >>>> to make it easier to find the start of the tape again.
Now we need to write the actual “code” which is the meat of the program. First it needs to walk over the data, and emit the same code that we wrote to generate the data.
Before we can do anything, skip back to the start of the tape:
(The final >>>> will have skipped us off the end, so we back up once to find the last character, then repeat until we find the sentinel zeros we left at the start).
We need to emit the leading >>>>:
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++....[-]
We generate the > character directly using +, emit it four times, and then clear the cell with [-] for good hygiene.
Now we enter a loop, printing out the ++++⋅⋅⋅>>> sequence for each byte. For each cell, we generate a spare + (in order to print), and then loop, printing that + an appropriate number of times. Because looping involves counting down, we also have to copy the initial byte to one of the scratch cells. I copied it to two of them for good measure, which ended up being unnecessary:
Generate a plus in the next cell over: >+++++++++++++++++++++++++++++++++++++++++++< Write out N pluses and copy the initial N twice: [>.>+>+<<<-]> Turn the plus into a greater-than and print four of those: +++++++++++++++++++.... Now move to the next byte: >>>
The end result of this is that we start with a tape that looks like
print out N +’s and four >s, and leave the tape as:
with the head on the next value of N. We wrap this in a loop, and we’ve now output the data, as it originally appeared.
We now reset back to the start of the tape again:
And walk over it once more, this time directly printing out the value at each cell:
Now that we’ve written the code, we need to encode it in the appropriate format. This is pretty quick in a Python repl:
>>> import re >>> s = open('in.bf').read() >>> t = re.sub(r'[^]+><.[-]', '', s) >>> print '>>>>'.join(['+' * ord(c) for c in t])
We can now concatenate these files, and run the result. It doesn’t quite match the input, because the input contained additional whitespace (we wanted it to be at least vaguely human-readable!), but if we pass the output through a brainfuck interpreter again, we observe that it is unchanged:
[nelhage@anarchique:~/nelhage/bf]$ gobf test.bf > out.bf [nelhage@anarchique:~/nelhage/bf]$ cmp test.bf out.bf ; echo $? test.bf out.bf differ: byte 5, line 1 1 [nelhage@anarchique:~/nelhage/bf]$ gobf out.bf > out1.bf [nelhage@anarchique:~/nelhage/bf]$ cmp out1.bf out.bf ; echo $? 0
