3

This quine I saw in an article by Ken Thompson (read here) isn't reproducing the same code. I was just curious why it's not working? is the code obsolete now?.

code of quine:

char s[] = {
        '\t',
        '0',
        '\n',
        '}',
        ';',
        '\n',
        '\n',
        '/',
        '*',
        '\n'
};

/*
 *The string s is a representation of the body
 *of this program from '0'
 * to the end
 */

main(){
        int i;

        printf("char\ts[] = {\n");
        for(i = 0; s[i]; i++)
                printf("\t%d, \n", s[i]);
        printf("%s",s);
}

output:

char    s[] = {
        9,
        48,
        10,
        125,
        59,
        10,
        10,
        47,
        42,
        10,
        0
};

/*

These are the compiler warnings on compiling (self_reproducing.c is the filename):

self_reproducing.c:20:1: warning: return type defaults to ‘int’ [-Wimplicit-int]
   20 | main(){
      | ^~~~
self_reproducing.c: In function ‘main’:
self_reproducing.c:23:2: warning: implicit declaration of function ‘printf’ [-Wimplicit-function-declaration]
   23 |  printf("char\ts[] = {\n");
      |  ^~~~~~
self_reproducing.c:23:2: warning: incompatible implicit declaration of built-in function ‘printf’
self_reproducing.c:1:1: note: include ‘<stdio.h>’ or provide a declaration of ‘printf’
  +++ |+#include <stdio.h>
    1 | char s[] = {

Oops! I ignored the 213 lines deleted line. So the question should be —what is the whole quine that is mentioned in the article?

Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
Manik
  • 573
  • 1
  • 9
  • 28
  • 1
    I don't think that is a quine. I think that is part of a quine. – user253751 Jul 01 '20 at 14:56
  • 2
    The warnings ain't exactly rocket science to fix, `#include `. – Lundin Jul 01 '20 at 14:58
  • With added includes it is not a quine anymore. You will probably have to ask your compiler for more tolerance. After all, there are only warnings. – Yunnosch Jul 01 '20 at 14:59
  • *"Figure 1 shows a self-reproducing program in the C programming language. This entry is much too large to win a prize, but it demonstrates the technique and has two important properties that I need to complete my story: 1) This program can be easily written by another program. 2) This program can contain an arbitrary amount of excess baggage that will be reproduced along with the main algorithm. In the example, even the comment is reproduced."* author says this about figure 1 in the article. – Manik Jul 01 '20 at 15:01
  • @Lundin I just added the compiler warnings if someone wants to see. The last question is asked about the problem as a whole. – Manik Jul 01 '20 at 15:03
  • If this is just the part of the quine then can someone tell what is the whole quine? – Manik Jul 01 '20 at 15:12
  • 2
    @Manik It would of course be the rest of the string characters needed to represent the remainder of the program. The author presumably abridged the program for the purpose of being able to more easily illustrate their point, without driving it home by taking a whole page – underscore_d Jul 01 '20 at 15:29
  • I guess you didn't see this line in the paper: `213 lines deleted` – stark Jul 01 '20 at 15:46
  • You could look at [C/C++ program that prints its own source code as its output](https://stackoverflow.com/a/10240050/15168) — amongst other examples. – Jonathan Leffler Jul 01 '20 at 16:28
  • 1
    From the output of this program, it can be seen that `'*'` produces `42`... One more instance of this [mystical number](https://en.wikipedia.org/wiki/Phrases_from_The_Hitchhiker%27s_Guide_to_the_Galaxy#The_Answer_to_the_Ultimate_Question_of_Life,_the_Universe,_and_Everything_is_42). What an eerie coincidence! – chqrlie Jul 01 '20 at 16:55

4 Answers4

2

I take that "not working" to mean not 'giving compiler warnings' - because the reasons for those are self-evident - but instead what else you wrote:

This quine [...] isn't reproducing the same code

The quine is self-reproducing, once we add back (213 lines deleted) that the author abridged and you deleted - which represent the rest of the code, plus the 0 NUL terminator that ends the array of chars:

/*
 * The string s is a representation of the body
 * of this program from '0'
 * to the end
 */

Your confusion seems to stem from how the program prints the integer ASCII values of the characters in said array, but it originally declared those characters like '\t', '\n', and so on. But integers with appropriate values are valid chars, so the code is self-reproducing, even if the elements are formatted as integers instead of 'c'haracters as in the original source. Either way, we end up with an array of the same chars; just that array was initialised in a different but equivalent fashion.

Why does it print them as integers? Because that is far easier/shorter than having to quote, conditionally escape, and so on for each element. It maps to the same machine code / array contents but requires a lot less faff to program the quine.

The author even wrote this!

(The purist will note that the program is not precisely a self-reproducing program, but wIll produce a self-reproducing program.)

As for the edited/added question, the whole quine would of course add the rest of the characters needed to represent the remainder of the program. The author presumably abridged the program for the purpose of being able to more easily illustrate their point, without driving it home by taking a whole page.

underscore_d
  • 6,309
  • 3
  • 38
  • 64
  • but isn't a quine supposed to output it's own code? where is the ```main() ```, ```printf``` etc. part? – Manik Jul 01 '20 at 15:16
  • @Manik: In the `(213 lines deleted)` which Thompson deleted from the listing because it would have gotten excessively long. Note that the last three characters that **are** listed are the beginning of the comment (`'/', '*', '\n'`). – DevSolar Jul 01 '20 at 15:21
  • I still don't see how this program will print the ```main(){...}``` part?. It's only printing the ```char s[] = {...}``` part – Manik Jul 01 '20 at 16:43
  • ...which in the full code would contain the rest of the characters in the source file, including all of `main()`. There's just not much point spending time showing you how that would look. – underscore_d Jul 01 '20 at 16:56
  • @Manik "*I still don't see how this program will print the `main(){...}` part?*" - It won't and it shouldn't, too. Read all of our answers carefully. – RobertS supports Monica Cellio Jul 01 '20 at 16:57
2

The code sequences '/', '\t', '\n', etc., are just mnemonics used to tell the compiler what character codes to use. It saves us from having to look-up the ASCII codes for them. In the case of some of the control codes, particularly carriage returns and new-lines, the actual code is architecture dependent, so these mnemonics are also there to make the code portable across operating systems. The point of the article however wasn't about writing quine's, it was about how easily systems can be hacked by the coders who operate and maintain them, without leaving any obvious foot-prints.

Context is important here. Thomson was attacking a vintage Unix system that is unlikely to be running on anything in existence today.

From the referenced article:

In college, before video games, we would amuse ourselves by posing programming exercises. One of the favorites was to write the shortest self-reproducing program.

A "self reproducing program" makes no mention of reproducing it's own source code.

jwdonahue
  • 6,199
  • 2
  • 21
  • 43
  • 1
    So what did Thompson mean by self-reproducing program then? – Manik Jul 01 '20 at 16:38
  • It does reproduce itself, when you consider the ultimate meaning of the code and how it would translate to machine code and characters in memory, both of which are the same regardless of whether the `char` string was initialised from integers or `'code points'`. – underscore_d Jul 01 '20 at 16:57
  • @Manik, I think his example actually generates source code, but that's not really point of the article, at least from my first read anyway. A program can generate machine or intermediate code of any kind, including human readable source. He was really trying to make the point, that if you can't trust the humans who produce and maintain the computing systems we use, you're doomed. So an exact reproduction of his original source code, wasn't the point. He simply demonstrated the self-replication concept (among the first to do so publicly). – jwdonahue Jul 01 '20 at 17:10
1

"This quine I saw in an article by Ken Thompson (read here) isn't reproducing the same code. I was just curious why it's not working?"

It does not give the expected output because it isn't meant to be a reproducible example for a "quine".

To cite Ken himself about the definition of a "quine" (emphasize mine):

"More precisely stated, the problem is to write a source program that, when compiled and executed, will produce as output an exact copy of its source."

The code shown doesn't reproduce an exact copy of its whole source code as output, because it doesn't meant to.

Ken even admit that himself (emphasize mine):

"Figure 1 shows a self-reproducing program in the C programming language. (The purist will note that the program is not precisely a self-reproducing program, but will produce a self-reproducing program.) This entry is much too large to win a prize, but it demonstrates the technique and has two important properties that I need to complete my story: ..."

and which is also proven by 213 lines deleted in Ken's code.

It is just meant to demonstrate what a "quine" program suppose to be and that its purpose is to print its source code.

"Is the code obsolete now?"

Apart from that the code is missing parts, to classify it as strict "quine",

Yes, the code is obsolete now. It was made back in 1984, before C was even standardized by ANSI and for a complete different machine like the ones we now have today.

This is proven by the warnings you get.

To compile this code without warnings and including the header file stdio.h, you would need a compiler (or a appropriate compiler option, like f.e. std=c89) which supports an implicit declaration for the printf() function, which is no longer supported since C99 (current standard is C18).

Note, that the compiler/linker will probably nonetheless link to the definition of printf() correctly, but it is an obsolete feature and not compliant to a modern standard.

Also the notation main() is no longer supported. It shall be int main (void) to be strictly standard-compliant or at least int main() which use is deprecated as it provides no prototype for main() or equivalent*, if no arguments are passed to main().

*The return type can be different but has to be compatible to an int.

"What is the whole quine that is mentioned in the article?"

It is just an example for a "quine". There is no full original example public available. Perhaps the original sleeps anywhere at an archive. But you can develop it by yourself if you follow the guideline that every piece of code needs to be outputted.

Reference "Reflections on Trusting Trust", Ken Thompson, August 1984:

RobertS supports Monica Cellio
  • 14,524
  • 7
  • 33
  • 80
0

You most probably did not include "<stdio.h>" library.

just add

    #include <stdio.h>

on top of your code.

The very same solution is advised in your compiler error

SunGrow
  • 87
  • 1
  • 8
  • 2
    It is then not a quine anymore. You are aware of the meaning of that word, aren't you? – Yunnosch Jul 01 '20 at 15:01
  • Where do you see a compiler error? I only see warnings. – Yunnosch Jul 01 '20 at 15:02
  • I did add ```#include ``` but the output remains the same though the warnings went away. I think it has not been added intentionally to make it a quine. – Manik Jul 01 '20 at 15:09
  • 2
    @RobertSsupportsMonicaCellio: This is a pre-C89 implicit declaration (obviously, as the paper is from 1984); the `#include ` is not necessary. The actual output logic is linked in via libc, and does not require the header (in that old C version). ;-) – DevSolar Jul 01 '20 at 15:26
  • @DevSolar Yes, of course. But OP is asking "*I was just curious why it's not working? is the code obsolete now?*" - So the answer should just be plain yes. – RobertS supports Monica Cellio Jul 01 '20 at 15:28
  • 2
    @RobertSsupportsMonicaCellio: It's also not working because the code OP posted is incomplete (see other answer). And "yes, it's obsolete, because {old-style implicit declaration}" would be a correct answer, while "you have to include ``" isn't, as it defeats the idea of a quine. – DevSolar Jul 01 '20 at 15:31
  • @DevSolar Yes, that makes sense. – RobertS supports Monica Cellio Jul 01 '20 at 15:32
  • One could argue that it is actually harder to write the largest quine than to write a small one. If you include the standard library headers or other "bloat", you have a more difficult task to get it 100% correct. – jwdonahue Jul 01 '20 at 17:39