Subject: XML, "holes" and programming styles in R5 and R+
From: Andrei Klimov (Andrei.Klimov@supercompilers.com)
Date: Sun Jun 04 2000 - 05:37:26 MSD
Добрый день!
Направляю в 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)
Под словами переписать под рефал плюс, я подразумеваю, в том числе и
возможное (если оно потребуется) расширение рефал-плюс библиотеки.
Например, функцией, которая одним чохом читает ВЕСЬ файл (а не по
одному символу):
$func ReadChars! s.Channel s.Length = e.Chars;
/* считать s.Length (или до конца файла) символов из файла.
Если s.Length < 0 -- считать от текущей позиции до конца
файла...
*/
This archive was generated by hypermail 2b25 : Mon Oct 25 2004 - 21:24:58 MSD