Un quine es un programa informático que no requiere ninguna entrada y produce una copia de su propio código fuente como única salida. Los términos estándar para estos programas en la teoría de la computabilidad y la literatura sobre ciencias de la computación son "programas autorreplicantes", "programas autorreproductores" y "programas autocopiantes".
Un quine es un punto fijo de un entorno de ejecución, cuando ese entorno se considera como una función que transforma los programas en sus salidas. Los quines son posibles en cualquier lenguaje de programación Turing-completo , como consecuencia directa del teorema de recursión de Kleene . Para divertirse, los programadores a veces intentan desarrollar el quine más corto posible en cualquier lenguaje de programación dado .
El nombre "quine" fue acuñado por Douglas Hofstadter , en su libro de divulgación científica Gödel, Escher, Bach , en honor al filósofo Willard Van Orman Quine (1908-2000), quien realizó un extenso estudio de la autorreferencia indirecta , y en particular de la siguiente expresión productora de paradojas, conocida como paradoja de Quine :
"Da falsedad cuando va precedido de su cita" da falsedad cuando va precedido de su cita.
La idea de los autómatas autorreproductores surgió en los albores de la informática, si no antes. John von Neumann teorizó sobre ellos en la década de 1940. Más tarde, el artículo de Paul Bratley y Jean Millo "Recreaciones informáticas: autómatas autorreproductores" los analizó en 1972. [1] Bratley se interesó por primera vez en los programas autorreproductores después de ver el primer programa conocido de este tipo escrito en Atlas Autocode en Edimburgo en la década de 1960 por el profesor e investigador de la Universidad de Edimburgo Hamish Dewar.
El requisito de "descargar código fuente" de la Licencia Pública General Affero de GNU se basa en la idea de un quine. [2]
En general, el método utilizado para crear un quine en cualquier lenguaje de programación es tener, dentro del programa, dos partes: (a) código utilizado para realizar la impresión propiamente dicha y (b) datos que representan la forma textual del código. El código funciona utilizando los datos para imprimir el código (lo cual tiene sentido ya que los datos representan la forma textual del código), pero también utiliza los datos, procesados de manera sencilla, para imprimir la representación textual de los datos en sí.
Aquí hay tres pequeños ejemplos en Python3:
# Ejemplo A. chr(39) == "'". a = 'a = {}{}{} ; print(a.format( chr (39), a , chr(39)))' ; print ( a.format ( chr ( 39 ), a , chr ( 39 ))) # Ejemplo B. chr(39) == "'". b = 'b = %s%s%s ; print(b %% (chr(39), b, chr(39)))' ; print ( b % ( chr ( 39 ), b , chr ( 39 )))# Ejemplo C. %r se citará automáticamente. c = 'c = %r ; print(c %% c)' ; print ( c % c )El siguiente código Java demuestra la estructura básica de un quine.
public class Quine { public static void main ( String [] args ) { char q = 34 ; // Carácter de comillas String [] l = { // Matriz de código fuente "public class Quine" , "{" , " public static void main(String[] args)" , " {" , " char q = 34; // Carácter de comillas" , " String[] l = { // Matriz de código fuente" , " " , " };" , " for (int i = 0; i < 6; i++) // Imprimir código de apertura" , " System.out.println(l[i]);" , " for (int i = 0; i < l.length; i++) // Imprimir matriz de cadenas" , " System.out.println(l[6] + q + l[i] + q + ',');" , " for (int i = 7; i < l.length; i++) // Imprimir este código" , " System.out.println(l[i]);" , " }" , "}" , }; for ( int i = 0 ; i < 6 ; i ++ ) // Imprimir el código de apertura System . out . println ( l [ i ] ); for ( int i = 0 ; i < l . length ; i ++ ) // Imprimir la matriz de cadenas System . out . println ( l [ 6 ] + q + l [ i ] + q + ',' ); for ( int i = 7 ; i < l . length ; i ++ ) // Imprimir este código System . out . println ( l [ i ] ); } } El código fuente contiene una matriz de cadenas de sí mismo, que se muestra dos veces, una vez entre comillas.
Este código fue adaptado de una publicación original de c2.com, donde el autor, Jason Wilson, lo publicó como una versión minimalista de un Quine, sin comentarios de Java. [3]
Gracias a la nueva función de bloques de texto en Java 15 (o más reciente), es posible una versión más legible y sencilla: [4]
clase pública Quine { public static void main ( String [] args ) { String textBlockQuotes = new String ( new char [] { '"' , '"' , '"' }); char newLine = 10 ; String fuente = """ clase pública Quine { public static void main(String[] args) { String textBlockQuotes = new String(new char[]{'"', '"', '"'}); char newLine = 10; String fuente = %s; System.out.print ( source.formatted (textBlockQuotes + newLine + source + textBlockQuotes)); } } " " " ; System.out.print ( source.formatted ( textBlockQuotes + newLine + source + textBlockQuotes ) ) ; } } Algunos lenguajes de programación tienen la capacidad de evaluar una cadena como un programa. Quines puede aprovechar esta característica. Por ejemplo, este quine de Ruby :
eval s = "imprimir 'eval s=';p s" Lua puede hacer:
s = "imprimir(cadena.formato('s=%c%s%c; cargar(s)()',34,s,34))" ; cargar ( s )()En Python 3.8:
ejecutar ( s := 'print("ejecutar(s:= %r )" %s )' )En muchos lenguajes funcionales, incluidos Scheme y otros lenguajes Lisp , y lenguajes interactivos como APL , los números se autoevalúan. En TI-BASIC , si la última línea de un programa devuelve un valor, el valor devuelto se muestra en la pantalla. Por lo tanto, en dichos lenguajes, un programa que consta de un solo dígito da como resultado un quine de 1 byte. Dado que este tipo de código no se construye a sí mismo, esto a menudo se considera una trampa.
1En algunos lenguajes, particularmente lenguajes de script pero también C , un archivo fuente vacío es un punto fijo del lenguaje, siendo un programa válido que no produce salida. [a] Un programa vacío de este tipo, presentado como "el programa autorreproductor más pequeño del mundo", una vez ganó el premio al "peor abuso de las reglas" en el Concurso Internacional de Código C Ofuscado . [5] El programa en realidad no fue compilado, sino que se usó cppara copiar el archivo en otro archivo, que podría ejecutarse para no imprimir nada. [6]
Los quines, por definición, no pueden recibir ningún tipo de entrada, ni siquiera leer un archivo, lo que significa que se considera que un quine está "haciendo trampa" si consulta su propio código fuente. El siguiente script de shell no es un quine:
#!/bin/sh # Quine no válido. # Leer el archivo ejecutado desde el disco es hacer trampa.
cat $0 Una variante más corta, que explota el comportamiento de las directivas shebang :
#!/bin/gatoOtras técnicas cuestionables incluyen el uso de mensajes del compilador; por ejemplo, en el entorno GW-BASIC , ingresar "Error de sintaxis" hará que el intérprete responda con "Error de sintaxis".
El concepto de quine puede extenderse a múltiples niveles de recursión, dando lugar a los " programas ouroboros " o relés de quine. No deben confundirse con las multiquinas.
Este programa Java genera el código fuente de un programa C++ que genera el código Java original.
#include <iostream> #include <string> usando el espacio de nombres std ; int main ( int argc , char * argv []) { char q = 34 ; cadena l [] = { " " , "=============<<<<<<<< Código C++ >>>>>>>>==============" , "#include <iostream>" , "#include <string>" , "usando espacio de nombres std;" , "" , "int main(int argc, char* argv[])" , "{" , " char q = 34;" , " cadena l[] = {" , " };" , " para(int i = 20; i <= 25; i++)" , " cout << l[i] << endl;" , " para (int i = 0; i <= 34; i++)" , " cout << l[0] + q + l[i] + q + ',' << endl;" , " para (int i = 26; i <= 34; i++)" , " cout << l[i] << endl;" , " devuelve 0;" , "}" , "=============<<<<<<<< Código Java >>>>>>>>=============" , " clase pública Quine" , "{" , " public static void main (String[] args)" , " {" , " char q = 34;" , " String[] l = {" , " };" , " para (int i = 2; i <= 9; i++)" , " System.out.println(l[i]);" , " para (int i = 0; i < l.length; i++)" , " System.out.println(l[0] + q + l[i] + q + ',');" , " para (int i = 10; i <= 18; i++)" , " System.out.println(l[i]);" , " }" , "}" ,}; para ( int i = 20 ; i <= 25 ; i ++ ) cout << l [ i ] << finl ; para ( int i = 0 ; i <= 34 ; i ++ ) cout << l [ 0 ] + q + l [ i ] + q + ',' << finl ; para ( int i = 26 ; i <= 34 ; i ++ ) cout << l [ i ] << endl ; devuelve 0 ; } clase pública Quine { public static void main ( String [] args ) { char q = 34 ; String [] l = { " " , "=============<<<<<<<< Código C++ >>>>>>>>==============" , "#include <iostream>" , "#include <string>" , "usando espacio de nombres std;" , "" , "int main(int argc, char* argv[])" , "{" , " char q = 34;" , " string l[] = {" , " };" , " for(int i = 20; i <= 25; i++)" , " cout << l[i] << endl;" , " para (int i = 0; i <= 34; i++)" , " cout << l[0] + q + l[i] + q + ',' << endl;" , " para (int i = 26; i <= 34; i++)" , " cout << l[i] << endl;" , " devuelve 0;" , "}" , "=============<<<<<<<< Código Java >>>>>>>>=============" , " clase pública Quine" , "{" , " public static void main (String[] args)" , " {" , " char q = 34;" , " String[] l = {" , " };" , " para (int i = 2; i <= 9; i++)" , " System.out.println(l[i]);" , " para (int i = 0; i < l.length; i++)" , " System.out.println(l[0] + q + l[i] + q + ',');" , " para (int i = 10; i <= 18; i++)" , " System.out.println(l[i]);" , " }" , "}" , }; para ( int i = 2 ; i <= 9 ; i ++ ) System . out .println ( l [ i ] ) ; para ( int i = 0 ; i < l.longitud ; i ++ ) Sistema.salida.println ( l [ 0 ] + q + l [ i ] + q + ' ,' ) ; para ( int i = 10 ; i < = 18 ; i ++ ) Sistema.salida.println ( l [ i ] ) ; } } Se han elaborado programas con distintas duraciones de ciclo:
David Madore, creador de Unlambda , describe las multiquinas de la siguiente manera: [16]
"Una multiquina es un conjunto de r programas diferentes (en r lenguajes diferentes; sin esta condición podríamos considerarlos todos iguales a una única quina), cada uno de los cuales puede imprimir cualquiera de los r programas (incluido él mismo) según el argumento de la línea de comandos que se le pase. (No se permite hacer trampa: los argumentos de la línea de comandos no deben ser demasiado largos; pasar el texto completo de un programa se considera hacer trampa)."
Una multiquina formada por 2 lenguajes (o biquina) sería un programa que:
Una biquine podría entonces verse como un conjunto de dos programas, ambos capaces de imprimir cualquiera de los dos, dependiendo del argumento de la línea de comando suministrado.
En teoría, no hay límite en la cantidad de idiomas en una multiquina. Se ha producido una multiquina de 5 partes (o pentaquina) con Python , Perl , C , NewLISP y F# [17] y también hay una multiquina de 25 idiomas. [18]
Similar a un multiquine, pero a diferencia de este, un programa políglota es un programa o script de computadora escrito en una forma válida de múltiples lenguajes de programación o formatos de archivo mediante la combinación de su sintaxis. No es necesario que un programa políglota tenga una cualidad de autorreproducción, aunque un programa políglota también puede ser un quine en una o más de sus posibles formas de ejecución.
A diferencia de las quines y multiquines, no se garantiza la existencia de programas políglotas entre conjuntos arbitrarios de idiomas como resultado del teorema de recursión de Kleene, porque se basan en la interacción entre las sintaxis y no en una propiedad demostrable de que uno siempre puede estar integrado dentro de otro.
Una quine endurecida por radiación es una quine a la que se le puede quitar cualquier carácter individual y aún así produce el programa original sin ningún carácter faltante. Por necesidad, estas quines son mucho más complicadas que las quines comunes, como se ve en el siguiente ejemplo en Ruby : [19]
eval = 'eval$q=%q(puts %q(10210/ #{ 1 1 si 1 == 21 } }/.i rescate##/ 1 1"[13,213].max_by{|s|s.size}#"##").gsub(/\d/){["= \47 eval$q=%q( #$q )# \47 ## \47",:eval,:instance_,"||=9"][eval$&]} salir)#' ##'instancia_eval = 'eval$q=%q(puts %q(10210/ #{ 1 1 si 1 == 21 } }/.i rescate##/ 1 1"[13,213].max_by{|s|s.size}#"##").gsub(/\d/){["= \47 eval$q=%q( #$q )# \47 ## \47",:eval,:instance_,"||=9"][eval$&]} salir)#' ##'/ #{ eval eval if eval == instance_eval } }/ . yo rescato ##/ eval eval "[eval||=9,eval_de_instancia||=9].max_by{|s|s.size}#" ##" Utilizando técnicas de programación relacional , es posible generar quines automáticamente transformando el intérprete (o equivalentemente, el compilador y el entorno de ejecución) de un lenguaje en un programa relacional y luego resolviendo para un punto fijo . [20]
