Свежий номер №4-5 (381-382) / Квин-программы, или… 1 LIST Константин Кноп, kk@knop.spb.ru 08.02.2001 Я порой сам удивляюсь: сколько лет уже пишу в «Компьютерре» про всякую околопрограммистскую всячину, сначала в «Досугах», а потом и в «Кнопках», - а вот все никак не доходили руки до такого лакомого кусочка, которым являются самовоспроизводящиеся программы - программы, печатающие свой собственный текст. Хотя… Такой ли он лакомый для нынешнего Интернет-поколения? Молодежь, безусловно, уже не обязана знать замечательную книгу Чарльза Уэзерелла «Этюды для программистов», а больше про интроспективные программы и прочесть-то негде. Тем не менее, надо когда-то закрывать это белое пятно. Сразу честно предупреждаю: разбираться в таких программах - занятие не для слабонервных. Но если уж разобрались (а тем паче если написали такую программу сами) - непременно получите море удовольствия. Начну с того, откуда взялись названия. Ч. Уэзерелл использовал слово «интроспекция», что в переводе с философского языка на обычный означает «самопознание». Стандартное английское название 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);} Чтобы понять Си-программу, нужно иметь в виду, что символ с кодом 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$ Здесь 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]= «Три дела, однажды начавши, трудно закончить», - утверждал в позапрошлом веке Козьма Прутков. Увы, Козьме Петровичу явно не доводилось писать популярные статьи о программистских задачках, иначе бы он твердо усвоил, что таких дел не три, а минимум четыре… Рассказ о квин-программах невозможно закончить, его можно только продолжать и продолжать. Очень хочется привести квин-программу, которая является таковой одновременно на нескольких языках. Невозможно удержаться, чтобы не упомянуть о парах программ, каждая из которых генерирует другую программу этой пары. Вот, например, такая пара на Си и Паскале: 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);} А еще бывает совсем смешная разновидность квинов. Я не буду объяснять, в чем юмор, а просто приведу пример. Наберите в командной строке (имеется в виду сеанс 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 приведены квин-программы для многих других языков и систем программирования. [i38158]
|