Куайн (программирование)

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Куайн, квайн (англ. quine) — компьютерная программа, которая выдаёт на выходе точную копию своего исходного текста.

Следует заметить, что программы, использующие внешние данные, квайнами не считаются; то есть исключается прочтение текста программы из файла, ввод его с клавиатуры и так далее. Кроме того, не считается квайном «программа», не содержащая вообще никакого кода (вырожденный случай). В книге «Этюды для программистов» Чарльза Уэзерелла сформулировано более строгое условие: программа не должна пользоваться трюками, позволяющими получить доступ к своему исходному коду, хранящемуся в памяти загрузчика или интерпретатора. Поэтому квайн на бейсике 10 LIST — не совсем честный, также как SOURCE TYPE на языке Форт.

Термин получил название от имени американского логика и философа Уилларда Ван Ормана Квайна (англ. Willard Van Orman Quine) (1908—2000), который занимался углубленным изучением косвенного самоупоминания (англ. indirect self-reference).

История[править | править вики-текст]

Квайн существует в любом языке программирования, имеющем возможность выводить произвольную вычисляемую строку текста. Идея квайнов была впервые описана Полом Братли (англ. Bratley, Paul) и Жаном Милло (англ. Millo, Jean) в «Computer Recreations; Self-Reproducing Automata», Software — Practice & Experience, выпуск 2 (1972), с.397—400. Братли заинтересовался саморепродуцированием программ после знакомства с первой такой программой, написанной на языке программирования Atlas Autocode в Эдинбурге в 1960-х преподавателем и исследователем Хэмишем Дюаром (англ. Hamish Dewar).

Вот исходный текст этой программы:

%BEGIN
!THIS IS A SELF-REPRODUCING PROGRAM
%ROUTINESPEC R
R
PRINT SYMBOL(39)
R
PRINT SYMBOL(39)
NEWLINE
%CAPTION %END~
%CAPTION %ENDOFPROGRAM~
%ROUTINE R
%PRINTTEXT '
%BEGIN
!THIS IS A SELF-REPRODUCING PROGRAM
%ROUTINESPEC R
R
PRINT SYMBOL(39)
R
PRINT SYMBOL(39)
NEWLINE
%CAPTION %END~
%CAPTION %ENDOFPROGRAM~
%ROUTINE R
%PRINTTEXT '
%END
%ENDOFPROGRAM

Примеры[править | править вики-текст]

В случае написании квайна на Си/Си++ программа разделяется на две части: (а) исходный текст первой части (кода) и (б) код, ответственный за вывод результата. Программа использует вторую часть для вывода первой и какой-либо специальный приём для вывода второй части. Есть множество способов организовать данные в исходном тексте программы, но обычный признак первой части квайна (блока данных) — отображение в нём какой-либо части всей программы.

JavaScript[править | править вики-текст]

function f(){alert(f.toString()+"f();");}f();

Паскаль[править | править вики-текст]

Приведённая программа составлена инженером Каунасского политехнического института Витаутасом Валайтисом.

program autobiografija (output);
  var c : array[1..14] of string[60];
      i : integer;
begin
c[ 1]:='program autobiografija (output); ';
c[ 2]:=' var c : array[1..14] of string[60]; ';
c[ 3]:=' i : integer; ';
c[ 4]:='begin ';
c[ 5]:='for i := 1 to 4 do writeln(c[i]); ';
c[ 6]:='for i := 1 to 13 do writeln(c[14,1],c[14,2],i:2,c[14,5], ';
c[ 7]:=' c[14,6],c[14,7],c[14,8],c[i],c[14,8],c[14,9]); ';
c[ 8]:='for i := 1 to 8 do write(c[14,i]); ';
c[ 9]:='for i := 1 to 8 do write(c[14,i]); ';
c[10]:='for i := 8 to 60 do write(c[14,i]); ';
c[11]:='writeln(c[14,8],c[14,9]); ';
c[12]:='for i := 5 to 13 do writeln(c[i]); ';
c[13]:='end. ';
c[14]:='c[14]:=''; ';
for i := 1 to 4 do writeln(c[i]);
for i := 1 to 13 do writeln(c[14,1],c[14,2],i:2,c[14,5],
           c[14,6],c[14,7],c[14,8],c[i],c[14,8],c[14,9]);
for i := 1 to 8 do write(c[14,i]);
for i := 1 to 8 do write(c[14,i]);
for i := 8 to 60 do write(c[14,i]);
writeln(c[14,8],c[14,9]);
for i := 5 to 13 do writeln(c[i]);
end.

Delphi/Паскаль[править | править вики-текст]

(перенос строки добавлен для читабельности)

var s:string='var s:string=;begin insert(#39+s+#39,s,14);write(s)end.';
begin insert(#39+s+#39,s,14);write(s)end.

Си/Си++[править | править вики-текст]

#include<stdio.h>
char*i="\\#include<stdio.h> ",n='\n',q='"',*p=
"%s%cchar*i=%c%c%s%c,n='%cn',q='%c',*p=%c%c%s%c,*m=%c%c%s%c%c;%s%c",*m=
"int main(){return!printf(p,i+1,n,q,*i,i,q,*i,q,n,q,p,q,n,q,m,q,n,m,n);}"
;int main(){return!printf(p,i+1,n,q,*i,i,q,*i,q,n,q,p,q,n,q,m,q,n,m,n);}

Это классический квайн на Си, полностью отвечающий ANSI. Можно сделать рабочий вариант короче, но он будет нарушать стандарты, и следовательно будет плохо переносим.

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

#include <stdio.h>
void main(char* a){printf(a,10,34,a="#include <stdio.h>%cvoid main(char* a){printf(a,10,34,a=%c%s%c,34);}",34);}

Ещё более короткий вариант в дополнение к этому эксплуатирует нестандартную возможность неявного объявления функции (англ. implicit declaration) для printf():

main(a){printf(a,34,a="main(a){printf(a,34,a=%c%s%c,34);}",34);}

C#[править | править вики-текст]

using System;
class A
{
   static void Main()
   {
      string s=@"using System;
                 class A
                 {
                    static void Main()
                    {
                       string s=@{0}{1}{0};
                       Console.Write(s,'{0}',s);}}}}";
                       Console.Write(s,'"',s);
                    }
                 }";
   }
}

Forth[править | править вики-текст]

s" 2dup cr 115 emit 34 emit space type 34 emit space type cr" 2dup cr 115 emit 34 emit space type 34 emit space type cr

и ещё

s" 2constant s : quine 115 emit 34 emit space [ s ] sliteral 2dup type 34 emit type ;"2constant s : quine 115 emit 34 emit space [ s ] sliteral 2dup type 34 emit type ;

Или такой с циклами

: q s" 2dup 32 34 115 32 113 32 58 7 0 do emit loop type 34 emit type ;"2dup 32 34 115 32 113 32 58 7 0 do emit loop type 34 emit type ;

Но самый простой — с использованием слова SOURCE (оставляет после своего выполнения адрес входной строки) и TYPE для печати полученного результата:

SOURCE TYPE

Фортран[править | править вики-текст]

(Свободный формат записи кода (стандарт ФОРТРАН-90), переносы строк добавлены для читабельности)

character(65)::s='character(65)::s=;print*,s(1:17),char(39),s,char(39),s(18:65);end';
print*,s(1:17),char(39),s,char(39),s(18:65);
end

Лисп[править | править вики-текст]

((lambda (x) (print (list x (list 'quote x)))) '(lambda (x) (print (list x (list 'quote x)))))

и ещё один изящный пример из книги «Let Over Lambda»:

(let ((let '`(let ((let ',let)) ,let))) `(let ((let ',let)) ,let))

Python[править | править вики-текст]

print (lambda s:s+`s`+')')("print (lambda s:s+`s`+')')(")

Ещё один вариант для Python:

_='_=%r;print _%%_';print _%_

и другие[1].

Haskell[править | править вики-текст]

main = putStr (s ++ show s) where s = "main = putStr (s ++ show s) where s = "

Brainfuck[править | править вики-текст]

(переносы строк добавлены для читабельности)

>>+++++++>>++>>++++>>+++++++>>+>>++++>>+>>+++>>+>>+++++>>+>>++>>+
>>++++++>>++>>++++>>+++++++>>+>>+++++>>++>>+>>+>>++++>>+++++++>>+
>>+++++>>+>>+>>+>>++++>>+++++++>>+>>+++++>>++++++++++++++>>+>>+>>
++++>>+++++++>>+>>+++++>>++>>+>>+>>++++>>+++++++>>+>>+++++>>+++++
++++++++++++++++++++++++>>+>>+>>++++>>+++++++>>+>>+++++>>++>>+>>+
>>+++++>>+>>++++++>>+>>++>>+>>++++++>>+>>++>>+>>++++++>>+>>++>>+>
>++++++>>+>>++>>+>>++++++>>+>>++>>+>>++++++>>+>>++>>+>>++++++>>++
>>++++>>+++++++>>+>>+++++>>+++++++>>+>>+++++>>+>>+>>+>>++++>>+>>+
+>>+>>++++++>>+>>+++++>>+++++++>>+>>++++>>+>>+>>++>>+++++>>+>>+++
>>+>>++++>>+>>++>>+>>++++++>>+>>+++++>>+++++++++++++++++++>>++>>+
+>>+++>>++>>+>>++>>++++>>+++++++>>++>>+++++>>++++++++++>>+>>++>>+
+++>>+>>++>>+>>++++++>>++++++>>+>>+>>+++++>>+>>++++++>>++>>+++++>
>+++++++>>++>>++++>>+>>++++++[<<]>>[>++++++[-<<++++++++++>>]<<++.
.------------------->[-<.>>+<]>[-<+>]>]<<[-[-[-[-[-[-[>++>]<+++++
++++++++++++++++++++++++>]<++>]<++++++++++++++>]<+>]<++>]<<[->.<]<<]

PHP[править | править вики-текст]

 <?php $a="$"; $e='printf(\'<?php %sa="$"; %se=%s; eval(%se);\', $a, $a, var_export($e, 1), $a);'; eval($e);

Ruby[править | править вики-текст]

s="s.inspect+%q{;puts 's='+eval(s)}";puts 's='+eval(s)

И два наиболее коротких:

_="_=%p;puts _%%_";puts _%_
puts <<2*2,2
puts <<2*2,2
2

Tcl[править | править вики-текст]

eval [set B {puts "eval \[set B {$B}\]"}]

Также пример без eval:

puts [format [set s {puts [format [set s {%s}] $s]}] $s]

Java[править | править вики-текст]

Версия с printf (c версии Java 5.0): (строка str разделена для читабельности)

package test;
public class Reproduce{
static String str = "package test;%2$1cpublic class Reproduce"
        + "{%2$1cstatic String str = %3$1c%1$1s%3$1c;%2$1cpublic static void main(String"
        + "[] args){System.out.printf(str, str,'%4$1cn','%3$1c','%4$1c%4$1c');}}";
public static void main(String[] args){System.out.printf(str, str,'\n','"','\\');}}

PL/SQL[править | править вики-текст]

DECLARE C VARCHAR(10):='''';X VARCHAR2(255):=
'DECLARE C VARCHAR(10):=;X VARCHAR2(255):=;BEGIN X:=;BEGIN dbms_output.put_line(SUBSTR(X,1,23)||C||C||C||C||SUBSTR(X,24,18));dbms_output.put_line(C||X||C);dbms_output.put_line(SUBSTR(X,52));END;'
;BEGIN DBMS_OUTPUT.put_line(SUBSTR(X,1,23)||C||C||C||C||SUBSTR(X,24,18));DBMS_OUTPUT.put_line(C||X||C);DBMS_OUTPUT.put_line(SUBSTR(X,52));END;

SQL[править | править вики-текст]

SELECT REPLACE(REPLACE('SELECT REPLACE(REPLACE("$",CHAR(34),CHAR(39)),CHAR(36),"$") AS Quine',CHAR(34),CHAR(39)),CHAR(36),'SELECT REPLACE(REPLACE("$",CHAR(34),CHAR(39)),CHAR(36),"$") AS Quine') AS Quine

Perl[править | править вики-текст]

$_=q{$_=
print("\$_=q{".$_."};".&p($_));sub p {@_[0]=~s/\$\_\=//;return @_[0]}};
print("\$_=q{".$_."};".&p($_));sub p {@_[0]=~s/\$\_\=//;return @_[0]}

Короче:

$_=q{$_=q{x};s/x/$_/;print};s/x/$_/;print

Malbolge[править | править вики-текст]

Написание квайна на Malbolge хотя и затруднительно, но всё же возможно.

Вариации[править | править вики-текст]

Квайн n-ного порядка[править | править вики-текст]

Квайном n-ного порядка для n>1 называется программа, которая выводит на экран такой код A_1, что \forall k: 1<k<n запуск кода A_{k-1} выводит на экран код A_k. При этом код A_{n-1} выводит на экран код изначальной программы.

Цепной квайн[править | править вики-текст]

Цепным квайном для списка языков программирования A_1,...,A_n называется такой код на языке A_1, что при поочерёдном запуске всех кодов \forall k<n код на языке A_k выводит произвольный код на языке A_{k+1}. При этом сгенерированный в результате n-1 шагов код на языке A_n выводит на экран изначальный код на языке A_1.

Японский программист Юсукэ Эндо в 2013 году создал цепной квайн для n=50 с началом на языке программирования Ruby (впрочем, согласно определению, благодаря цикличности алгоритма при наличии кодов на всех языках начинать исполнение цикла можно с любого из них). Языки программирования в квайне расположены в алфавитном порядке.[2][3].

Другие вариации[править | править вики-текст]

Юсукэ Эндо также создал псевдоквайн на Ruby, выводящий свой текст с помощью псевдоанимации (прорисовки новых комбинаций символов на консоли с заданным интервалом)[4].

Также своеобразной математической вариацией квайна можно считать самореферентную формулу Таппера — неравенство, точки истинности которого в определённой области плоскости рисуют эту же формулу.

См. также[править | править вики-текст]

  • HQ9+эзотерический язык программирования; позволяет с помощью одной команды вывести свой выполняющийся код.

Примечания[править | править вики-текст]

Литература[править | править вики-текст]

  • Ч. Уэзерелл, Этюды для программистов, М.: «Мир», 1982, с. 59.
  • Хофштадтер, Дуглас: «Гедель, Эшер, Бах: эта бесконечная гирлянда». Издательство: Бахрах-М. ISBN 5-94648-001-4, 0-465-02656-7. 2001 г.

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