Subject: Re: Re: Re: Re: Как следует компилировать ре фаль скую операциюотождествления
From: Andrey Slepuhin (pooh@msu.ru)
Date: Wed Dec 06 2000 - 23:05:07 MSK
Arkady Klimov wrote:
> ----- 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 1:25 PM
> Subject: Re: Re: Re: Как следует компилировать рефаль скую операциюотождествления
>
>
> | Arkady Klimov wrote:
> |
> | > ----- 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>;
> | > =;
> | > }
> | >
> | > рекурсия уже не будет концевой. Не дорога ли цена?
> |
> | В первом случае будет нормальный хвостовой вызов и ничто этому
> | не помешает, а во втором случае его не будет - куда конкатенацию девать?
> | Хвостовой вызов там может быть, только если у нас семантика ленивая -
> | сначала делаем конкатенацию с неготовым выражением, а потом вычисляем выражение.
> |
> Да, точнее, если реализация конкатенации у нас ленивая
> (на семантику-то языка это не влияет),
> а еще точнее - нестрогая (то есть выполняется раньше своих аргументов).
> Именно такая сейчас в рефалах 5 и 6. Поэтому не будет большой проблемой
> запустить указанную функцию над последовательностью из 1000000 символов.
Ммм... Конкатенация-то может быть нестрогой, а вот как наччет хвостового
вызова дальше? Хвостовой вызов предполагает, что мы полностью освобождаемся
от контекста _вызывающей_ функции. Однако нам в итоге нужно в качестве
результата вернуть результат конкатенации и _вызываемая_ функция ничего
про него знать не должна, поскольку он не находится в рамках ее контекста.
Если в рефалах 5 и 6 такое реализовано, то интересно, как при этом
удалось обойтись без всяких нечестных хаков?
Андрей(С)
-- A right thing should be simple (tm)
This archive was generated by hypermail 2b25 : Mon Oct 25 2004 - 21:24:58 MSD