Editor's Note: Today we're pleased to introduce you to a new segment of our blog: MetaMonday's - a chance for us to get really low-level and meta for you. Today's meta post comes from our Systems Architect, John Ku, who is well-versed in all things related to computer science and philosophy. So, let's get on with it!
This MetaMonday post delves into the puzzling nature of quines and will show you how to create one in Ruby. If you've got a passion for self-reference, mathematical logic, functional programming, or philosophical paradoxes - this post is for you!
What Is A Quine?
A quine is a self-referential program that performs the neat trick of outputting its own source code without cheating. Cheating could be accomplished by accessing the external file system that the code is stored on, or in trivial cases, compiling empty code which, unsurprisingly, prints itself.
The Challenge of Writing Quines
Initially, you might think that writing a quine would be pretty easy to do. After all, most programming languages will have a command to simply print out a string. For example, in Ruby, puts "Hello World!" would print out Hello World! as its output. So couldn't a Ruby quine then, simply consist of the puts command followed by a string containing that line of code?
On close inspection, we can see that that strategy won't actually work because it results in an infinite regression. The string printed by the puts command would have to include the whole source code, including the string itself and the puts command that precedes it. We might start out with something like:
where source_code can be thought of as a variable containing that entire line of code. However, to output that line of code in our Ruby quine, we'll need to print it out with puts, yielding:
puts "puts \"#{source_code}\""
We escaped the inside quotations with backslashes since we want them to be printed as characters rather than interpreted by Ruby as marking the beginning or end of a string. But that's the least of our worries, since we now notice that we still haven't come any closer to figuring out what goes inside source_code or even how to output that line of code along with the puts line.
The problem is that we have to include the
puts command outside of the string in order to print
source_code, yet including more code outside the string always adds onto the total source code. Thus, trying to substitute all of the source code we've arrived at so far into
source_code would just lead to an infinite regression in which our program's output is always one step behind its own source code and unable to close its self-referential loop.
Quine's Paradox and an English Example
How are quines possible then? Rather than simply reproducing the source code as a flat string, the string itself must be generated by the code. Nearly all quines turn out to share a very similar structure for accomplishing this task, generally consisting of some data (e.g. a string) and some code which operates on that data. The data is then made into a representation of the code; the code, in turn, takes the data and prints it twice: once as a data structure and once as executable code.
Let's see how this might work in a language that all of our readers presumably understand: English. Here's an English phrase which outputs itself when interpreted:
"Preceded by its own quotation" preceded by its own quotation.
The quoted phrase acts as the data structure, which also represents code, in English, for performing the syntactical operation of preceding something by its quotation. When the whole phrase is interpreted, what results is the very same English phrase, making it a quine.
We can see how this phrase works with a complete sentence from Quine's Paradox:
"Yields falsehood when preceded by its own quotation" yields falsehood
when preceded by its own quotation.
While not technically a quine since it seems to yield a truth value when evaluated rather than itself, it does involve the same essential trick of self-reference. This self-referential sentence is paradoxical because it's an indirect way of saying the same thing that the Liar Paradox says: "This sentence is false."
English to Ruby
The strategy for indirect self-reference implemented in the English quine above can be loosely translated into Ruby to produce a quine like the following:
lambda { |s| puts s + s.dump }.call "lambda { |s| puts s + s.dump }.call "
Here the quotation follows rather than precedes the code, but the result is the same. Basically, the line of code above says to take the quoted string and print it, followed by its quotation.
The lambda method takes a block of code enclosed in curly braces and creates an anonymous function defined by the block of code passed. In functional programming, these functions can then be stored in variables and passed around as first-class objects to higher-order functions, but in this case, it is simply called immediately with the string that follows as input.
When the function is called, the string gets bound to the variable s and the program prints the string along with its quotation. Since the string represents the command to print it followed by its quotation, the result of running this program is the code itself.
We could also have written this in a more conventional Ruby style, as follows:
def follow_by_quote(s)
puts s + s.dump
end
follow_by_quote "def follow_by_quote(s)\n puts s + s.dump\nend\nfollow_by_quote "
Are Quines Useless?
Now that you've gotten a taste of what quines are all about, you might be wondering whether they are of any practical use for anything other than nerd sniping. Now, we've actually already seen one use for them in formulating philosophical paradoxes, namely in Quine's Paradox, where its indirect self-reference was used to restate the Liar's Paradox. This leads us to other uses.
It turns out that the proof of Gödel's Incompleteness Theorem also uses the same sort of indirect self-reference we see in quines and in Quine's Paradox. The primary trick Gödel performed was to map a meta-mathematical logic about number theory into number theory itself and use it to state a theorem that that very theorem could not be proven.
This theorem is not quite as paradoxical as the Liar Paradox, but it is still quite counter-intuitive. The theorem cannot be proven true since its truth entails that it can't be proven true. However, it cannot be false since its falsehood entails that it can be proven true. Thus, if number theory is to remain consistent and free of contradictions, the theorem must be true but unprovable. That there are such true but unprovable theorems is arguably one of the most important mathematical discoveries in the past century.
Moreover, if we take a step back and broaden our perspective, we can see quines as one type of fixed point, or a point on a function that is mapped to itself by the function. For quines, the function in question would be the evaluation of a string of code which is performed by the programming language's compiler or interpreter. The quine is a fixed point because it is both the input and output of that evaluation function.
Fixed points have proven to be of great practical importance in theoretical computer science. In fact, a stronger version of the fixed point theorem that guarantees that our strategy for building quines will succeed has informed advances in programming language design and optimization.
The Y Combinator, for instance, shares a similar structure to our quines above and uses fixed points to define recursive (or self-referential) functions non-recursively, resulting in an exponential improvement in the amount of computation time required.
Unfortunately, I can't really do justice to these dense topics in this post, but I hope after reading this, you can share my appreciation of quines not just as an intriguing and wondrous programming puzzle but also as a glimpse into the nature of self-reference and recursion.
A Few Additional Resources
Godel's Theorem in words of one syllable:
http://www2.kenyon.edu/Depts/Math/Milnikel/boolos-godel.pdf
Hal Fulton claims to have the first Ruby Quines:
http://rubyhacker.com/ruby-quine.html
Shortest Ruby Quine (at the end of this post):
http://philcrissman.com/2008/11/30/real-quines-in-ruby
There is also an explanation of how that shortest Ruby quine works here:
http://thisbindle.com/personal/ruby/
(It basically does the same thing as my Ruby quine above).
Lots of quines in different languages (no Ruby though):
http://www.nyx.net/~gthompso/quine.htm
How to write a quine in C#:
http://igoro.com/archive/how-to-write-a-self-printing-program/
![[Slashdot]](http://slashdot.org/favicon.ico)
![[Digg]](http://digg.com/favicon.ico)
![[Reddit]](http://reddit.com/favicon.ico)
![[del.icio.us]](http://del.icio.us/favicon.ico)
![[Facebook]](http://www.facebook.com/favicon.ico)
![[Technorati]](http://technorati.com/favicon.ico)
![[Google]](http://www.google.com/favicon.ico)
![[StumbleUpon]](http://www.stumbleupon.com/favicon.ico)
