Un quine es un programa de computadora que no recibe información y produce una copia de su propio código fuente como único resultado. Los términos estándar para estos programas en la teoría de la computabilidad y la literatura informática son "programas autorreplicantes", "programas autorreproducibles" y "programas autocopiantes".
Un quine es un punto fijo de un entorno de ejecución, cuando ese entorno se ve como una función que transforma programas en sus salidas. Las quinas son posibles en cualquier lenguaje de programación completo de Turing , como consecuencia directa del teorema de recursividad de Kleene . Para divertirse, los programadores a veces intentan desarrollar el quine más corto posible en cualquier lenguaje de programación determinado .
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 para la siguiente expresión productora de paradojas, conocida como paradoja de Quine :
"Da falsedad cuando va precedido de su cita" produce falsedad cuando va precedido de su cita.
La idea de los autómatas autorreproductores surgió desde 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 "Computer Recreations: Self-Reproducing Automata" los discutió en 1972. [1] Bratley se interesó por primera vez en los programas autorreproducibles después de ver el primer programa conocido 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 "fuente de descarga" de la Licencia Pública General de Affero 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 piezas: (a) código utilizado para realizar la impresión real 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 forma sencilla, para imprimir la representación textual de los datos mismos.
Aquí hay tres pequeños ejemplos en Python 3:
# Ejemplo A. chr(39) == "'". a = 'a = {}{}{} ; print(a.format(chr(39), a, chr(39)))' ; imprimir ( a . formato ( chr ( 39 ), a , chr ( 39 )))# Ejemplo B. chr(39) == "'". b = 'b = %s%s%s ; imprimir(b %% (chr(39), b, chr(39)))' ; imprimir ( b % ( chr ( 39 ), b , chr ( 39 )))# Ejemplo C. %r cotizará automáticamente. c = 'c = %r ; imprimir(c %% c)' ; imprimir ( c % c )El siguiente código Java demuestra la estructura básica de un quine.
clase pública 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++) // Imprime este código" , "System.out.println(l[i]);" , " }" , "}" , }; for ( int i = 0 ; i < 6 ; i ++ ) // Imprimir código de apertura System . afuera . println ( l [ yo ] ); for ( int i = 0 ; i < l . length ; i ++ ) // Imprimir matriz de cadenas System . afuera . println ( l [ 6 ] + q + l [ i ] + q + ',' ); for ( int i = 7 ; i < l . length ; i ++ ) // Imprime este código System . afuera . println ( l [ yo ] ); } } El código fuente contiene una matriz de cadenas de sí mismo, que se genera 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 Quine, sin comentarios de Java. [3]
Gracias a la nueva función de bloques de texto en Java 15 (o posterior), es posible una versión más sencilla y legible: [4]
clase pública Quine { public static void main ( String [] args ) { String textBlockQuotes = new String ( new char [] { '"' , '"' , '"' }); char newLine = 10 ; String source = "" " clase pública Quine { public static void main(String[] args) { String textBlockQuotes = new String(new char[]{'"', '"', '"'}); char newLine = 10; String source = % s; System.out.print(source.formatted(textBlockQuotes + newLine + fuente + textBlockQuotes)); } } """ ; Sistema . afuera . imprimir ( fuente . formateado ( textBlockQuotes + newLine + fuente + textBlockQuotes )); } } Algunos lenguajes de programación tienen la capacidad de evaluar una cadena como un programa. Quines puede aprovechar esta característica. Por ejemplo, esta Ruby Quine:
eval s = "imprimir 'eval s=';p s" Lua puede hacer:
s = "print(string.format('s=%c%s%c; carga(s)()',34,s,34))" ; cargar ( s )()En Python 3.8:
ejecutivo ( s := 'print("exec(s:= %r )" %s )' )En muchos lenguajes funcionales, incluidos Scheme y otros Lisps , 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 tales lenguajes, un programa que consta de un solo dígito da como resultado un quine de 1 byte. Dado que dicho código no se construye por sí solo, esto a menudo se considera una trampa.
1Otras 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".
Quines, por definición, no puede recibir ningún tipo de entrada, incluida la lectura de un archivo, lo que significa que se considera que un quine está "haciendo trampa" si mira su propio código fuente. El siguiente script de shell no es quine:
#!/bin/sh # Quine no válido. # Leer el archivo ejecutado desde el disco es hacer trampa. gato $0 Una variante más corta, que explota el comportamiento de las directivas shebang :
#!/bin/gatoEn algunos lenguajes, particularmente en los lenguajes de scripting pero también en C , un archivo fuente vacío es un punto fijo del lenguaje, siendo un programa válido que no produce resultados. [a] Llamar quine a un archivo vacío a menudo se considera hacer trampa.
Un programa tan vacío, presentado como "el programa autorreproducible más pequeño del mundo", ganó una vez 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]
El concepto de Quine se puede extender a múltiples niveles de recursividad, dando lugar a " programas Ouroboros " o retransmisiones de Quine. Esto no debe 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 principal ( int argc , char * argv []) { char q = 34 ; cadena l [] = { " " , "=============<<<<<<<< Código C++ >>>>>>>>========= ====" , "#include <iostream>" , "#include <string>" , "usando el espacio de nombres std;" , "" , "int main(int argc, char* argv[])" , "{" , "char q = 34;" , "cadena l[] = {" , " };" , " for(int i = 20; i <= 25; i++)" , " cout << l[i] << endl;" , " for(int i = 0; i <= 34; i++)" , " cout << l[0] + q + l[i] + q + ',' << endl;" , " for(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;" , " Cadena [] l = {" , " };" , " for(int i = 2; i <= 9; i++)" , " System.out.println(l[i]);" , " for(int i = 0; i < l.length; i++)" , " System.out.println(l[0] + q + l[i] + q + ',');" , " for(int i = 10; i <= 18; i++)" , " System.out.println(l[i]);" , " }" , "}" , }; for ( int i = 20 ; i <= 25 ; i ++ ) cout << l [ i ] << endl ; for ( int i = 0 ; i <= 34 ; i ++ ) cout << l [ 0 ] + q + l [ i ] + q + ',' << endl ; para ( int yo = 26 ; yo <= 34 ; i ++ ) cout << l [ i ] << endl ; devolver 0 ; } clase pública Quine { public static void main ( String [] args ) { char q = 34 ; Cadena [] l = { " " , "=============<<<<<<<< Código C++ >>>>>>>>========= ====" , "#include <iostream>" , "#include <string>" , "usando el espacio de nombres std;" , "" , "int main(int argc, char* argv[])" , "{" , "char q = 34;" , "cadena l[] = {" , " };" , " for(int i = 20; i <= 25; i++)" , " cout << l[i] << endl;" , " for(int i = 0; i <= 34; i++)" , " cout << l[0] + q + l[i] + q + ',' << endl;" , " for(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;" , " Cadena [] l = {" , " };" , " for(int i = 2; i <= 9; i++)" , " System.out.println(l[i]);" , " for(int i = 0; i < l.length; i++)" , " System.out.println(l[0] + q + l[i] + q + ',');" , " for(int i = 10; i <= 18; i++)" , " System.out.println(l[i]);" , " }" , "}" , }; para ( int i = 2 ; i <= 9 ; i ++ ) Sistema . afuera . println ( l [ yo ] ); para ( int i = 0 ; i < l . longitud ; i ++ ) Sistema . afuera . imprimirln ( l [ 0 ] + q + l [ i ] + q + ',' ); para ( int i = 10 ; i <= 18 ; i ++ ) Sistema . afuera . println ( l [ yo ] ); } } Estos programas se han elaborado con ciclos de diferente duración:
David Madore, creador de Unlambda , describe las multiquinas de la siguiente manera: [16]
"Una multiquine es un conjunto de r programas diferentes (en r lenguajes diferentes; sin esta condición, podríamos considerarlos todos iguales a un solo quine), cada uno de los cuales es capaz de imprimir cualquiera de los r programas (incluido él mismo) de acuerdo con el Se pasa el argumento de la línea de comando. (No se permiten trampas: los argumentos de la línea de comando no deben ser demasiado largos; pasar el texto completo de un programa se considera hacer trampa)".
Una multiquine compuesta por 2 idiomas (o biquine) sería un programa que:
Una bicicleta podría verse entonces como un conjunto de dos programas, los cuales pueden imprimir cualquiera de los dos, dependiendo del argumento de la línea de comando proporcionado.
En teoría, no hay límite en la cantidad de idiomas en una multiquina. Se ha producido una multiquina (o pentaquina) de 5 partes 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 él, un programa políglota es un programa de computadora o script escrito en una forma válida de múltiples lenguajes de programación o formatos de archivo combinando 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 quines y multiquines, no se garantiza la existencia de programas políglotas entre conjuntos arbitrarios de lenguajes 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 una siempre puede estar incrustada dentro de otra.
Un quine endurecido por radiación es un quine al que se le puede eliminar cualquier carácter y aún produce el programa original sin ningún carácter faltante. Por necesidad, tales quines son mucho más complicados que los quines ordinarios, como se ve en el siguiente ejemplo en Ruby : [19]
eval = 'eval$q=%q(pone %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$&]} salida)#' ##'instancia_eval = 'eval$q=%q(pone %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$&]} salida)#' ##'/ #{ eval eval si eval == instancia_eval } }/ . yo rescato ##/ eval eval "[eval||=9,instance_eval||=9].max_by{|s|s.size}#" ##" 