new_one's home     About     Feed Stuffs and things

Quine

Quine? Quoi?

A quine is a computer program that, when run, prints out its own source code. Programs such as print(open(__file__).read()) that read their own source from disk violate the spirit of the problem; rather, the program must somehow compute it when it is run. One cool fact about quines stems from Kleene’s recursion theorem. I’ll use Wikipedia’s explanation here:

Quines are possible in any Turing complete programming language, as a direct consequence of Kleene’s recursion theorem. For amusement, programmers sometimes attempt to develop the shortest possible quine in any given programming language.

“For Amusement”

And who doesn’t like amusement? Let’s make a quine in Rust, the new programming language being developed by Mozilla and the community. If you’ve never done a quine before, you may think the task is trivial since the problem is so simple. However, once you start writing it, you may quickly stumble into the problem of self-recursion. For example (with Python), you may start with print("print(print(...))") and realize that your source code will always have one more print than you are actually printing.

One way around this block is to split the problem into two parts: turn your program into a “data” section and a “code” section, such that the code will at runtime transform the data into a textual representation of itself. That probably sounds a little obtuse, so let’s begin with a simple example:

# representation of some code, where each element is the ascii value of each character
data = [100,97,116,97]
# code that prints the data, then the code
print("data = [{}]".format(','.join(data)))
# -> data = [100,97,116,97]
print(''.join(map(chr, data)))
# -> data

Now, we can extend this idea to a full program, this time in Rust. See the code at main.rs, or run it for yourself on the playpen. The idea is similar to that illustrated in the example above, where an array of numbers represents the code. This code first prints out the data, then it prints out the code itself by using the data. I take advantage of the built-in slice Show implementation to save some manual string building. The data is an array of offsets of the ASCII value of each character with the preceding, with an initial value of 0. We simply add the values to an accumulator and print as we go, with the following code:

let mut c = 0;
for x in p.iter() {
    c += *x;
    print!("{}", (c as u8) as char);
}

Bonus: the “error code” quine

Another way to make a quine is to take advantage of the compiler’s error printing. The idea is that you write a program which generates a particular error that matches itself. Depending on the kind of error being generated by the compiler, you can apply an interative process to make this program:

  1. Make a program that does not compile.
  2. Make the compiler’s error output the contents of the program.
  3. Repeat 2 until the contents and the error match.

Applying this process in the playpen, here’s the result:

<anon>:1:50: 1:51 error: unknown start of token: `
<anon>:1 <anon>:1:50: 1:51 error: unknown start of token: `
                                                          ^
playpen: application terminated with error code 101

Running this code will produce itself as a compiler error message.

Further reading