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

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

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

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

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

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

Куайн существует в любом языке программирования, имеющем возможность выводить произвольную вычисляемую строку текста[источник не указан 154 дня]. Идея куайнов была впервые описана Полом Братли (англ. 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

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

Куайн 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 (впрочем, согласно определению, благодаря цикличности алгоритма при наличии кодов на всех языках начинать исполнение цикла можно с любого из них). Языки программирования в куайне расположены в алфавитном порядке. К 2015 году он довёл число языков в этом куайне до 100.[1].

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

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

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

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

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

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

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

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

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