17-07-2023
Куайн, квайн (англ. 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.
(перенос строки добавлен для читабельности)
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 Си. Можно сделать рабочий вариант короче, но он будет не таким портируемым.
Вариант короче:
#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);}
И еще короче:
main(a){printf(a,34,a="main(a){printf(a,34,a=%c%s%c,34);}",34);}
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);}}
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))
print (lambda s:s+`s`+')')("print (lambda s:s+`s`+')')(")
Ещё один вариант для Python:
_='_=%r;print _%%_';print _%_
и другие[1].
main = putStr (s ++ show s) where s = "main = putStr (s ++ show s) where s = "
(переносы строк добавлены для читабельности)
>>+++++++>>++>>++++>>+++++++>>+>>++++>>+>>+++>>+>>+++++>>+>>++>>+ >>++++++>>++>>++++>>+++++++>>+>>+++++>>++>>+>>+>>++++>>+++++++>>+ >>+++++>>+>>+>>+>>++++>>+++++++>>+>>+++++>>++++++++++++++>>+>>+>> ++++>>+++++++>>+>>+++++>>++>>+>>+>>++++>>+++++++>>+>>+++++>>+++++ ++++++++++++++++++++++++>>+>>+>>++++>>+++++++>>+>>+++++>>++>>+>>+ >>+++++>>+>>++++++>>+>>++>>+>>++++++>>+>>++>>+>>++++++>>+>>++>>+> >++++++>>+>>++>>+>>++++++>>+>>++>>+>>++++++>>+>>++>>+>>++++++>>++ >>++++>>+++++++>>+>>+++++>>+++++++>>+>>+++++>>+>>+>>+>>++++>>+>>+ +>>+>>++++++>>+>>+++++>>+++++++>>+>>++++>>+>>+>>++>>+++++>>+>>+++ >>+>>++++>>+>>++>>+>>++++++>>+>>+++++>>+++++++++++++++++++>>++>>+ +>>+++>>++>>+>>++>>++++>>+++++++>>++>>+++++>>++++++++++>>+>>++>>+ +++>>+>>++>>+>>++++++>>++++++>>+>>+>>+++++>>+>>++++++>>++>>+++++> >+++++++>>++>>++++>>+>>++++++[<<]>>[>++++++[-<<++++++++++>>]<<++. .------------------->[-<.>>+<]>[-<+>]>]<<[-[-[-[-[-[-[>++>]<+++++ ++++++++++++++++++++++++>]<++>]<++++++++++++++>]<+>]<++>]<<[->.<]<<]
<?php $a="$"; $e='printf(\'<?php %sa="$"; %se=%s; eval(%se);\', $a, $a, var_export($e, 1), $a);'; eval($e);
s="s.inspect+%q{;puts 's='+eval(s)}";puts 's='+eval(s)
eval [set B {puts "eval \[set B {$B}\]"}]
Также пример без eval:
puts [format [set s {puts [format [set s {%s}] $s]}] $s]
Версия с 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','"','\\');}}
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;
Куайн (программирование).