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

Question

Leí el papel clásico de Ken Thompson Reflexiones sobre confianza de confianza en el que solicita a los usuarios a escribir un Quine Como introducción a su argumento (lectura muy recomendable).

Un quine es un programa de computadora que no toma 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 rápidamente ve que esto es imposible. he finalizado escribiendo uno yo mismo Usar Python pero aún así tener problemas para explicar "el truco". Estoy buscando una excelente explicación de por qué son posibles Quines.

Answer 1

El truco normal es usar printf de tal manera que la cuerda de formato representa la estructura del programa, con un poseedor de lugar para la cadena en sí para obtener la recursión que necesita:

El ejemplo de C estándar 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);}

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

Answer 2

Aquí hay uno que escribí que usa putchar en vez 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ías poder ver que hay un costura en la representación de texto que refleja un costura En el texto del programa en sí, donde cambia de trabajar al principio a trabajar en el final. El truco para escribir un quine es superar esta "joroba", donde cambias a cavar a tu manera afuera del agujero! Sus opciones están limitadas por la representación textual y las instalaciones 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 buen inicio El quine escribiendo un programa para leer un archivo de texto y generar una matriz 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 serie de número que representa el programa. Inserte eso en la matriz estática, ejecutarlo nuevamente hasta que se asienta hacia abajo, y eso le consigue una quine. Pero, está vinculado a un conjunto de caracteres específico (== no 100% portátil). Un programa como el anterior (y no el clásico printf hack) funcionará igual en ASCII o EBCDIC (el clásico printf Hack falla en EBCDIC porque contiene ASCII codificada dura).

---

editar:

Al leer la pregunta nuevamente, cuidadosamente (finalmente), parece que en realidad está buscando más filosofía menos técnica. El truco que te permite salir de la regresión infinita es el de dos. Debe obtener tanto el programa codificado como el programa ampliado 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 futura manifestación, el cuadro. La imagen dentro de este cuadro es una copia directa del original.

Así es como naturalmente producirías un dibujo recursivo a mano: la televisión de una televisión de televisión. En algún momento te cansas y simplemente dibuja algo de mirada sobre la pantalla, porque la recursión se ha establecido suficientemente.

---

editar:

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

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

produce falso cuando se agrega a sí mismo

Lo cual es una paradoja, similar a la solicitud de David de algo que "me pone feliz cuando está triste, y me entristece cuando feliz" respondió 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 niños Turing, Church y Thue. El truco que hace posible transponer el quine del reino del juego de palabras a una demostración programática (desenredando el paradoja Parte en el camino), fue el método de Gödel para codificar las operaciones aritméticas en sí mismas como números, por lo que una expresión matemática completa puede codificarse en un solo entero (enorme). En particular, una función matemática que realiza una decodificación de esta representación puede expresarse en la misma forma (numérica). Este número (una función codificada por Gödel) es Tanto el código como los datos.

Este poder-trio (código, representación, datos) puede transponerse a diferentes repesentaciones. Eligiendo una representación diferente (o un cadena Como: bytes-> ascii-> hexadecimal-> entero), altera el comportamiento del código, que altera la apariencia de los datos.