Квайн или indirect self-reference

Информацию о QUINE вы можете почерпнуть из Wikipedia. Здесь, исключительно для удобства, я продублирую часть материала, немного его расширив и, видимо, откорректировав в некоторых моментах. Так же приведу свое решение для языка Java.

1. История;
2. Постановка задачи;
3. Решение.

1. История
Куайн, квайн (quine [kwi:n]) - программа, воспроизводящая (печатающая) сама себя (свой исходный код).

Профессор Гарвардского университета, Уиллард Ван Орман Куайн (Willard Van Orman Quine) - философ и логик. Одной из изучаемых областей было косвенное самоупоминание (indirect self-reference). В связи с чем, видимо, и было присвоенно его имя данному типу задач в программировании.

2. Постановка задачи:

1. Программа должна печатать свой исходный код;
2. Внешние данные (чтение текста из файла, клавитуры, ...) использовать воспрещается;
3. Программа, не содержащая исходного кода, квайном не является. (Вырожденный случай);


Сама по себе задача не является сложной. Поэтому, мы добавили еще один пункт.
4. Должна содержать наименьшее возможное количество байт исходного кода.
   

3. Решение

В момент, когда я приступал к реализации программы, мне ничего не было известно о "Квайнах". Мождно было воспользоваться "google.com" но это не спортивно и не интересно.

Решение задачи напрямую зависит от языка программирования и предоставляемых им средств. Так, например, для языка Basic, самой короткой программой будет "10 LIST".

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

1 String programm = "class A {" 2 "public static void main(String[] args) {" + 3 " String programm=<вся проблема в том, что будет здесь>;" + 4 " System.out.prinln(programm);" + 5 "}" + 6"};"

Вот, половина программы готова. Остается только самое интересное в этой задаче: из 3ей строки очевидно, что без реккурсивной вставки нам не обойтись. Для этого есть несколько вариантов, но так как мы используем Java 1.6, то я выбираю java.util.Formatter и java.io.PrinteStream. В дальнейшем будет видно, что данный выбор является так же и самым экономичным для размера исходного кода.

1 String programm="class A { "+ 2 " public static void main(String[] args){"+ 3 " String programm=%c%s%1$c;"+ 4 " System.out.printf(programm,34,programm);"+ 5 " }"+ 6 "}"

Полный текст выглядит так:

1class A { 2 public static void main(String[] args) { 3 String programm = "class A { "+ 5 " public static void main(String[] args){"+ 6 " String programm=%c%s%1$c;"+ 7 " System.out.printf(programm,34,programm);"+ 8 " }"+ 9 "}"; 10 System.out.printf(programm, 34, programm); 11 } 12}

Уберем все лишнее и получим 172 байта:

class A{public static void main(String[]a){String b="class A{public static void main(String[]a){String b=%c%s%1$c;System.out.printf(b,34,b);}}";System.out.printf(b,34,b);}}

При получении данного варианта, возникает желание уменьшить программу, хоть как нибудь. Кто то возможно скажет, что куда уже меньше, для Java и так хороший результат.
Но хороший - это не лучший, мы ведь стремимся к вечному и красивому.

Конструкция "public static void main(String[]a)" очень громоздкая, и справедливо хочется избавиться от нее. Что я и сделал подменой на static конструкцию.
Код был переписан к 116 байтам:

class B{static{String b="class B{static{String b=%c%s%1$c;System.out.printf(b,34,b);}}";System.out.printf(b,34,b);}}

Программа компилируется и работает. Для запуска рекомендую разделить output. Сделать вы это можете так:

"java B 1>std.out 2>err.out 3>wrn.out".
std.out - будет содержать исходный код программы.
err.out - java.lang.NoSuchMethodError: main
                    Exception in thread "main"
wrn.out - будет пустым.

Авторами данного кода являются: Максимом Прохоренко и Константином Вырским.

Среди знакомых были неплохие попытки читерства на 176 байт :)

class P{public static void main(String[]a)throws Exception{java.io.InputStream in=new java.io.FileInputStream("P.java");int b;while((b=in.read())>0)System.out.print((char)b);}}

А какой результат, получился у вас? Делитесь в коментариях или пишите письма. Так же буду рад, если вы укажете на мои не точности или поправите меня.

P.S.

Недавно, в руки мне попала, книга "Алгоритмические трюки для программистов." (Генри Уоррен, мл. ISBN:5-8459-0471-4 рус.)
Где я вычитал следующее: "Самая короткая программа на C, известная автору книги, написанна Владом Таировым и Рашидом Фахреевым и содержит 64 символа:"

main(a){printf(a,34,a="main(a){printf(a,34,a=%c%s%с,34);}",34);)}

P.P.S. Огромное множество, примеров, для разных языков вы сможете найти на сайте Гарри Томпсона.

Вступление или зачем все началось.

Великодушно приветствую читателей блога!

Это первая моя статья в блоге и, наверное, самая важная, примерно так же, как и первый шаг к достижению цели. В ней мне бы хотелось поразмышлять о следующием:

1. Цели блога;
2. Основы поведения (правила);

1. Цели
По роду своей деятельности (я - программист), мне приходится разбираться с интересными и не очень проблемами или задачами. Часто краткую и вразумительную информацию, понятную для себя, найти не так-то просто. И даже после того, как найдешь и изучишь её, наша память подкидывает сюрпризы, в том смысле, что долгое время не используя (не обращаясь к) предмет изучения, практически весь путь поисков информации приходиться проходить заново. Этому явлению памяти я и хочу бросить вызов. Делать это собираюсь написанием сжатых статей с сылками на обработанный материал. Сжатые статьи - это, скорее всего, смесь выводов о проделанной работе вместе с HOWTO и FAQ собственного производства.

Так же собираюсь заниматься переводом наиболее интересных статей.

Искренне надеюсь, что данный материал будет помошником не только мне, но и Вам.


2. Основы поведения (правила)
Данный блог задумывается как динамичный, исходя из этого, все статьи, могут изменяться и дополняться (эта статья не исключение). Здесь возникает вопрос, как же быть с комментариями? На момент написания статьи я не придумал процедуру комментирования (комуницирования с читателем), но я бы хотел, чтоб статьи и комментарии отражали суть проблемной области. Поэтому, я наверняка займусь модерированием комментариев. Вы спросите: "А как же (а где же) демократия?" :). Обещаю, для полноценного общения и обсуждения я, в скором времени, что нибудь придумаю. Но это то, что касается лично меня.

Читатель же не должен смущаться, высказывая свои мысли, но должен помнить следующее:

• Будьте вежливы по отношению друг к другу.
• Spam/flood запрещен. Абсолютно.
• Подпись не должна быть навязчивой или нести рекламное сообщение.
  

Вот, вроде бы и все. Начало положено!