(Disclaimer) I wrote this more as a journal entry as I was learning about recursive theory and using quines as a starting point, then realized it might be beneficial for anyone who's interested in learning how to start thinking about them and all the interesting stuff they entail. I'm pretty sure this belongs in Meditations, but if not I apologize.
Quines are programs that print out copies of themselves, character for character. Quines are made of 2 essential parts, encoding (data) and actual code:
- (data) An encoding of the actual code is made.
- (code) The executable part of the encoding is then executed as code using it as input (the code is a subset of the encoding).
In other words, the data contains the "encoding" of the executable code, which is then "fed into" the actual code. The quine combines the two parts to make identical the program itself and its printed output.
The "encoding" is of course just a string. If we assign variables it must show up in the string (we need not to - we can use literal or inline strings). Where we print that also shows up. The string says "this is what I'm about to do to myself" and then the code goes and does it. Since a quine's job is simply to print itself, this reduces to "this is what I'm about to print, using all or part of this exact string."
Here's an example in English:
Print out two copies of the following, the second one in quotes:
"Print out two copies of the following, the second one in quotes."
Notice the statement itself is the code, and the encoding is the statement wrapped in quotes. Both the code and the encoding are one and the same, but that need not be the case (English is flexible - but hey, so is Perl!)
What follows is a straightforward derivation of a quine in Perl. It took many attempts and lots of dead-ends, but I hope I can translate the underlying ideas simply and clearly. I had a lot of help in the thought process behind constructing one here. I now see the identical quine and a few other similar ones here (maybe click that one later).
Remember: encoding + code; in this example I'll make an encoding, then print it (the order of which is unimportant - thanks rubasov). I start by creating a variable that stores the encoding, realizing that the encoding must also start with an assignment if the eventual output is to match:
$s = '$s = ...
At this point you can fall off a cliff by pursuing the temptation to keep recursing - so, don't! Instead just mark a placeholder for the current string that you can fill in later using the actual code (hint hint):
$s = '$s = X';
I closed off the string only to free myself into now thinking how the code should look, which I can then go back and paste into the encoding afterward.
So, how should the actual code look? The trick is deciding how you want Perl to fill in the X. Again, this example being straightforward I use printf, which by its very design does exactly what we want. Since we'll fill in the encoded string with the printf function during execution, we can use %s as the placeholder for the definition of $s:
$s = '$s = %s'; printf($s,...)
Whoops, forgot to paste in printf in the encoding:
$s = '$s = %s; printf($s,...)'; printf($s,...)
Yes, things are starting to flesh out now! Now, what should we put in %s? Why the encoded string of course:
$s = '$s = %s; printf($s,$s)'; printf($s,$s)
This is a basic sketch of any quine you'll come across. In fact, if you run it you'll see we're almost done:
$s = $s = %s; printf($s,$s); printf($s,$s) # Output
All we're missing is the quotation marks! Again, this conundrum is solved by using placeholders:
$s = '$s = %c%s%c; printf($s,39,$s,39)'; printf($s,39,$s,39)
(Note that if you try to use a pair of literal \' you'll have to keep recursively accounting for the accumulating backslashes in the encoding - until you printf-format them - so you might as well keep it simple and format the darn quotation marks.)
And that's it, we have a quine! The key to all this (for me at least) was realizing that we actually make an encoding inside the encoding, which gets filled in during execution. In other words, the code knows how to translate the encoding into the program itself. Also, adding code is easy to accommodate in the encoding by merely pasting it in, so long as we don't fall off the "recursive cliff."
Here's a modified version of the same quine that compacts the encoding and statement of execution:
printf($s='printf($s=%c%s%c,39,$s,39)',39,$s,39)
Here's an adaptation of an elegant and popular example that "abuses" Perl's flexibility a bit more:
say << '' x 2
say << '' x 2
This looks very much like the English example, and in fact works almost exactly the same way. It uses the magic of Perl's << here-doc operator, which allows the statement of execution (top) to appear inline with the multiline encoding (bottom). As a side benefit no substitution is necessary and no quotes are needed, and we end up with the elegant code as presented.
Links
- http://www.perlmonks.org/?node_id=661934
- http://www.perlmonks.org/?node_id=62389
- http://www.madore.org/~david/computers/quine.html
- http://www.nyx.net/~gthompso/quine.htm
Corrections and comments are, of course, welcome. |
Re: How I Learned About Quines
by rubasov (Friar) on Apr 16, 2010 at 11:23 UTC
|
As a side note to your nice explanation: You are free to choose the ordering of code and data (encoding). If you start from code+data (opposed to data+code), you'll get a functional programming style quine, like this:
sub{print qq[sub{print qq[$_[0]]}->(q[$_[0]])]}->(q[sub{print qq[$_[0]
+]}->(q[$_[0]])])
In a digestible form (but this way it screws up the whitespaces):
sub {
print qq[
sub {
print qq[
$_[0]
]
}->(
q[
$_[0]
]
)
]
}->(
q[
sub {
print qq[
$_[0]
]
}->(
q[
$_[0]
]
)
]
)
Sorry for the parentheses haters.
| [reply]
[d/l]
[select] |
|
|
| |
Re: How I Learned About Quines
by ambrus (Abbot) on Apr 16, 2010 at 11:45 UTC
|
Apart from the webpages you mention, there's also Douglas Hofstadter's book Gödel, Escher, Bach. For perl specifically, there's my Short quines.
Update: These days I also started to like quines that look like this:
print+("\\","\"",",","print+(",")[3,1,0,0,1,2,1,0,1,1,2,1,2,1,2,1,3,1,
+2,1,4,1,4]")[3,1,0,0,1,2,1,0,1,1,2,1,2,1,2,1,3,1,2,1,4,1,4]
Update 2010-01-28: These unpack quines by mtve below are nice. Here's my attempt.
print unpack a44X44a43xaXXaaXaXaxaXaX4axa, "print unpack a44X44a43xaXX
+aaXaXaxaXaX4axa, \"\\\nn"
Or, if you don't need the newline, this works too.
print unpack a35X35a34xaXXaaXaXXa,"print unpack a35X35a34xaXXaaXaXXa,\
+"\\"
Update 2012-12-12: see also General quine, Short quines.
| [reply]
[d/l]
[select] |
|
|
uuencode to the rescue!
print unpack a27uX30a30X3u,"print unpack a27uX30a30X3u,!(@"
| |
|
|
well duh, just to complement that never-ending unpack
print
pack'a*c3X2a*c4X2a2c4X3a2c3X3c3X2c2Xa3cXc2Xa3',("print
pack'a*c3X2a*c4X2a2c4X3a2c3X3c3X2c2Xa3cXc2Xa3',(",34,44,")x7")x7
| |
Re: How I Learned About Quines
by GrandFather (Saint) on Apr 16, 2010 at 08:56 UTC
|
My first Quine (although I wasn't aware it was called that) was written in C and I went through very much the process you describe. However some languages make it fairly trivial to write a quine. Consider:
seek DATA, 0, 0;
print <DATA>
__DATA__
Prints:
seek DATA, 0, 0;
print <DATA>
__DATA__
Adding strictures is left as an exercise (rather a trivial one to be sure) for the reader.
True laziness is hard work
| [reply]
[d/l]
[select] |
|
|
I believe that's called "cheating." :)
I started out with
open $fh, '<', $0 or die $!;
print while <$fh>;
which even then felt wrong. | [reply]
[d/l] |
Re: How I Learned About Quines
by BioLion (Curate) on Apr 16, 2010 at 14:57 UTC
|
Slightly OT, but why 'quine' - does it mean / stand for anything? And apart from the obvious naughty applications, are they used for anything other than exercises? Excuse any naivity in these questions...!
Just a something something...
| [reply] |
|
|
Quoting the redoubtable Wikipaedia:
"Quines are named after philosopher Willard Van Orman Quine (1908–2000), who made an extensive study of indirect self-reference. He coined, among others, the following paradox-producing expression, known as Quine's paradox:
"Yields falsehood when preceded by its quotation" yields falsehood when preceded by its quotation.
(Quine (Computing))
----
I Go Back to Sleep, Now.
OGB
| [reply] |
|
|
| [reply] |
|
|
|
|
|
|
One more quine
by mtve (Deacon) on Apr 19, 2010 at 11:08 UTC
|
I've started to write uuencoded one, but then I've realized it could be simple:
print unpack'a*@0HX'x2,q 7print unpack'a*@0HX'x2,q 7
Just to save it, here is uuencoded:
print unpack'u@0HXa*@0H',q 3;<')I;G0@=6YP86-K)W5`,$A882I`,$@G+'$@3
| |
|
|
| |
|
|
perl -e 's sslcsene s sa zs sgxlt print lc for uc sazsslcseneazsazsaazzsazsgxltazprintazlcazforazucaz'
gives:
s sslcsene s sa zs sgxlt print lc for uc s sslcsene s sa zs sgxlt print lc for uc
Which is not the same :(
| [reply]
[d/l]
[select] |
|
|
|
|
|
|
Re: How I Learned About Quines
by mtve (Deacon) on Apr 25, 2010 at 09:04 UTC
|
Non-alphanumeric quine, should be golfed more.
()!~('$!%%(!,$( #/$*,#,...# #&/,$($#( #.$!%%(!,$"( #/$( %%#%.%*#+.+
+&//-%(.&#//-%.,).*.$%- $+( +". +($+". +(".+%.&/,(~^=$:^$"))})'
^',>~`~``,,~>~,~~,,>^~,,>^~,``~,,>>,~>,,>~`~``,^,~>~,,~,,~,,,,>,~,~>>>
+>,,~>>>>>~~``~,,,,~,,,~,^`^,,>,^`^,,^,,,,``~,'
^'
+ ')
| |
|
|
| |
Re: How I Learned About Quines
by moritz (Cardinal) on May 05, 2010 at 11:39 UTC
|
Mostly unrelated, but I'd like to share the story with you nonetheless:
The other day I discussed quine zip archives with friends shortly before I went to bed. Then I dreamt that my sister made me a belated Christmas present, which consisted of a book (Flemish for beginners :-) and a model of a quine building.
In my dream that was a tower that was open at one side, and if you looked into the cupola you saw another building, which in turn contained the tower again - in full size. I was very happy about such a geeky present.
When I gradually woke up I realized more and more that such a thing can't really exist in our 3D real world, and was a bit disappointed. Still a rather nice and geeky dream :-)
Perl 6 - links to (nearly) everything that is Perl 6.
| [reply] |
Re: How I Learned About Quines
by mtve (Deacon) on May 05, 2010 at 11:29 UTC
|
| |
|
|
