Квин-программы, или… 1 LIST

Константин Кноп, Konstantin@Knop.com
Опубликовано: 8.2.2001
Этот материал Вы всегда сможете найти по его постоянному адресу: http://www.computerra.ru/offline/2001/381/7123/

Я порой сам удивляюсь: сколько лет уже пишу в «Компьютерре» про всякую околопрограммистскую всячину, сначала в «Досугах», а потом и в «Кнопках», - а вот все никак не доходили руки до такого лакомого кусочка, которым являются самовоспроизводящиеся программы - программы, печатающие свой собственный текст. Хотя…

Такой ли он лакомый для нынешнего Интернет-поколения? Молодежь, безусловно, уже не обязана знать замечательную книгу Чарльза Уэзерелла «Этюды для программистов», а больше про интроспективные программы и прочесть-то негде. Тем не менее, надо когда-то закрывать это белое пятно. Сразу честно предупреждаю: разбираться в таких программах - занятие не для слабонервных. Но если уж разобрались (а тем паче если написали такую программу сами) - непременно получите море удовольствия.

Начну с того, откуда взялись названия. Ч. Уэзерелл использовал слово «интроспекция», что в переводе с философского языка на обычный означает «самопознание». Стандартное английское название self-reproducing program длинное и неудобное. Возможно, поэтому самым популярным для этого класса программ стало название quine [kwi:n], данное в честь логика Вилларда Квина (Willard van Orman Quine). Я рискнул просто транслитерировать это слово по-русски, так что буду называть объект нашего рассказа квин-программами. Как вы уже поняли, основным свойством квин-программ является то, что результатом их работы является листинг самой программы.

Простейшим примером квин-программы является бейсиковская

1 LIST

Словарик компьютерного жаргона приводит еще два примера - на Си и на Лиспе:

char*f=”char*f=%c%s%c;main() {printf(f,34,f,34,10);}%c”; main(){printf(f,34,f,34,10);}
((LAMBDA (X) (LIST X (LIST ‘QUOTE X))) ‘(LAMBDA (X) (LIST X (LIST ‘QUOTE X))))

Чтобы понять Си-программу, нужно иметь в виду, что символ с кодом 34 - это парная кавычка. Трюк (если это считать трюком) состоит в том, что в переменную f загоняется все то, что предстоит напечатать, включая кавычки. Ну, а решение на Лиспе абсолютно честное и без трюков - просто в этом языке есть такая мощная вещь, как лямбда-операторы…

А вот почти то же самое, что и на Си, но уже в синтаксисе Perl (автор - Кириакос Георгиу):

printf($x,39,$x=’printf($x,39,$x=%c%s%c,39);’,39);

Ну, и для тех, кто не понял ни Си, ни Перла, приведу два примера попроще - на Бейсике. В строке 10 делается вся работа, а строка 20 содержит «данные» для строковой переменной A$, а на самом деле - повтор 10-й строки. Правда, такая конструкция работает не в каждой версии Бейсика…

10 READ A$:PRINT 10 A$:PRINT 20 “DATA” A$
20 DATA READ A$:PRINT 10 A$:PRINT 20 “DATA” A$
Второй бейсик-пример (Фред Голвин):
5 P$=”+CHR(34):PRINT MID(P$,35)+P$+P$’5 P$=”+CHR(34):PRINT MID(P$,35)+P$+P$’5 P$=”

Здесь chr - функция, дающая символ с указанным ASCII-номером, а mid (p$,35) - вся концовка строки p$, начиная с 35-го символа, иначе говоря, 5 P$=”. Напечатав ее, а потом дважды саму строку p$, мы тем самым печатаем всю программу.

Если гнаться за краткостью квин-программ, то язык, допускающий одно из самых коротких «честных» решений (то есть без фокусов, связанных с особенностями компилятора), - это малоизвестный у нас False. Вот эта строчка (программа Мэтью Хендри):

[“‘[,34,$!34,’],!”]’[,34,$!34,’],!

Рискну привести еще довольно объемную программу на Паскале, написанную Дэниелом Мартином (см. листинг). После внимательного ее чтения становится понятной идея большей части квин-программ на Паскале: нужно как-то решить «проблему кавычки». Д. Мартину для этого пришлось печатать элементы массива посимвольно и отдельно обрабатывать каждую встречающуюся кавычку (см. цикл по переменной j).

А вот решение Джеффри Свифта на JavaScript, которое по идее должно быть записано в одну длинную строку:

a=new Array();a[0]=’a=new Array();’;a[1]=’[‘;a[2]=’]’;a[3]=’\’’;a[4]=’\\’;a[5]=’=’;a[6]=
’a’; a[7]=’;’;a[8]=’’;a[9]=’for(i=0;i<10;i++)
document.writeln((i==0?a[0]:a[8])+a[6]+a[1]+i+a[2]+a[5]+a[3]+
((i==3||i==4)?a[4]:a[8])+a[i]+a[3]+a[7]+(i==9?a[9]:a[8]))’;
for(i=0;i<10;i++)document.writeln((i==0?a[0]:a[8])+a[6]+
a[1]+i+a[2]+a[5]+a[3]+((i==3||i==4)?a[4]:a[8])+a[i]+a[3]+a[7]+
(i==9?a[9]:a[8]))

«Три дела, однажды начавши, трудно закончить», - утверждал в позапрошлом веке Козьма Прутков. Увы, Козьме Петровичу явно не доводилось писать популярные статьи о программистских задачках, иначе бы он твердо усвоил, что таких дел не три, а минимум четыре…

Рассказ о квин-программах невозможно закончить, его можно только продолжать и продолжать. Очень хочется привести квин-программу, которая является таковой одновременно на нескольких языках. Невозможно удержаться, чтобы не упомянуть о парах программ, каждая из которых генерирует другую программу этой пары. Вот, например, такая пара на Си и Паскале:

main(){char*p=”program p;begin writeln(%cmain(){char*p=%c%s%c; printf(p,39,34,p,34,39);}%c)end.”;printf(p,39,34,p,34,39);}
program p;begin writeln(‘main(){char*p=”program p;begin writeln(%cmain(){char*p= %c%s%c; printf(p,39,34,p,34,39);}%c)end.”; printf(p,39,34,p,34,39);}’)end.

А еще бывает совсем смешная разновидность квинов. Я не буду объяснять, в чем юмор, а просто приведу пример. Наберите в командной строке (имеется в виду сеанс MS-DOS) вот такой текст:

C:\>Bad command or file name

и смело жмите на Enter. Ну как, работает?

Комментарий для юниксоидов: не бойтесь, и вы тоже можете сделать такую же штуку:

$ xxx: not found

Дерзайте! Я написал свою первую квин-программу (на Фортране), когда мне только-только исполнилось 17 лет. А вы чем хуже?

Все процитированные здесь программы являются свободно распространяемыми (public domain), согласно www.nyx.net/~Egthompso/copyrights.htm. На страничке www.nyx.net/~Egthompso/quine.htm приведены квин-программы для многих других языков и систем программирования.