Subject: Re: Re: Как следует компилировать рефалскую операцию отождествлени
From: Arkady Klimov (klark@bagirra.net)
Date: Wed Dec 06 2000 - 12:35:16 MSK
----- Original Message -----
From: Andrey Slepuhin <pooh@msu.ru>
To: Arkady Klimov <klark@bagirra.net>
Cc: Sergei M. Abramov <abram@botik.ru>; <refal@botik.ru>; Anton Yu. Orlov <orlov@mccme.ru>
Sent: Wednesday, December 06, 2000 11:05 AM
Subject: Re: Re: Как следует компилировать рефальскую операцию отождествления
| Arkady Klimov wrote:
|
| > Сергей Михайлович, привет,
| > привет участникам дискуссии!
| > Спасибо за инициативу и интересные материалы.
| > Прошу прощения, что долго не включался, отвечать было недосуг, но я все
| > читал и более-менее разбирался. Все очень интересно. Для Р+ и вообще
| > отображение в массивное представление это то, что надо. Но в первом письме
| > ты писал, что эти методы будут также интересны для реализаторов Р-5 и т.п.,
| > то есть рефалов на списковом представлении. У меня есть в этом сомнения,
| > попробуй их развеять. Ты справедливо замечаешь, что сложность операций может быть
| > (и будет для списков) O(L). Но дальше ты писал, что алгоритм от этого не зависит.
| > Согласен, алгоритм не зависит, но сложность его зависит и возможно радикально.
| > Рассмотрим пример такого образца (из функции доступа к копилке):
| >
| > (e.name) (e.1 (e.name '=' e.value) e2)
| >
| > При существующей реализации его сложность - это объем символов из содержимого
| > правого списка, которые надо просмотреть при поиске. Когда сравнение неудачное,
| > это обычно 1-2 символа на одно имя. То есть время будет грубо пропорционально
| > количеству имен. Если же перед сравнением мы будет сначала вычислять длину,
| > тратя O(L), то время поиска резко увеличится в разы - пропорционально средней
| > длине имени.
|
| С моей точки зрения правильная списковая реализация для рефал-выражений
| должна отслеживать их длину при конкатенациях и отщеплениях - это
| не вносит никакого оверхеда. Также могут существуют другие полезные
| инварианты, следить за которыми не мешало бы. Так, в новом рантайме
| рефала+ реализован флаг, указывающий, что выражение является "flat",
| т.е. не содержит скобочных термов.
Что значит "отслеживать", "следить"? Хранить (длину содержимого)
внутри всех термов? В принципе, это, наверно, возможно. Правда,
по всей видимости, тогда придется смириться с таким минусом, как то,
что в следующей функции
Dela
'a' e.1 = <Dela e.1>;
s.a e.1 = s.a <Dela e1>;
=;
}
рекурсия уже не будет концевой. Не дорога ли цена?
Аркадий
| Андрей(С)
|
| --
| A right thing should be simple (tm)
This archive was generated by hypermail 2b25 : Mon Oct 25 2004 - 21:24:58 MSD