Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
PerlMonks  

Comment on

( #3333=superdoc: print w/replies, xml ) Need Help??

(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:

  1. (data) An encoding of the actual code is made.
  2. (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.


In reply to How I Learned About Quines by blakew

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and all is quiet...

    How do I use this? | Other CB clients
    Other Users?
    Others lurking in the Monastery: (5)
    As of 2018-04-19 23:49 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?
      Notices?