quines, and brainfuck

written 2023-04-27

introduction

a quine is a program which without taking any input, outputs it's own source code — a fixed point of the programming language in question. quines are unwieldy beings because they mix what is often considered two distinct levels of abstractions: source code, and the programs the code represent.

brainfuck is a minimalistic programming language consisting of only 8 simple commands in the source and a pointer into a big array of integers as the only runtime storage medium. the language was designed to be implementable with as small of a compiler as possible, sacrificing usability for implementation simplicity.

in this blog, we'll explore how to combine these two, writing a quine in brainfuck. is there any practical use for this, or any important lesson to take away from the exercise? i'm not sure, but i'm leaning towards a "definitely not".

quines, and not brainfuck

before we develop a quine in the brainfuck language, we'll start with something a bit more managable — a quine in the Python programming language. we'll be putting a lot of valid code inside string literals, which can make it slightly difficult to identify what parts of the code are expressions and what are strings. use the code highlighting to your advantage!

starting off, we know we'll be needing to print something. let's start off with a print statement:

print("...")

what to print? we must make sure the print itself is included:

print("print(\"...\")")

and then:

print("print(\"print(\\"...\\")\")")

and at this point we might as well conclude this quine will need to be infinitely long.

giving up on printing the source directly, we can instead try assigning the source code to a variable, and then printing the variable

source = "print(source)"
print(source)

however this doesn't print the variable assignment itself on the first row. if we add the variable assignment to the print statement and adjust the variable accordingly, we get

source = "print(\"source = \" + source + \"\\n\" + source)"
print("source = " + source + "\n" + source)

which is very close, but the first time source is printed, the quote escapes are included. while some languages do include functions for "unescaping" strings (such as the repr() function in Python), we can instead try storing the variable in a way which is easier to print a representation of. let's pick a format where the source is stored as a list of codepoints:

source = [112, 114, 105, 110, 116, 40, 34, 115, 111, 117, 114, 99, 101, 32, 61, 32, 91, 34, 32, 43, 32, 34, 44, 32, 34, 46, 106, 111, 105, 110, 40, 115, 116, 114, 40, 120, 41, 32, 102, 111, 114, 32, 120, 32, 105, 110, 32, 115, 111, 117, 114, 99, 101, 41, 32, 43, 32, 34, 93, 10, 34, 32, 43, 32, 34, 34, 46, 106, 111, 105, 110, 40, 99, 104, 114, 40, 120, 41, 32, 102, 111, 114, 32, 120, 32, 105, 110, 32, 115, 111, 117, 114, 99, 101, 41, 41]
print("source = [" + ", ".join(str(x) for x in source) + "]\n" + "".join(chr(x) for x in source))

here, the number is each code point in the following line. the expression ", ".join(str(x) for x in source) evaluates to a comma-separated string of all the numbers in source (resulting in the list on the first line), while the expression "".join(chr(x) for x in source) results in the string produced by concatenating all the code points in the list (resulting in the second line). together, these two expressions combined results in a proper quine!

in the program above, we can identify three parts which are common to a lot of quines. the program consists of three parts:

1. representing the source of part 2 and 3 in some storage (in our case, assigning the source to a list of codepoints)
2. printing the assignment in part 1 by using the stored variable
3. printing the code represented by part 1 using the same variable

introduction to brainfuck

as mentioned in the introduction, brainfuck is quite an unusual programming language unless you've worked with esolangs before. in brainfuck, the only form of storage is an array of bytes, often referred to as the 'tape', which stretches out as far as the runtime of the language allows. accessing the tape is done through a pointer often referred to as the 'pointer'. if you've read about turing machines before, you might see some similarities here (note however, that brainfuck does not have the concept of states from turing machines).

the eight commands in brainfuck are as follows:

• +: increase the value which the 'pointer' points to by one
• -: decrease the value which the 'pointer' points to by one
• >: move the pointer one step to the right
• <: move the pointer one step to the left
• .: print the value to which the 'pointer' points as an ASCII codepoint
• ,: read an ASCII codepoint from the user, storing it in the pointed to value
• [: if the value pointed to is zero, jump forward to the matching ]
• ]: if the value pointed to is nonzero, jump backward to the matching [

writing a quine in brainfuck

applying the three-part technique described earlier, we first need to choose a way to represent brainfuck source code. the absolute simplest way to store the source code would be to store each command as a code point in memory. however, as we need to loop over the text, and the loop iterations are probably going to need some temporary memory, we put a zero cell between each adjacent character in memory to be used as auxilliary storage.

for example, the code ,[-] would be represented in memory as

44 0 91 0 45 0 93 0 0 0 0 0 ...
^

which would be generated by the program

++++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++++>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<<<<<<

the second part has the job of printing this program. to do this, we'll loop through all the characters until a we find a zero marking the end of the data, print the respective number of +'s, print two >'s, go to the next character and repeat. at the end, we'll need to go back through the code and print two >'s for each character on the way back.

to do the first part:

[ # loop through the chars until we reach a zero
  # we have three cells, A, B and C
  # cell A and C are auxilliary zero-cells, and cell B contains the current char
  > # go to cell C (temporary value to the right of the current char)
  +++++++++++++++++++++++++++++++++++++++++++ # set it to 43 (the ascii code for plus)
  < # go to cell B (the current char)
  [ - # loop until B is zero
    < + # increase A (the temporary cell to the left)
    >> . # to go C and print it (the ascii plus)
    < # go back to B
  ]
  # now B is zero, A conatins the value of the current char, and C is still an ascii plus
  < # go to A
  [ - # loop until it's zero
    > + # increase B
    < # go back to A
  ]
  # now B contains the current char again, and A is zero
  >> # go to C
  +++++++++++++++++++ # increase it by 19 (it now contains 43+19=62, the ascii value for >
  .. # print it twice
  [-] # set it to zero
  > # go to the next char to be printed
]
<< # go back to the last non-zero char

stripping the comments and whitespace,

[>+++++++++++++++++++++++++++++++++++++++++++<[-<+>>.<]<[->+<]>>+++++++++++++++++++..[-]>]<<

we then want to go back to the start, printing a << for each char

[ # loop until zero
  # we again have A, B and C
  < ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ # set A to 60, ascii value for <
  .. # print it twice
  [-] # set it back to zero
  < # go to the previous char
]
>> # go to the first non-zero char

again, stripping:

[<++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++..[-]<]>>

for the third part, we want to print out the code being represented itself. this is quite a bit lot simpler,

[ # loop until zero
  . # print the current char
  >> # go to the next char
]

stripped being

[.>>]

part 2 and 3 together form the source which part 1 will encode. combined, they are (with added newlines between the parts)

[>+++++++++++++++++++++++++++++++++++++++++++<[-<+>>.<]<[->+<]>>+++++++++++++++++++..[-]>]<<[<++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++..[-]<]>>[.>>]

i don't want to encode all of this into brainfuck by hand, so let's use a short python script to generate the program:

source = "[>+++++++++++++++++++++++++++++++++++++++++++<[-<+>>.<]<[->+<" \
         "]>>+++++++++++++++++++..[-]>]<<[<++++++++++++++++++++++++++++" \
         "++++++++++++++++++++++++++++++++..[-]<]>>[.>>]"
print("".join("+" * ord(c) + ">>" for c in source) + "<<" * len(source) + source)

resulting in the final quine

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++++>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>++++++++++++++++++++++++++++++++++++++++++++++>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++++>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>++++++++++++++++++++++++++++++++++++++++++++++>>++++++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>>++++++++++++++++++++++++++++++++++++++++++++++>>++++++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>++++++++++++++++++++++++++++++++++++++++++++++>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>><<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<[>+++++++++++++++++++++++++++++++++++++++++++<[-<+>>.<]<[->+<]>>+++++++++++++++++++..[-]>]<<[<++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++..[-]<]>>[.>>]

isn't it beautiful :3