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

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

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

Имя

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

«Выдает ложь, если ему предшествует цитирование» дает ложь, если ему предшествует цитирование.

История

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

Требование «источника загрузки» Стандартной общественной лицензии GNU Affero основано на идее квина. ^[2]

Примеры

Конструктивный, который

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

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

# Example A. chr(39) == "'".
a = 'a = {}{}{}; print(a.format(chr(39), a, chr(39)))'; print(a.format(chr(39), a, chr(39)))

# Example B. chr(39) == "'".
b = 'b = %s%s%s; print(b %% (chr(39), b, chr(39)))'; print(b % (chr(39), b, chr(39)))

# Example C. %r will quote automatically.
c = 'c = %r; print(c %% c)'; print(c % c)

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

public class Quine
{
  public static void main(String[] args)
  {
    char q = 34;      // Quotation mark character
    String[] l = {    // Array of source code
    "public class Quine",
    "{",
    "  public static void main(String[] args)",
    "  {",
    "    char q = 34;      // Quotation mark character",
    "    String[] l = {    // Array of source code",
    "    ",
    "    };",
    "    for (int i = 0; i < 6; i++)           // Print opening code",
    "        System.out.println(l[i]);",
    "    for (int i = 0; i < l.length; i++)    // Print string array",
    "        System.out.println(l[6] + q + l[i] + q + ',');",
    "    for (int i = 7; i < l.length; i++)    // Print this code",
    "        System.out.println(l[i]);",
    "  }",
    "}",
    };
    for (int i = 0; i < 6; i++)           // Print opening code
        System.out.println(l[i]);
    for (int i = 0; i < l.length; i++)    // Print string array
        System.out.println(l[6] + q + l[i] + q + ',');
    for (int i = 7; i < l.length; i++)    // Print this code
        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 может воспользоваться этой функцией. Например, этот Руби Куайн:

eval s="print 'eval s=';p s"

Луа может делать:

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 и другие Lisps , а также в интерактивных языках, таких как APL , числа имеют самовычисление. В TI-BASIC , если последняя строка программы возвращает значение, возвращаемое значение отображается на экране. Следовательно, в таких языках программа, состоящая только из одной цифры, дает в результате 1-байтовый квин. Поскольку такой код не создается сам по себе, это часто считается мошенничеством.

Пустые какие

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

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

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

#!/bin/sh
# Invalid quine.
# Reading the executed file from disk is cheating.
cat $0

Более короткий вариант, использующий поведение директив shebang :

#!/bin/cat

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

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

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

Пример

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

#include <iostream>
#include <string>
using namespace std;

int main(int argc, char* argv[])
{
    char q = 34;
    string l[] = {
    "    ",
    "=============<<<<<<<< C++ Code >>>>>>>>=============",
    "#include <iostream>",
    "#include <string>",
    "using namespace 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 Code >>>>>>>>=============",
    "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; 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;
}

public class Quine
{
  public static void main(String[] args)
  {
    char q = 34;
    String[] l = {
    "    ",
    "=============<<<<<<<< C++ Code >>>>>>>>=============",
    "#include <iostream>",
    "#include <string>",
    "using namespace 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 Code >>>>>>>>=============",
    "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]);
  }
}

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

Хаскелл → Питон → Руби ^[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 → Пробелы → 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 rescue##/

1 1"[13,213].max_by{|s|s.size}#"##").gsub(/\d/){["=\47eval$q=%q(#$q)#\47##\47

",:eval,:instance_,"||=9"][eval$&]}
exit)#'##'

instance_eval='eval$q=%q(puts %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$&]}
exit)#'##'

/#{eval eval if eval==instance_eval}}/.i rescue##/

eval eval"[eval||=9,instance_eval||=9].max_by{|s|s.size}#"##"

Автоматическая генерация

Используя методы реляционного программирования , можно автоматически генерировать куайны, преобразуя интерпретатор (или, что то же самое, компилятор и среду выполнения) языка в реляционную программу, а затем находя фиксированную точку . ^[20]

См. также

Примечания

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

Ссылки

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

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

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

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

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

[Bratley_Millo-1] Братли, Пол ; Милло, Жан (1972). «Компьютерные развлечения: самовоспроизводящиеся автоматы». Программное обеспечение: практика и опыт . 2 (4): 397–400. дои : 10.1002/спе.4380020411 . S2CID 222194376 .

[Stet_and_AGPLV3-2] Кун, Брэдли М. (21 ноября 2007 г.). «стет и AGPLv3» . Юридический центр свободы программного обеспечения. Архивировано из оригинала 15 марта 2008 года . Проверено 14 июня 2008 г.

[3] «Программа Куайна» . wiki.c2.com .

[4] «Простой Java quine, самовоспроизводящийся (самокопирующийся) Java-код с текстовыми блоками. Этот код можно запускать с помощью Java 15+ или Java 13+ со специальными флагами. Лицензия является общедоступным достоянием, права не защищены» .

[6] «Наихудшее нарушение правил IOCCC 1994 г.» . Архивировано из оригинала 12 ноября 2020 года.

[7] «Мейк-файл» . IOCCC.org . Архивировано из оригинала 23 апреля 2019 года . Проверено 4 апреля 2019 г.

[8] Дэн Пипони (5 февраля 2008 г.). «Куайн третьего порядка на трех языках» .

[9] Брюс Эдигер. «Просите, и вы получите: Самовоспроизводящуюся программу, проходящую через три поколения: Python, Bash, Perl» . Архивировано из оригинала 23 февраля 2011 г. Проверено 17 марта 2011 г.

[10] бм (1 февраля 2011 г.). «мультихайн» . Архивировано из оригинала 15 апреля 2013 г.

[11] Дэн Пипони (30 января 2011 г.). «Куайн Сентрал» .

[12] Руслан Ибрагимов (20 апреля 2013 г.). «Quine Ruby -> Java -> C# -> Python» (на русском языке). Архивировано из оригинала 4 марта 2016 года . Проверено 20 апреля 2013 г.

[13] Шиничиро Хамадзи (10 ноября 2007 г.). «Quine от shinh (C C++ Ruby Python PHP Perl)» . (этот тоже полиглот )

[14] Ку-ма-ме (22 сентября 2009 г.). «Программирование Уроборос на 11 языках программирования» . Архивировано из оригинала 29 августа 2011 года . Проверено 17 марта 2011 г.

[15] Юсуке Эндо (2 ноября 2021 г.). «Quine Relay — программа-уроборос с более чем 100 языками программирования» . Гитхаб .

[16] Майкл Вехар (10 ноября 2019 г.). «C печатает JavaScript» .

[17] Дэвид Мадор. «Квайны (самовоспроизводящиеся программы)» .

[18] Рейнард ван Тондер (14 января 2020 г.). «Пентахин — мультихин 5 частей» . Гитхаб .

[19] Лу Ван (21 мая 2021 г.). "Квайн Хамелеон # Варианты" . Гитхаб .

[20] Юсуке Эндо. «Радиационно-стойкий Куайн» . Гитхаб . Проверено 24 февраля 2014 г.

[21] Берд, Уильям Э.; Холк, Эрик; Фридман, Дэниел П. (9 сентября 2012 г.). «MiniKanren, живой и без тегов: генерация Quine с помощью реляционных интерпретаторов (Жемчужина программирования)» (PDF) . Материалы ежегодного семинара по схемам и функциональному программированию 2012 г. Схема '12. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 8–29. дои : 10.1145/2661103.2661105 . ISBN 978-1-4503-1895-2 .

[1]

[2]

[3]

[4]

[а]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

v т и Стандартные тестовые задания
Панграмма Эталонная реализация Проверка работоспособности Стандартное тестовое изображение
Искусственный интеллект	Китайская комната Тест Тьюринга
Телевидение ( тестовая карта )	Цветные полосы SMPTE Цветные полосы EBU Тестовая таблица «голова индейца» Таблица разрешений EIA 1956 г. Тестовая карта BBC A , B , C , D , E , F , G , H , J , W , X ЭТП-1 Круглый узор Philips ( PM 5538 , PM 5540 , PM 5544 , PM 5644 ) Снелл и Уилкокс SW2/SW4 Телефункен ФуБК Тестовая карта TVE ВЕЙТ
Компьютерные языки	"Привет, мир!" программа Куайн Алгоритм Трабба Пардо – Кнута Тест мужчина или мальчик Просто еще один хакер Perl
Сжатие данных	Калгари корпус Кентерберийский корпус Силезское тело енвик8, енвик9
3D компьютерная графика	Корнеллская коробка Стэнфордский кролик Стэнфордский дракон Юта чайник Список
Машинное обучение	ImageNet база данных МНИСТ Список
Типографика ( текст-заполнитель )	Этаоин шрдлу Гамбургевоны Очень хорошо сделано Быстрая коричневая лиса перепрыгивает через ленивую собаку
Другой	3DБенчи Кислота 1 2 3 «Плохое яблоко!!» Тестовый файл EICAR функции для оптимизации ГТУБЕ Гарвардские приговоры Летать «Северный ветер и солнце» "Закусочная Тома" Универсальный лидер SMPTE Созвездие ЕВРИОН Вымогательство Вебдрайвер Торс Таблица испытаний разрешения ВВС США 1951 года