Talk:Quine (computing)

From Wikipedia, the free encyclopedia

Contents

[edit] Redirect?

I believe that "Quine" should redirect to the philosopher Quine and not to the present article. The former was a very significant intellectual figure of the 20th century, whereas the latter discusses amusing programs that are only interesting to hardcore programmers. Or, perhaps there should be a disambiguation page. In any case, I do feel that most people who enter "Quine" in the search box are looking for the philosopher. --Ivan 10:35, 9 June 2006 (UTC)

There is a disambiguation link at the top of the article, which works fine when there are only two pages that may be confused; a disambiguation page seems a bit much for just two pages. Also, "hardcore programmers" is a bit misleading. While it certainly takes an amount of skill to craft an good quine, I would think the idea of a self-printing program is of intellectual interest to programmers of all skills. For what it's worth, I found this page while looking for the computer topic, and only incidentally discovered they're named after the philosopher. Paulymer5 14:22, 10 June 2006 (UTC)
It's a good question...we have a program interesting to programmers and computer scientists, and a philosopher interesting to philosophers and logicians. I've read "Two Dogmas" and most of Word and Object and some of Quine's essays, and also written quines in three or four languages...but I really don't know which meaning is less familiar to the general public. Incidentally, there are also articles on Robert Quine, Richard Quine, and Edgar Quine. If we are going to keep just these two pages, with a disambiguation link from one to the other, I'd lean toward leaving the situation as it is, to minimize disruption and broken links; also because putting each topic under just its full name seems slightly more graceful than having to get into "Quine (computer program)" territory if it's not necessary. DanielCristofani 19:06, 10 June 2006 (UTC)
The MoS says that preference when dabbing articles should always be given to more popular articles. This is difficult to measure precisely, but wikilinks is the best available proxy. Here, W.V.O. Quine has 238 wikilinks, almost 6 times as many as Quine (computing), with a mere 40. Also, the computing term was named for the philosopher. Even if the wikilinks weren't so clearly in support of W.V.O., it seems logical to give prominence to the original Quine, rather than his namesake. I strongly recommend swapping the position of W.V.O.'s article with the computing article, to correspond to the MoS. Thomas B 18:12, 11 September 2006 (UTC)

[edit] capitalization

another example of why capitalization in wikipedia must be fixed: Quine the man versus quine the program. If nothing else, this has to be fixed before the wiktionary [[1]] gets too far along, since a dictionary that confuses cases is intolerable.

Wikipedia does not confuse cases. Wikipedia does require/assume that the first letter of every title is capitalized. -- Zoe

[edit] "cheating"

I believe this article is inaccurate in a rather important way. I thought a program can only be called a "quine" if it produces its own source without directly accessing it. The bottom two examples are examples of such non-quines: They just read and output the source of the program, instead of actually algorithmically producing it. In other words, the bottom two examples are examples of "cheating". Anyone agree or disagree? -- Timwi 21:37 21 Jun 2003 (UTC)

Since nobody replied, I went forth and removed the two invalid quines. I've replaced the Basic one with a true Basic quine. -- Timwi 19:24 22 Jun 2003 (UTC)
Surely 'q' in HQ9? It is a command that produces its own source... That is kind of cheating, like LIST in Basic. Mark Richards 01:24, 7 Jul 2004 (UTC)
The current JavaScript version is also cheating. I will remove it. 200.73.52.251 (talk) 21:37, 13 December 2007 (UTC)

[edit] "English version" quine

Also, I remember seeing a plaintext 'English version', 'write this', go back to step 4 etc somewhere - anyone know anything about it? Mark Richards 01:30, 7 Jul 2004 (UTC)

Should we copy the "English version" at Wiki:QuineProgram ? Or is there some other version you're thinking of ? Perhaps the one in Hofstadter's book ?

[edit] Turing-completeness

Does the ability to implement a quine in a particular programming language imply that language's Turing-completeness? Ben-Arba 03:08, Jul 31, 2004 (UTC)

For an example of a non-trivial non-Turing quine, you can build a zip file that expands to itself. 84.210.16.121 23:49, 24 August 2006 (UTC)
Of course it does not. See Hq9plus. But there is some theorem that implies something like the other way around, I think (just vaguely remembering), i.e. that a quine exists for each Turing-complete language, or something like that. --Mormegil 09:54, 18 Aug 2004 (UTC)
No chance. A language can be Turing-complete without IO capabilities. 80.192.83.27 23:34, 28 November 2005 (UTC)
When you prove a language Turing-complete, you specify a general embedding of a Turing machine in the language. If you then write a program that writes its own source on an empty tape and halts, I'd say that's a quine 84.210.16.121 23:49, 24 August 2006 (UTC)

For some discussion of a set of requirements to allow a quine to be written in a programming language see

  • Barwise, K. J. & Moss, L. (1996) Vicious Circles. On the Mathematics of Non-Wellfounded Phenomena ISBN 1-57586-008-2

In particular it's useful to have enough text processing facilities to enable partial evaluation on the language. (Often this means little more than simply concatenating strings together.) It's obvious that you don't need Turing completeness. Consider the programming language A that has one command A whose sole purpose is print the character A. In fact, in this language, all programs are quines. Sigfpe (talk) 23:15, 6 February 2008 (UTC)

[edit] LISP Quine

Wouldn't

(1)

work as a LISP quine? After all its output would be:

(1)

Right? Ben-Arba 05:44, Aug 26, 2004 (UTC)

Hmmm, would it? Isn't this an error (trying to evaluate non-existent function 1)? (Haven't used LISP for quite a long time...) But, either way, the point is that such "trivial" quines are IMHO not considered "interesting". There is even no need for it to be so "complicated". You can write just 1, LISP throws it back to you. (And maybe even an empty statement may be considered quine...) There are many languages where a trivial "program" is identical to the output, but there is no fun in that. :-) --Mormegil 07:42, 26 Aug 2004 (UTC)

[edit] How I/O-free aproaches to quines can be defined so that they exclude trivial things automatically

I have been thinking many of such things. A huge advantage of Ben-Arba's proposal above is the elimination of printing, output etc. How to eliminate the concept of “output”, (in general, all “unpure” imperative things) from the concept of quine? How to achieve a pure mathematical “idea” (in the Platonic sense) of notion quine? How to lift the concept of quine from a hacker's progamming thing to a mathematical (mathematical logic, metamathematical) concept?

Thoughts (maybe erronous) about this in /Nontrivial IO-free quine.

Physis 11:48, 30 September 2006 (UTC)

[edit] BASIC quine

Much as I admire the rather convoluted example given for the BASIC quine, I think that a simpler quine would be appropriate for an introductory text such as this encyclopædia article. BASIC is a programming language many readers are likely to be familiar with on a very basic (no pun intended) level. I think the simple quine I have added is more likely to be understood by most non-programmers, and therefore better illustrates what a quine actually is. —Psychonaut 08:01, 13 Dec 2004 (UTC)

[edit] Linux shell scripting

Would the following be considered a quine?

#!/bin/cat

--BJ 05:53, 22 Jan 2005 (UTC)

No, because it doesn't lead to bin/cat being printed out.

155.232.250.35 22:13, 12 December 2005 (UTC) DJCM

It isn't supposed to. It is interpreted as a script and calls /bin/cat with self as a parameter. A perfectly valid quine (and quite original one too). And by the way - you can write anything in the rest of the file and it will work too! --Misza13 (Talk) 22:54, 30 December 2005 (UTC)

I was bold and went ahead and added this --68.58.69.117 13:51, 9 February 2006 (UTC)/Random832

[edit] Mention to Hofstadter?

How come Douglas Hofstadter is not mentioned in the text? Wasn't he the one who coined the term? - pgimeno 10:50, 2005 May 1 (UTC)

[edit] Assembly and Machine Code

Could someone make one that does it in assembly and/or machine code? Superm401 | Talk 01:23, Jun 4, 2005 (UTC)

For assembly, it's just tedious: here are some. http://www.nyx.net/~gthompso/self_asm.txt
For machine language, it's trivial. Of course a machine language quine outputs a machine language program, so it's not very readable, but if you send the output to a file, that file is an executable identical to the original machine language program. To avoid "cheating", the data used are separate from the code that's executed, but the two can be exact copies of each other, with none of the complicated transformations needed in many quines. Here's the hex listing of one I just wrote in x86 machine language as a DOS com program (if you don't want to mess with hex editors you can get it at http://www.hevanet.com/cristofd/quine.com):
b4 40 bb 01 00 b9 12 00 ba 12 01 cd 21 b4 40 cd 21 c3
b4 40 bb 01 00 b9 12 00 ba 12 01 cd 21 b4 40 cd 21 c3
And the corresponding ASM as explanation:
mov ah, 40h ; code for the DOS general "write" function
mov bx, 1 ; "file handle" for standard output
mov cx, 18 ; length of half the file
mov dx, 256+18 ; offset in memory of the second or "data" copy
int 21h ; interrupt to call the write function, to write first copy
mov ah, 40h ; restore ah for second call, since it was wiped by return value from first call
int 21h ; second call
ret ; terminate program
DanielCristofani 09:12, 4 Jun 2005 (UTC)
I'm afraid I don't understand. I know little assembly and no machine code. How is the program generating the copy? Can you explain in more depth? Perhaps more comments(I know it's tedious). Also, please note that the program is required to output itself, not save itself to a file. Does yours do so? Superm401 | Talk 15:08, Jun 6, 2005 (UTC)
Okay...let's see. If I get any details wrong, someone can correct me. The program is a sequence of 36 bytes. Since they're machine code, they're executed directly by the computer, not needing to be compiled or interpreted by another program first; for instance, the computer's processor sees the two bytes "b4 40" as meaning "set the register AH to the value 40 (hexadecimal) or 64 (decimal)", which in assembly would be written as "mov ah, 40h".
There are various file formats for executable files, but the DOS com file is about the simplest; it consists only of a sequence of assembly-language commands the computer is to execute, and data the program may use; the entire contents of the file are loaded into memory in one big chunk, and executed from the beginning. This is in contrast to the exe format which is more complicated, containing different segments which the OS is to load into memory in different places, and give different kinds of memory protection to, and so on, plus instructions about how to do all this. Linux mostly uses the ELF format which is also fairly complicated. We choose a COM file for simplicity.
Our file consists of 18 bytes worth of commands, which are executed directly by the processor, and another 18 bytes which are identical to the first 18, but are not executed. They are instead used as data to avoid cheating. All this is loaded into memory when the program is run. Then we have to output the second 18 bytes twice, and terminate the program. To do this, we will simply use the DOS function "write" which outputs the contents of a part of memory as a raw sequence of bytes, just like our original executable. Most of the program consists of setting up the data needed to tell the "write" function exactly what to do.
(In answer to your question about files, I should clarify: like most quines, the program outputs a copy of itself to "standard output", which means it will be output to the screen unless the user chooses to redirect the output to a file by saying (e.g.) "quine.com >file" at the prompt. In terms of a program's interaction with DOS, though, writing to "standard output" is much like writing to a file; you can use the same "write" command, putting "1" where you would usually put the file handle. When sent to the screen, the output naturally looks like a jumble of non-alphabetic characters, as does the executable if you view its contents. See http://www.hevanet.com/cristofd/quinetest.png and http://www.hevanet.com/cristofd/quinetest2.png.)
More detail about setting up the data for the "write" function. We have to tell DOS that we want the write funtion (function 40H); that we want to send the data to standard output ("file" handle 1); that we want to send 18 bytes of data (the length of the second half of the file); and what memory address we want to get the data from (274, which is where the second half of the data will end up in memory; DOS loads the COM file into memory starting at address 256, and stores a variety of its own apparatus in the first 256 bytes). We put these values into specified registers, then call "int 21h" which tells DOS we want it to do something for our program. DOS will check the values of the registers and output the specified part of memory to the specified destination, which in this case is the standard output. Then we have to output the same data again. Most of the registers should still have the values we put in them before, but we will have to fix AH since DOS will have stored a value there to let us know that the original write function worked properly (or didn't). Then we call DOS to do the second write, and then use a "ret" instruction to terminate the program (the most concise way to do it). The commands to do all this take up the first 18 bytes of the program, and again the second 18 bytes are just a copy of the first 18, and are not executed but are output twice.
The thing will still run fine on Windows (tested on XP) since Windows contains a complete DOS simulator.
Feel free to ask more questions if you have any.
DanielCristofani 23:12, 6 Jun 2005 (UTC)
I understand now (Thanks). Can I add the machine code one to the article page? Since the talk pages are GFDL, I'll go ahead if you don't reply in about a week. I'd prefer your confirmation, though.Superm401 | Talk 01:22, Jun 8, 2005 (UTC)
I have no problem with that. I'd make sure to say that it's an MS-DOS COM file. The next question is of course whether to include it like ´@»�¹�ºÍ!´@Í!ô@»�¹�ºÍ!´@Í!à or like b4 40 bb 01 00 b9 12 00 ba 12 01 cd 21 b4 40 cd 21 c3 b4 40 bb 01 00 b9 12 00 ba 12 01 cd 21 b4 40 cd 21 c3 or both; either way will need some explaining. DanielCristofani 07:37, 8 Jun 2005 (UTC)
I'll go with the former. Thanks. Superm401 | Talk 00:38, Jun 17, 2005 (UTC)
I will however, after a little more thought, put in the hex and maybe even the assembly as a means to understand it, as you did above. Superm401 | Talk 00:43, Jun 17, 2005 (UTC)
I didn't include the assembly, to avoid monopolizing the space. Superm401 | Talk 02:21, Jun 17, 2005 (UTC)

[edit] Two Copies

I don't understand why would you want to have another copy of the program as the data – you might as well use the code directly as data.
B4 40 BB 01 00 B9 0E 00 BA 00 01 CD 21 C3
--Mormegil 07:38, 7 Jun 2005 (UTC)
I think the gist of a quine is that executing code may not read itself. That means extra code must be added(in a string, list of characters, etc.), which will allow the printing of the whole program. However, to accomodate the fact that the program can not be longer than itself, and the code to print the program must also be printed, some manipulation of data is necessary(printing part twice, using character escapes, replacing and/or duplicating parts of strings, etc.) to allow the whole thing to be printed. That is generally a large part of why a quine is impressive, as I understand it. In Cristofani's case, the manipulation is simple, but present. Print a non-executing part twice. However, your version accesses itself, which is considered unacceptable as a quine. This seems to be that because self-reference is used, none of the sort of data manipulation I listed above is needed. Superm401 | Talk 01:22, Jun 8, 2005 (UTC)
That's exactly what I was thinking. The rule that the working code must output a copy of itself without accessing itself as data is my best attempt to extrapolate the rule used for quines in other languages, though I freely admit that in the case of machine language it looks somewhat artificial. DanielCristofani 07:37, 8 Jun 2005 (UTC)
Ok, I get your point. But then, I must say it really looks an artificial distinction to me (in the case of machine language). :-) --Mormegil 09:16, 8 Jun 2005 (UTC)

[edit] Hex Editor Quine?

While we're on the subject I will note that since the machine-language quine is produced by typing hexadecimal digits into a hex editor, that sequence of hex digits could be considered another kind of "source code" and a quine could easily be made that would output itself in hex; that would not be a machine-language quine exactly, and I don't know quite what it would be called. DanielCristofani 07:37, 8 Jun 2005 (UTC)

Actually, I would consider that a quine as well, albeit a different one. I would say that any quine should display the source exactly as it was created. That can be accomplished in your original version by saving the meaningless ascii characters that are equivalent to the hex to a com file, then running that file, as depicted in one of the .png files you posted. That's why I am posting the ascii version, as noted above. Very strictly speaking, I would say that if you saved the file in a hex editor, it should show in hex. Therefore, what you described would be a quine. You are right that it wouldn't be a machine code quine exactly, but it would be a hex-formatted machine code quine in my view. Superm401 | Talk 00:38, Jun 17, 2005 (UTC)

[edit] Javascript Examples

I can't get any of the javascript examples to work (in the javascript console of firefox). The first one produces an error, and while the second one runs, it fails to output the alert part. I'll move them here for now.

unescape(q="unescape(q=%220%22).replace(0,q)").replace(0,q)

function quine()
{
  // any code here
}
alert(quine);

80.212.255.141 8 July 2005 13:47 (UTC)

Have you tried this at all? --67.172.99.160 20:34, 13 August 2005 (UTC)
function quine()
{
  // any code here
  alert(quine);
}

You seem to be correct that none of the ones there work. However, opening a document containing <script type="text/javascript"> document.write(unescape(q="document.write(unescape(q=%220%22).replace(0,q));").replace(0,q)); </script>

produces

document.write(unescape(q="document.write(unescape(q=%220%22).replace(0,q));").replace(0,q));


Is that sufficient? Superm401 | Talk 05:27, August 14, 2005 (UTC)


Here's a javascript quine I wrote a while ago (entered into the browsers address bar)
javascript:(foo=function(){alert("javascript:(foo="+String(foo).replace(/\s+/g,"")+")();");})();
Saibot 04:17, 29 May 2007 (UTC)

[edit] Cleanup/split badly needed

I don't think it should be the primary purpose of Wikipedia to list a quine in every <insert profanity here> computer language there is. Giving a few examples is all right, provided they are informative and commented, and not hacks; merely having a whole list of quines is just pointless. I suspect that many authors have had a lot of fun here, demonstrating their ability to use the <foo> programming language, but there are other places to do that, and we are not even approaching an encyclopedic article on quines. I suggest moving all the "sample quine" sections to another article (perhaps Quine examples or Quine list depending on whether we attempt to be complete?); I would in fact suggest simply deleting them, but maybe that is too harsh. It is probably better to let the article be a stub than this mess; however, my own discussion of quines could serve as a basis for the article. I'll wait to see what people have to say before doing anything; however, I'm putting a cleanup warning up. --Gro-Tsen 23:48, 2 September 2005 (UTC)

You're right, of course. I had a feeling this would happen eventually. We can leave the discussion up for a while to gain consensus. Eventually, I agree that we should remove all but a few diverse examples of possible quines. If you have the copyright on that external page, do feel free to copy parts of it into the Wikipedia article. Keep in mind the style guidelines though. Superm401 | Talk 00:15, September 3, 2005 (UTC)
Removing information from the encyclopedia is a big no-no - especially that much of it. I came here looking for a quine in C++ and was dissapointd to see it gone. Remember, this is the reference to the sum of all human knowledge, not just a few examples. --Alterego 22:49, 15 September 2005 (UTC)
Your premise is fundamentally flawed. The role of the encyclopedia is to collect and condense knowledge, not information. Knowledge is concerned with the meaning of information. Necessarily, compiling the encyclopedia entails ignoring huge amounts of unimportant information and removing unimportant information that was mistakenly added, as well as refactoring raw information into the meaning it represents.
This page in your preferred version is analogous to a hypothetical version of the article about trigonometric functions that instead of describing the properties and applications of the functions lists hundreds of numerical values. Indeed, there are uses of such tables, but they do not represent knowledge.
Now, I can see why you would find the C++ version important. It represents the knowledge required to construct or analyze it. But there are hundreds of programming languages, and infinitely many possible quines, and all those quines rely on the same few basic techniques. For this page, it therefore suffices to discuss the techniques used for generating quines. Examples should be used in context, to illustrate these techniques (because humans are often good at learning from example), but not instead of explanations, and certainly not gratuitously.
Fortunately, we have a Wikimedia project dedicated to the specific purpose of collecting raw information rather than knowledge. This project is called Wikisource, and I moved the list of quines there. Why is it unacceptable for you to go to the Wikisource page to get the C++ version?
Because apparently that page is scheduled to be deleted.Onlynone 21:57, 28 September 2006 (UTC)
For what it's worth, I read David's essay a while back and thought it was brilliant, certainly the best treatment of the topic I've encountered. I would support using it as a basis for a rewrite of this article. - Fredrik | talk 09:38, 16 September 2005 (UTC)
I don't mind it being at wikisource, but I didn't see a link. Cheers. --Alterego 23:36, 16 September 2005 (UTC)
To add to your rewrite comment, I think the article should take a more philisophical bent. Indirect self-reference is a very interesting concept metaphysically, (e.g., "This sentence is not a lie" and I believe Godel's incompleteness theorem uses the idea as well). Also some interesting papers on the subject e.g., * Dennett, Daniel C. (1988). "Quining Qualia". Consciousness in Modern Science.  --Alterego 23:49, 16 September 2005 (UTC)
Sigh. Somebody (not I, because I tend never to finish what I start) had had the guts to clean up the article by removing the dozen uninteresting examples in just as many languages. (To make myself clear: I completely approve that move.) But now they're starting to proliferate again. And they're just as obscure and unreadable as before. I think the article should give just one example of a quine (beside the historical example, perhaps), and it should be completely readable and un-hackish. To emphasize my point, here's the kind of program I have in mind:
/* A simple quine (self-printing program), in standard C */

/* Written by David A. Madore <david.madore@ens.fr> - Public domain */

#include <stdio.h>

/* String representation of the program code.  The string _itself_ is
 * coded as two consecutive '@' characters. */
const char progdata[] =
  "/* A simple quine (self-printing program), in stan"
  "dard C */\n\n/* Written by David A. Madore <david.ma"
  "dore@ens.fr> - Public domain */\n\n#include <stdio.h"
  ">\n\n/* String representation of the program code.  "
  "The string _itself_ is\n * coded as two consecutive"
  " '@' characters. */\nconst char progdata[] =\n@@;\n\ni"
  "nt\nmain (void)\n{\n  int i, j;\n\n  /* Print the progr"
  "am code, character by character. */\n  for ( i=0 ; "
  "progdata[i] ; i++ )\n    {\n      if ( progdata[i] ="
  "= '@' && progdata[i+1] == '@' )\n\t{\n\t  /* Here we m"
  "ust quote the code! */\n\t  printf (\"  \\\"\");\n\t  for "
  "( j=0 ; progdata[j] ; j++ )\n\t    {\n\t      if ( pro"
  "gdata[j] == '\\\\' )\n\t\tprintf (\"\\\\\\\\\");\n\t      else "
  "if ( progdata[j] == '\"' )\n\t\tprintf (\"\\\\\\\"\");\n\t    "
  "  else if ( progdata[j] == '\\t' )\n\t\tprintf (\"\\\\t\")"
  ";\n\t      else if ( progdata[j] == '\\n' )\n\t\tprintf "
  "(\"\\\\n\");\n\t      else\n\t\tprintf (\"%c\", progdata[j]);"
  "\n\t      if ( j%50 == 49 )\n\t\tprintf (\"\\\"\\n  \\\"\");\n\t"
  "    }\n\t  printf (\"\\\"\");\n\t  i++;\n\t}\n      else\n\tpri"
  "ntf (\"%c\", progdata[i]);\n    }\n  return 0;\n}\n";

int
main (void)
{
  int i, j;

  /* Print the program code, character by character. */
  for ( i=0 ; progdata[i] ; i++ )
    {
      if ( progdata[i] == '@' && progdata[i+1] == '@' )
        {
          /* Here we must quote the code! */
          printf ("  \"");
          for ( j=0 ; progdata[j] ; j++ )
            {
              if ( progdata[j] == '\\' )
                printf ("\\\\");
              else if ( progdata[j] == '"' )
                printf ("\\\"");
              else if ( progdata[j] == '\t' )
                printf ("\\t");
              else if ( progdata[j] == '\n' )
                printf ("\\n");
              else
                printf ("%c", progdata[j]);
              if ( j%50 == 49 )
                printf ("\"\n  \"");
            }
          printf ("\"");
          i++;
       }
      else
        printf ("%c", progdata[i]);
    }
  return 0;
}
OK, maybe it needs some cleaning up yet (embedded tabs are a problem on Wikipedia, and I guess I should change the non-copyright statement and avoid the GNU coding standards), but my point is that when you read this sort of program you understand how it works and you understand that it is not a hack, whereas every other <insert profanity here> quine example makes a <insert another profanity> attempt at being smart and becomes, consequently, quite useless for pedagogical purposes. --Gro-Tsen 05:16, 13 December 2005 (UTC)
If you want my suggestion, we keep four quines. One, a clearly-written in C or some similar language, as you mention. (Although C itself isn't very easy to write a clean quine in. All the backslashes complicate things a lot.) Two, the Scheme one; it's pretty clean. Three, the historical one. Four, an overly-concise one! The article mentions the game of finding the shortest quine, so we probably want to include an example of that together with the note "the game of writing the shortest quine often results in unreadable code like the following". I think we can afford to keep those four, since they won't take that much room and the article is not that long. DanielCristofani 09:34, 13 December 2005 (UTC)
Sounds like a sensible compromise. And you're right, maybe the “readable” example should be given in something other than C (yet it's difficult to find a truly neutral language that doesn't have some sort of bias which would complicate things, except perhaps going back to old things like Algol). --Gro-Tsen 04:19, 19 December 2005 (UTC)
I'm thinking if we really want one that's neutral and comprehensible to all readers, we should write it in English. Then I tried to write a good one in English, and got tangled in details, and then forgot about it, which is why I'm answering this more than a month later. I still think that may be the best idea though--comments? DanielCristofani 01:18, 10 February 2006 (UTC)
Thinking about it, how about this?
Output the following line twice, then STOP; do not obey the next instruction.
Output the following line twice, then STOP; do not obey the next instruction.
DanielCristofani 01:25, 10 February 2006 (UTC)
"Output the following line" seems like reading the source, which is verbotem. Of course, it's hard to say what's "fair" when there are no real variables. What about:
Output the quoted message on the next line twice. Put the second copy on a new line, surrounded by single quotes.
'Output the quoted message on the next line twice. Put the second copy on a new line, surrounded by single quotes.'
Superm401 - Talk 02:40, 12 February 2006 (UTC)
This gets into much the same set of issues I got bogged down in before, and was trying to sidestep with the version above:
One, it won't be obvious to everyone that "the quoted message on the next line" means everything INSIDE the quotes but not including them; people not familiar with the use-mention distinction may well interpret your program as outputting this:
'Output the quoted message on the next line twice. Put the second copy on a new line, surrounded by single quotes.'
' 'Output the quoted message on the next line twice. Put the second copy on a new line, surrounded by single quotes.' '
Two, putting the second line in quotes won't make it obvious to everyone that it's not to be executed. English does not have a distinction between instructions and data; it has the use-mention distinction, which again is NOT widely familiar.
Three, if either line got broken, it would play havoc with the sense, so I think we need to keep each line down to 80 characters for portability.
What do you think about this revised version?
The next line is not an instruction, but data; output it twice and then STOP.
The next line is not an instruction, but data; output it twice and then STOP.
DanielCristofani 08:04, 12 February 2006 (UTC)
Why do you need the " and the STOP." if you say the next line is data? Superm401 - Talk 19:12, 12 February 2006 (UTC)
Mostly to further emphasize the point, since there is a natural tendency to keep reading. More subtly, lengthening the end of the sentence gives the reader time to digest the first part of the line before the eyes automatically start to scan the next line. (I am trying to make it read smoothly for people. If I were writing for computers or logicians I might not have included that part.) Real programming languages are divided--some have an explicit termination instruction and some do not. I think it's reasonable to err on the side of being more explicit here. DanielCristofani 10:57, 15 February 2006 (UTC)
Incidentally, I like the readable C version--only thing is I would vote for K&R brace style... DanielCristofani 11:17, 15 February 2006 (UTC)
I guess you're right, K&R style is probably more standard than GNU style. I don't care much either way, so I'm following you're advice and rewriting this in K&R style (well, I basically let the indent program do the rewriting, so if you don't agree with it, don't hesitate to do more rewriting). --Gro-Tsen 16:43, 15 February 2006 (UTC)

[edit] Scheme/Lisp example

I think it's necessary to understand what's going on. On the other hand, Haskell and Python look like line noise and not very useful for understanding the idea. Discuss. ;)  Grue  15:01, 20 September 2005 (UTC)

[edit] Input

Should it be specified that quines may not take any input? This very succinctly forbids quines reading their own code and printing it, or a quine like the brainfuck code:

+[,.]

when given input:

+[,.]

What do you think? -- 04:19, 7 October 2005 (UTC)

NO. We can not set any rules on what defines a quine. That would be original research. Superm401 | Talk 04:23, 7 October 2005 (UTC)
If attempting to express or formulate the existing consensus about how a word is used constitutes "original research", Wikipedia is much farther from being able to avoid original research than I had thought. And not taking input is definitely part of the consensus idea of a quine. (This is my two bits; I'm not the original poster.) DanielCristofani 12:07, 8 October 2005 (UTC)
I only bring it up because if that is the case, a 'quine' which reads its own source file is definitely not a quine, whereas in the current article it would merely be "considered cheating". Perhaps my issue is with that phrase, as it seems vague - does it imply that such programs are indeed valid quines but are looked down upon, or that they are not really quines? (original poster) 00:09, 9 October 2005 (UTC)
If you want to describe current consensus about the meaning of the word, that's fine as long as you provide a citation. What you can't do is tweak the meaning yourself. I have no objection to making the existing rules for quines more explicit in the article. Superm401 | Talk 12:07, 10 October 2005 (UTC)

I guess I was trying to point out that current concensus is that a program which quines itself by taking itself as input (whether from a file or other source) is not a quine. The article itself supports this; I would just prefer a more concrete word than "cheating" to describe such programs - a phrasing such as "Programs which take input in order to quine themselves are not quines." or perhaps even "Programs which take input may not be quines." (original poster) -- Ben-Arba 19:59, 11 October 2005 (UTC)

In retrospect, either should be fine. Superm401 | Talk 20:21, 11 October 2005 (UTC)
My understanding of a quine is that it can't read from any file or external input once it has started executing. Thus, the file system and any user interaction are forbidden. However, the program can read its own code in in memory, if it is available at the time of execution. We could interpret the definition by stating that the program only has access to: its own data areas in memory (heaps and stacks), its own code in memory (compiled, opcoded or raw), and any API or global function that is available for early or late binding (for instance, in Smalltalk you would have access to the embedded editor object). However, whatever restriction we impose, it is always possible for somebody to bend the rules; for instance, by modifying the interpreter so that it creates a global variable with the program it loads (thus giving a BASIC program access to its uncompiled code in memory). Languages that are interpreted on-the-fly or from uncompiled sources are easier to quine, because the interpreter may offer a fairly powerful "introspection" API. Languages that are designed to be self-modifying are also easy to quine. I think that while the definition proves to be quite elastic, our main concern would be that a quine, having no true purpose, has to be either entertaining or pedagogical. Hugo Dufort 08:07, 22 November 2006 (UTC)

[edit] Scrabble Reference

"Agentsoo (→Trivia - actually it is in the Scrabble dictionary, and this fact is not interesting anyway)" actually, the word is NOT in the scabble dictionary, and, this is interesting, as it is the kind of word that if one knows it, one often wants to play in scrabble.

[edit] Javascript example

I've put a working javascript example in. It's a slight variant of one of the ones discussed above that were removed because they didn't work properly. I think this is a useful addition because it's actually extremely short, it's obvious what it's doing, and easy enough to understand if you know very little programming. It also highlights something that I think is an extremely cool feature of Javascript: functions are objects that have a toString() function that returns the source code of the function. --JulesH 2006-08-31T20:44:33Z

[Please sign your additions on talk pages.] I'm rather strongly opposed to having any quine examples other than the historic one, the C one and the Scheme/Lisp one: go any step further and dozens of users will beg to add their favorite (or personal) quine in their favorite personal language. I'm also generally opposed to having uncommented code here: quines are rather tricky programs in general and we're trying to be didactic, so they should be commented, and clarity should be favoured over conciseness. It is true that the JavaScript feature you mention is interesting, but I think that means the quine should go to the JavaScript page rather than here. Another issue is that the use of "alert" as a mean of printing could be criticized by some purists (what does it mean for a quine to "print" its own code?). But I won't revert the edit unless we can reach a clear consensus: so I'd like to hear other people's opinion on whether to keep this example or not. --Gro-Tsen 21:26, 31 August 2006 (UTC)
If the use of 'alert' is an objection, the following script produces output in a browser window:
function nl() { document.body.appendChild(document.createElement("br")); }
function o(s) { document.body.appendChild (document.createTextNode(s)); nl(); }
function a() { o(nl); o(o); o(a); o("a();"); }
a();
I'm not sure that it's particularly better, as it is substantially more complicated, but it's still readable at least. JulesH 07:41, 1 September 2006 (UTC)

[edit] Java version

I added a Java version, tested on JDK1.4.2 and Java5. It is designed for neither readability nor compactness. It is a good way to show off the limitations of character arrays and printing in the language itself. My knowledge of displaying text without long horizontal scrolling in Wikipedia is limited. Is there a simple way to wrap the text within the dashed line block without altering the Java source code? --darklilac 18:23, 22 September 2006 (UTC)

[edit] Fixed Point Demonstration versus Programming Hack

Hi! I am a former MSc student of Paul Bratley. :)

(Please note that I have rewritten this comment about 10 times today. Sorry for the inconvenience. It took me a few tries to really write down my opinion on the subject.)

Quines can be very tricky. Same could be said about anything that implies self-analysis or bootstrapping (for instance, meta-circular interpreters and bootstrapping compilers).

I think the C example given in this wiki entry is too long and, because of that, it does not clearly represent the concept.

Jxh wpda 20:03, 2 February 2007 (UTC)
That was my impression as well. Here is a C quine of my invention:
#define q(k)int main(){return!puts(#k"\nq("#k")");}
q(#define q(k)int main(){return!puts(#k"\nq("#k")");})
which IMHO better conveys the idea of invoking a program (in this case a macro) on its own source to create the quine.

We should ponder why quines are interesting; maybe the article is not absolutely clear on the matter. I can clearly see three very different interpretations (and purposes) for the concept on quines.

1) Quines as an easy-to-grasp example of the concepts of "fixed point" and "self similarity" in computer science. This is the original intent; quines can even be expanded so that a program Quine_A prints a program Quine_B that, when executed, produces Quine_A in return (quines are quite similar to autograms, and these mutual quines are similar to mutual autograms). Quines have also been used to show that a program can indeed contain its own MD5 hash. There is a true pedagogical value in there.

2) Quines as an illustration of the concepts of "self reference" or "introspection" in computer science. This is part of the original intent, although with the multiplication of programming languages and the richness of modern execution environments, these features aren't as impressive as they used to be. The focus shouldn't be on technology but rather of the theorical side, the analysis of language structure. Quines in Scheme or in Turing Machines are interesting tools; for instance, a self-replicating Turing Machine (a Von Neuman Machine maybe?) could be seen as a quine.

3) Quines as an intellectually rewarding activity or as a technical challenge, aka the "wow value". I think the current focus has been on this less important interpretation; the article and the discussion are equally focused on technicalities and programming tricks. Most quines that use a trivial language feature to achieve their goal aren't showing anything about a "fixed point", despite the fact that they may be self-referencing. While the quine can be used to expose unintended characteristics or possibilities of a language, or to explore its limits, it is a bit far from lambda calculus and fundamental theories.

Self-analysis is a natural feature of LISP dialects, in particular Scheme, because the language elements are represented as data structures the same way strings/variables are; they also share the same memory space and are equally accessible. Some languages offer more limited self-analysis features. Most high-level languages that are neither object-oriented nor list-based are very limited in that fashion. In these languages, quines are more a question of finding the fixed point than a question of experimenting with the language's introspective features.

Some approaches that have been seen "in the wild" are using the "evaluate()" function (or its equivalent) that is available in many computer languages, notably Javascript and Clipper. Some interesting technical properties in these languages is that because of late binding, it is possible to reference the "string" definition of the program in the string itself, making it easier to print code. (Note: we will use alert() instead of a print (console) function in the following examples because it is more convenient in Javascript).

Here is a sketch of such a Javascript program. It prints itself properly, except for the newline character. Thanks to late binding in eval(), the program in the variable "program" can reference the variable itself!

 var program = "alert('var program=\"' + program + '\"; eval(program)')";
 eval(program);


A way of getting around the use of eval() in Javascript would be to use DOM inspection to find the code on the page, and then to print it. Here is a working example (with its HTML outer shell):

 <script language="javascript" id="myquine">
 var qnode = document.getElementById("myquine");
 alert(qnode.text);
 </script>


A better example would also include a printout of the HTML "outer shell" itself (which could be considered as part of the program itself, although this affirmation could be disputed). While it is a bit harder, the code is still short:

 <script id="myquine" language="javascript">
 var qparent = document.getElementById("myquine");
 var qstring = "<"+qparent.nodeName;
 var qattrs = qparent.attributes;
 for(i=0;i<qattrs.length;i++)
 {
   qstring += " " + qattrs[i].nodeName + "=\"";
   qstring += qattrs[i].nodeValue + "\"";
 }
 qstring += ">" + qparent.text + "</"+qparent.nodeName+">";
 alert(qstring);
 </script>


These are good examples of "programmatic tricks" that produce quines, rather than "fixed points". Maybe the examples on the topic page could cover both, since they are equally interesting.

[edit] Another JavaScript quine

I tried to write another JavaScript quine:

(function(){alert("(" + arguments.callee.toString() + ")();");})();

You can always adopt alert to something else, such as in a JavaScript shell, you could:

(function(){print("(" + arguments.callee.toString() + ")();");})();

Or simply write the function code in the HTML document:

(function(){document.write("(" + arguments.callee.toString() + ")();");})();

This works because the toString() method, sometimes even toSource() in some browsers, is available for any function, for example...

var x = function(){var blah;};
x.toSource() == "function(){var blah;}"

Note: toString() results in a formatted source while toSource() results in a one-liner. In addition with the fact that for any function, arguments.callee refers to the function itself, this quine is possible.

kourge 04:16, 5 January 2007 (UTC)

[edit] C quine needlessly complicated

I've seen oneliners based on the same idea. And because they're oneliners, you can see the whole structure in one go, no need for scrolling and figuring things out.

main(a){a="main(a){a=%c%s%c;printf(a,34,a,34);}";printf(a,34,a,34);}

(Author: Dario Dariol)

This isn't the shortest there is - you could put the a="..." bit inside the printf, but perhaps that might result in evaluation order problems; better not to do it.

It also assumes 34 is the character code for ". You can fix this at the expense of (a little) clarity. 82.139.85.127 17:51, 7 February 2007 (UTC)

This example has various problems: it uses a long line (over 70 characters), has no comments at all (very bad for an example of C code), and assumes 34 and 10 are character codes for quotes and newline. Until these problems are fixed, I am reverting to the previous example. --Gro-Tsen 06:49, 18 April 2007 (UTC)
I don't see the lack of comments as being a very strong rationale to remove the entry. Except for the basic example (which I thought in the classic example would just be a one liner consisting of the LIST command), none of the other examples have comments. Below is one of my invention that addresses your other concerns. The code defines a macro on the first line. Invoking the macro with an argument creates a C program that outputs the argument on the first line, and outputs the argument being passed to the macro on the second line. The second line passes the macro definition to the macro, creating a quine. --Jxh wpda 23:49, 23 April 2007 (UTC)
#define q(k)int main(){return!puts(#k"\nq("#k")");}
q(#define q(k)int main(){return!puts(#k"\nq("#k")");})
Your example lacks a prototype for puts so it is not valid, unfortunately (it also lacks a proper declaration of main, and it is very badly formatted). I think at least one quine example should show clearly that there is no need for a quine to be terse, obscure, uncommented, or formatted in a way that is more obscure than the way programs are usually formatted—or any such thing. Now perhaps we should give two C examples, one terse and one verbose, but I really think at least one example should be given in the article of a quine that reads like a completely normal program, with comments, ordinary indentation, no language hacks whatsoever, and so on. --Gro-Tsen 01:24, 25 April 2007 (UTC)
The declaration for main is fine, for all flavors of C including C99. The puts prototype is trivial to add for C99 compliance, but I authored the program pre C99. A C99 compliant program doesn't require a return, since falling off the end of main without a return denotes success in C99 (but this is not true pre C99). I don't know if utilizing a documented feature of the language can really be considered a hack. I don't really have a problem with including two examples either. As to which is more esthetically pleasing (in either an artistic or pragmatic sense), everyone has their own tastes, so I don't think it is worth to delve too much into that topic. (As an aside, this will not compile if your compiler is set in C++ mode. It is a C program. With GCC 3.4, I used the following options: -W -Wall -O -ansi -std=c99 -pedantic.) --Jxh wpda 16:59, 25 April 2007 (UTC)
#define q(k)int puts();int main(){return!puts(#k"\nq("#k")");}
q(#define q(k)int puts();int main(){return!puts(#k"\nq("#k")");})
Look, this may be technically valid code, but nobody would write stuff like this outside a quine—no reasonable coding standards allow such monstrosities—and I don't think the fact that the program is a quine should allow any more liberty for obfuscation than any other code example. If you insist on adding such a concise-and-unreadable example to the article, suit yourself, but if you wish to replace the existing example, then the replacement should be at least as good in all aspects of readability and formatting. This is an example of code in an encyclopedia we're writing! it should be clear and readable, worthy of being shown to novice C programmers to illustrate programming style, not an obfuscated hack that uses arcane subtleties of the preprocessor or of the way functions can be prototyped. We don't want people imitating that sort of style in real programs, do we? --Gro-Tsen 21:57, 26 April 2007 (UTC)
I agree that my quine is not a good example of C programming style. I don't understand why that makes it a bad C quine example. I don't intend to replace the existing example. --Jxh wpda 21:20, 30 April 2007 (UTC)

[edit] Add VB quine?

I know that this page has been overflowing with quines, but I'm asking this for a reason. You see, the above code depends on the availability of a command to quickly insert a string into itself (printf). In VB no such thing is available. Giving a quine in VB shows that you can easily do the work yourself, making this type of quine possible in practically any language.

(Program broken over multiple lines for clarity. For a real quine, replace every linebreak with ": ".)

Sub Main()
A = "Sub Main(): A = "": B = Left(A, 17): A = Mid(A, 17): MsgBox B & B & A & A: End Sub"
B = Left(A, 17)
A = Mid(A, 17)
MsgBox B & B & A & A
End Sub

(Note: this was written literally within one minute. Better VB quines may exist.) 82.139.85.127 18:36, 7 February 2007 (UTC)

[edit] PHP Quine

A quine in PHP seems really easy to do:

<?php readfile(__FILE__); ?>

This will display properly when run via CLI, but won't appear properly in a web browser (due to the browser interpreting the < as the start of a HTML tag). For something that displays properly in a browser:

<?php echo htmlentities(file_get_contents(__FILE__)); ?>

I guess it's also easy for most other interpreted languages as well :)

—— Daniel15 (Talk/Contribs) 04:48, 14 April 2007 (UTC)

Read the article first: Note that programs which take input are not considered quines. This would allow the source code to be fed to the program via keyboard input, opening the source file of the program, and similar mechanisms. --Mormegil 08:21, 26 April 2007 (UTC)

[edit] Self-replicating formula

Here's something interesting [2] - a formula that plots itself. Not sure if it counts as a proper quine, but might be worth a mention. 131.111.195.8 20:42, 14 May 2007 (UTC)

Since the number n is given separately, I think this formula is a sham. It wouldn't be if n were "printed" along with the formula, something which is possible for reasons similar to the reason quines exist, but as such it's just, one might say, an implementation of a printing function in the language of mathematics. Of course, it could still be mentioned in the article, but with a disclaimer. --Gro-Tsen 10:10, 15 May 2007 (UTC)
Well it looks like n is just to show where on the plot the formula actually appears. It isn't included in the formula itself. 131.111.195.8 11:43, 15 May 2007 (UTC)
The point is that depending how n is chosen one could print anything, so here n is chosen so that it prints the generating rule. —Preceding unsigned comment added by 24.201.100.166 (talk) 02:14, 23 November 2007 (UTC)

Tupper's Self-Referential Formula is not a quine because it does not output its complete source code. The bounds for x and y are part of the source code for creating the image. This means that N is part of the source code too, but it is not included in the image. If Tupper's Formula were a quine then so would the program that outputs every possible string of length equal to or less than its source code length. If it is not a quine, why link to it without a disclaimer? Either it should not be an external link or it should have a short clarification. This is justification for the edit "not really a quine, but easy to confuse with one". DavidCreswick (talk) 00:37, 21 January 2008 (UTC)

It's even worse than that, because if you look closely, you'll notice that all the actual information is located in n. So it's the mathematical equivalent of a program that can print its own source code if it has access to its source code as a datafile. Shinobu (talk) 22:26, 23 March 2008 (UTC)

[edit] Changed the javascript example

When I tested the given javascript example, it introduced extra linebreaks and indentations, thus made it not a so true quine. I decided to change it to a hook on window.onload and use that objects toSource to add a text node to the body of a page (assuming we are using a html page as base). At least for me on firefox, it reproduce a 100% identical copy:

window.onload = function() { document.body.appendChild(document.createTextNode(window.onload.toSource().replace(/.*?\{(.*)\}.*/, "window.onload = function() { $1 }"))); }

→AzaToth 15:52, 7 June 2007 (UTC)

[edit] Simple Perl quine

#!/usr/bin/perl -w
use strict; 
use LWP;
use HTTP::Request;
my $ua = LWP::UserAgent->new();
$ua->agent('Mozilla/5.0');
my $url = "http://en.wikipedia.org/wiki/Talk:Quine_(computing)";
my $request = HTTP::Request->new(GET => $url);
my $response = $ua->request($request);
my $page = $response->content;

my $beginning = '#!/usr/bin/perl';
my $end = q'print \$code;';
$page =~ /($beginning.*$end)/s;
my $code = $1 . "\n";
#wikipedia messes up greater-than symbols
my $gt = chr(62);
$code =~ s/\>/$gt/g;
print $code;

I have a gut feeling that this is considered cheating... --Snarius (talk) 17:27, 18 December 2007 (UTC)

Yes, because it has the ability to take input. Shinobu (talk) 22:21, 23 March 2008 (UTC)

[edit] ACM Spam?

The link to "Reflections on Trusting Trust" (section "Further reading") is

http://www.acm.org/classics/sep95/

which redirects to

http://portal.acm.org/toc.cfm?id=SERIES11430&type=series&coll=ACM&dl=ACM

which is a site that doesn't even contain the words "reflections" or "trust". Can anyone repair that link, or should we remove this spam entirely?

Vog (talk) 18:51, 20 January 2008 (UTC)

Sigh. This sort of thing makes me want to hurt someone badly. I really wish webmasters had a compulsory course in the importance of lasting and durable URL's. Well, I put up another link to the same text. Thanks for pointing this out. --Gro-Tsen (talk) 00:06, 21 January 2008 (UTC)