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

Question

leí el papel clásico de Ken Thompson Reflections on Trusting Trust en la que se solicita a los usuarios a escribir Quine como una introducción a su argumento (muy recomendable leer).

Un quine es un programa de computadora que no toma entrada y produce una copia de su propio código fuente como su único resultado.

El enfoque ingenuo es simplemente querer decir:

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

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

Answer 1

El truco lo normal es utilizar printf tal que el formato de cadena representa la estructura del programa, con un lugar titular de la propia cadena para obtener la recursividad que necesita:

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

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

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

Answer 2

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

Usted debe ser capaz de ver que hay una costura en la representación de texto que refleja una costura en el propio texto del programa, donde cambia de trabajar en el inicio de trabajos en el cabezal. El truco para escribir un Quine es superar esta "joroba", donde cambias a tu camino 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 Jump Start la quine escribiendo un programa para leer un archivo de texto y la salida de un conjunto 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. Inserta eso en la matriz estática, ejecútalo de nuevo hasta que se estabilice, y eso te da una quine. Pero, está vinculado a un juego de caracteres específico (== no es 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 codificado).

---

edición:

La lectura de la pregunta de nuevo, con cuidado (por fin), parece que realmente está buscando más la filosofía menos técnica. El truco que le permite salir de la regresión infinita es two-fer. Debe obtener tanto el programa codificado como el programa expandido con 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 directa del original.

Así es como harías naturalmente para producir un dibujo recursivo a mano: la televisión de una televisión. En algún momento te cansas y simplemente haces un poco de resplandor sobre la pantalla, porque la recursión se ha establecido lo suficiente.

---

edición:

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

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

produce falsa cuando se adjunta al mismo

que es una paradoja, similar a la petición de David como algo que "me hace feliz cuando está triste, y me pone triste cuando está 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 chicos de Turing, la iglesia y Thue. El truco que hace posible transponer el Quine del reino de los juegos de palabras a una demostración programática (desenroscando la paradoja parte en el camino), era el método de Gödel de codificar las operaciones aritméticas mismas como números, por lo que toda una expresión matemática se puede codificar en un entero único (enorme). En particular, una función matemática que realiza una descodificación de esta representación se puede expresar en la misma forma (numérica). Este número (una función codificada por Gödel) es tanto código como datos.

Este power-trio (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.