Александр, да, теперь я понял.
Получилось так, что мы писали навстречу друг другу.
Я только что послал письмо, где обрисовал картину более подробно с
возможными решениями, но, к сожалению, неидеальными.
Андрей
On Wed, Feb 13, 2019 at 2:10 PM Александр Коновалов
a.v.konovalov87_AT_mail.ru <refal@botik.ru> wrote:
> Андрей!
>
> Описываю, что я имел ввиду, на Рефале. Будем предполагать, что в этой
> реализации используются подвешенные скобки.
>
> F {
> = <G ('abc') ('abc')>;
> }
>
> G {
> t.1 t.2 = <H t.1 t.2 t.2 t.1>;
> }
>
> H {
> t.X t.X t.Y t.Y = t.X t.Y;
> }
>
> В памяти всё равно могут остаться два экземпляра ('abc'). Потому что
> первый раз мы сравниваем t.1 с t.2 (и присваиваем первому терму ссылку
> на второй), а второй раз — t.2 с t.1 (и присваиваем третьему терму ссылку
> на четвёртый). При первом присваивании одна ссылка на t.1 удаляется, одна
> ссылка на t.2 появляется. При втором наоборот. К моменту выполнения
> правой части в памяти останутся по два экземпляра ('abc'), на каждый
> из которых по две ссылки.
>
>
>
> С уважением,
> Александр Коновалов
>
>
>
> *From:* Andrei Klimov andrei.klimov_AT_gmail.com <refal@botik.ru>
> *Sent:* Wednesday, February 13, 2019 1:08 PM
> *To:* refal@botik.ru
> *Subject:* Re: Коллапсируюшее представление данных
>
>
>
> Александр, тогда я видимо совсем вас не понял – ни псевдокод, ни
> объяснение словами в предыдущем письме:
>
>
>
> ср, 13 февр. 2019 г., 0:18 Александр Коновалов a.v.konovalov87_AT_mail.ru
> <refal@botik.ru>:
> Добрый вечер, Сергей!
> > 2. Наконец, если нам пришлось делать длинное сравнение и в конце
> выяснилось, что термы таки равны, то мы делаем "коллапсирующие джунгли" --
> делаем присваивание: p2 = p1, L2=L1 (второе лишнее, но пусть будет). Тут и
> память освободилась и следующий раз сравнение на равенство пройдет быстрее
> ;-)
> *А если у нас в поле зрения есть несколько экземпляров одинаковых пар (p1,
> L1), (p2, L2). В первый раз сравниваются пары в порядке (p1, L1) == (p2,
> L2) и мы присвоили p1 := p2. В другой раз (другие экземпляры) сравнились в
> порядке (p2, L2) == (p1, L1) и коллапсировались уже p2 := p1. Тогда память
> не освободится. Такое может быть?*
>
>
>
> По-видимому, я не сообразил, про какое представление рефал-выражений идет
> речь.
>
> И я тоже виноват, что не пояснил, что подразумевал. Договорю.
>
>
>
> Лучше всего рассмотреть "подвещенные" скобки: скобочный терм (e0)
> представляется ссылкой на представление e0. Это ссылка хранится в месте
> терма (e0) в выражениях, в которые он входит. То есть,
>
> - <представление выражение e1(e0)e2> = <представление e1> <ссылка на
> (e0)> <представление e2>
>
> Заметим, что это рассуждение не зависит от того, массивное представление
> выражений или одно- или двунаправленное списочное.
>
>
>
> Если в процессе отождествления повторных переменных были обнаружены равные
> термы (e0), входящие в два выражения, то в одном из выражений ссылка на
> (e0) заменяется на вторую, а второе представление (e0) может освободиться
> (сборкой мусора или по счетчику ссылок).
>
>
>
> Александр, тонкость, о которой вы пишите, присутствует в таком
> представлении с такой операцией сравнения?
>
>
>
> Если речь о том, что отнюдь не все равные термы будут сколлапсированы, а
> только те, что когда-то пройдут через операцию сравнения их вхождений в
> какие-то выражения, то да, это так. В частности это гасило пыл попробовать
> такую реализацию, так как программисту очень трудно предсказывать пользу:
> произошла ли экономия памяти и операций сравнения или нет.
>
>
>
> On Wed, Feb 13, 2019 at 12:17 PM Александр Коновалов
> a.v.konovalov87_AT_mail.ru <refal@botik.ru> wrote:
>
> Доброе утро, Андрей!
>
> Спасибо за интересное письмо!
>
> *«Память освободится, но отдельно в первой паре и во второй, а чтобы
> остался один экземпляр из четырёх, нужно ещё одно сравнение.»*
>
> Я имел ввиду другое. Поясню псевдокодом:
>
> def equals(lhs, rhs):
> if lhs.L == 0 && rhs.L == 0:
> return True
> elif lhs.L == rhs.L && strcmp(lhs.p, rhs.p) == 0:
> // коллапсируем
> lhs.p := rhs.p
> return True
> else:
> return False
>
> x1 := (p1, L)
> x2 := (p2, L)
> x3 := (p1, L)
> x4 := (p2, L)
>
> equals(x1, x2)
> equals(x4, x3)
>
> Предполагается, что p1 и p2 — указатели на разные строки с одинаковым
> содержимым. После выполнения этого псевдокода будет x1.p ≡ x2.p ≡ p2 и x3.
> p ≡ x4.p ≡ p1. Т.е. память не освободится. Просто переменные поменяются
> ссылками. Поэтому и нужно дополнительное ранжирование. Вроде вот этого:
>
> *«То есть в ящиках поддерживаются индексы в некотором отношении линейного
> порядка для последующего быстрого сравнения»*
>
> Либо можно сравнивать указатели как числа и присваивать большему меньшее.
>
>
>
> Я не понял, зачем может понадобится отношение порядка для коллапсирования.
>
>
>
> *«Чтобы экономить память (и надеялись — и время), для системы Сантра Игоря
> Шенкова я ещё в 80-е годы разработал библиотечку ROTAB (References for
> Order Tabulation) для „коллапсирования рефал-выражений в ящики“ (выдаётся
> ссылка на тот же ящик, если уже формировался ящик с таким же содержимым)
> и табуляции их отношения порядка.»*
>
> Когда-то я подумывал о похожей системе для Рефала с массивным
> представлением. Поддерживается глобальное хеш-множество для всех скобочных
> термов в поле зрения, и, когда надо построить новый скобочный терм, вместо
> нового выбирается уже существующий. Нашёл, что для этой цели нужно
> использовать кольцевые хеши (rolling hash
> <https://www.google.ru/search?q=rolling+hash&tbm=isch>), поскольку они
> образуют группу. Это значит, что если известны хеши двух строк, хеш
> конкатенации вычисляется за константу. Если известен хеш строки и хеш её
> префикса, то хеш суффикса тоже вычисляется за константу (для известного
> хеша суффикса — аналогично). Вообще, я ещё летом поминал в рассылке
> кольцевые хеши.
>
> Но это были пустые размышления, поскольку тогда у меня не было своей
> нормальной реализации с векторами (нет и сейчас), а также понимал, что
> оверхед на всё это будет больше, чем потенциальная выгода.
>
>
>
> Да, интересная идея с кольцевыми хешами (хотя не могу сказать, что я ее
> полностью ухватил), но, действительно, неясно, есть ли овчинка выделки и не
> будет ли только хуже. Всё зависит от задач, и как универсальное
> представление вряд ли годится. Пример класса задач, где, в принципе, могла
> бы быть польза – это упомянутая компьютерная алгебра. Поэтому я думал
> поискать по литературе, не использовались ли коллапсирующие (склеивающие
> часть подвыражений) или табулируемые (склеивающие все равные подтермы) в
> каких-нибудь системах компьютерной алгебры. Но так руки не дошли.
>
>
>
> Всего наилучшего,
>
> Андрей
>
