23
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ We tried sorting this out in chat the other day... it's tricky... \$\endgroup\$ – Martin Ender Mar 11 '15 at 19:10
  • \$\begingroup\$ @MartinBüttner Which chatroom, btw? And even if it is ultimately very difficult or impossible to answer completely, it would still be useful to come up with a standard set of criteria that handles most cases reasonably. \$\endgroup\$ – AJMansfield Mar 11 '15 at 19:13
  • \$\begingroup\$ This chatroom. \$\endgroup\$ – Martin Ender Mar 11 '15 at 19:20
  • \$\begingroup\$ Related \$\endgroup\$ – mbomb007 May 1 '17 at 21:38
27
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ How does this address the 'execute the data as code' type quine discussed at the end of the page you link to in the first paragraph? \$\endgroup\$ – AJMansfield Mar 11 '15 at 21:53
  • 1
    \$\begingroup\$ @AJMansfield What do you mean by "address"? Include or exclude? My intention is to include eval-based quines (and usually the eval will still appear in the data part of the quine, thus meeting my definition). \$\endgroup\$ – Martin Ender Mar 11 '15 at 22:02
  • \$\begingroup\$ so, under this definition, {".~"}.~ in golfscript is legitimate, but {nop} isn't? \$\endgroup\$ – John Dvorak Mar 12 '15 at 3:24
  • \$\begingroup\$ @JanDvorak One way to justify that: {".~"}.~ will do well if it is required to apply another function to the parts of the code, while {nop} won't. \$\endgroup\$ – jimmy23013 Mar 12 '15 at 3:47
  • 1
    \$\begingroup\$ @JanDvorak Yes, that's my intention. And user23013 has a good point that the former can be used as the basis for a generalised quine. Maybe it would be worth considering to make that part of a definition (although "can be used as the basis" is rather vague). \$\endgroup\$ – Martin Ender Mar 12 '15 at 10:23
  • \$\begingroup\$ What is the rule for quines that are just literals? \$\endgroup\$ – Erik the Outgolfer Oct 6 '16 at 11:57
  • \$\begingroup\$ @EriktheGolfer They don't satisfy this definition. \$\endgroup\$ – Martin Ender Oct 6 '16 at 12:00
  • \$\begingroup\$ @MartinEnder For example, in GolfScript, someone can write something like "", and claim that each quote identifies the other one. For those who do not know GolfScript, they can be convinced. \$\endgroup\$ – Erik the Outgolfer Oct 6 '16 at 12:04
  • \$\begingroup\$ @EriktheGolfer That is not a quine. And I don't understand what your second sentence has to do with anything. Are you saying the definition of a quine depends on whether you can trick someone into believing that something is a quine? \$\endgroup\$ – Martin Ender Oct 6 '16 at 12:07
  • \$\begingroup\$ @MartinEnder Well, I have a while to use GolfScript, but I thought "" prints "" (or ""\n). Anyways, if I write a quine ab, and say that a identifies b, and b identifies a, then is it valid? \$\endgroup\$ – Erik the Outgolfer Oct 6 '16 at 12:10
  • \$\begingroup\$ @EriktheGolfer This seems like a very hypothetical question. If you can dig up a language and a specific program where this works, we can discuss this more constructively. \$\endgroup\$ – Martin Ender Oct 6 '16 at 12:20
  • \$\begingroup\$ @MartinEnder I made a chatroom. \$\endgroup\$ – Erik the Outgolfer Oct 6 '16 at 12:32
  • 1
    \$\begingroup\$ A similar situation in more familiar syntax: suppose I have a programming language which prints every command as it's executed, with no newline, but always ensures that output has a final newline if it's missing one; is print "\n" a quine? \$\endgroup\$ – user62131 Dec 15 '16 at 21:02
  • 1
    \$\begingroup\$ Due to the cheaty-but-not-technically-cheating quines that Dennis has posted recently, I suggest we amend the definition to say something like "There must be at least one explicit instruction that manipulates values already introduced, while not introducing any hardcoded values of its own." There's probably a clearer, more exact way to phrase that though. \$\endgroup\$ – ETHproductions Jan 25 '17 at 16:42
  • 2
    \$\begingroup\$ I've come up with a small modification to this that keeps to the same spirit (possibly more accurately), but excludes most of the exploits I'm aware of: "A proper quine contains at least one datum that encodes both its own representation in the output, and something in the output other than itself." It might be better to use a different sort of definition, but that seems like the best way to salvage this one. \$\endgroup\$ – user62131 May 5 '17 at 1:07
25
\$\begingroup\$

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.

\$\endgroup\$
  • 4
    \$\begingroup\$ Maybe this requirement is a bit too strong. I would consider this quine proper but it's not payload capable, since the string referring to the code is printed directly (as Fission does not have strings as data types). In fact, I'm not even sure that payload capable quines are possible in all languages (while yes, it should be possible to write any generalised quine in any Turing complete language, I don't think it's guaranteed that you can find a single form that can handle all possible payloads). \$\endgroup\$ – Martin Ender May 29 '15 at 10:08
  • 1
    \$\begingroup\$ @MartinEnder: To belatedly answer an old comment, while I don't know much about Fission, it seems to me that at least slight variations of that quine like '!+!;R" could be made to carry a payload. For example, '!+!'H!e!l!!o!',!' !'W!o!r!l!d!'!!;R" prints its own code followed by Hello, World!. Sure, it's a bit awkward because I couldn't use " in the payload, but I believe the subset of Fission that this quine can carry is still quite expressive. Still, that's certainly an interesting borderline case. \$\endgroup\$ – Ilmari Karonen Aug 11 at 21:22
6
\$\begingroup\$

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.

\$\endgroup\$
  • 3
    \$\begingroup\$ Fixed-point theorems may be unintuitive, but they're not paradoxical. If quines were truly paradoxical, they would break compilers. As for your last paragraph: do you have a citation? On the basis of a quick read through pages 490 to 499 of GEB, it seems that Hofstadter talks about self-reps rather than quines when discussing computer programs, and he explicitly recognises that they're hard to define. \$\endgroup\$ – Peter Taylor Mar 12 '15 at 9:35
  • \$\begingroup\$ "To be sure, explicitness is a matter of degree; nonetheless there is an intuitive borderline on one side of which we perceive true self-directed self-reproduction, and on the other side of which we merely see copying being carried out by an inflexible and autonomous copying machine." (p495) \$\endgroup\$ – Peter Taylor Mar 12 '15 at 9:35
  • 1
    \$\begingroup\$ @PeterTaylor That's my point: they're hard to define. That's part of what makes them interesting. I think trying to come up with an exhaustive ruleset about what defines a "proper" quine misses the entire point of Quine programs. If somebody wants to introduce additional rules for a specific challenge, okay, but that doesn't really change what a "proper" Quine is. \$\endgroup\$ – Kevin Workman Mar 12 '15 at 13:11
  • \$\begingroup\$ What about a quine that does take in input, but gives the same result no matter what the input is (even empty)? \$\endgroup\$ – Sp3000 Mar 15 '15 at 5:30
  • \$\begingroup\$ @Sp3000 ...Why does it take any input then? I think that's a pretty hypothetical situation, but if we're going off the original core definition of a Quine, then it wouldn't count. I suppose you could get into a debate about whether taking input that doesn't actually affect anything really counts as "taking input", but again, that's all pretty hypothetical. \$\endgroup\$ – Kevin Workman Mar 15 '15 at 15:31
  • \$\begingroup\$ @KevinWorkman Well it actually happened to me. - basically because of the restrictions of the challenge I had to use i, for input. It pushes a char from STDIN if there is something, or -1 otherwise, but either way it just got popped so it didn't matter what it was. \$\endgroup\$ – Sp3000 Mar 15 '15 at 15:35
  • 1
    \$\begingroup\$ @Sp3000 Ha, well, I would say you're in the fuzzy gray area of Quine semantics. The original definition includes a requirement that no input be taken, but you can debate what exactly constitutes "taking input". I don't think there's a great catch-all rule though. \$\endgroup\$ – Kevin Workman Mar 15 '15 at 17:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .