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

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

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

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

Название «quine» было придумано Дуглас Хофштадтер в своей научно-популярной книге Гедель, Эшер, Бах, в честь философа Уиллард Ван Орман Куайн (1908–2000), который провел обширное исследование косвенная ссылка на себя, и, в частности, для следующего парадоксального выражения, известного как Парадокс Куайна:

«Дает ложь, если ей предшествует его цитата», дает ложь, если ей предшествует его цитата.

История

Идея самовоспроизводящиеся автоматы пришло из зарождения вычислительной техники, если не раньше. Джон фон Нейман теоретизировал о них в 1940-х годах. Потом, Пол Брэтли и статья Жана Милло «Компьютерные воссоздания: самовоспроизводящиеся автоматы» обсуждали их в 1972 году.[1]Брэтли впервые заинтересовался самовоспроизводящимися программами после того, как увидел первую известную такую ​​программу, написанную на Атлас Автокод в Эдинбурге в 1960-х годах Эдинбургский университет лектор и исследователь Хэмиш Дьюар.

Требование об источнике загрузки Стандартная общественная лицензия Affero основан на идее лозы.

Примеры

Конструктивные лозы

В общем, метод, используемый для создания куин на любом языке программирования, состоит в том, чтобы иметь в программе две части: (а)код используется для фактической печати и (б)данные который представляет собой текстовую форму кода. Код функционирует, используя данные для печати кода (что имеет смысл, поскольку данные представляют текстовую форму кода), но он также использует данные, обработанные простым способом, для печати текстового представления самих данных.

Вот три небольших примера на Python3:

1 а='a =% s% s% s; печать (a%%(chr (39), a, chr (39))) ';Распечатать(а%(chr(39),а,chr(39)))2 б='b ={}{}{}; print (b.format (chr (39), b, chr (39))) ';Распечатать(б.формат(chr(39),б,chr(39)))3 c='c =%р; печать (c%%в) ';Распечатать(c%c)4 # обратите внимание, что% r будет цитировать автоматически

В Python 3.8:

1 exec(s:='print ("exec (s: =%р)"% s)')

Следующее Ява код демонстрирует базовую структуру квайна.

общественный учебный класс Куайн{  общественный статический пустота главный(Нить[] аргументы)  {    char q = 34;      // Символ кавычки    Нить[] л = {    // Массив исходного кода    "паблик класс Куайн",    "{",    "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 ,    "System.out.println (l [6] + q + l [i] + q + ',');",    "for (int i = 7; i ,    "System.out.println (l [i]);",    "  }",    "}",    };    за(int я = 0; я < 6; я++)           // Распечатать код открытия        Система.из.println(л[я]);    за(int я = 0; я < л.длина; я++)    // Выводим строковый массив        Система.из.println(л[6] + q + л[я] + q + ',');    за(int я = 7; я < л.длина; я++)    // Распечатать этот код        Система.из.println(л[я]);  }}

Исходный код содержит сам массив строк, который выводится дважды, один раз в кавычках.

Этот код был адаптирован из оригинального сообщения c2.com, где автор, Джейсон Уилсон, разместил его как минималистичную версию Quine без комментариев Java.[2]

Eval quines

Некоторые языки программирования имеют возможность оценивать строку как программу. Куайнс может воспользоваться этой функцией. Например, это Рубин лоза:

оценка s="print 'eval s ='; p s"

"Жульничество" кайнс

Самооценка

На многих функциональных языках, включая Схема и другие Лиспы и интерактивные языки, такие как APL, числа являются самооценочными. В TI-BASIC, если последняя строка программы возвращает значение, возвращаемое значение отображается на экране. Следовательно, на таких языках программа, содержащая одну цифру, дает 1-байтовый quine. Поскольку такой код не строить само по себе это часто считается обманом.

1

На некоторых языках, особенно языки сценариев но также C, пустой исходный файл - это фиксированная точка языка, являющаяся допустимой программой, не производящей вывода.[а] Такая пустая программа, представленная как «самая маленькая самовоспроизводящаяся программа в мире», однажды выиграла приз за «худшее нарушение правил» в Международный конкурс запутанного кода C.[3] Программа фактически не компилировалась, а использовалась cp чтобы скопировать файл в другой файл, который можно было бы выполнить, чтобы ничего не печатать.[4]

Другие сомнительные методы включают использование сообщений компилятора; например, в GW-BASIC среды, ввод «Синтаксической ошибки» заставит интерпретатор ответить «Синтаксической ошибкой».

Проверка исходного кода

Куайнс, по определению, не может получать любой форма ввода, включая чтение файла, что означает, что quine считается "читерским", если он смотрит на свой собственный исходный код. Следующее ракушка скрипт не квинт:

#! / bin / sh# Неверный quine.# Чтение исполняемого файла с диска - чит.Кот $0

Программы Уроборос

Концепция куайна может быть расширена до нескольких уровней рекурсии, начиная с "уроборос программ »или хайн-реле. Это не следует путать с мультикинс.

Пример

Эта программа Java выводит исходный код программы C ++, которая выводит исходный код Java.

#включают <iostream>#включают <string>с помощью пространство имен стандартное;int главный(int argc, char* argv[]){    char q = 34;    нить л[] = {    "    ",    "============= <<<<<<<< Код C ++ >>>>>>>> =============",    "#include ",    "#include <строка>",    "используя пространство имен 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 static void main (String [] args)",    "  {",    "char q = 34;",    "Строка [] l = {",    "    };",    "for (int i = 2; i <= 9; i ++)",    "System.out.println (l [i]);",    "for (int i = 0; i ,    "System.out.println (l [0] + q + l [i] + q + ',');",    "for (int i = 10; i <= 18; i ++)",    "System.out.println (l [i]);",    "  }",    "}",    };    за(int я = 20; я <= 25; я++)        cout << л[я] << конец;    за(int я = 0; я <= 34; я++)        cout << л[0] + q + л[я] + q + ',' << конец;    за(int я = 26; я <= 34; я++)        cout << л[я] << конец;    возвращаться 0;}
общественный учебный класс Куайн{  общественный статический пустота главный(Нить[] аргументы)  {    char q = 34;    Нить[] л = {    "    ",    "============= <<<<<<<< Код C ++ >>>>>>>> =============",    "#include ",    "#include <строка>",    "используя пространство имен 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 static void main (String [] args)",    "  {",    "char q = 34;",    "Строка [] l = {",    "    };",    "for (int i = 2; i <= 9; i ++)",    "System.out.println (l [i]);",    "for (int i = 0; i ,    "System.out.println (l [0] + q + l [i] + q + ',');",    "for (int i = 10; i <= 18; i ++))",    "System.out.println (l [i]);",    "  }",    "}",    };    за(int я = 2; я <= 9; я++)        Система.из.println(л[я]);    за(int я = 0; я < л.длина; я++)        Система.из.println( л[0] + q + л[я] + q + ',' );    за(int я = 10; я <= 18; я++)        Система.из.println(л[я]); }}

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

Multiquines

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

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

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

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

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

Теоретически нет ограничений на количество языков в мультихине, 5-частный мультихайн (или пентаквин) был произведен с Python, Perl, C, NewLISP, и F #[15]и есть еще 25-язычный мультихайн.[16]

Радиационно стойкий

А радиационно стойкий quine - это quine, из которого можно удалить любой отдельный символ, но при этом исходная программа по-прежнему воспроизводится без пропущенных символов. По необходимости, такие хайны гораздо более запутанные, чем обычные хайны, как видно из следующего примера. Рубин:[17]

оценка='eval $ q =% q (ставит% q (10210 / # {1 1 if 1 == 21}} /. i rescue ## /1 1 "[13,213] .max_by {| s | s.size} #" ## "). Gsub (/ d /) {[" = 47eval $ q =% q (# $ q) # 47 ## 47",: eval,: instance _," || = 9 "] [eval $ &]}выход)#'##'instance_eval='eval $ q =% q (ставит% q (10210 / # {1 1 if 1 == 21}} /. i rescue ## /1 1 "[13,213] .max_by {| s | s.size} #" ## "). Gsub (/ d /) {[" = 47eval $ q =% q (# $ q) # 47 ## 47",: eval,: instance _," || = 9 "] [eval $ &]}выход)#'##'/#{оценка оценка если оценка==instance_eval}}/.я спасать##/оценка оценка"[eval || = 9, instance_eval || = 9] .max_by {| s | s.size} #"##"

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

Примечания

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

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

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

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

внешняя ссылка