Куайн (вычисления)

Самовоспроизводящаяся программа

Вывод quine точно такой же, как и его исходный код ( подсветка синтаксиса , демонстрируемая текстовым редактором в верхней половине изображения, не влияет на вывод quine).

Куайн — это компьютерная программа , которая не принимает никаких входных данных и выдает копию собственного исходного кода в качестве единственного результата. Стандартными терминами для этих программ в литературе по теории вычислимости и информатике являются «самовоспроизводящиеся программы», «самовоспроизводящиеся программы» и «самокопирующиеся программы».

Куайн — это фиксированная точка среды выполнения, если эту среду рассматривать как функцию , преобразующую программы в их выходные данные. Куайны возможны в любом языке программирования, полном по Тьюрингу , что является прямым следствием теоремы Клини о рекурсии . Для развлечения программисты иногда пытаются разработать кратчайший куайн на любом языке программирования .

Имя

Название «куайн» было придумано Дугласом Хофштадтером в его научно-популярной книге « Гёдель, Эшер, Бах » в честь философа Уилларда Ван Ормана Куайна (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 ( л [ я ] ); } }              

Такие программы выпускаются с различной длиной цикла:

• Хаскелл → Питон → Руби ^[7]
• Python → Bash → Perl ^[8]
• C → Haskell → Python → Perl ^[9]
• Haskell → Perl → Python → Ruby → C → Java ^[10]
• Руби → Java → C# → Python ^[11]
• C → C++ → Ruby → Python → PHP → Perl ^[12]
• Ruby → Python → Perl → Lua → OCaml → Haskell → C → Java → Brainfuck → Whitespace → Unlambda ^[13]
• Ruby → Scala → Scheme → Scilab → Shell (bash) → S-Lang → Smalltalk → Squirrel3 → Standard ML → ... → Rexx (128 (а ранее 50) языков программирования) ^[14]
• Веб-приложение → C (исходный код веб-приложения состоит из HTML , JavaScript и CSS ) ^[15]

Мультикины

Дэвид Мадор, создатель Unlambda , описывает мультихины следующим образом: ^[16]

«Мультиквин — это набор r различных программ (на r разных языках — без этого условия мы могли бы принять их всех равными одному куайну), каждая из которых способна напечатать любую из r программ (включая себя) в соответствии с передается аргумент командной строки. (Жульничество не допускается: аргументы командной строки не должны быть слишком длинными – передача полного текста программы считается мошенничеством)».

Мультикином, состоящим из двух языков (или бикином), будет программа, которая:

• При запуске представляет собой куайн на языке X.
• При предоставлении определяемого пользователем аргумента командной строки выводит вторую программу на языке Y.
• Учитывая, что вторая программа на языке Y при нормальном запуске также будет куайном на языке Y.
• Учитывая вторую программу на языке Y и аргумент командной строки, определяемый пользователем, будет создана исходная программа на языке X.

Тогда 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}#" ##" 

Смотрите также

• Портал компьютерного программирования

• Диагональная лемма
• Эффект Дросте
• Комбинатор с фиксированной точкой
• Самомодифицирующийся код
• Самопереводчик
• Самовоспроизводящаяся машина
• Самовоспроизведение
• Самостоятельный переезд
• ТиддлиВики
• Самореферентная формула Таппера
• Языки программирования
• Парадокс Куайна
• Полиглот (компьютер)

Примечания

1. Примеры включают Bash , Perl и Python.

Рекомендации

1. Брэтли, Пол; Милло, Жан (1972). «Компьютерные развлечения: самовоспроизводящиеся автоматы». Программное обеспечение: практика и опыт . 2 (4): 397–400. дои : 10.1002/сп.4380020411. S2CID  222194376.
2. Кун, Брэдли М. (21 ноября 2007 г.). «стет и AGPLv3». Юридический центр свободы программного обеспечения. Архивировано из оригинала 15 марта 2008 года . Проверено 14 июня 2008 г.
3. "Программа Куайна". wiki.c2.com .
4. «Простой Java quine, самовоспроизводящийся (самокопирующийся) Java-код с текстовыми блоками. Этот код можно запускать с помощью Java 15+ или Java 13+ со специальными флагами. Лицензия является общедоступным достоянием, права не защищены».
5. «Наихудшее нарушение правил IOCCC 1994 г.» . Архивировано из оригинала 12 ноября 2020 года.
6. "Makefile". IOCCC.org . Архивировано из оригинала 23 апреля 2019 года . Проверено 4 апреля 2019 г.
7. Дэн Пипони (5 февраля 2008 г.). «Куайн третьего порядка на трех языках».
8. Брюс Эдигер. «Просите, и вы получите: Самовоспроизводящуюся программу, проходящую через три поколения: Python, Bash, Perl». Архивировано из оригинала 23 февраля 2011 г. Проверено 17 марта 2011 г.
9. BM (1 февраля 2011 г.). «мультихин». Архивировано из оригинала 15 апреля 2013 г.
10. Дэн Пипони (30 января 2011 г.). «Куайн Сентрал».
11. Руслан Ибрагимов (20 апреля 2013 г.). «Quine Ruby -> Java -> C# -> Python» (на русском языке). Архивировано из оригинала 4 марта 2016 года . Проверено 20 апреля 2013 г.
12. Шиничиро Хамадзи (10 ноября 2007 г.). «Quine от shinh (C C++ Ruby Python PHP Perl)».(этот тоже полиглот )
13. Ку-ма-ме (22 сентября 2009 г.). «Программирование Уроборос на 11 языках программирования». Архивировано из оригинала 29 августа 2011 года . Проверено 17 марта 2011 г.
14. Юсуке Эндо (2 ноября 2021 г.). «Quine Relay — программа-уроборос, поддерживающая более 100 языков программирования». Гитхаб .
15. Майкл Вехар (10 ноября 2019 г.). «C печатает JavaScript».
16. Дэвид Мадор. «Квайны (самовоспроизводящиеся программы)».
17. Рейнард ван Тондер (14 января 2020 г.). «Пентахин – мультихин 5 частей». Гитхаб .
18. Лу Ван (21 мая 2021 г.). «Квайн Хамелеон # Варианты». Гитхаб .
19. Юсуке Эндо. «Радиационно-стойкий Куайн». Гитхаб . Проверено 24 февраля 2014 г.

дальнейшее чтение

• Дуглас Хофштадтер : Гёдель, Эшер, Бах: Вечная золотая коса
• Кен Томпсон : «Размышления о доверии» ( Сообщения ACM , 27 (8):761-3)

Внешние ссылки

• TiddlyWiki, квайн, проявленный как вики
• Куайн Пейдж (Гэри П. Томпсон)
• Краткое руководство по самореферентным программам
• QuineProgram в Wiki Портлендского репозитория шаблонов
• Обсуждение Куайнса Дэвидом Мадором
• ZIP-файл Куайн
• Заархивируйте файлы до конца
• Введение в куайны, в частности в куайны, использующие более одного языка.
• Веб-страница Quine: веб-страница HTML+JavaScript, соответствующая стандартам, на которой отображается собственный исходный код.
• HTML Quine: HTML-страница, которая использует только HTML и CSS для отображения собственного исходного кода.
• Quine Challenge для JavaScript-машины Тома с серией интерактивных подсказок.
• Java Quine, построенный прямо на основе теоремы Клини о неподвижной точке, композиции и snm.
• Куайн с QR-кодом