Talk:Quine

Contents

1 capitalization 2 "cheating" 3 "English version" quine 4 Turing-completeness 5 LISP Quine 6 BASIC quine 7 Linux shell scripting 8 Mention to Hofstadter? 9 Assembly and Machine Code 9.1 Two Copies 9.2 Hex Editor Quine?

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] (http://wiktionary.org)] 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

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

"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 ?

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)

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)

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)

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)

Linux shell scripting

Would the following be considered a quine?

#!/bin/cat

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

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)

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

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)

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)

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)