Андрей!
Описываю, что я имел ввиду, на Рефале. Будем предполагать, что в этой
реализации используются подвешенные скобки.
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
<http://a.v.konovalov87_AT_mail.ru> <refal@botik.ru <mailto: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
<http://a.v.konovalov87_AT_mail.ru> <refal@botik.ru <mailto: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> ),
поскольку они образуют группу. Это значит, что если известны хеши двух строк,
хеш конкатенации вычисляется за константу. Если известен хеш строки и хеш её
префикса, то хеш суффикса тоже вычисляется за константу (для известного хеша
суффикса — аналогично). Вообще, я ещё летом поминал в рассылке кольцевые хеши.
Но это были пустые размышления, поскольку тогда у меня не было своей нормальной
реализации с векторами (нет и сейчас), а также понимал, что оверхед на всё это
будет больше, чем потенциальная выгода.
Да, интересная идея с кольцевыми хешами (хотя не могу сказать, что я ее
полностью ухватил), но, действительно, неясно, есть ли овчинка выделки и не
будет ли только хуже. Всё зависит от задач, и как универсальное представление
вряд ли годится. Пример класса задач, где, в принципе, могла бы быть польза –
это упомянутая компьютерная алгебра. Поэтому я думал поискать по литературе, не
использовались ли коллапсирующие (склеивающие часть подвыражений) или
табулируемые (склеивающие все равные подтермы) в каких-нибудь системах
компьютерной алгебры. Но так руки не дошли.
Всего наилучшего,
Андрей
