Квайн — это компьютерная программа , которая не принимает никаких входных данных и производит копию своего собственного исходного кода в качестве единственного выхода. Стандартные термины для таких программ в теории вычислимости и литературе по информатике — «самовоспроизводящиеся программы», «самовоспроизводящиеся программы» и «самокопирующиеся программы».
Куайн — это фиксированная точка среды выполнения, когда эта среда рассматривается как функция, преобразующая программы в их выходные данные. Куайны возможны в любом языке программирования, полном по Тьюрингу , как прямое следствие теоремы Клини о рекурсии . Для развлечения программисты иногда пытаются разработать максимально короткий куайн в любом заданном языке программирования .
Название «куайн» было придумано Дугласом Хофштадтером в его научно-популярной книге «Гёдель, Эшер, Бах » в честь философа Уилларда Ван Ормана Куайна (1908–2000), который провел обширное исследование косвенной самореференции и, в частности, следующего парадоксального выражения, известного как парадокс Куайна :
«Выдает ложь, если ему предшествует его цитата» выдает ложь, если ему предшествует его цитата.
Идея самовоспроизводящихся автоматов возникла на заре вычислительной техники, если не раньше. Джон фон Нейман теоретизировал о них в 1940-х годах. Позже, в 1972 году, Пол Брэтли и Джин Милло в своей статье «Computer Recreations: Self-Reproducing Automata» обсуждали их. [1] Брэтли впервые заинтересовался самовоспроизводящимися программами после того, как увидел первую известную такую программу, написанную в Atlas Autocode в Эдинбурге в 1960-х годах преподавателем и исследователем Эдинбургского университета Хэмишем Дьюаром.
Требование «источника загрузки» в GNU Affero General Public License основано на идее квайна. [2]
В общем, метод, используемый для создания квайна на любом языке программирования, заключается в том, чтобы иметь в программе две части: (a) код, используемый для фактической печати, и (b) данные , представляющие текстовую форму кода. Код функционирует, используя данные для печати кода (что имеет смысл, поскольку данные представляют текстовую форму кода), но он также использует данные, обработанные простым способом, для печати текстового представления самих данных.
Вот три небольших примера на Python3:
# Пример A. chr(39) == "'". a = 'a = {}{}{} ; print(a.format(chr(39), a, chr(39)))' ; print ( a .format ( chr ( 39 ) , a , chr ( 39 ))) # Пример B. chr(39) == "'". b = 'b = %s%s%s ; print(b %% (chr(39), b, chr(39)))' ; print ( b % ( chr ( 39 ), b , chr ( 39 )))# Пример C. %r будет заключаться в кавычки автоматически. c = 'c = %r ; print(c %% c)' ; print ( c % c )Следующий код Java демонстрирует базовую структуру квайна.
public class Quine { public static void main ( String [] args ) { char q = 34 ; // Символ кавычек String [] l = { // Массив исходного кода "public class Quine" , "{" , " public static void main(String[] args)" , " {" , " char q = 34; // Символ кавычек" , " String[] l = { // Массив исходного кода" , " " , " };" , " for (int i = 0; i < 6; i++) // Вывести код открытия" , " System.out.println(l[i]);" , " for (int i = 0; i < l.length; i++) // Вывести массив строк" , " System.out.println(l[6] + q + l[i] + q + ',');" , " for (int i = 7; i < l.length; i++) // Распечатать этот код" , " System.out.println(l[i]);" , " }" , "}" , }; for ( int i = 0 ; i < 6 ; i ++ ) // Распечатать код открытия System . out . println ( l [ i ] ); for ( int i = 0 ; i < l . length ; i ++ ) // Распечатать массив строк System . out . println ( l [ 6 ] + q + l [ i ] + q + ',' ); for ( int i = 7 ; i < l . length ; i ++ ) // Распечатать этот код System . out . println ( l [ i ] ); } } Исходный код содержит массив строк, который выводится дважды, один раз в кавычках.
Этот код был адаптирован из оригинального поста с c2.com, где автор, Джейсон Уилсон, разместил его как минималистичную версию Quine, без комментариев Java. [3]
Благодаря новой функции текстовых блоков в Java 15 (или более поздней версии) возможна более читабельная и простая версия: [4]
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.print ( source.formatted (textBlockQuotes + newLine + source + textBlockQuotes)); } } " " " ; System.out.print ( source.formatted ( textBlockQuotes + newLine + source + textBlockQuotes ) ) ; } } Некоторые языки программирования имеют возможность оценивать строку как программу. Quines могут воспользоваться этой возможностью. Например, этот Ruby quine:
eval s = "печать 'eval s=';p s" Lua может:
s = "print(string.format('s=%c%s%c; load(s)()',34,s,34))" ; load ( s )()В Python 3.8:
exec ( s := 'print("exec(s:= %r )" %s )' )Во многих функциональных языках, включая Scheme и другие Lisp , а также интерактивных языках, таких как APL , числа являются самооценивающимися. В TI-BASIC , если последняя строка программы возвращает значение, возвращаемое значение отображается на экране. Поэтому в таких языках программа, состоящая только из одной цифры, приводит к 1-байтовому квайну. Поскольку такой код не конструирует сам себя, это часто считается мошенничеством.
1В некоторых языках, особенно скриптовых, а также в C , пустой исходный файл является фиксированной точкой языка, будучи допустимой программой, которая не выводит никаких данных. [a] Такая пустая программа, представленная как «самая маленькая в мире самовоспроизводящаяся программа», однажды выиграла приз за «худшее злоупотребление правилами» на Международном конкурсе запутанного кода на языке C. [ 5] Программа на самом деле не была скомпилирована, а использовалась cpдля копирования файла в другой файл, который можно было выполнить, чтобы ничего не вывести. [6]
Quines, по определению, не может получать никаких форм ввода, включая чтение файла, что означает, что quine считается "мошенничеством", если он смотрит на свой собственный исходный код. Следующий скрипт оболочки не является quine:
#!/bin/sh # Неверный квин. # Чтение исполняемого файла с диска — мошенничество.
cat $0 Более короткий вариант, использующий поведение директив shebang :
#!/bin/котДругие сомнительные методы включают использование сообщений компилятора; например, в среде GW-BASIC ввод «Syntax Error» заставит интерпретатор ответить «Syntax Error».
Концепция quine может быть расширена до нескольких уровней рекурсии, что приводит к появлению " программ уробороса ", или quine-реле. Это не следует путать с мультиquines.
Эта программа Java выводит исходный код для программы C++, которая выводит исходный код Java.
#include <iostream> #include <string> с использованием пространства имен std ; int main ( int argc , char * argv []) { char q = 34 ; string l [] = { " " , "=============<<<<<<< Код на C++ >>>>>>>>=============" , "#include <iostream>" , "#include <string>" , "используя пространство имен std;" , "" , "int main(int argc, char* argv[])" , "{" , " char q = 34;" , " string 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;" , " return 0;" , "}" , "============<<<<<<< Код Java >>>>>>>>==============" , "public class Quine" , "{" , " public static void main(String[] args)" , " {" , " char q = 34;" , " String[] 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]);" , " }" , "}" ,}; для ( int i = 20 ; i <= 25 ; i ++ ) cout << l [ i ] << endl ; для ( int i = 0 ; i <= 34 ; i ++ ) cout << l [ 0 ] + q + l [ i ] + q + ',' << endl ; для ( int i = 26 ; i <= 34 ; i ++ ) cout << l [ i ] << endl ; return 0 ; } public class Quine { public static void main ( String [] args ) { char q = 34 ; String [] l = { " " , "=============<<<<<<< Код на C++ >>>>>>>>==============" , "#include <iostream>" , "#include <string>" , "используя пространство имен std;" , "" , "int main(int argc, char* argv[])" , "{" , " char q = 34;" , " string 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;" , " return 0;" , "}" , "============<<<<<<< Код Java >>>>>>>>==============" , "public class Quine" , "{" , " public static void main(String[] args)" , " {" , " char q = 34;" , " String[] 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 = 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 ] ) ; } } Такие программы были созданы с различной продолжительностью цикла:
Дэвид Мадор, создатель Unlambda , описывает мультиквины следующим образом: [16]
«Мультиквайн — это набор из r различных программ (на r различных языках — без этого условия мы могли бы считать их все равными одному квайну), каждая из которых способна распечатать любую из r программ (включая себя) в соответствии с переданным ей аргументом командной строки. (Обман не допускается: аргументы командной строки не должны быть слишком длинными — передача полного текста программы считается обманом)».
Мультиквайном, состоящим из 2 языков (или биквайном), будет программа, которая:
Тогда биквину можно рассматривать как набор из двух программ, каждая из которых способна вывести на печать любую из двух программ в зависимости от переданного аргумента командной строки.
Теоретически, нет ограничений на количество языков в мультиквине. Мультиквин из 5 частей (или пентаквин) был создан с помощью Python , Perl , C , NewLISP и F# [17] , а также существует мультиквин из 25 языков. [18]
Похожая на мультиквин, но в отличие от мультиквина, программа -полиглот — это компьютерная программа или скрипт, написанный в допустимой форме нескольких языков программирования или форматов файлов путем объединения их синтаксиса. Программа-полиглот не обязана обладать качеством самовоспроизводства, хотя программа-полиглот также может быть квином в одном или нескольких возможных способах выполнения.
В отличие от квайнов и мультиквайнов, полиглот-программы не гарантированно существуют между произвольными наборами языков в результате теоремы Клини о рекурсии, поскольку они полагаются на взаимодействие между синтаксисами, а не на доказуемое свойство, согласно которому один язык всегда может быть встроен в другой.
Радиационно-устойчивый квин — это квин, из которого можно удалить любой одиночный символ, и который все равно будет производить исходную программу без отсутствующих символов. По необходимости такие квины гораздо более запутанны, чем обычные квины, как видно из следующего примера на Ruby : [19]
eval = 'eval$q=%q(puts %q(10210/ #{ 1 1 if 1 == 21 } }/.i спасение##/ 1 1"[13,213].max_by{|s|s.size}#"##").gsub(/\d/){["= \47 eval$q=%q( #$q )# \47 ## \47",:eval,:instance_,"||=9"][eval$&]} выход)#' ##'instance_eval = 'eval$q=%q(puts %q(10210/ #{ 1 1 if 1 == 21 } }/.i спасение##/ 1 1"[13,213].max_by{|s|s.size}#"##").gsub(/\d/){["= \47 eval$q=%q( #$q )# \47 ## \47",:eval,:instance_,"||=9"][eval$&]} выход)#' ##'/ #{ eval eval if eval == instance_eval } }/ . я спасаю ##/ eval eval "[eval||=9,instance_eval||=9].max_by{|s|s.size}#" ##" Используя методы реляционного программирования , можно автоматически генерировать квайны, преобразуя интерпретатор (или, что эквивалентно, компилятор и среду выполнения) языка в реляционную программу, а затем решая для фиксированной точки . [20]
