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

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

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

Термин получил название от имени американского логика и философа Уилларда Ван Ормана Куайна (англ. 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

Примеры

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

Delphi/Паскаль

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

  {$APPTYPE CONSOLE}const s=
 '{$APPTYPE CONSOLE}const s=;begin writeln(copy(s,1,26),#39,s,#39,copy(s,27,57));end.'
                            ;begin writeln(copy(s,1,26),#39,s,#39,copy(s,27,57));end.

Си/Си++

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

#include <stdio.h>
int main (void) { char q='"'; puts("#include <stdio.h>"); char *x = "int main (void) 
{ char q='%c'; puts(%c#include <stdio.h>%c); char *x = %c%s%c; printf (x,q,q,q,q,x,q,q,q); 
return puts(%c%c); }"; printf (x,q,q,q,q,x,q,q,q); return puts(""); }

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

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);}}

Фортран

(Свободный формат записи кода (стандарт ФОРТРАН-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

Forth

SOURCE TYPE

Лисп

Не вполне корректное решение, поскольку в нем отсутствуют операции непосредственного вывода программы.

    (funcall (lambda (x) 
               (append x (list (list 'quote x))))
             '(funcall (lambda (x) 
                          (append x (list (list 'quote x))))))

Более корректное решение:

(progn (setf a "(progn (setf a ~S) (format t a a))") (format t a a))

Предложено одним из студентов ШАД.

Python

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

Еще вариант c python:

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

Взято c http://miscoranda.com/37

Brainfuck

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

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

PHP

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

 <?php
	$bax='$';
	$eval='printf ("<?php
	%sbax=\'%s\';
	%seval=%s;
	eval(%seval);
?>",
	$bax,
	$bax,
	$bax,
	var_export($eval, true),
	$bax);';
eval($eval);
?>

Ruby

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

Tcl

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

Perl

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

Java

(взято с сайта http://www.javatalks.ru)

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

package test;
public class Reproduce {
static String str="package test;%2$2cpublic 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','%4$1c%3$1c','%4$1c%4$1c');}}";
public static void main(String[] args){System.out.printf(str, str,'\n','"','\\');}}

REXX

В языке Rexx имеется ряд операторов для работы с исходным текстом: его отображение (sourceline) и исполнение введенной строки как части программы (interpret). Куайн на Рекксе реализуется обычными средствами языка:

a = sourceline(1); say a

JavaScript

Аналогично, в некоторых реализациях JavaScript встроенный объект Function может «знать» своё текстовое представление:

(function(){
  alert("(" + arguments.callee.toString() + ")()")
})()

BASIC

В бейсике существует оператор для вывода исходного текста программы LIST. Таким образом, Куайн на бейсике может состоять всего лишь из одного оператора:

LIST

HQ9+

В HQ9+ также существует оператор для вывода исходного текста программы — Q. Таким образом, Куайн на HQ9+ может состоять всего лишь из одного символа:

Q

См. также

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

Ссылки

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