Куайн — это компьютерная программа , которая не принимает никаких входных данных и выдает копию собственного исходного кода в качестве единственного результата. Стандартными терминами для этих программ в литературе по теории вычислимости и информатике являются «самовоспроизводящиеся программы», «самовоспроизводящиеся программы» и «самокопирующиеся программы».
Куайн — это фиксированная точка среды выполнения, если эту среду рассматривать как функцию , преобразующую программы в их выходные данные. Куайны возможны в любом языке программирования, полном по Тьюрингу , что является прямым следствием теоремы Клини о рекурсии . Для развлечения программисты иногда пытаются разработать кратчайший куайн на любом языке программирования .
Название «куайн» было придумано Дугласом Хофштадтером в его научно-популярной книге « Гёдель, Эшер, Бах » в честь философа Уилларда Ван Ормана Куайна (1908–2000), который провел обширное исследование косвенной самореференции , и в частности для следующего парадоксального выражения, известного как парадокс Куайна :
«Выдает ложь, если ему предшествует цитирование» дает ложь, если ему предшествует цитирование.
Идея самовоспроизводящихся автоматов возникла на заре вычислительной техники, если не раньше. Джон фон Нейман теоретизировал о них в 1940-х годах. Позже, в 1972 году, в статье Пола Брэтли и Жана Милло «Компьютерные развлечения: самовоспроизводящиеся автоматы» они обсуждались. [1] Брэтли впервые заинтересовался самовоспроизводящимися программами после того, как увидел первую известную такую программу, написанную в Atlas Autocode в Эдинбурге в 1960-х годах. лектор и исследователь Эдинбургского университета Хэмиш Дьюар.
Требование «Источника загрузки» Стандартной общественной лицензии Affero основано на идее квина. [2]
В общем, метод, используемый для создания квина на любом языке программирования, предполагает наличие в программе двух частей: (а) кода , используемого для фактической печати, и (б) данных , которые представляют текстовую форму кода. Код функционирует, используя данные для печати кода (что имеет смысл, поскольку данные представляют собой текстовую форму кода), но он также использует данные, обработанные простым способом, для печати текстового представления самих данных.
Вот три небольших примера на Python 3:
# Пример A. chr(39) == "'". а = 'а = {}{}{} ; print(a.format(chr(39), a, chr(39)))' ; распечатать ( a . format ( chr ( 39 ), a , chr ( 39 )))
# Пример Б. chr(39) == "'". б = 'b = %s%s%s ; print(b %% (chr(39), b, chr(39)))' ; напечатать ( b % ( chr ( 39 ), b , chr ( 39 )))
# Пример C. %r будет автоматически цитировать. с = 'с = %r ; print(c %% c)' ; распечатать ( c % c )
Следующий код Java демонстрирует базовую структуру quine.
общественный класс 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 . вне . println ( л [ я ] ); for ( int i = 0 ; i < l . length ; i ++ ) // Печать массива строк System . вне . println ( l [ 6 ] + q + l [ i ] + q + ',' ); for ( int i = 7 ; i < l . length ; i ++ ) // Распечатываем этот код System . вне . println ( л [ я ] ); } }
Исходный код содержит массив строк, который выводится дважды, один раз в кавычках.
Этот код был адаптирован из оригинального сообщения с 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)); } } """ ; Система . вне . print ( source . formatted ( textBlockQuotes + newLine + source + textBlockQuotes )); } }
Некоторые языки программирования имеют возможность оценивать строку как программу. Quines может воспользоваться этой функцией. Например, этот Руби Куайн:
eval s = "напечатать 'eval s=';p s"
Луа может делать:
s = "print(string.format('s=%c%s%c; load(s)()',34,s,34))" ; нагрузка ( с )()
В Python 3.8:
exec ( s := 'print("exec(s:= %r )" %s )' )
Во многих функциональных языках, включая Scheme и другие Lisps , а также в интерактивных языках, таких как APL , числа имеют самовычисление. В TI-BASIC , если последняя строка программы возвращает значение, возвращаемое значение отображается на экране. Следовательно, в таких языках программа, состоящая только из одной цифры, дает в результате 1-байтовый квин. Поскольку такой код не создается сам по себе, это часто считается мошенничеством.
1
В некоторых языках, особенно в языках сценариев, а также в C , пустой исходный файл является фиксированной точкой языка, являясь допустимой программой, которая не выдает никаких результатов. [a] Такая пустая программа, представленная как «самая маленькая в мире самовоспроизводящаяся программа», однажды выиграла приз «худшее нарушение правил» на Международном конкурсе запутанного кода C. [5] На самом деле программа не была скомпилирована, а использовалась cp
для копирования файла в другой файл, который можно было запустить и ничего не распечатать. [6]
Другие сомнительные методы включают использование сообщений компилятора; например, в среде GW-BASIC ввод «Синтаксическая ошибка» приведет к тому, что интерпретатор ответит «Синтаксическая ошибка».
Куайны, по определению, не могут получать какие-либо входные данные, включая чтение файла, а это означает, что куайн считается «читерством», если он просматривает свой собственный исходный код. Следующий сценарий оболочки не является куайном:
#!/bin/sh # Неверный куайн. # Чтение исполняемого файла с диска является мошенничеством. кот $0
Более короткий вариант, использующий поведение директив shebang :
#!/бин/кот
Во многих языках программирования пустой исходный файл является допустимой программой, которая не выдает никаких результатов. Назвать такой пустой файл куайном часто считается мошенничеством.
Концепция куайна может быть расширена до нескольких уровней рекурсии, что дает начало « программам уробороса » или куайн-реле. Не следует путать с мультихинами.
Эта программа Java выводит исходный код программы C++, которая выводит исходный код Java.
#include <iostream> #include <string> using namespace 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;" , " строка 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;" , «вернуть 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 = 20 ; я <= 25 ; я ++ ) cout << l [ i ] << endl ; for ( int i = 0 ; i <= 34 ; i ++ ) cout << l [ 0 ] + q + l [ i ] + q + ',' << endl ; для ( интервал я = 26 ; я <= 34 ; я ++ ) cout << l [ я ] << endl ; вернуть 0 ; }
общественный класс 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;" , " строка 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;" , «вернуть 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 я знак равно 2 ; я <= 9 ; я ++ ) System . вне . println ( л [ я ] ); for ( int я знак равно 0 ; я < l . длина ; я ++ ) System . вне . println ( л [ 0 ] + q + л [ я ] + q + ',' ); for ( int я = 10 ; я <= 18 ; я ++ ) System . вне . println ( л [ я ] ); } }
Такие программы выпускаются с различной длиной цикла:
Дэвид Мадор, создатель Unlambda , описывает мультихины следующим образом: [16]
«Мультиквин — это набор r различных программ (на r разных языках — без этого условия мы могли бы принять их всех равными одному куайну), каждая из которых способна напечатать любую из r программ (включая себя) в соответствии с передается аргумент командной строки. (Жульничество не допускается: аргументы командной строки не должны быть слишком длинными – передача полного текста программы считается мошенничеством)».
Мультикином, состоящим из двух языков (или бикином), будет программа, которая:
Тогда biquine можно рассматривать как набор из двух программ, каждая из которых может печатать любую из двух, в зависимости от предоставленного аргумента командной строки.
Теоретически ограничений на количество языков в мультикине нет. Мультикин (или пентаквин) из 5 частей был создан с помощью Python , Perl , C , NewLISP и F# [17] , а также существует мультикин из 25 языков. [18]
Подобно мультихайну, но в отличие от него, полиглотная программа — это компьютерная программа или сценарий, написанный в допустимой форме на нескольких языках программирования или форматах файлов путем объединения их синтаксиса. От полиглотной программы не требуется качества самовоспроизведения, хотя полиглотная программа также может быть квайной в одном или нескольких возможных способах выполнения.
В отличие от кайнов и мультиквинов, полиглотные программы не гарантированно существуют между произвольными наборами языков в результате теоремы рекурсии Клини, поскольку они полагаются на взаимодействие между синтаксисами, а не на доказуемое свойство, согласно которому один всегда может быть встроен в другой.
Радиационно-стойкий куайн — это куайн, из которого можно удалить любой отдельный символ, но при этом он по-прежнему создает исходную программу без пропущенных символов. По необходимости такие куины гораздо более запутаны, чем обычные куины, как видно из следующего примера на Ruby : [19]
eval = 'eval$q=%q(puts %q(10210/ #{ 1 1 if 1 == 21 } }/.i escape##/ 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 escape##/ 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}#" ##"