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

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

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

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

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

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

История [ править ]

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

Требование «скачать источник» Стандартной общественной лицензии Affero основано на идее quine.

Примеры [ править ]

Конструктивные лозы [ править ]

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

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

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

В Python 3.8:

exec ( s : = 'print ("exec (s: = % r )" % s )' )

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

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

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

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

Благодаря новой функции текстовых блоков в Java 15 (или новее) возможна более удобочитаемая и простая версия: ^[3]

открытый  класс  Quine  { public  static  void  main ( String []  args )  { String  textBlockQuotes  =  new  String ( new  char [] { '"' ,  '"' ,  '"' }); char  newLine  =  10 ;  String  source  =  " " " открытый класс Quine { public static void main (String [] args) { String textBlockQuotes = new String (new char [] {'" ' ,  '"' , '"' }); Символ  Newline  =  10 ; Строка  источника  =  % s ; система . Из . Println ( источник . Отформатирован ( textBlockQuotes  +  Newline  +  источник  +  textBlockQuotes )); } } """;  System.out.println (source.formatted (textBlockQuotes + newLine + source + textBlockQuotes)); } }

Eval quines [ править ]

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

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

"Мошенничество" quines [ править ]

Самооценка [ править ]

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

1

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

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

Проверка исходного кода [ править ]

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

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

Программы Уроборос [ править ]

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

Пример [ править ]

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

#include  <iostream>#include  <строка>используя  пространство имен  std ;int  main ( int  argc ,  char *  argv []) {  char  q  =  34 ;  строка  l []  =  {  "" ,  "============= <<<<<<<< Код C ++ >>>>>>>> ========= ==== " ,  " #include <iostream> " ,  " #include <string> " ,  " using namespace 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 >>>>>>>> ============= " ,  " открытый класс 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 ;  для ( int я  =  0 ;  я  <=  34 ;  i ++ )  cout  <<  l [ 0 ]  +  q  +  l [ i ]  +  q  +  ','  <<  endl ;  для ( int  i  =  26 ;  i  <=  34 ;  i ++ )  cout  <<  l [ i ]  <<  endl ;  возврат  0 ; }

публичный  класс  Quine {  публичный  статический  void  main ( String []  args )  {  char  q  =  34 ;  String []  l  =  {  "" ,  "============= <<<<<<<< Код C ++ >>>>>>>> ========= ==== " ,  " #include <iostream> " ,  " #include <string> " ,  " using namespace 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 >>>>>>>> ==========" ,  " открытый класс 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  =  2 ;  i  <=  9 ;  i ++ )  System . из .println ( l [ я ] ); for ( int  i  =  0 ;  i  <  l . length ;  i ++ )  System . из . println (  l [ 0 ]  +  q  +  l [ i ]  +  q  +  ','  );  для ( int  i  =  10 ;  i  <=  18 ;  i ++ )  System . из . println (l [ i ] ); } }

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

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

Multiquines [ править ]

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

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

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

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

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

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

Радиационно-стойкий [ править ]

Излучение закаленного Куайн является Куайном , который может иметь любой одиночный символ удаляется и до сих пор производит оригинальную программу, не недостающего характера. По необходимости такие кайны намного более запутаны, чем обычные кайны, как видно из следующего примера в Ruby : ^[18]

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

См. Также [ править ]

Заметки [ править ]

Ссылки [ править ]

Дальнейшее чтение [ править ]

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

Внешние ссылки [ править ]