Un quine es un programa de computadora que no recibe 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 en la literatura informática son "programas autorreplicantes", "programas autorreproductores" y "programas autocopiantes".
Un quine es un punto fijo de un entorno de ejecución, cuando el entorno de ejecución se ve como una función que transforma programas en sus salidas. Los quines 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 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 hizo 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 precedida de su cita", da falsedad cuando va precedida de su cita.
Historia
La idea de los autómatas que se reproducen a sí mismos 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 de autorreproducción 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 una quine [ cita requerida ] .
Ejemplos de
Quines constructivos
En general, el método usado para crear un quine en cualquier lenguaje de programación es tener, dentro del programa, dos partes: (a) código usado para hacer la impresión real y (b) datos que representan la forma textual del código. El código funciona usando 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 usa los datos, procesados de manera simple, para imprimir la representación textual de los datos en sí.
Aquí hay tres pequeños ejemplos en Python3:
a = 'a = % s% s% s ; print (a %% (chr (39), a, chr (39)))' ; imprimir ( a % ( chr ( 39 ), a , chr ( 39 )))b = 'b = {} {} {} ; print (b.format (chr (39), b, chr (39)))' ; imprimir ( b . formato ( chr ( 39 ), b , chr ( 39 )))c = 'c = % r ; print (c %% c)' ; imprimir ( c % c )# tenga en cuenta que% r cotizará automáticamente
En Python 3.8:
exec ( s : = 'print ("exec (s: = % r )" % s )' )
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 ;>, "System.out.println (l [6] + q + l [i] + q + ','); " , "for (int i = 7; i ;>, "System.out.println (l [i]);" , "}" , "}" , }; for ( int i = 0 ; i < 6 ; i ++ ) // Imprimir código de apertura System . fuera . println ( l [ i ] ); for ( int i = 0 ; i < l . length ; i ++ ) // Imprimir matriz de cadenas System . fuera . println ( l [ 6 ] + q + l [ i ] + q + ',' ); for ( int i = 7 ; i < l . length ; i ++ ) // Imprime este código System . fuera . println ( l [ i ] ); } }
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. [2]
Gracias a la nueva función de bloques de texto en Java 15 (o más reciente), es posible una versión más simple y legible: [3]
public class Quine { public static void main ( String [] args ) { String textBlockQuotes = new String ( new char [] { '"' , '"' , '"' }); char newLine = 10 ; String source = " " " public class Quine { public static void main (String [] args) { String textBlockQuotes = new String (new char [] {'" ' , '"' , '"' }); char newLine = 10 ; String source = % s ; System . out . println ( source . formatted ( textBlockQuotes + newLine + source + textBlockQuotes )); } } "" "; System.out.println (fuente.formateado (textBlockQuotes + newLine + fuente + textBlockQuotes)); } }
Eval quines
Algunos lenguajes de programación tienen la capacidad de evaluar una cadena como programa. Quines puede aprovechar esta función. Por ejemplo, este Ruby quine:
eval s = "imprimir 'eval s ='; p s"
Lua puede hacer:
s = "print (cadena.format ('s =% c% s% c; cadena (s) ()', 34, s, 34))" ; cadena ( s ) de carga ()
Quines "engañando"
Autoevaluación
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 valor, el valor devuelto se muestra en la pantalla. Por lo tanto, en tales lenguajes, un programa que contiene un solo dígito da como resultado una quine de 1 byte. Dado que dicho código no se construye a sí mismo, a menudo se considera una trampa.
1
En algunos lenguajes, particularmente lenguajes de scripting 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 tan vacío, presentado como "el programa de autorreproducción más pequeño del mundo", una vez ganó el premio "peor abuso de las reglas" en el Concurso Internacional de Código C ofuscado . [4] En realidad, el programa no se compiló, sino que se usó cp
para copiar el archivo en otro archivo, que podría ejecutarse para no imprimir nada. [5]
Otras 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".
Inspección de código fuente
Quines, por definición, no puede recibir ningún tipo de entrada, incluida la lectura de un archivo, lo que significa que un quine se considera "trampa" si mira 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 una trampa. gato $ 0
Programas de Ouroboros
El concepto de quine puede extenderse a múltiples niveles de recursividad, originando " programas ouroboros " o quine-releys. Esto no debe confundirse con multiquines .
Ejemplo
Este programa Java genera la fuente de un programa C ++ que genera el código Java original.
#include #include usando el espacio de nombres std ;int main ( int argc , char * argv []) { char q = 34 ; cadena l [] = { "" , "============= <<<<<<<< Código C ++ >>>>>>>> ========= ==== " , " #include " , " #include " , " usando el 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 >>>>>>>> ============= " , " public class Quine " , " {" , " public static void main (String [] args) " , " {" , " char q = 34; " , "Cadena [] l = {" , "};" , "para (int i = 2; i <= 9; i ++)" , "System.out.println (l [i]);" , "para (int i = 0; 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 ] << 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 ; return 0 ; }
public class Quine { public static void main ( String [] args ) { char q = 34 ; Cadena [] l = { "" , "============= <<<<<<<< Código C ++ >>>>>>>> ========= ==== " , " #include " , " #include " , " usando el 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 >>>>>>>> ==========" , " public class Quine " , " {" , " public static void main (String [] args) " , " {" , " char q = 34; " , "Cadena [] l = {" , "};" , "para (int i = 2; i <= 9; i ++)" , "System.out.println (l [i]);" , "para (int i = 0; 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 . fuera . println ( l [ i ] ); para ( int i = 0 ; i < l . longitud ; i ++ ) System . fuera . println ( l [ 0 ] + q + l [ i ] + q + ',' ); para ( int i = 10 ; i <= 18 ; i ++ ) System . fuera . println ( l [ i ] ); } }
Estos programas se han elaborado con varias duraciones de ciclo:
- Haskell → Python → Ruby [6]
- Python → Bash → Perl [7]
- C → Haskell → Python → Perl [8]
- Haskell → Perl → Python → Ruby → C → Java [9]
- Ruby → Java → C # → Python [10]
- C → C ++ → Ruby → Python → PHP → Perl [11]
- Ruby → Python → Perl → Lua → OCaml → Haskell → C → Java → Brainfuck → Espacio en blanco → Unlambda [12]
- Ruby → Scala → Scheme → Scilab → Shell (bash) → S-Lang → Smalltalk → Squirrel3 → Standard ML → ... → Rexx (128 (y antes 50) lenguajes de programación) [13]
- Aplicación web → C (el código fuente de la aplicación web consta de HTML , JavaScript y CSS ) [14]
Multiquines
David Madore, creador de Unlambda , describe multiquines de la siguiente manera: [15]
"Un multiquine es un conjunto de r programas diferentes (en r idiomas diferentes; sin esta condición, podríamos tomarlos 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 la se pasa el argumento de la línea de comandos. (Tenga en cuenta que no se permiten trampas: los argumentos de la línea de comandos no deben ser demasiado largos; pasar el texto completo de un programa se considera trampa) ".
Un multiquine que consta de 2 idiomas (o biquine) sería un programa que:
- Cuando se ejecuta, es un quine en lenguaje X.
- Cuando se le proporciona un argumento de línea de comando definido por el usuario, imprime un segundo programa en el lenguaje Y.
- Dado el segundo programa en el lenguaje Y, cuando se ejecuta normalmente, también sería un quine en el lenguaje Y.
- Dado el segundo programa en el lenguaje Y, y provisto con un argumento de línea de comando definido por el usuario, produciría el programa original en el lenguaje X.
Entonces, una biquine podría verse como un conjunto de dos programas, los cuales pueden imprimir cualquiera de los dos, dependiendo del argumento de línea de comando proporcionado.
Teóricamente, no hay límite en el número de idiomas en un multiquine. Se ha producido un multiquine de 5 partes (o pentaquine) con Python , Perl , C , NewLISP y F # [16] y también hay un multiquine de 25 idiomas. [17]
Endurecido por radiación
Una quine endurecida por radiación es una quine a la que se le puede quitar 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 : [18]
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,: instancia _," || = 9 "] [eval $ &]} salir) # ' ##'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,: instancia _," || = 9 "] [eval $ &]} salir) # ' ##'/ # { eval eval if eval == instance_eval } } / . i rescate ## /eval eval "[eval || = 9, instancia_eval || = 9] .max_by {| s | s.size} #" ## "
Ver también
- Lema diagonal
- Combinador de punto fijo
- Código auto modificable
- Auto-intérprete
- Máquina de autorreplicación
- Autorreplicación
- Auto reubicación
- Fórmula autorreferencial de Tupper
- Lenguajes de programación
- La paradoja de Quine
Notas
- ^ Los ejemplos incluyen Bash , Perl y Python
Referencias
- ^ Bratley, Paul ; Millo, Jean (1972). "Recreaciones informáticas: autómatas que se reproducen a sí mismos". Práctica y experiencia en software . 2 (4): 397–400. doi : 10.1002 / spe.4380020411 . S2CID 222194376 .
- ^ http://wiki.c2.com/?QuineProgram
- ^ https://gist.github.com/destan/c0db5a237e9875a56141403aaa6cb9c7
- ^ IOCCC 1994 Peor abuso de las reglas
- ^ "Makefile" . IOCCC.org . Consultado el 4 de abril de 2019 .
- ^ Dan Piponi (5 de febrero de 2008). "Un tercer orden quine en tres idiomas" .
- ^ Bruce Ediger. "Pregunte y recibirá: Programa autorreplicante que pasa por tres generaciones, Python, Bash, Perl" .
- ^ bm (1 de febrero de 2011). "multiquine" . Archivado desde el original el 15 de abril de 2013.
- ^ Dan Piponi (30 de enero de 2011). "Quine Central" .
- ^ Ruslan Ibragimov (20 de abril de 2013). "Quine Ruby -> Java -> C # -> Python" (en ruso).
- ^ Shinichiro Hamaji (10 de noviembre de 2007). "Quine por shinh (C C ++ Ruby Python PHP Perl)" .(este también es políglota )
- ^ Ku-ma-me (22 de septiembre de 2009). "Programación Uroboros con 11 lenguajes de programación" .
- ^ Yusuke Endoh. "Quine Relay - Un programa de uroboros con más de 100 lenguajes de programación" .
- ^ Michael Wehar (10 de noviembre de 2019). "C imprime JavaScript" .
- ^ David Madore. "Quines (programas autorreplicantes)" .
- ^ Rijnard van Tonder. "Pentaquina - 5 partes multiquine" .
- ^ Lu Wang. "Quine Chameleon # Variants" .
- ^ Yusuke Endoh. "Quine endurecido por radiación" . Consultado el 24 de febrero de 2014 .
Otras lecturas
- Douglas Hofstadter : Gödel, Escher, Bach: una trenza dorada eterna
- Ken Thompson : " Reflexiones sobre la confianza en la confianza " ( Comunicaciones de la ACM , 27 (8): 761-3)
enlaces externos
- TiddlyWiki, un quine manifestado como wiki
- La página de Quine (por Gary P. Thompson)
- Una breve guía de programas autorreferenciales
- QuineProgram en el repositorio de patrones de Portland Wiki
- Discusión de David Madore sobre Quines
- Archivo zip Quine
- Zip archivos hasta el final
- Una introducción a Quines - en particular, quines usando más de un idioma
- Página web de Quine: una página web HTML + JavaScript conforme a los estándares que muestra su propio código fuente
- HTML Quine: una página HTML que solo usa HTML y CSS para mostrar su propio código fuente
- Quine Challenge para Tom's JavaScript Machine , con una serie de sugerencias interactivas
- Un Java Quine construido directamente a partir del teorema de punto fijo de Kleene, composición y snm
- Un código QR quine