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

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

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

История

Куайны возможны в любом тьюринг-полном языке программирования — как следствие _en . Идея куайнов была впервые описана Полом Братли ( англ. Bratley, Paul ) и Жаном Милло ( англ. Millo, Jean ) в «Computer Recreations; Self-Reproducing Automata», Software — Practice & Experience, выпуск 2 (1972), с. 397—400. Братли заинтересовался саморепродуцированием программ после знакомства с первой такой программой, написанной на языке программирования в Эдинбурге в 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 -го порядка для ${\displaystyle n>1}$ называется программа, которая выводит на экран такой код ${\displaystyle A_{1}}$ , что ${\displaystyle \forall k:1<k<n}$ запуск кода ${\displaystyle A_{k-1}}$ выводит на экран код ${\displaystyle A_{k}}$ . При этом код ${\displaystyle A_{n-1}}$ выводит на экран код изначальной программы.

Цепной куайн

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

Японский программист в 2013 году создал цепной куайн для ${\displaystyle n=50}$ с началом на языке программирования Ruby (впрочем, согласно определению, благодаря цикличности алгоритма при наличии кодов на всех языках начинать исполнение цикла можно с любого из них). Языки программирования в куайне расположены в алфавитном порядке. К 2018 году он довёл число языков в этом куайне до 128 .

Другие вариации

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

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

См. также

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

Примечания

Литература

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