quine - para - los 17 comandos de busqueda

¿Cuál es el "truco" para escribir un Quine?

Question

Leí el artículo clásico de Ken Thompson, Reflections on Trusting Trust, en el que solicita a los usuarios que escriban un Quine como introducción a su argumento (lectura muy recomendable).

Una quine es un programa de computadora que no toma ninguna entrada y produce una copia de su propio código fuente como su única salida.

El enfoque ingenuo es simplemente querer decir:

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

Pero uno ve rápidamente que esto es imposible. Terminé escribiendo uno mismo usando Python, pero todavía tengo problemas para explicar "el truco". Estoy buscando una excelente explicación de por qué los Quines son posibles.

Answer 1

Aquí hay uno que escribí que usa putchar lugar de printf ; Por lo tanto, tiene que procesar todos sus propios códigos de escape. Pero es% 100 portátil en todos los conjuntos de caracteres de ejecución C.

Debería poder ver que hay una costura en la representación de texto que refleja una costura en el texto del programa en sí, donde cambia de trabajar en el principio a trabajar en el final. El truco para escribir un Quine es superar esta "joroba", ¡donde cambias a cavar para salir del agujero! Sus opciones están limitadas por la representación textual y las facilidades de salida del idioma.

#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;
}

Un truco común es hacer que comience la sesión de escritura escribiendo un programa para leer un archivo de texto y generar una serie de números. Luego lo modifica para usar una matriz estática y ejecuta el primer programa contra el nuevo programa (matriz estática), produciendo una matriz de números que representa el programa. Insértelo en la matriz estática, ejecútelo nuevamente hasta que se estabilice, y eso le dará una quine. Pero , está vinculado a un conjunto de caracteres específico (== no 100% portátil). Un programa como el anterior (y no el hacking clásico de printf ) funcionará igual en ASCII o EBCDIC (el hackeo clásico de printf falla en EBCDIC porque contiene ASCII codificado).

editar:

Al leer la pregunta de nuevo, con cuidado (finalmente), parece que en realidad estás buscando más técnica menos filosofía. El truco que te permite salir de la regresión infinita es la doble fer . Debe obtener el mismo programa codificado y el programa expandido de los mismos datos: utilizando los mismos datos de 2 maneras. Por lo tanto, estos datos solo describen la parte del programa que rodea su manifestación futura, el marco . La imagen dentro de este marco es una copia recta del original.

Así es como naturalmente harías un dibujo recursivo a mano: la televisión de un televisor de televisión. En algún momento te cansas y solo esbozas un poco de deslumbramiento sobre la pantalla, porque la recursión ha sido suficientemente establecida.

editar:

Estoy buscando una excelente explicación de por qué los Quines son posibles.

La "posibilidad" de un Quine se adentra en las profundidades de las revoluciones matemáticas de los siglos XIX y XX. El quine "clásico" de WVO Quine, es la secuencia de palabras (IIRC)

cede falso cuando se adjunta a sí mismo

que es una paradoja, similar a la solicitud de David de algo que "me hace feliz cuando estoy triste, y me pone triste cuando está feliz", contestado por el medallón inscrito en ambos lados: "esto también pasará".

El mismo tipo de nudo fue investigado por los pioneros de la lógica matemática moderna como Frege, Russell y Whitehead, Łukasiewicz, y por supuesto, nuestros muchachos Turing, Church y Thue. El truco que hace posible transponer el Quine del reino del juego de palabras a una demostración programática (desenrollando la parte de la paradoja a lo largo del camino), fue el método de Gödel de codificar las operaciones aritméticas como números, por lo que se puede codificar una expresión matemática completa en un solo entero (enorme) En particular, una función matemática que realiza una decodificación de esta representación se puede expresar en la misma forma (numérica). Este número (una función codificada en Gödel) es código y datos.

Este trío de poder (Código, Representación, Datos) se puede transponer a diferentes representaciones. Al elegir una Representación diferente (o una cadena como: bytes-> ASCII-> hexadecimal-> entero), altera el comportamiento del Código, lo que altera la apariencia de los Datos.

Answer 2

El truco normal es usar printf modo que la cadena de formato represente la estructura del programa, con un marcador de posición para que la cadena obtenga la recursión que necesita:

El ejemplo estándar de C de http://www.nyx.net/~gthompso/quine.htm ilustra esto bastante bien:

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

edit : después de escribir esto, hice un poco de búsqueda: http://www.madore.org/~david/computers/quine.html ofrece una descripción muy buena y más teórica de qué son exactamente las quines y por qué funcionan.