Programas autorreplicantes

Desde que empecé a escribir en el blog de Lobosoft, deseaba dedicar una entrada a los quines, ya que me llamaron la atención desde siempre por sus peculiares características. Un quine, tal y como lo describe la Wikipedia, es un programa (un metaprograma, en realidad) capaz de replicarse a sí mismo. Es decir, que al ejecutarlo produce como salida una copia de su propio código fuente. Esto, que podría parecer una obviedad, no lo es tanto por la principal restricción que se les impone, a saber:

Un quine no puede abrir el fichero en el que está escrito (lenguajes interpretados) ni el de su código fuente (lenguajes compilados) para escribirlo en pantalla.

De este modo, la sencillez aparente que parecía subyacer en la programación de los quines desaparece por completo. Para verlo más claramente, estudiemos cómo programaríamos un quine en lenguaje C:

[c]
#include

int
main (void)
{
printf("#include \n\nint\nmain (void)\n{\n");
printf("printf(\"#include \\n\\nint\\nmain (void)\\n{\\n\");\n");
[/c]

Empezamos a programarlo y... ¡sorpresa! Parece que entramos en un bucle infinito. El programa comienza con la inclusión de los ficheros de cabecera necesarios y la declaración de la función main. A continuación, con printf escribimos en la salida estándar una cadena de caracteres con el comienzo del programa. En ese momento, hay que escribir una sentencia que escriba a la anterior, y ahí comienza nuestro ciclo sin fin.

Para resolver esta recursividad inherente a la propia escritura del quine, existen varios métodos, siendo el que veremos ahora uno de los más funcionales. Empezaremos por "escribir" todo el código de nuestro programa en un array de caracteres, y no en una cadena (string) que "envuelva" al código anterior y que, para ser escrita, necesite volver a ser incluida en otra cadena y así ad infinitum, en un equivalente programático de las muñecas rusas.

Un quine correcto y operativo, pero no muy elegante, podría ser el siguiente:
[c]
#include

int
main (void)
{
char *s1="#include %c%cint%cmain (void)%c{%c";
char *s2=" char *s%c=%c%s%c;%c char *s%c=%c%s%c;%c";
char *s3=" char n='%cn', q='%c', b='%c%c';%c";
char *sp=" printf(";
char *s4="%ss1,n,n,n,n,n);%c";
char *s5="%ss2,'1',q,s1,q,n,'2',q,s2,q,n);%ss2,'3',q,s3,q,n,'p',q,sp,q,n);%c";
char *s6="%ss2,'4',q,s4,q,n,'5',q,s5,q,n);%ss2,'6',q,s6,q,n,'7',q,s7,q,n);%c";
char *s7="%ss2,'8',q,s8,q,n,'9',q,s9,q,n);%ss2,'0',q,s0,q,n,'x',q,sx,q,n);%c";
char *s8="%ss3,b,q,b,b,n);%ss4,sp,n);%ss5,sp,sp,n);%c";
char *s9="%ss6,sp,sp,n);%ss7,sp,sp,n);%ss8,sp,sp,sp,n);%c";
char *s0="%ss9,sp,sp,sp,n);%ss0,sp,sp,n,n,n);%c return 0;%c}%c";
char *sx="--- This is an intron. ---";
char n='\n', q='"', b='\\';
printf(s1,n,n,n,n,n);
printf(s2,'1',q,s1,q,n,'2',q,s2,q,n); printf(s2,'3',q,s3,q,n,'p',q,sp,q,n);
printf(s2,'4',q,s4,q,n,'5',q,s5,q,n); printf(s2,'6',q,s6,q,n,'7',q,s7,q,n);
printf(s2,'8',q,s8,q,n,'9',q,s9,q,n); printf(s2,'0',q,s0,q,n,'x',q,sx,q,n);
printf(s3,b,q,b,b,n); printf(s4,sp,n); printf(s5,sp,sp,n);
printf(s6,sp,sp,n); printf(s7,sp,sp,n); printf(s8,sp,sp,sp,n);
printf(s9,sp,sp,sp,n); printf(s0,sp,sp,n,n,n);
return 0;
}
[/c]

Un poco críptico, sí señor, pero ayudará a desvelar un par de secretos de la programación de quines. Por un lado, si examinamos el código podremos ver que existen dos partes claramente diferenciadas. Una serie de definiciones de constantes, que constituyen, por así decirlo, el bloque de datos del programa, seguido por una serie de sentencias que serán las que se ejecuten, usando el bloque de datos para replicar su propio código. También encontramos, entre medias, una línea con un intron, que no es más que una parte de código que no aporta nada a la funcionalidad del quine y que, de no existir, no afectaría a su comportamiento.

El ejemplo de quine para C que presenta la Wikipedia es algo más sencillo, pero se basa en la misma filosofía:

[c]
#include
char*i="\\#include&ltstdio.h>",n='\n',q='"',*p=
"%s%cchar*i=%c%c%s%c,n='%cn',q='%c',*p=%c%c%s%c,*m=%c%c%s%c%c;%s%c",*m=
"int main(){return!printf(p,i+1,n,q,*i,i,q,*i,q,n,q,p,q,n,q,m,q,n,m,n);}"
;int main(){return!printf(p,i+1,n,q,*i,i,q,*i,q,n,q,p,q,n,q,m,q,n,m,n);}
[/c]

En una próxima entrada veremos cómo la programación de quines guarda una importante relación con la seguridad de los sistemas informáticos y la programación de virus (aparte, claro está, de prestarse a la celebración de concursos geek, donde resulta ganador quien escribe el quine más corto en un determinado lenguaje).

Referencias: