quinesnake: a quine that plays snake over its own source!

Conor Taylor — 2nd May 2019

A quine is a program that takes no input and prints its own source as its only output. “Stepping outside itself”, e.g. by printing the contents of its own file, isn’t allowed; so you can't just write a program which reads its own source file and prints it to stdout. Quines are generally interesting to look at because if you haven't written one before, it will likely seem extremely difficult or impossible to write.

Source as data

The standard trick used to write a quine is to represent a copy of the program’s own source as data within the program, usually in a string. It can then be formatted into itself and printed. This two-line Python quine is a neat example of xthis:

s = 's = %r\nprint(s%%s)'
print(s%s)

Quinesnake uses this string formatting to allow it to print its own source, but makes things more interesting by playing the classic game snake over the source (with wasd controls) after it’s printed! It’s still a quine, it just runs a game loop to accept keyboard control input, and highlights parts of the text as it continuously prints it to render the snake and the food, using the curses library:

Starting out

Finding a good place to start writing a program like this is quite tricky; do you start with the quine or the game? In my case, since I didn't know quite what the completed code would look like when I started, I decided to start by representing the game board as an array of # characters:

std::wstring s = L"####################"
                 "####################"
                 "####################"
                 "####################"
                 "####################"
                 "####################"
                 "####################"
                 "####################"
                 "####################"
                 "####################";

The reason why std::wstring is used here instead of std::string is explained later.

The commented version of quinesnake uses a board like this to play snake over. Once the game was functional I replaced the # characters with the source of the program (the source as data). The logic of the snake game itself is quite trivial and is available in a readable format in quinesnake-commented.cpp.

Minifying the code

The game playing code needs to be as small as possible since it'll be represented twice in the source. There are a number of techniques used to make quinesnake as small as possible. Perhaps the most interesting one is that it compiles itself. Making the source file executable and executing it invokes g++ on itself with a number of flags, includes and defines. This works because the first line of the program, /*bin/ls>/dev/null..., is interpreted as a shell command, despite also being a valid C++ comment. The sed magic, borrowed mostly verbatim from stedolan’s minhttp project, parses the C++ comments (which contain the shell commands to compile the program) out of the source file and executes them as a single shell command. Without this it’s really tricky to minify the program, because include and define statements must be on their own line.

To keep track of the state of the game, and to make the source as confusing to read as possible (which is also important!), quinesnake stores the game state in the spare bits of the source-as-data string used by the quine. The type of this string is std::wstring, a string class for storing wide (>=16 bit, or wchar_t) characters. Since quinesnake only uses it to store 8-bit ASCII characters, that leaves the rest spare to store the state of the character in the output (empty, snake, or food. 2 bits needed), and the direction of the snake pixel that proceeds this one (up, down, left or right. Also 2 bits needed), if it’s part of the snake. Every other wchar_t in the string contains these 4 bits of game state in the higher order bits above the regular character, so they’re removed by casting the wchar_t down to char when printing.

So the byte format of every other wchar_t in the std::wstring is as follows:

+--------------------------------+--------+--------+----------------+
|             8 bits             | 2 bits | 2 bits |    4-36 bits   |
+--------------------------------+--------+--------+----------------+
 ^                                ^        ^          ^
 8-bit ASCII chracter             state    direction  unused

I say every other wchar_t because there is no reason to do this for every wchar_t. The snake is rendered two characters wide (so that it appears the same width whether it's vertically or horizontally oriented). So annotating each position would be redundant.

Finally, string formatting in these programs can be a huge pain when special characters need to be escaped (e.g. quotes or newlines) so that they appear as special characters in the source, but escaped characters in the source-as-data string. To not have to worry about this, quinesnake uses a raw wide string for the data, which does no special character escaping. The little substitution that’s required is done manually instead, by manually finding the %d substitution token in the raw string to replace it with the string itself, using string::replace (although this is only done in quinesnake.cpp, not in the commented version).

You can see the full source on the quinesnake github repo!