What counts as a proper quine?

Question

The basic definition of a quine is a program that, when run, produces its own source code as output. There are a number of techniques and a number of way to implement those techniques across a number of different languages.

However, not all quine programs are equal. Clearly, any quine in HQ9+ or a related language is not a proper quine, and nor is an empty program.

Some cases are more ambiguous, though. Some languages like PHP or HTML, when given a program with no executable tokens, will just output the contents. However, that does not necessarily mean that every quine written in one of those languages necessarily takes advantage of this.

Another type of 'cheating' quine, one that directly accesses its source code, via a file or otherwise, and outputs that.

A program shouldn't necessarily be considered 'cheating', though, just because it accesses a file. For instance, if a program were to use source code spread across multiple different files, it could still be a proper quine, assuming it outputs all of its source. It might even use external non-code files, such as images or other data. This doesn't necessarily mean that it is not a proper quine, as long as it outputs all of its source code and source data.

A program might even directly access its own source code file: For instance, in PostScript it is common practice to access the source file in order to access binary data appended to the end of the source file. In this case, the program is merely accessing source data, and shouldn't necessarily be considered 'cheating' for it.

One particularily ambiguous case is this answer to Build a Twitter-quine. (Long story short, write a program that tweets its source code.) One version of the program uses a link-shortener service to redirect a shortened URL (http://tinyurl.com/erjk34) to a longer one (https://twitter.com/intent/tweet?text=window.open(%22http%3A%2F%2Ftinyurl.com%2Ferjk34%22)%3B). Even though the question OP stated that cheating quines are allowed, it is still worth considering whether this is a proper quine or not, or if the link redirection (not the code performing the redirection, the redirection itself) should be considered part of the program's source.

What should the criteria be for determining what is and isn't a proper quine in quine-related challenges?

Answer 1

We've been discussing this in chat recently, and coming up with a solid definition seems difficult. The best idea I've got is to base a definition for a true quine on the principles given on this page: a true quine will in one way or another consist of data, and code. The data represents the code, and the code takes the data, and produces both the data's and the code's representation from it. Any quine which doesn't do that in some way, seems to be a cheaty quine (PHP quines which just print code verbatim, GolfScript quines which just print a variable on program termination, quines which read the source code).

So I don't know how workable this is in practice, but here is a suggestion:

It must be possible to identify a section of the program which encodes a different part of the program. ("Different" meaning that the two parts appear in different positions.)

Furthermore, a quine must not access its own source, directly or indirectly.

Some examples

Here is Ruby quine

_="_=%p;puts _%%_";puts _%_

One can easily identify parts of the string which encode bits of the code that are outside the string, i.e. the _= and the ;puts _%%_.

Here is a CJam quine, I'd consider legitimate:

{"_~"}_~

The "_~" encodes the _~ at the end of the code.

Note that the encoding part doesn't necessarily have to be identical to the encoded part. E.g. if you look at my Prelude quine, the long number at the end encodes the entire remainder of the code (since Prelude doesn't even have strings).

I think this definition should catch most cases, and more importantly rule out all the common quine cheats. I'd be very interested in examples this doesn't catch, both false positives and false negatives.

Answer 2

Instead of arguing about what counts as a "real" or "proper" quine, which I suspect is too subjective and context-dependant to ever permit a non-contentious definition, let me try to instead suggest a related, hopefully slightly less loaded dichotomy:

Definition: A quine is payload-capable if it can be extended, in some systematic manner, to include a "payload" of additional code capable of performing arbitrary computation, in addition to printing its source code. A payload-capable quine, in its base form, must include all the code necessary to carry and execute a payload, even if no actual payload is present.

Examples:

• {whatever} is a GolfScript quine, but it is not payload-capable. Neither is 1 or an empty program.

• {".~"}.~, however, is a payload-capable quine in GolfScript, as it can be extended to {".~"anything}.~, where anything is arbitrary GolfScript code that is executed by the GolfScript interpreter.

• ".`\\".`\ is also payload-capable, as it can be extended to ".`\\foo".`\foo, where foo is arbitrary GolfScript code (and where any special characters in the first instance of foo are escaped according to the GolfScript double-quoted string escaping rules).

• Any file that does not include the string <? is a PHP quine, but no such quine is payload-capable (as they'd have to include <? to execute the payload).

• open+0;print<0> is a payload-capable Perl quine, although it "cheats" by reading its own source code.

Notes:

This definition deliberately focuses on a single aspect, the ability to carry out arbitrary computation as part of the quine. It does not even attempt to rule out other types of "improper" quines, such as those that read their own source code or that use string eval. If one would like to exclude such, one might require e.g. that:

"Solutions must be payload-capable, and must not read their source code or use string eval."

(Tangentially, as a fair warning, {".~"}.~ is still a valid payload-capable quine even if string eval is forbidden, as is function q(){return q+";q()"};q() in JavaScript; both simply exploit a convenient language feature that makes functions stringify to their own source code.)

I was tempted to call a payload-capable quine "non-trivial", and those that cannot carry a payload "trivial", but in the end, deliberately chose to use the most literally descriptive and non-loaded term possible. In particular, the term "payload-capable" has the virtue of having no likely alternative interpretations: a person seeing it will either recognize (or guess) what it means, or will have to ask (or Google it, or follow a link, if provided).

Some level of judgement may be required when deciding whether, in the absence of an actual payload, a given quine really does "include all the code necessary to carry and execute a payload". For example, the Perl quine open+0;print<0> might require an extra semicolon between itself and the payload, but this is not true for all payloads; indeed, for some payloads, it might be optimal to include the payload expression as an extra argument to the print.

In any case, the intent of this clause is simply to rule out silly and obtuse claims that, say, an empty program should be considered a payload-capable quine in GolfScript, just because the {".~"}.~ can be added together with the payload. Where there is genuine ambiguity, I would recommend lenience in enforcing this rule.

In any case, by far the best and least subjective way to decide the matter, at least in my personal opinion, is to simply design your challenge to include some extra task, in addition to merely printing out your source code, that requires an actual payload to be included. By doing so, any quibbles about whether a given quine is really payload-capable, or what counts as necessary code to execute a payload, are eliminated — any quine that can perform the required extra task is payload-capable by definition, and demonstrably includes all the necessary code.

Answer 3

For the record, I'm the author of the original twitter quine that cheated by using a tinyurl link to redirect to twitter's web query-string-based "API" to create a tweet containing that tinyurl link.

Also for the record, I fully admitted that was "cheating", but the original challenge said that cheating was encouraged- including reading from a file (which is normally not "allowed" in quines).

But more to the point, the thing that makes quine programs interesting is that they're paradoxical. Consider this quote from wikipedia:

The name "quine" was coined by Douglas Hofstadter, in his popular science book Gödel, Escher, Bach: An Eternal Golden Braid, in the honor of philosopher Willard Van Orman Quine (1908–2000), who made an extensive study of indirect self-reference, and in particular for the following paradox-producing expression, known as Quine's paradox:

"Yields falsehood when preceded by its quotation" yields falsehood when preceded by its quotation.

In some languages, particularly scripting languages, an empty source file is a fixed point of the language, being a valid program that produces no output. Such an empty program, submitted as "the world's smallest self reproducing program", once won the "worst abuse of the rules" prize in the International Obfuscated C Code Contest.

So the answer to your question of "What counts as a proper quine?" is another concept from the EGB book:

Mu.

In other words, there is no official Department of Quine Rules and Regulations. What defines a "true quine" depends on who is asking the question. It's a fun thing to think about, and part of what makes it so fun is that it isn't really well-defined. It's paradoxical- the whole point of naming them Quines was to underline that paradox.

So, I don't think there's a real answer to your question, outside of specific challenges. If you want to put additional limitations or rules on "what defines a quine" on any challenges you issue, that's fine. But that doesn't really impact the definition of a "proper quine". We could go back to the wikipedia definition:

A quine is a non-empty computer program which takes no input and produces a copy of its own source code as its only output.

That's the core, and adding anything on top of it (such as the requirement that it must include some kind of encoding mechanism) seems a bit arbitrary, and detracts from the whole point of quines. Quines are supposed to be weird and paradoxical.

For a more concrete answer, I think the most important aspect of a quine is the takes no input requirement. From there you can get into a separate debate about what counts as input, but I think your example of reading from several files is pretty obviously out.

So if you're asking what a quine is, you should probably ask the guy who coined the term. And he says a quine is any program that doesn't take any input, and only outputs its own source code. Anything on top of that is just extra.