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

---

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

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

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

Куайном 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}}$.

---