Мауриц Корнелис Эшер. Рисующие руки
«Yields falsehood when preceded by its quotation» yields falsehood when preceded by its quotation.
Willard Van Orman Quine
Квайнами (quine) называются программы, печатающие свой собственный текст при каждом запуске.
Основной трюк в том, что никакими трюками пользоваться нельзя. Нельзя использовать файлы, особенности операционной системы или компилятора/интерпретатора. Лучше вообще не использовать стандартные функции кроме простого вывода на печать (т.е. в стандартный поток вывода).
Можно пользоваться только штатными конструкциями языка программирования.
Задача (и её решение) существовали задолго до того, как ей придумали название. Первому достоверно известному квайну столько же лет, сколько и мне. Т.е. написал его в глубокой древности некий Hamish Dewar. Автором же термина «квайн» является Дуглас Хофштадтер. Это один из философов, наиболее близких к программированию. Некоторые считают его программистом, настолько спятившим, чтобы начать писать философские книги. Термин «квайны» Хофштадтер ввёл в своей знаменитой книге ГЭБ (Д.Р.Хофштадтер. Гёдель, Эшер, Бах: Бесконечная гирлянда). Книга очень забавная. В бумажном виде она давно стоит у меня на полке и ждёт, когда я прочитаю её от корки до корки. Пока я иногда просто открываю её где попало и читаю пока есть время и желание. Вполне возможно (и даже скорее всего) я уже прочёл её всю но наверняка утверждать это нельзя. Придётся как-нибудь дать студентам такую задачу на объединение отрезков. Но это будет совсем другая история, а пока — квайны. А чтобы узнать в честь кого ввели такое название, разберитесь с эпиграфом к этой статье.
Мне кажется достаточно полезным поломать голову над написанием такой программы. Польза в том, что начинаешь задумываться об исполняемой (интерпретируемой) и не исполняемой части кода, о том как они разделяются. Как исполняемая часть кода соотносится с не исполняемой. Например, с содержимым строковых констант. Такие размышления могут довести Вас до теоремы Клини о неподвижной точке или даже до теоремы Райса. Часть долгих зимних каникул стоит потратить на изобретение своего квайна на С++. А для тех, кому для творчества нужен пример или шаблон могу предложить классический (народный) квайн на языке Си.
|
1 2 3 4 5 6 |
#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);} |
Конечно всё выглядит довольно запутано, поэтому укажу где спрятан ключ — он хранится в переменной q.
Если вдруг захочется двигаться дальше в этом направлении попробуйте написать самоинтерпретатор, т.е. интерпретатор языка программирования на самом этом языке. Лучше выбрать какой-то совсем простой язык из тех, что есть на ideone.com. И конечно никаких трюков вроде eval(). Или можно попытаться разобраться в идее самореферентной формулы Тапера.