Subject: Re: another subtraction result
From: Sergei M. Abramov (abram@botik.ru)
Date: Wed Oct 04 2000 - 12:33:30 MSD
День добрый, всем!
Антон, я подумал, что после того, как удалось получить при помощи Scp4
вполне приличную функцию вычитания можно переписку вывести из подполья и
данное письмо показать общественности.
В цитаты старой переписки я добавил немного /** разъяснений **/
-----Original Message-----
From: Antonio <antonio0@mail.ru>
To: Sergei M. Abramov <abram@botik.ru>
Date: 3 октября 2000 г. 19:51
Subject: Re: another subtraction result
Доброго Вечера!
Как я понял (проанализировав Рефал Плюс /** в него выведен результат
Scp4 за счет альтернативного бэкэнда--спасибо, я смог читать **/),
инвертировался общий случай:
scp <ura add (eX (XЕ 1)) eY>
Как результат, получен код программы: substr eX eY
Код довольно странный (неисповедимы пути scp4), но правильный:
substr eX eY --> цикл F1 --> цикл F2
Цикл F1 пробегается по eY (отбрасывает 1) до и накапливает равный eZ
(добавляя-навешивая 1, на ХЕ 1).
Цикл F2 отнимает 1 от еХ и eZ.
Кажется я ничего не перепутал?
Да все правильно. И кажется ясно откуда взялись эти два цикла --- из
Ccond и Clash соответственно. Именно ветвления из этих функций остались в
residual-е. Мы с АНдреем как-раз это обсуждаем, но возможно, что такое нынче
суперкомпиляция (как теория вообще) не ест.
Спасибо АНдрею за исправление в Scp4 ошибок, которые выявила работа над "scp
<ura ...>"
Да, АНдрей абсолютно прав--так и должно остаться при нынешнем
технологическом уровне Scp -- два неслитых цикла.
Объединить эти два неслитых цикла способна только следущая технология
(ScpWalk). (Андрей К! Вот оно!)
Тем самым достигнуто предельное (для нынешней Scp-технологии) качество
автоматически построенного вычитания.
Кроме того, ясно, какие задачи на инверсию дадут более чистый результат: те
задачи, в которых не будет цикла в Clash. Например, это тот случай, когда
мы инвертируем программы, результатом которых является атом.
Например--инвертируем предикаты.
Таких TSG-программ мы с Робертом уже сколько-то накопили: проверка того, что
строка есть путь в графе, и т.п.
/** автоматически полученное вычитание **/ Можно погонять под Р+ с
трассировкой и полюбоваться. При этом хорошо входные данные
"раскрасить"--использовать вместо ("АТОМ" (1)), другие атомы в /**
аргументах**/ Х и Y:
(CONS 'x (CONS 'x (CONS 'x (CONS 'x 'xnil)))) (CONS 'y (CONS
'y (CONS 'y 'ynil)))
Ну я пока не поставил Р+, руки не доходят. Но я скажу Антону и Юре.
Да, спасибо.
Он получается если просуперкомпилировать результат
суперкомпиляции.
Это принесло некоторый результат (тот что я прислал Вам последний), но
сейчас я от этого отказался, так как хватает первого прохода (произошло
улучшение /** Scp4 **/) , а второй проход теперь сосем не помогает.
И еще для Scp4 обычно из-за раскрытия снизу (или сверху -- непомню) это
не то что непомогает, а он начинает по одному проходу цикла отделять.
Видимо тут про "перестройку снизу" и "перестройку сверху" -- куда
подклеивать обобщающую конфигурацию после обобщения.
На школе мы это обсуждали: делать перестройку надо снизу (а не так как это
сделал М.С.Горбачев), но при этом использовать hyper-cycle в
суперкомпиляции. Тогда и переобобщений не будет и отмотки лишних витков не
будет.
Все это описано в http://www.botik.ru/AbrGlu/ mc_and_appls.zip --> scp.gs
a.. функция scp2 --> next_pass -- гиперцикл;
a.. функция procWh --> else ( (CALLC "Dn" kDn cDn i1 (mkParms cGen
sGenDn) [grGen]), i', bs3) -- перестройка снизу.
Да, и после такой чистки, хотелось бы переписать результат на TSG.
Тогда его можно показать Роберту... ;-)
...и возвращаться к УРА.
А что Роберт не понимает Рефал(5 или +)?
Роберт то может и поймет, а вот большая (но не лучшая) часть прогрессивного
человечества Рефал не читает...
Попробуем -- обязательно ли, чтобы он запускался? Или можно без
подробностей?
А много ли пришлось совершить надругательств над Ура, чтобы на нем
scp4 не ложился?
Какие это были упрощения (по смыслу, если можно текстовое, а не
рефальское
описание)...
Сначала, когда я писал первое письмо, УРА было искалечено до неузнавания
:) Ура было немного подправлено, но также было убрано около 70% программы --
все рестрикции, подстановки, и др , то что не нужно было для унарного
сложения. Однако потом, я конечно стал все восстанавливать, и осталось всего
два-три места. Правда теперь я обхожусь без повторной суперкомпиляции, и не
могу повторить присланный вам хит :), а остается программа чуть-чуть
большее. Но это не принципиально -- в ней те же два цикла. Итак изменения:
Первое, и самое главное -- это закомментирован вариант выбора в функции
CCond который в случае проверки CONS? и второго параметра ввиде (XE что-то)
запускает SplitE, который делает разбиение и создает новые СЕ-переменные.
Хотя в данном случае для унарного сложения он даже по этой ветке не идет.
Два вывода:
1.. суперкомпилятор не любит ветку где делаются новые фреш
С-переменные(и изменяется свободный индекс), надо пробовать с ней что-то
делать.
2.. суперкомпилятор пока не может откинуть все лишние ветки, это и
есть главная проблема во
Втором, что закомментироваваны ветки (одна в том же месте) другие в
Clash1 связанные с проверкой на (XA что-то).
Хотя честно можно сказать, что это, в отличие, от первого менее страшно,
так как если их оставить, то всего лишь добавятся в этих функциях, глупые
проверки на XA, а логика не изменится. Сейчас я пытаюсь их убрать фильтрами,
но пока ему очень не нравится эти фильтры, но это как-раз в состоянии
обсуждения с АНдреем.
Третье, пока я не понял, важно ли это или вообще фигня, но некоторые
(иногда, поэтому и сомнения) проблемы с функциями поиска конкретной
переменной в среде (в Apply_Cexp_CCsub) и поиска есть ли у нас такое же
решенное уравнение в функции MoveCL (если есть надо проверить
непротиворечивость). Но скорее --- это трудности технического характера, мне
кажется (и почти получается) их переписать более просто(и менее общо, но
работать должно для любых программ).
Спасибо за разъяснения--все стало ясным.
Огромное спасибо за усилия и письма,
И прошу прощения, что отвечаю не на все и с дикой задержкой--очень
тяжелое время (конец квартала, отчеты в Союз Бел. и России, дидлайн с
Робертом)....
Ага понимаю, просто хотелось понять не потерялся ли столь ценный
результат во всемирной паутине (всяко бывает).
Нет, не потерялся ;-)
А также уже необходима ваша моральная поддержка для продолжения и
получения более сильных результатов.
Всегда имеете!
А также: я так понимаю, что Вы с Робертом пишете статью по УРА, не могли
бы Вы ее прислать.
Здесь все пошло по накатанному пути:
Сначала мы написали статью на конференцию:
http://www.botik.ru/AbrGlu/URA/MPC2000/ -- статья доступна как DVI и PS, 25
страниц. Ее приняли, хотя конкурсь был не слабый (это не бахвальство
качеством статьи, а оценка интереса мировой общественности к теме, к
направлению исследований). Была конференция, доклад куча вопросов. Но, как
видно, это была кратенькая статья--25 страничек только. Сюда не вошло куча
материалов и доказательства (ограничение на длину). Но когда мы ее делали,
мы сразу копили материал на большую (журнальную) статью. Хотябы материал в
невылизанном виде (сырье).
Сейчас мы пишем (дидлайн был 30/09/2000 но его расширили и мы как раз сейчас
трудимся...) другую заказную статью--URA как подарок Нилу Джонсу к юбилею
(пока показывать еще не чего. Кодовое название URA-FEST. Как только--так
сразу Вас познакомлю с текстом)... Это будет "обучающая" статья. Менее
сухая, чем URA'MPC'2000 -- больше интуиции, больше примеров, но опять не
полная статья (всего страниц 25-30), расчитаная на заинтересованного,
желающего познакомиться но не страдающего от отсутствия формальных
доказательств и т.п. (формализм подменен интуицией). Таков жанр данной
публикации.
Кроме того, как обычно после конференции MPC'2000 организаторы отобрали из
всех докладов несколько хитов--и наш доклад в том числе (опять: это оценка
интереса к направлению) -- см. приложение. Тем самым, сразу после URA-FEST
мы переключимся на написание URA-Journal. Вот это будет полная версия
URA-статья. Какой-то материал уже накоплен (URA'MPC'2000 + загашник с
доказательствами), однако ну хоть сюда (если не в URA-FEST) хотелось бы
вставить отчет о первых результатах инверсной компиляции (Вот почему я
говорю: надо перевести вычитание на TSG ;-).
Что можно предложить: Вы добиваетесь инверсной TSG-->TSG компиляции чего-то
(обсудим еще)--1..2 TSG-программ. Цель: добиться, чтобы рисунок и
нижеследущие слова были бы правдой (не были бы сильной ложью):
----------------------------------------------------------------------------
----
Рисунок:
сверху исходная TSG-программа
ниже запрос на суперкомпиляцию
внизу результирующая TSG-программа
Слова в основном тексте:
Сегодня получены первые примеры инверсии программы за счет специализации
программы URA (см. Рис. ???).
Этот результат был получен следущим образом:
-1- Aлгоритм URA (ранее обсужденный в секции ??? и на рис. ???) был
переписан "один-водин" на язык Refal-5\cite{...};
-2- Для специализации использовался суперкомпилятор Scp-4\cite{...}.
Специализация выполнялась в абсолютно автоматическом режиме. Результатом
специализации являлась Рефал-5 программа, которая затем была переписана
(вручную? специально созданным простеньким бэкэндом к Scp-4/Р+?)
"один-в-один" в TSG-программу.
Отметим, что ....далее дискуссия о полученном качестве инверсной компиляции,
структуре и характеристиках результирующей программы, наметки на дальнейшие
улучшения--в том числе и за счет развития Scp-технологии, замеры
коэфициентов ускорения в Хаскелле и т.п.....
Слова в Благодарностях:
Авторы благодарны .... за реализацию первого эксперимента по инверсии
программы за счет специализации URA, АНдрею, В.Ф.Турчину--за систему Scp-4 и
техническую поддержку в этой части экспериментов.
----------------------------------------------------------------------------
----
Короче: небольшая под-секция в секции про эксперименты в URA-Journal,
застолбление приоритета "инверсия программ засчет специализации URA",
благодарности всем участникам.
Но для этого--не должны быть сильной ложью красивый рисунок и слова,
изложенные выше.
Сергей
This archive was generated by hypermail 2b25 : Mon Oct 25 2004 - 21:24:58 MSD