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

У этого термина существуют и другие значения, см. Куайн.

Куайн, квайн (англ. 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

Примеры

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

Паскаль

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

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)

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;

См. также

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

Примечания

1. ↑ Quine (Python), LiteratePrograms

Ссылки

• The Quine Page (англ.) — страница Гарри Томпсона.
• Tupper’s Self-Referential Formula — необычный пример: математическая формула (в данном случае программа), выполняемая интерпретатором Mathematica, выдает свой текст.
• Ч. Уэзерелл, Этюды для программистов, М.: «Мир», 1982, с. 59.
• Хофштадтер, Дуглас: «Гедель, Эшер, Бах: эта бесконечная гирлянда». Издательство: Бахрах-М. ISBN 5-94648-001-4, 0-465-02656-7. 2001 г.
• Un «quine» en Transact SQL et ANSI SQL (фр.).
• Как писать квайны, статья на Хабрахабре

Для улучшения этой статьи желательно?: Проставив сноски, внести более точные указания на источники.