Subject: Re: XML, "holes" and programming styles in R5 and R+
From: Arkady Klimov (Arkady.Klimov@supercompilers.com)
Date: Mon Jun 05 2000 - 13:42:39 MSD
Добрый день всем!
Хочу поделиться некоторыми замечаниями.
Сначала обще-философские.
У нас уже имеется несколько видов реализаций одного (грубо говоря) и того же
языка, а в будущем ожидаются и новые (Рефал-Java, например). И к сожалению
(а может, и к счастью) в разных реализациях очень сильно различаются времена
исполнения элементарных операций: то , что в одной делается быстро, в другой
выполняется медленно и наоборот. Отсюда возникает соблазн переписывания кода
под специфику конкретной реализации. Высказывается мнение, что это нужно,
чтобы в конретных условиях программа работала as fast as possible.
Но я хотел бы заметить, что это вообще говоря, не единственная цель. И
действуя в угоду ей, мы возможно, что-то теряем (и не столько скорость на
других реализациях, сколько, возможно качество самих программ -
идейную чистоту, читабельность и т.п.
Я не призываю отказыватся от переписывания, но призываю помнить, чем за это
приходится платить, и соразмерять выигрыш с этими возможными потерями.
Далее - технические.
----- Original Message -----
From: "Andrei Klimov" <Andrei.Klimov@supercompilers.com>
To: <refal@botik.ru>
Sent: Saturday, June 03, 2000 9:37 PM
Subject: XML, "holes" and programming styles in R5 and R+
> Добрый день!
>
> Направляю в refal@botik.ru письмо Сергея Абрамова
> о "дырках" (есть такое понятие в реализации Рефала Плюс) и
> различиях в стиле программирования в Рефале-5 и Рефале Плюс.
> Он написал его в ответ на мой мелкий вопрос Андрею Слепухину и ему,
> нет ли под рукой описания "дырок". Этот текст, на мой взгляд,
> заслуживает общего внимания и я попросил разрешения Сергея
> форварднуть его всем.
>
> Это обсуждение возникло в таком контексте:
>
> Сейчас активно проводятся работы по проверки рабочей гипотезы,
> что Рефал конкурентоспособен в мире обработки XML-документов.
> Если это так, мы имеем прекрасную возможность продемонстрировать
> миру, что можно дешево производить практически пригодные компиляторы
> с языков для обработки XML-я в Рефал, пользуясь суперкомпилятором Рефала.
>
> Александр Корлюков написал интерпретатор подмножества
> XSLT (XML Style Sheet Transformations), который успешно
> специализируется Рефал-суперкомпилятором Андрея Немытых.
> Таким образом (подмножество) XSLT компилируется в Рефал-5.
>
> Прогон небольших программ на XSLT показал обнадеживающие
> результаты по сравнению со скоростью исполнения на некоторых
> известных реализациях XSLT. Окончательное заключение сделаем,
> когда будут прогнаны большие тестовые программы и выяснено,
> какие наилучшие реализации XSLT имеются в мире, чтобы
> сравниваться именно с ними.
>
> Из реализаций Рефала мы, конечно, должны выбрать ту, которая
> покажет лучший результат на этой задаче. Для этого нужно
> сделать отображение выхода суперкомпилятора в другие Рефалы,
> в частности, Рефал Плюс, максимально учтя его особенности.
> (Этой задачей сейчас занимаются Юрий Климов и Антон Орлов.)
>
> Время работы программы на Рефале Плюс зависит от ряда параметров,
> в частности, от так называемых "дырок", которые были реализованны
> в переславль-залесской версии Рефала Плюс. По этому поводу и был
> задан невинный вопрос о том, что можно о них почитать.
>
> Определение для тех, кто не знаком с идеей "дырок":
>
> Def. Параметры "левая и правая дырки" задаются в процентах.
> Они указывают какое свободное место надо оставлять
> при размещении нового выражение в свободной памяти:
> "левая дырка" -- это объем памяти в % от длины этого выражения,
> который надо оставить свободным перед этим выражением,
> "правая дырка" -- после него.
>
> Дырки используются при конкатенации выражений:
> если у одного из них имеется соответствующая дырка,
> вмещающая второе выражение, то копируется только оно
> (в эту дырку).
>
> Перед тем, как передать слово Сергею, хочу обратиться к Рефал-сообществу
> с призывом к желающим принять участие в теме "Рефал и XML":
>
> Присоединяйтесь!
>
> Андрей (К).
>
> PS. Это письмо придет также членам рабочей группы "Рефал-XML",
> не подписанным на refal@botik.ru. Их адреса не видны, так как я их задал
> в BCC ("blind carbon copy"). Из-за этого их не будет в списке рассылки
ответов.
> При желании они смогут проследить за дальнейшей дискуссией в архиве:
> http://www.botik.ru/mail-archive/plus/
>
> А если хотите подписаться на refal@botik.ru -- обращайтесь ко мне.
Спасибо!
>
>
> ----- Original Message -----
> From: Sergei M. Abramov (at home)
> To: Andrei Klimov ; Andrei Slepuhin
> Cc: Yura Klimov
> Sent: Saturday, June 03, 2000 01:41
> Subject: Re: Description of holes wanted
>
>
> День добрый, всем!
>
>
> AK> Андрей (С), добрый день!
> AK>
> AK>Я заглянул в Вашу поставку Рефала Плюс и не нашел там объяснений про
дырки.
> AK>Есть только упоминание при перечислении параметров. Но мне кажется, что
> AK>несколько лет назад я видел текст про дырки. Он до Вас из Переславля не
дошел?
> AK>Или лежит так, что я не заметил?
> AK>
> AK>Сергей, ведь правда, что существовала страничка текста с описанием, что
> AK>такое дырки, да? Или мне мерещится. :-)
>
> Андрей (К), такой текст существовал, но я не думаю, что стоит тратить
время на
> его поиски (если он только не лежит в МГУ "под руками"), вот почему:
>
> =1= понимание и реализация дырок убежали вперед того текста;
>
> =2= написать актуальный правильный текст "с нуля" -- дело получаса
(которого,
> конечно не так легко найти в загруженном графике, но все-таки...)
>
> То есть, я "ЗА" написание нового правильного текста, а не за поиски
старого.
>
> Позволю дать Outline:
>
> ==================8<===================
>
> о Постановка проблемы (описание додырочной эпохи РПлюса):
>
> -- Пояснить о реализации операции конкатенации. Разные случаи при
> выполнении конкатенации:
> *1 ни один из участников не копируется (один из них пустой, они
лежат
> рядом);
> *2 только один участник копируется (рядом с другим, с нужной
стороны
> есть СВОБОДНОЕ пространство ДОСТАТОЧНОГО размера);
> *3 оба участника копируются.
>
> -- Пример программы (реверс? побайтное чтение файла?), которая
работает
> К*(К-1)/2 времени.
>
> о Понятие дырок, параметры управления дырочным механизмом.
>
> о Рекомендации по подбору оптимальных параметров дырок (на примере
программы
> из раздела 1)
>
> -- описание ключика, который дает по завершению статистику по
использованию
> памяти и по статистике (частотам) различных случаев при исполнении
> конкатенации в run-time:
>
> -- пример поиска оптимальных значений параметров для программки,
описанной в
> разделе "о1".
>
> ==================8<===================
>
> Юра! Я вам в вашей борьбе с плохим временем работы той самой программы не
> подсказал хороших дырочных параметров, вот почему:
>
> =1= не бывает универсальных правильных дырочных параметров;
>
> =2= подбирать оптимальные дырочные параметры надо по задаче (а иногда и по
> данным к ней:) -- это процесс не сложный и он базируется на идее
минимизации
> выпуклых функций методом подбора шага с адаптивным выбором шага (делим
последний
> шак или умножаем его на 2).
>
> В большинстве случаев важны только два дырочных параметра (левая и правая
> процентная длина дырки--х, у), при этом на время работы программы можно
смотреть
> как на выпуклую функцию Т(х,у).
>
> Берете данныем, на которых программа работает существенное но не
изматывающее
> вас время и замеряете время: Т(0,0), Т(100,0), Т(0,100), Т(100,100),
Т(100,100),
> Т(200,0), Т(0,200), Т(200,200), то бишь в углах сетки:
>
АРК:
Было бы неплохо, если бы можно было получить грубую оценку уже по одному
прогону. Для этого можно и нужно выдавать статистику не просто о событиях
(было копирование или нет) а вообще о плотности распределения исполнявшихся
конкатенаций по длинам аргументов (с некоторым шагом в логарифмической
шкале). Эта информация не зависит от установленной "дырочности", а
определяется исключительно алгоритмом. Пользуясь ею, я уверен, можно с
достаточной точностью прогнозировать относительное ускорение при тех или
иных значениях "левой и правой
дырочности". (Совсем точно, к сожалению, не получится, поскольку мы теряем
информацию о последовательных конкатенациях.) При этом возможно
автоматизировать выбор оптимального решения. И, как подсказал Андрей К.,
даже автоматически выполнять этот выбор на лету, постепенно меняя параметры
"дырочности" динамически.
А качество алгоритмов выбора оценивать затем повторными просчетами при
различных фиксированных параметрах "дырочности".
Думаю, это уже потянет на довольно интересную дипломную.
> * * *
>
> * * *
>
> * * *
>
> Смотря на получившиеся значения и предполагая, что Т выпуклая,
соображаете, в
> какой стороне у вас может жить минимум Т, и соответственно с этим:
>
> -- либо бьете мелкий квадратик на более мелкие части и измеряете
> (недостающие) точки, чтобы иметь Т в 9 точках этого квадрата;
>
> * * + *
> + + +
> * * + *
>
> * * *
>
> -- либо строите (недостающие) 9 точек квадрата 400х400.
>
> Наверное, можно для красоты ненаглядной 3D-сплайнами рисовать поверхность
в
> Екселе Т(х,у)... ;-)
>
> Маленькая, симпатичная лабораторка, не правда-ли?
>
> Удачи
>
> Сергей
>
> П.С. =================================================
>
> И еще, Юра!
>
> Ту задачу (признаюсь, я не смотрел на Ваш Рефал Плюс текст) считаю очень
важной
> для судьбы Рефала Плюс и для судьбы Scp4/Refal-5: разобраться с нею очень
нужно.
>
> При этом, важно не только подобрать дырки и на этом успокоиться... Нет,
важно
> сделать от нее (от кусков написанных в стиле Refal-5) сделать несколько
шагов
> к Рефалу Плюс.
>
> Да, я не смотрел _Вашу_ программу (и сейчас она у меня не под руками), но
я
> смотрел программу, которую мне предоставил А.Конышев (спасибо!).
>
> И я думаю, что мы говорим про одну и ту же программу (результат
суперкомпиляции
> некой обработки XML-я).
>
> Так вот, первый же взгляд на эту программу показывает, что она состоит из
> нескольких (главных) фаз:
>
> фаза 1 == считать текстовый файл в память;
> фаза 2 == перевести XML во внутреннее представление (спарить скобки,
тэги
> представить словами, разобраться с " --> "e; & -->
&)
> фаза 3 == собственно преобразование;
> фаза 4 == вывод.
>
>
> При этом:
>
> =1= пятерошные фазы:
>
> Функции реализующие 1, 2, 4 -- не суперкомпилировались: как они были
написаны на
> Рефале-5 программистом пятерошником, такими они и остались. Эти функции
написаны
> в пятерошном стиле и они могут оказаться ОЧЕНЬ КРИВЫМИ для "прямого"
переноса
> в Рефал Плюс. Их надо бы переписать заново (см. также Сноску (1) в конце
> письма).
>
> =2= плюсные фазы:
>
> Результатом суперкомпиляции является функция фазы 3. То есть, была
> некоторая рефал-5-функция, написанная программистом пятерошником, ее
> засунули в суперкомпилятор (с частично заданными данными) и Scp4 эту
> пятерошную программу ПОЛНОСТЬЮ ЗАНОВО переписал.
>
> Общий лозунг: Scp4 на самом деле ХОРОШИЙ ПЛЮСНЫЙ ПРОГРАММИСТ, из под "его
рук"
> выходят вполне плюсовые (по стилю и духу) программы.
>
> Фаза 3 (результат работы суперкомпилятора)--это ХОРОШАЯ Рефал Плюс
программа
> (как мне показалось). В ней только осталось раскомментировать описание
входного
> формата функций (они есть уже) и, неплохо бы, посчитать еще выходные
форматы--и
> вполне сносный код на Рефале Плюс.
>
> Те программы, которые написали программисты-пятерешники и которые не были
затем
> переписаны суперкомпилятором (Scp4 по своей природе является хорошим
> РефалаПлюс-программистом), так вот эти программы можно и нужно переписать
на
> рефале плюс.
>
> Когда я смотрел, какою техникой делается фаза 2 -- это чисто
Рефал-5-стрикт
> техника. Такой стиль написания поперек горлу Рефалу Плюс и на Рефале Плюс
> открытыми и откатными функциями это все делается лучше и пуще!
>
> Переписывать, переписывать и переписывать!
>
> Чтобы было ясно, о чем это я талдычу, я Вам напишу любимую замену A на B
(на
> всех скобочных уровнях) дважды: как ее могли бы написать
программист-пятерешник
> и плюсный-программист. Итак, маленькая "жемчужинка"...
>
> /* пример не надуманный, именно так примерно написана
> по стилю программистом-пятерешником фаза 2
> */
>
> /* рефала-плюс под руками нету, посему, пардон, возможны
> синт-неточности, но идея, я надеюсь, понятна.
> */
>
> программист-пятерешник =========================
>
> $func ZamenaAB e = e;
>
> ZamenaAB eX =
> eX:{
> 'A' eX-- = 'B' <ZamenaAB eX-->;
> sY eX-- = sY <ZamenaAB eX-->;
> (eY) eX-- = (<ZamenaAB eY-->) <ZamenaAB eX-->;
> /* empty */ = /* empty */;
> }
>
> плюсный-программист =========================
>
> $func RepAB! e = e; /* безоткатная главная функция */
> $func? RepAB? e = e;
> $func? RepTermAB? t = t;
>
> /* Откатные функции: если замена A -> B _меняет_ аргумент,
> тогда удача и мы строим измененный аргумент. Если не
> изменяет -- тогда просто неудача.
> */
>
> RepAB! eX = { <RepAB? eX>;
> eX;
> };
>
> /* Что есть изменяемое выражение и на что оно изменяется? */
>
> RepAB? eX tA eY, /* -- найти первый */
> <RepTermAB? tA>::tB, /* изменяемый терм? */
> <RepAB! eY> ::eZ, /* -- изменить хвост! */
> eX tB eZ; /* -- результат */
>
> /* Что есть изменяемый терм и на что он изменяется? */
>
> RepTermAB? \{ 'A', 'B';
> (eA), (<RepAB? eA>);
> };
>
> /////////////////////////////////////////////////////////////
АРК:
Есть предложения думать о том, можно ли и как такие преобразования
осуществлять автоматически. В данном случае речь идет о том, чтобы умный
компилятор догадался о двух разных моментах:
1. Что терм можно не строить заново, если в нем не было замен.
2. Что можно использовать повторно куски выражений; при этом они копируются,
но быстро, поскольку может использоваться специальная команда.
>
> Сноска (1)
>
> Под словами переписать под рефал плюс, я подразумеваю, в том числе и
> возможное (если оно потребуется) расширение рефал-плюс библиотеки.
>
> Например, функцией, которая одним чохом читает ВЕСЬ файл (а не по
> одному символу):
>
> $func ReadChars! s.Channel s.Length = e.Chars;
> /* считать s.Length (или до конца файла) символов из файла.
> Если s.Length < 0 -- считать от текущей позиции до конца
> файла...
> */
АРК:
Я думаю, будет полезнее, если такая функция будет строить не выражение
(где на каждый символ уходит 8 байтов), а символ-строку.
Такую штуку я когда-то сделал в Рефале-6, назвав ее, кажется, ReadBlock.
Оказалось полезным в программках типа форматной печати.
(Однако, должен признать, что эта "оптимизация" тоже идет в ущерб
идейной чистоте).
>
This archive was generated by hypermail 2b25 : Mon Oct 25 2004 - 21:24:58 MSD