Subject: Re: Как следует компилировать рефальскую операцию отождествления
From: Sergei M. Abramov (at home) (abram@botik.ru)
Date: Fri Dec 08 2000 - 18:26:35 MSK
Алик, привет!
Извини, что долко молчал--замотался!
-----Original Message-----
From: Arkady Klimov <klark@bagirra.net>
Date: 5 декабря 2000 г. 22:36
Subject: Re: Как следует компилировать рефальскую операцию отождествления
>Спасибо за инициативу и интересные материалы....
>Все очень интересно.
Спасибо на добром слове!
>Для Р+ и вообще отображение в массивное представление
>это то, что надо.
Кажется--да.
>Но в первом письме ты писал, что эти методы будут
>также интересны для реализаторов Р-5 и т.п.,
>то есть рефалов на списковом представлении.
Да.
>У меня есть в этом сомнения, попробуй их развеять.
>Ты справедливо замечаешь, что сложность операций
>может быть (и будет для списков) O(L). Но дальше
>ты писал, что алгоритм от этого не зависит.
>Согласен, алгоритм не зависит, но сложность его
>зависит и возможно радикально.
Более точно, что я ХОТЕЛ сказать (но возможно мне это НЕ ОЧЕНЬ удалось) это то,
что ПОРА стать ревизионистами, пора навести ревизию, пора еще раз подумать.
По крайней мере для случая квази-закрытых переменных:
e.Src : e1 A e1 B e1 C e1 D e1
предложенный ревизионизм эффективен для любого представления (списковое,
массивное): он работает как О(len_Src), вместо классического О(len_Src^4).
Для меня это достаточный аргумент чтобы всех ПРИЗВАТЬ к попытке ревизионизма
(ВСЕХ:
остроконечников и тупоконечников,
списочников и массивщиков,
врезанных и подвешанных,
со счетчиками и без).
Думать надо всем. Потом разбираться, в каких случаях какие методы лучше/хуже
для каких представлений.
Еще раз: лично для меня достаточно демонстрации ОДНОГО ранее прозеванного
случая, чтобы не побояться еще раз просмотреть (не побояться сделать ревизию).
> ... Есть только опасение в том, что
>значительная часть кода в компиляторе
>и интелекта при его создании будут
>потрачены как бы зря, поскольку в
>практических программах не будут
>востребованы ...
Ну да, ну да... Можно сказать (даже доказать статистической обработкай архива
всех в мире рефал-программ), что образцов вида "e.Src : e1 A e1 B e1 C e1 D e1"
нормальные люди ме пишут...
Ну да, до сих пор не писали (может быть). Но придет один новый юзер, напишет и
ведь стыдно будет за эффективность.
>Рассмотрим пример такого образца (из функции доступа к копилке):
>
>(e.name) (e.1 (e.name '=' e.value) e2)
>
>При существующей реализации его сложность - это объем символов из содержимого
>правого списка, которые надо просмотреть при поиске.
Ну... все-таки, я бы сказал, что О(L_name x L_storage). И это не зависит от
реализации...
>Когда сравнение неудачное, это обычно
>1-2 символа на одно имя.
;-)))) Посволь мне не согласиться и сказать, так "когда сравнение неудачное, это
обычно О(L_name/2)==О(L_name) символа на одно имя.
> ... То есть время будет грубо пропорционально
>количеству имен.
Ну уж нет, я бы сказал, что О(L_name x L_storage)
>Если же перед сравнением мы будет сначала вычислять длину,
>тратя O(L), то время поиска резко увеличится в разы - пропорционально средней
>длине имени.
Время увеличится в О(1), сохранив порядок О(L_name x L_storage) ;-))
>Но, повторяю, мое сомнение касается только
>применимости этих методов к списковой
>реализации.
Принято. Бесспорно.
А мои призывы были такие: лично мне одного примера достаточно для того, чтобы
призвать ЗАДУМАТЬСЯ.
А после этого применять или не применять--да черт с ним, в конце концов это дело
вкуса (и лени) реализатора.
В конце концов, мое любимое про программиста: "Сынок, ради Бога ничего не меняй!
Пусть все так и остается!"
Но в главном ты прав:
> ... Но это я так написал, чтобы иметь в виду,
>на самом деле надо продолжать в том же духе,
>и смотреть, что получается. А там видно
>будет.
Это точно. Если не пробовать, то видно не будет ;-)))
> ... Короче, я бы призывал ... вести ее разработку
>с прицелом на векторное представление, не оглядываясь
>на списки.
Так и делаем.
Разок, походя, призвали списочников оглянуться (на всякий случай) на эти
методы--вдруг понравится (по крайней мере в одном-то случае они эффективны ;-)?
Или просто из гуманистических побуждений захочется каплю свежего взгляда и
интеллекта потратить "на чужом поле", пролить на чужую мельницу...
Что же касается идеи "поддержка длины в списочном представлении":
> ... И тут мы возвращаемся к тому с чего
>начали - практической невозможности
>организовать вычисление и хранение
>длин списков с приемлемой для
>режима интерпретации сложностью.
Ты знаешь, чисто интуитивно я с тобою не соглашусь. Мне все-таки >>кажется<<,
что
==> в любой РАЗУМНОЙ списковой реализации Рефала за РАЗУМНЫЕ затраты (не
зависящие от длин);
==> МОЖНО сделать ДЕШЕВОЕ отслеживание длин
-- ВСЕХ ПОДВЕШЕННЫХ скобок,
-- всех АРГУМЕНТОВ в К-термах (вызов функции--те же подвешенные
скобки, в некотором роде).
Но я не готов тратить свое (и твое) время на проверку (опровержение) этого моего
интуитивного утверждения. Окончательно это доказывается только завершенной
отлаженной реализацией и это дело реализатора из лагеря списочников (не я).
>Короче, я бы призывал не мудрствовать
>по поводу "единой для всех" схемы компиляции,
>а просто вести ее разработку с прицелом
>на векторное представление, не оглядываясь на списки.
Согласен с твоими призывами. Не оглядоваемся (вот уже .... лет).
>Потом интересно будет посмотреть,
>нельзя ли сделать заметное упрощение
>в арсенале приемов, при котором типичные
>случаи практически не пострадали бы.
Ты знаешь, кажется и так все настолько просто вышло. Пока кажется--проще
некуда.
Удачи,
доживем до реализации (не за горами, я надеюсь...)
Сергей
This archive was generated by hypermail 2b25 : Mon Oct 25 2004 - 21:24:58 MSD