Quines

I was browsing reddit recently when I can across a link to a quine. Not just any ordinary quine, either – a polyglot quine. It works in three different languages: Haskell, OCaml, and Scheme.

For those who aren’t familiar with the term, a quine is a program that prints its own source code. There are a few fairly obvious caveats: it can’t read the code from the filesystem, it can’t take user input, empty programs don’t count. The term was coined by Douglas Hofstadter, who named it after logician Willard van Orman Quine. Interestingly, at the moment (and many moments before and after the current one – it’s a long book) I’m working my way through one of Hofstadter’s excellent books, Gödel, Escher, Bach, in which the word was coined and he goes into depth on the subject of quines. Unfortunately, I haven’t gotten to that point yet. When I do, I’ll be sure to mention it.

Quines are lots of fun to write, but more challenging than they may seem at first glance. I was inspired by this polyglot quine to write up a short one in Ruby. I started by trying the brute force method: creating a string containing the program.

s = "s =

Here I ran into a problem. I had added the program prior to the string back into the string, but if I had started adding the string itself, it would just have gotten longer and longer.

s = "s =\"s =\\\"s =\\\\\\\"s =

That was clearly not getting me anywhere, so I decided to just put off adding the string. For the time being, I just put a question mark where the string should have been and ended the string.

s = "s = ?"

If we assume that we’ll find some way to add in the string itself in place of that question mark, all we need to do is print the string. We’ll also have to modify what comes after the question mark so it matches the program.

s = "s = ?\nputs s" 
puts s

But what about that question mark? Well, it turns out that it’s actually very easy to deal with. We already have a variable that contains the string. All we have to do is substitute out the question mark for the string itself.

Note, however, that the string we want to substitute in isn’t exactly the same as what s contains. It has quotes around it; rather than a newline, it actually has backslash-n. Ruby has a string method, dump, which handily returns exactly what we need: a string that, if evaluated, would result in the original string. In a different language, I would probably have had to implement this myself, but that would have been, if not succinct, at least doable.

To substitute in the string, I used the gsub method which does just that: replaces all occurances of one string with another. I couldn’t use the literal question mark character, because then that would show up in s and get replaced, so instead I used 63.chr, which returns the ASCII character encoded as 63, the question mark.

s = "s = ?\nputs s.gsub(63.chr, s.inspect)" 
puts s.gsub(63.chr, s.inspect)

And that is a quine.

I think the interesting part of all this is that the challenge in writing a quine¹ isn’t in writing the code or even making any sort of intellectual leap. It’s not hard to realize, “Oh! I should replace the question mark!”. The challenge is in putting the question mark there in the first place. You have to be able to move on to trying to tackle the rest of the problem. In that way, it’s very much like recursion: you have to have faith that your method call/question mark will do what it’s supposed to, because by virtue of that faith, you’re able to guarantee that it will be fulfilled.

Anyone else have any cool quines to share? I went to all that trouble to create commenting code, I don’t want to see it go to waste!

¹ At least a quine of this variety. There are other ways to do it. For instance, in Javascript, printing a function actually prints the source code for the function, which makes the whole thing much easier.