Quelle est «l'astuce» pour écrire un Quine?

Question

J'ai lu le papier classique de Ken Thompson Réflexions sur la confiance de confiance dans lequel il incite les utilisateurs à écrire un Quine comme introduction à son argument (lecture hautement recommandée).

Une Quine est un programme informatique qui ne prend aucune entrée et produit une copie de son propre code source comme seule sortie.

L'approche naïve est simplement de vouloir dire:

print "[insert this program's source here]"

Mais on voit rapidement que c'est impossible. Je ai fini par Écrire un moi-même Utiliser Python mais j'ai toujours du mal à expliquer "l'astuce". Je recherche une excellente explication des raisons pour lesquelles des quenes sont possibles.

Answer 1

L'astuce normale consiste à utiliser printf de telle sorte que la chaîne de format représente la structure du programme, avec un halmatoffoteur pour la chaîne elle-même pour obtenir la récursivité dont vous avez besoin:

L'exemple C standard de http://www.nyx.net/~gthompso/quine.htm illustre assez bien cela:

char*f="char*f=%c%s%c;main(){printf(f,34,f,34,10);}%c";main(){printf(f,34,f,34,10);}

Éditer: Après avoir écrit ceci, j'ai fait un peu de recherche: http://www.madore.org/~david/computers/quine.html Donne une très bonne description plus théorique de ce que sont exactement des quines et pourquoi ils fonctionnent.

Answer 2

En voici un que j'ai écrit qui utilise putchar à la place de printf; Ainsi, il doit traiter tous ses propres codes d'échappement. Mais il est% 100 portable sur tous les jeux de caractères d'exécution C.

Vous devriez pouvoir voir qu'il y a un couture Dans la représentation de texte qui reflète un couture Dans le texte du programme lui-même, où il passe du travail au début à travailler à la fin. L'astuce pour écrire un Quine est de surmonter cette "bosse", où vous basculez pour creuser votre chemin dehors du trou! Vos options sont limitées par la représentation textuelle et les installations de sortie du langage.

#include <stdio.h>

void with(char *s) {
    for (; *s; s++) switch (*s) {
    case '\n': putchar('\\'); putchar('n'); break;
    case '\\': putchar('\\'); putchar('\\'); break;
    case '\"': putchar('\\'); putchar('\"'); break;
    default: putchar(*s);
    }
}
void out(char *s) { for (; *s; s++) putchar(*s); }
int main() {
    char *a[] = {
"#include <stdio.h>\n\n",
"void with(char *s) {\n",
"    for (; *s; s++) switch (*s) {\n",
"   case '\\",
"n': putchar('\\\\'); putchar('n'); break;\n",
"   case '\\\\': putchar('\\\\'); putchar('\\\\'); break;\n",
"   case '\\\"': putchar('\\\\'); putchar('\\\"'); break;\n",
"   default: putchar(*s);\n",
"    }\n}\n",
"void out(char *s) { for (; *s; s++) putchar(*s); }\n",
"int main() {\n",
"    char *a[] = {\n",
NULL }, *b[] = {
"NULL }, **p;\n",
"    for (p = a; *p; p++) out(*p);\n",
"    for (p = a; *p; p++) {\n",
"   putchar('\\\"');\n",
"   with(*p);\n",
"   putchar('\\\"'); putchar(','); putchar('\\",
"n');\n",
"    }\n",
"    out(\"NULL }, *b[] = {\\",
"n\");\n",
"    for (p = b; *p; p++) {\n",
"   putchar('\\\"');\n",
"   with(*p);\n",
"   putchar('\\\"'); putchar(','); putchar('\\",
"n');\n",
"    }\n",
"    for (p = b; *p; p++) out(*p);\n",
"    return 0;\n",
"}\n",
NULL }, **p;
    for (p = a; *p; p++) out(*p);
    for (p = a; *p; p++) {
    putchar('\"');
    with(*p);
    putchar('\"'); putchar(','); putchar('\n');
    }
    out("NULL }, *b[] = {\n");
    for (p = b; *p; p++) {
    putchar('\"');
    with(*p);
    putchar('\"'); putchar(','); putchar('\n');
    }
    for (p = b; *p; p++) out(*p);
    return 0;
}

---

Une astuce commune est de Début de saut La Quine en écrivant un programme pour lire un fichier de texte et sortir un tableau de nombres. Ensuite, vous le modifiez pour utiliser un tableau statique et exécutez le premier programme par rapport au nouveau programme (Array statique), produisant un tableau de nombre qui représente le programme. Insérez cela dans le tableau statique, passez-le à nouveau jusqu'à ce qu'il s'installe, et cela vous fait un quiine. Mais, il est lié à un jeu de caractères spécifique (== pas à 100% portable). Un programme comme celui ci-dessus (et non le classique printf hack) travaillera la même chose sur ASCII ou EBCDIC (le classique printf Le piratage échoue dans EBCDIC car il contient ASCII à code dur).

---

Éditer:

En relue à nouveau la question, soigneusement (enfin), il semble que vous recherchiez en fait plus de technique de philosophie. L'astuce qui vous permet de sortir de la régression infinie est le à deux fer. Vous devez obtenir à la fois le programme codé et le programme élargi à partir des mêmes données: en utilisant les mêmes données 2 façons. Ces données ne décrivent donc la partie du programme entourant sa manifestation future, la Cadre. L'image de cette trame est une copie droite de l'original.

C'est ainsi que vous allez naturellement produire un dessin récursif à la main: la télévision d'une télévision. À un moment donné, vous vous fatiguez et esquissez simplement un peu d'éclat sur l'écran, car la récursivité a été suffisamment établie.

---

Éditer:

Je recherche une excellente explication des raisons pour lesquelles des quenes sont possibles.

La «possibilité» d'une quiine entre dans les profondeurs des révolutions mathématiques des XIXe et 20e siècles. Le "Classic" Quine de Wvo Quine, est la séquence des mots (IIRC)

donne faux lorsqu'il est annexé à lui-même

Ce qui est un paradoxe, semblable à la demande de David pour quelque chose qui "me rend heureux quand il est triste, et me rend triste quand il est heureux" répondu par le médaillon inscrit des deux côtés: "Cela aussi passera".

Le même genre de nouer a été étudié par les pionniers de la logique mathématique moderne tels que Frege, Russell et Whitehead, łukasiewicz et bien sûr, nos garçons Turing, Church et Thue. L'astuce qui permet de transposer La Quine du royaume du jeu de mots à une démonstration programmatique (détachant le paradoxe En partie en cours de route), était la méthode de Gödel pour coder les opérations arithmétiques elles-mêmes comme des nombres, de sorte qu'une expression mathématique entière peut être codée en un seul entier (énorme). En particulier, une fonction mathématique qui effectue un décodage de cette représentation peut être exprimée sous la même forme (numérique). Ce nombre (une fonction codée Gödel) est Code et données.

Ce trio de puissance (code, représentation, données), peut être transposé à différentes repessions. En choisissant une représentation différente (ou un chaîne Comme: bytes-> ascii-> hexadecimal-> entier), modifie le comportement du code, ce qui modifie l'apparence des données.