37
\$\begingroup\$

Note: In this Meta question, it was determined that the correct thing to do if you think an established consensus has become outdated is to post a new question, even if the question would otherwise be considered a duplicate.

Background

Our current rule for defining a "proper quine" is as follows:

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.

However, in the time since the precedent was set, several counterexamples have turned up that bring this consensus into question.

Known issues with the current definition

Two literals which each print the other

Examples:

RProgN

1
1

Try it online!

7

23723

Try it online!

A few languages (mostly stack-based languages) naturally process things at the right hand end of the program first. This means that if you write two literals into a program, you'll get the literals output in reverse order. This is something of an end-run around the aim to prevent a quine consisting only of literals; it's also inconsistent (the same rule would disallow the comparable solution in a language that prints literals from left to right).

A second issue with this is that it can lead to some absurd conclusions. Suppose the task were instead to write an order-2 cyclic quine (i.e. two programs that each output the other), but the two programs were allowed to be identical. You'd assume that any proper quine would also be a correct answer to this question, but with our current definition, quines like the above are no longer valid 2-cyclic quines (but would be valid 3-cyclic quines). A good proper quine definition would ideally avoid this sort of issue.

Literals which print themselves plus a no-op

Examples:

05AB1E, 2 bytes

1

Try it online!

PowerShell, 2 bytes

1

Try it online!

In both PowerShell and 05AB1E, an empty program prints nothing, and an integer prints itself followed by a newline. Additionally, a final newline is a no-op and has no effect; as a result, if we append the no-op to the literal, we get a proper quine by the current definition (because it's clear that the integer encodes the newline, rather than the newline encoding itself). On the other hand, it very much seems as though this sort of answer isn't in the spirit of proper quine competitions. (Interestingly, this loophole is one that people haven't widely tried to exploit, perhaps out of a sense of fair play.) It seems like a good proper quine definition would disallow this sort of thing.

Programs which explicitly print output that would have been printed implicitly

This has only come up once naturally, in 7, and it requires the program to be expressed in binary (7C E7); thus the situation's somewhat hard to get your head around. Here's the description I gave in the comments of the old quine definition challenge:

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?

The conclusion we came up with on discussion of this at the time is that our current definition of a proper quine doesn't handle this situation at all, not giving a clear answer on whether or not this is a proper quine. We'd want our definitions to handle all cases.

Uncertainty about what characters make up a literal

Befunge-98 (cfunge)

 'k<@,k␇

(No TIO link, because this doesn't work on FBBI, the interpreter TIO uses.)

In this quine, the final 7 characters each encode themselves, and the first is a space. The space is produced from a string literal defined using k', and the string literal wraps around the program. String literals in Befunge-98 (at least in cfunge) treat any wrap around the program as a single space character, and merge any string of consecutive whitespace into a single space. So is the space at the start of the program produced from the literal space, or from the wrap? Removing either the space, or the wrap, would still leave a space in the string. The current quine definition seems to assume that it's always possible to uniquely identify what characters in a program are responsible for producing a particular piece of data, but that's not always the case.

Kimian (error) quines

See this question for a ton of examples of error quines. The basic problem here is that the error message being printed comes mostly from the language implementation, rather than from anything in the program. So what part of the program encodes it? Applying our current proper quine definition in this sort of situation is hard, and it's unclear whether error quines count by default.

Note that any new definition will have to take into account the fact that error messages often echo part of the source; this complicates attempts to determine whether the quine is literal-only (e.g. see the error quine at the end of this post; the first line is clearly responsible for determining the content of the second, but it isn't exactly a string literal), and also raises questions as to whether the program is reading its own source.

Finally, there's a defensible opinion that some people hold error quines are never proper quines, regardless of how they function. Clarity on this point would be useful.

Generalized quines which rearrange parts of the output

This problem was inspired by this challenge, which asks programs to output an anagram of themselves. In this sort of problem, how do you tell which parts of the input correspond to which parts of the output? It's possible to tell if all the characters of the program are unique, but if there are duplicates, you can't necessarily tell which character of the program was being printed by any particular character of the output.

Situations which are only informally defined at present

Topological quines

See, for example, the current Cubix recordholder. The basic idea is to exploit a language where the source code has unusual topology (like a cube or a torus), and wrap a string literal so that it goes entirely around the program, allowing the program to effectively read its own source code.

But wait, I thought a proper quine wasn't allowed to access its own source, even indirectly? However, topological quines are typically accepted on PPCG. So the proper quine definition could really use clarifying to be clear as to whether or not this sort of case is allowed.

Reading the memory that contains your program

When a program runs, it typically loads itself into memory as a memory image. Languages that use a parserless interpreter have that image identical to the program's source; this most commonly includes machine code and Befunge one-liners. Here's an example (the question is basically "write code that compiles into a quine"; thus, the compiled output of the linked answer is a quine, even though the answer itself is not a quine).

Some languages also give access to this memory, e.g. Befunge's g instruction (or in machine code, the fact that the code segment is addressable). This is commonly used in machine code for defining the equivalent of a string literal (in fact, it's what string literals compile into). Modern OSes tend to have a separate "read-only data" section for this sort of constant, but using it is just a guideline, rather than a rule, and you can actually mix all the code and data together if you want to.

So the question is, under what circumstances can this sort of memory-reading instruction be used in a proper quine? The current consensus appears to be "you can read any part of your program image that isn't actually executed", but that doesn't seem to be stated anywhere in the quine definition.

Situations which our current definition handles, but new definitions need to take into account

Literal-only quines

One of the two most common cheats (other than reading your source from disk), that we'd want to disallow in a quine definition, is the literal-only quine: write a literal (typically a number, although some languages allow almost anything in literals), and have it implicitly printed. This answer contains a listing of many languages which do this (together with a few that don't).

Literal-only quines are considered improper, and in fact much of the reason we have a proper quine definition is to try to exclude them in an unambiguous way.

Eval quines

Jelly, 6 bytes

“ØV”ṘV

Try it online!

A Pear Tree / Python

a= "print('a=',repr(a),';eval(a)#r3TQJ')" ;eval(a)#r3TQJ

Try it online!

The basic idea behind an eval quine is to write basically the entire program inside a string literal, then evaluate the string literal, giving the program an effective method of seeing most of its own source. Unlike most traditional quines, you therefore have to write most of the program only once, rather than the normal twice. We currently accept this sort of thing as a proper quine. However, disallowing it is also a defensible opinion (that is seen every now and then), because the same characters are used as both code or data. A good proper quine definition needs to come to an opinion on whether or not we want to accept this sort of thing.

It should be noted that banning eval and friends outright is probably a bad idea, because some languages (e.g. Underload, Muriel) require eval-alikes to do any nontrivial control flow.

Self-quoting programs

In some languages, e.g. 7, the initial content of memory is taken from the program itself, and the interpreter proceeds via evaluating copies of that memory. So, for example, something which (in more normal syntax) could be written as print; exit; anything would be, effectively, an eval quine.

This sort of program is unambiguously disallowed under the current quine definition; in general, though, it falls into a grey area both in terms of being literal-only, and in terms of reading its own source. (The current definition treats it like a literal-only program, although it's clearly a bit different in nature from those.) It should be noted that unlike a typical literal-only quine, this sort of program is a universal quine constructor; you can add extra code to it in order to produce a generalised quine that outputs any function of its source code.

The question

How can we improve, or outright replace, our current proper quine definition so that it can handle all these edge cases with respect to what should count as a quine?

Note that it seems likely that most proposed definitions will use different rules to disallow literal-only improper quines and source-code-reading improper quines, via some definition of "literal-only" and some definition of "source-code-reading". This means that the best possible solution may involve mixing parts of different quine definitions, meaning that they should likely be posted in different posts; in other words, we're voting on parts of a quine definition here, rather than on complete definitions.

\$\endgroup\$
  • 1
    \$\begingroup\$ By the way, if you're aware of any edge cases on quine propriety that aren't listed here, feel free to edit them into the post (or suggest an edit if you don't have the rep to edit it outright); it's more important to make sure we cover all the cases we can think of than it is to preserve the spirit of the post. Unfortunately, the question can't be marked community wiki without also making all the answers community wiki, but this post is intended in the "spirit" of a community wiki. \$\endgroup\$ – user62131 May 12 '17 at 21:53
  • 1
    \$\begingroup\$ "with our current definition, quines like the above are no longer valid 2-cyclic quines (but would be valid 3-cyclic quines)" Sorry if I'm missing something obvious, but how is this conclusion drawn? \$\endgroup\$ – ETHproductions May 13 '17 at 15:12
  • 2
    \$\begingroup\$ @ETHproductions: With a 2-cyclic quine, you're requiring that the output of the output is equal to the original program, and each part of the original program encodes the corresponding part of the output of the output, thus it's improper. With a 3-cyclic quine, you swap three times, so now each part of the program doesn't encode the corresponding part of the output of the output of the output. \$\endgroup\$ – user62131 May 13 '17 at 16:46
12
\$\begingroup\$

A proper quine must contain data that encodes both itself, and something else

Our current quine definition has the following phrase:

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.)

Although it doesn't fix all the problems with the definition, several potential issues (such as programs that rearrange themself) can be fixed like this:

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

Improving further on this would likely require an objective definition of "encodes", or else a replacement with some entirely different method of preventing literal-only quines. However, this seems to me like it's mostly just a straight improvement of the current definition, and thus would seem like a step forwards until/unless we think of something that works better.

\$\endgroup\$
  • \$\begingroup\$ Do builtins encode themselves? Ex the keyboard letters builtin on jelly. \$\endgroup\$ – Christopher May 13 '17 at 13:56
  • \$\begingroup\$ @Christopher If you're talking about ØQ, no. ØQ evaluates to the array ['QWERTYUIOP', 'ASDFGHJKL', 'ZXCVBNM']. If it evaluated to a string containing 'ØQ', and this string was used to encode the original instance of ØQ, it would be encoding itself. \$\endgroup\$ – ETHproductions May 13 '17 at 15:07
  • \$\begingroup\$ @ETHproductions I was talking about examples such as H in HQ9+ \$\endgroup\$ – Christopher May 13 '17 at 15:57
  • 1
    \$\begingroup\$ The most interesting quines do not provide an easy way to encode anything else but itself. The zip that extracts to itself is a prime example of what I consider a good quine. \$\endgroup\$ – John Dvorak May 13 '17 at 16:59
  • 2
    \$\begingroup\$ @JanDvorak The compressed data in that case encodes both itself and the ZIP format headers and any other non-compressed data. \$\endgroup\$ – LegionMammal978 May 13 '17 at 22:45
  • \$\begingroup\$ @LegionMammal978 I challenge you to create - based on the preexisting zip quine - a zip file that extracts to itself plus a file named "proof-of-success.txt" with the contents "yay!" \$\endgroup\$ – John Dvorak May 13 '17 at 22:50
  • \$\begingroup\$ @JanDvorak See this ZIP quine, which also includes an image. \$\endgroup\$ – LegionMammal978 May 14 '17 at 0:22
  • \$\begingroup\$ Great. Now modify it in the way I said :-D Shouldn't be hard, if it's a payload-quine \$\endgroup\$ – John Dvorak May 14 '17 at 0:23
  • 2
    \$\begingroup\$ Here's a proper Haskell quine possibly not fitting your statement: (\s t->s++show(succ<$>t)++show(pred<$>s))"(\\s t->s++show(succ<$>t)++show(pred<$>s))""'[r\USs,=r**rgnv'rtbb;#=s(**rgnv'oqdc;#=r((" \$\endgroup\$ – Ørjan Johansen May 17 '17 at 3:22
  • \$\begingroup\$ @ØrjanJohansen: Or in other words, a quine of the form A "B" "A" where the "A" encodes the "B" and the "B" encodes both A and "A". Clever, if somewhat ridiculous. It's going to be quite hard to objectively distinguish between that, and two literals which each encodes the other. \$\endgroup\$ – user62131 May 17 '17 at 3:25
  • \$\begingroup\$ Well, B still encodes two different parts of the program, just not itself. \$\endgroup\$ – Ørjan Johansen May 17 '17 at 3:27
  • \$\begingroup\$ Does this definition still allowed "Eval quines"? \$\endgroup\$ – Kevin Cruijssen Jul 3 '17 at 11:22
  • \$\begingroup\$ Hmm, I suppose this definition excludes most 2D quines with wrapping string literals, doesn't it? The literal encodes everything but the start literal command usually. \$\endgroup\$ – Jo King Feb 21 '18 at 10:59
  • \$\begingroup\$ @JoKing Technically at least part of such a program must be 1) encoding itself via the wrapping string literal, and 2) encoding the quote via whatever method is used. In the ><> quine ":1-or>o# (source), the # obviously encodes itself in the string literal, but also is used to generate the quotation mark via :1-. \$\endgroup\$ – ETHproductions Feb 21 '18 at 15:38
  • \$\begingroup\$ @KevinCruijssen Yes, because the evaluated string encodes both itself and whatever code is necessary to evaluate it. \$\endgroup\$ – ETHproductions Feb 21 '18 at 15:40
0
\$\begingroup\$

A quine must produce itself by processing data

To be very explicit:

  1. A quine must contain data
  2. A quine must contain commands/function calls to process above data
  3. The output of a quine must include the result of above manipulation
  4. The output of a quine must be identical to its source code
  5. A quine cannot read its own source code

This excludes:

  1. Data-only quines, as they don't manipulate data
  2. Command-only quines (such as a command that outputs the source code)

Some other notes:

  • This does not require that the entire output is generated using data processing
  • A print command is considered processing
  • When I say "A quine must contain", I mean that it must contain in its source code.
  • At a language level, the distinction between code and data is impossible. For example, is the string a = "print(1)" data or code? If we look at how a quine is executed, the distinction becomes clear.
    • If the string is evaluated (we run eval(a)), then it is code.
    • If the string is processed (we run print(a) or a.substr(4)), then it is data.
    • If we do both, then it can be considered both data and code
    • The data from step 1 must be distinct from the commands in step 2. Otherwise, we could argue that a literal 2 is simply the command print() that is passed the data 2.
\$\endgroup\$
  • 4
    \$\begingroup\$ It seems rather subjective/unclear to me what "processing data" means, especially in languages which don't have a clear separation between data and code. For example, this quine in 7 consists of nothing but a literal containing a print statement; however, in 7, if the end of the program is reached, the top literal on the stack is copied and evalled, so it ends up printing itself. Would you consider this a proper quine or not? \$\endgroup\$ – user62131 May 17 '17 at 16:03
  • \$\begingroup\$ So, if I understand you correctly, 7 iterates through characters (as literals), and puts them on the stack (so 3 is on the stack). Then it uses the first character in the source code as a command, which is 3 (or print), which prints the stack (which contains 3). If my understanding is correct, then I'd consider it a cheating quine because the first step reads the source code. \$\endgroup\$ – Nathan Merrill May 17 '17 at 17:57
  • \$\begingroup\$ It doesn't just blindly push the characters to the stack. 3 is a literal that pushes the print command 3 to the stack; that command is subsequently printed as 3 because the "boldness" isn't part of the output formatting. However, not all characters push themselves, e.g. 1 pushes 7 to the stack, and not all characters even push things (6 would escape the top of the stack immediately). \$\endgroup\$ – user62131 May 17 '17 at 18:01
  • \$\begingroup\$ @ais523 who is doing the printing? The 3 command, or is the stack implicitly printed? If the 3 command is doing the printing, then doesn't every output necessarily start with a 3? \$\endgroup\$ – Nathan Merrill May 17 '17 at 18:15
  • \$\begingroup\$ a) the 3 command (note 3 is a different command, it pushes 3 to the stack; and 3 can't be expressed in the original source, the only way to get at it is by using a 3 command and evaluating the result); b) no, you could use other commands to put something else on the stack before you ran the 3 command, and then it would print something else. The implicit part of the program is the dup+eval; everything else is explicit. \$\endgroup\$ – user62131 May 17 '17 at 18:29
  • \$\begingroup\$ @ais523 That's interesting. It also leads to arguments of "in my language, each literal is just a print command with different data". I've tried to close that loophole, see my last bullet point? \$\endgroup\$ – Nathan Merrill May 17 '17 at 18:43

You must log in to answer this question.