Subject: Как следует компилировать рефальскую операцию отождествления
From: Sergei M. Abramov (abram@botik.ru)
Date: Tue Nov 21 2000 - 19:53:51 MSK
День добрый, всем!
Позвольте данной репликой начать дискуссию на тему:
<<Как следует компилировать рефальскую операцию отождествления:
RefalResExp : RefalPattern >>
Казалось бы, про это написано в куче книг--читай да программируй!
Однако, если добавить ровно одну вводную:
<<представление рефал-данных таково, что дешевы операции вычисления
длины и прямого доступа (по индексам) к термам и подвыражениям
(вырезки) рефальского выражения>>
ответ становится не столь очевидным.
Ребята из Рефал-5 команды! То, что я предлагаю обсудить имеет смысл
(имеет эффект) не только для случая, когда слова <<дешевы операции>>
понимаются как:
* <<время исполнения есть О(1)>> (* R+ run-time *)
но и для случая:
* <<время исполнения есть О(length)>> (* R5 run-time *)
Сегодня делаются (замечательные и нужные) усилия по компиляции в Си как
Рефала Плюс, так и Рефала 5. Я утверждаю, что ПОРА ЗАНОВО И СОВМЕСТНО
ПЕРЕСМОТРЕТЬ АЛГОРИТМЫ РЕАЛИЗАЦИИ ОТОЖДЕСТВЛЕНИЯ С ОБРАЗЦОМ В РЕФАЛЕ, с
учетом указанной выше вводной и с учетом того, что это нужно для любого
Рефала (и для Рефала Плюс, и для Рефала-5) при его компиляции в Си.
А поэтому, хочется привлечь к дискуссии все рефал-головы и на выходе
поиметь один, обсужденный всеми алгоритм эффективной компиляции в Си
операции вида:
RefalResExp : RefalPattern
Причем я утверждаю, что этот алгоритм мало зависит от того, какую
сложность /* О(1) или О(length) */ имеют такие базовые операции
"доступа":
int L = length(ref_expr);
rexp eX = subexpr(eOld, index_start, L);
rterm tY = subterm(eOld, index);
и т.п. /* см. например Р+ модуль ACCESS */
========================================================================
А теперь один маленький примерчик, который показывает, что многое в этой
кухне надо делать ЗАНОВО. И в Р+, и в Р5.
Спросим себя, какую сложность имеет такая перестройка и во что она
должна компилироваться:
eOld : e1 e1,
...и дальше...
Насколько я понимаю, по классике и во всех (ВО ВСЕХ, включая Р5-->Си)
сегодняшних реализациях эта штука имеет сложность О(L*L). А хочется
видеть вот такую компиляцию в C/C++ этого фрагмента:
{ int L;
rexpr e1;
{ rexpr е1_1;
L = length(eOld);
if (L % 2) /* если не делится на 2 */
goto <<current_label_if_fail>>;
L = L / 2;
e1 = subexp(eOld, 0, L);
e1_1 = subexp(eOld, L, L);
if (!(is_equal_exp(e1,e1_1))
goto <<current_label_if_fail>>;
};
<<Си код компиляции "...и дальше...">>
}
Данный код работает со сложностью О(L) /* как для Р5, так и для Р+
реализации примитивов "subexp", "length", "is_equal_exp" */.
Задачка: скомпилировать такие
(1) eSrc : e1 A e1
(2) eSrc : A e1 B e1 C e1 D
Все это--безвариантные (беспереборные, O(L)) образцы. Квази-закрытые
е-переменные, обобщающие случай старой/доброй закрытой переменной...
Скажут--на практике такое редко... Да дело не в этом, дело в том, что
при реализации в run-time примитивов
length(...), subexpr(..., index, len), и т.п.
мне кажется компиляция в такие примитивы должна идти немного подругому,
нежели это описано в классике.
========================================================================
Позволю перед сообществом поставить вопрос о том, чтобы совместными
усилиями разработать общий новый алгоритм компиляции фрагмента
<<RefalResExp : RefalPattern>>
такой, чтобы в частном случае <<eOld : e1 e1>> он давал бы алгоритм,
приведенный выше...
/* то есть, написать текст, не обязательно на языке
программирования--можно на псевдокоде, статью, в конце
концов */
Лично я не имею сейчас в голове >>точного досконального описания<<
такого алгоритма. А кто-нибудь имеет?
Сейчас я предприму попытку выписать ДРАФТ такого алгоритма, а всех
приглашаю его чиркать и дополнять, пока не появится посмотренный всеми,
почирканный и вылизанный всеми алгоритм.
Для удобства чиркания, я предлагаю работать с текстовым файлом
(прилагаю), вставляя в него свои абзацы.
/* и отмечая реплики как-то, например в таком стиле:
<<СА: 21.11.2000 12:00
.... реплика: добавить, удалить, переформулировать....
СА: 21.11.2000 12:00>>
*/
Или кардинально правя файл и присылая новые версии... Спасибо!
Удачи
Сергей
This archive was generated by hypermail 2b25 : Mon Oct 25 2004 - 21:24:58 MSD