Self-reproducing programs, if you've never heard of them, are fascinating objects. This is Ken Thompson's description in his classic 1983 Turing Award address:
In college, before video games, we would amuse ourselves by posing programming exercises. One of the favorites was to write the shortest self-reproducing program. [...]
More precisely stated, the problem is to write a source program that, when compiled and executed, will produce as output an exact copy of its source. If you have never done this, I urge you to try it on your own. The discovery of how to do it is a revelation that far surpasses any benefit obtained by being told how to do it. The part about "shortest" was just an incentive to demonstrate skill and determine a winner.
What is really remarkable about programs printing their own
source code is that they are fixed points of their
execution environments. That is, if we have a Ruby program
quine.rb that produces its source code when executed,
then the following shell commands' output are exactly the
same:
cat quine.rb ruby quine.rb ruby quine.rb | ruby ruby quine.rb | ruby | ruby | ...
Since the result of executing ruby quine.rb is the
original source code, piping that to ruby only executes
this code again and giving the same result. The process can be
repeated ad infinitum.
There are many ways to accomplish this feat. But before going on, I would like to reiterate Ken's advice to you to put this page away and try coming up with a solution on your own. It may take an evening or longer, but your time will be well spent.
The easiest solution is practically cheating. Since Ruby
lets you refer to the current source file directly through the
__FILE__ variable, we simply read from it and print it
out!
puts File.read(__FILE__)
Executing this recursively using pipes unfortunately raises an error. The reason is that __FILE__ evaluates to '-' when the current source file is actually the standard input. We can still do it, though, using a feature of the Zsh shell called process substitution:
ruby quine.rb ruby =(ruby quine.rb) ruby =(ruby =(ruby quine.rb)) ...
Here, the shell replaces each =(...) block with the
name of a temporary file whose content is the result of
executing that block. Bash also have this feature (using the
<(...) notation). However, executing it recursively in
Bash results in an empty line. I suspect the cause to be
difference in implementation: Bash performs process
substitution using /dev/fd/N as the temporary files,
where as Zsh just uses regular files.
Anyway, this first program is in the same vein as another classic Unix solution:
#!/bin/cat
However, due to how the shebangs sets things up, you won't get this script to actually execute recursively. Or perhaps there is a way that I don't know?
If the two above solutions did not feel like cheating to you, then check out this solution which won an entry in the 1994 International Obfuscated C Code Contest. The source file is simply empty! On one hand, it is a worst abuse of rules. On the other, it does qualifies technically as a fixed point of its execution environment:
echo | ruby | ruby | ruby
Enough of cuteness. Here's a real programmer's quine:
s="s=%s; printf(s,s.inspect)\n"; printf(s,s.inspect)
Why is this more interesting than the previous ones? Because
not only you can actually see the inherent infinite regression
when %s is replaced by the value of s itself,
but also that it requires very little of the host language: just
the ability to output a computable string (here using the good
old printf). It turns out that quines are possible in
any programming language that has the ability to output any
computable string, as a direct consequence of
Kleene's recursion theorem.
I've been using the name along the way, but this form of self-reproducing programs is often called a quine in honor of the philosopher and logician W. V. O. Quine, who discovered this paradox:
“Yields falsehood when preceded by its quotation”
yields falsehood when preceded by its quotation.
This sentence is very similar to our program, as you can imagine
the its reference inside the double quotes taking the
role of %s and the outter its taking the role of
s.
Using a similar structure, we can construct a solution
using blocks -- everyone's favorite feature of Ruby.
It is quite trivial to define a method that yield strings and
give it block that will print back those strings, including the
yield directives, like this:
def hello
yield 'Hello, world!'
end
hello { |s| puts " yield '#{s}'" } #-> yield 'Hello, world!'
Now, to make it a quine, we'll need to print out the method
definition and the call with the given block itself, somehow.
My idea is to write a package with a function quine
that takes a symbol named after a user-defined method and will
print out the method definition and the anticipated method
call, so that this program will print it own source code:
require 'quine' def hello yield 'Hello, world!' end quine :hello
Here is the quine library:
puts "require 'quine'"
def quine(name)
puts "def #{name}"
method(name).call { |s| puts " yield '#{s}'" }
puts "end"
puts "quine :#{name}"
end
This certainly isn't the shortest quine around. It is nice,
though, as you can yield multiple strings -- whatever
you want -- and quine will reproduce them, as long as
each string fits into one line and is surrounded by single
quotes. You can also define multiple yielding methods and
call quine on each of them!
If you are still in the mood for quines, then check out this ■
Previous Post