letters

letters.htm

Избранные места из переписки с друзьями

Александр Корлюков. Подчеркну, что я здесь ничего не программирую, записываю условие задачи - и только. Полученное никак не годится для каких-либо осмысленных пусков на счет при обычном, без использования суперкомпилятора, программировании.

Действительно, сейчас имеется предикат, принимающий значение истина на ответе к задаче, и ложь (отождествление невозможно) - на не ответе. Если я знаю ответ, то могу пустить программу на счет и получу на экране истину, если не знаю ответа, то тоже могу пустить программу на счет и получить на экране ложь. Бред какой-то !

Андрей Климов. Постановку задачи надо комментировать (на презентациях) по-другому: Это отнюдь "не бред" и никак не то, что "не годится для каких-либо осмысленных пусков на счет при обычном, без использования суперкомпилятора, программировании". Это, на самом деле, осмысленное программирование предиката, который, как ты правильно написал, можно запускать на счет при разных данных и получать "да" или "нет". Здесь нет ничего "бредового", кроме факта, что суперкомпилятор умеет решать обратную задачу. ;-) А вот это, с точки зрения "простого программиста", действительно, "бред"! ;-)

Аркадий Климов. А я не понял исходного утверждения. Как это "могу пустить программу на счет", не зная "ответа", то есть ее, программы, исходных данных? Что здесь имелось в виду?

Андрей Климов. Я отвечал, поняв так, что просто пропущены слова "взяв любое значение и, как правило, не попав в ответ". (Хотя домысливать опасно, но я не делал негативных выводов (;-) и на всякий случай пересказал своими словами то, что я понял).

Александр Корлюков. Здесь я эмоционально пытался отметить нестандартность использования суперкомпилятора в этом примере. Стандартное использование - это оптимизация имеющейся программы. Здесь нет разногласий Второй момент нестандартности - в этом примере нас интересует только текст остаточной программы, а не ее функционирование. Глядя на текст мы получаем ответ к исходной математической задаче.

*************************************************************
* Sorry, your program to be transformed has a semantic error.
****************************** The End **********************

Аркадий Климов. Это я тоже не понял. Какая semantic error имеется в виду? Что это значит? Разве в исходной программе есть ошибка? Может это свидетельство ошибки в суперкомпиляторе? Почему ты решил, что "это означает, что задача решения не имеет". Или это сообщение означает, что область определения программы пустая? Тогда надо было бы, чтобы так и сообщалось (это, наверно, Андрею Немытых). Или выдавалась бы остаточная программа вида

Go { };

что, было бы, наверно, логично.

Андрей Климов. Это вопрос к АНдрею, и я думаю, он сейчас пришлет свое пояснение. Но, как я понимаю, это вопрос как бы "дизайна": как выдавать программу, которая имеет заведомо пустую область определения. АНдрей выбрал такое решение, но я с тобой согласен, что это непонятно. Если бы в свое время АНдрей мне это не пояснил, я бы тоже недоумевал.

Но формально вариант Go { }; действительно правильнее. Ведь суперкомпилятор -- это система эквивалентных преобразований программ, то есть он должен выдать программу, которая при тех же данных дает тот же результат". А здесь он отказался выдавать. ;-)

Александр Корлюков. Если относить эту задачу к обычным переборным, то давайте попробуем организовать такой перебор на каком-либо другом из известных языков программирования ! Семь вложенных друг в друга циклов, которые потом надо будет изменять на восемь циклов, или упорядочить лексикографически варианты - даже не хочется думать об этом.

Аркадий Климов. Ну почему же не хочется. Есть, например, такой язык - Пролог, на нем исходная постановка будет иметь примерно такое же (по структуре) описание. Но, конечно, не такое привычное. Кстати, если повезет, то Пролог иногда решает и задачи с "бесконечным перебором" (в смысле, говоря, что решений нет: поскольку некоторые бесконечные множества из области значений неизвестных могут отвергаться целиком). Но, по-видимому, есть задачи, которые суперкомпилятор решит а Пролог нет. Я имею в виду Пролог как таковой, без метавычислителя типа Partial Deduction, о котором я слышал только от Андрея Климова на семинарах.

Андрей Климов. С реализациями Partial Deduction я дела не имел (может их и нет), но общался с людьми, занимающимися ею, а также просматривал статьи. (Поверхностный) вывод, который я для себя сделал, такой: Это фактически суперкомпиляция, переложенная для логических исчислений. (Исчисление типа rewrite rules отличается от функционального языка лишь недетерминизмом, который для существа суперкомпиляции совершенно не важен и используется только для оптимизации частных колесиков типа экранировки нижних ветвей образцом e.1). Но может у них есть какие-нибудь специфические изобретения, которые я не заметил из-за шапочного знакомства с этой темой.

Интересно, как насчет обратного утверждения: решит ли суперкомпилятор все, что решит Пролог? Точнее, гипотеза такова: если Пролог, запущенный на поиск ВСЕХ решений, остановится за конечное время с выдачей множества ВСЕХ решений, то суперкомпилятор соответствующую задачу сделает с результатом в форме конечной одношаговой программы.

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

Андрей Климов. Отличный пример! Мне он кажется наилучшим из тех, что ты присылал. Этот пример понятен сразу и впечатляет. (Особенно удачен "бантик": "Почему не получилось при 8 агентах?"). Можно считать, что на мне опробовано, что он хорошо подходит для кратких презентаций (а это для меня "больная" тема;-).

Замечательный пример! Это то, что в журналах публикуют в разделах под кратким названием "Pearls". -- Одна загвоздка -- нет еще журнала "Суперкомпиляция". (;-) Но уверен, будет!

Александр Корлюков. Несколько раз в переписке упоминалось об использовании примера на презентациях. Я не знаю о чем речь. Способ подачи этого примера будет зависеть от публики.

Андрей Климов. "Публичность" примера включает в себя много нюансов, если их попытаться рационализировать. Я просто поделился ощущением. Мне кажется, что люди обычно в детали не вдаются, и очень важна "художественность" задачи.

Во-первых, Джеймс Бонд -- здесь культовый герой.

Во-вторых, сама постановка задачи очень понятна -- составление "развед-задания".

В-третьих, даже непонятность, как это получилось, превращается для нас в позитив: "Я не понимаю, а суперкомпилятор понял".

Александр Корлюков. Мой способ изложения больше напоминает показ фокуса.

Андрей Климов. Во-во! Именно это хорошо подходит к презентациям! ;-)

Александр Корлюков. Перебор 35 случаев, и я не пойму, почему. Количество случаев равно 5^5 = 3125, нигде вроде нет указаний, что без повторений.

Аркадий Климов. Здесь как бы все 3125 случаев и рассмотрены, но некоторые множества рассмотрены скопом. Например случай s1="001" содержит все варианты остальных переменных (первое предложение). Это очень интересно, почему так получилось.

Моя гипотеза такова: если предположить, что "001" следит за "001", то есть за собой, то ясно, что "001" уже не может следить за "002", что требуется в условии. Хитрее случай, когда "001" следит за "002". Отсюда, по условию, "002" следит за "002" => аналогичная ситуация.

Сергей Абрамов. День добрый, всем! Да, отличный пример:

1.. достаточно сложный -- чтобы читатель смог поразиться проницательности методов метавычислений;

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

вполне достаточно Ura, а не Scp.