RE: Коллапсируюшее представление данных

[Александр Коновалов a . v . konovalov87_AT_mail . ru]

Доброе утро, Антон!

«Чтобы ответить на вопрос, много ли это даёт, хорошо было бы прогнать на 
представительном наборе программ на Рефале+, которого, однако, не наблюдается 
:)»

Как это знакомо! Когда я разрабатывал Простой Рефал и давал связанные с ним 
курсовые (на оптимизации), протестировать быстродействие можно было только на 
самом себе. Потом я переделал Простой Рефал в Рефал-5λ (совместимый с 
Рефалом-5) и с набором тестовых программ стало проще :-).

Мне обидно немного за Рефал Плюс — столько трудов вложено, но им пользуются 
мало. По крайней мере, я не знаю ничего о его использовании кем-то и где-либо. 
И сам помочь не могу, поскольку всё моё программирование на Рефале — разработка 
самоприменимого компилятора для другого диалекта.

Front-end’ы Рефала-5 и Рефала-6 для Рефала Плюс на сколько совместимы?

 

С уважением,
Александр Коновалов 

 

From: Anton Orlov orlovan_AT_gmail.com  
Sent: Thursday, February 14, 2019 3:48 AM
To: refal@botik.ru
Subject: Re: Коллапсируюшее представление данных

 

 

 

On Wed, Feb 13, 2019 at 6:13 AM Andrei Klimov andrei_AT_klimov.net 
mailto:refal@botik.ru> > wrote:

Александр, еще раз добрый день!

 

Я понял, о чем вы писали и зачем требуется отношение порядка. Объясню своими 
словами на подвешенных скобках.

 

Пусть (eX) и (eY) входят в два выражения e1(eX)e2 и e3(eY)e4, и при их 
сравнении выяснилось, что (eX) = (eY).

И пусть на представления (eX) и (eY) есть еще ссылки из других выражений.

Тогда замена ссылки на (eX) в первом выражении на ссылку на (eY) не освобождает 
память представления (eX).

И наоборот, замена ссылки на (eY) во втором на ссылку на (eX) не освобождает 
память представления (eY).

Более того, теряется информация про равенство (eX), или соответственно (eY), 
равным термам в других выражениях.

 

Хотелось бы, чтобы был разумный способ выбрать, что на что заменять, чтобы 
какое-то из представлений равных термов лидировало и затягивало бы в себя 
ссылки с других.

Например, в реализации со счетчиками ссылок на скобочный терм, можно переносить 
на представление с большим счетчиком.

 

В Рефале+ (в рантайме Андрея Слепухина) именно так и сделано.

Чтобы ответить на вопрос, много ли это даёт, хорошо было бы прогнать на 
представительном наборе программ на Рефале+, которого, однако, не наблюдается 
:).

 

Антон

 

А если есть отношение порядка между представлениями, то можно выбирать 
наименьшее.

Если сборка мусора не меняет расположение представлений в памяти (что, как 
правило, имеет место быть), то подходящий порядок задают адреса.

Но все равно процесс "затягивания" ссылок на самое "тяжелое" представление 
будет медленным и плохо предсказуемым.

 

Чтобы не терять информацию об уже обнаруженных равенствах термов, лучший (как 
мне помнится) вариант, который был придуман такой:

Головная ячейка представления скобочного терма может быть прокси, то есть 
ссылкой на окончательное представление или снова на прокси.

Тогда при выяснении равенства (eX) и (eY) в вышеприведенном примере головная 
ячейка, скажем, (eY) становится прокси, ссылающимся на головную ячейку (eX). 
Подмена ссылки в выражении тоже делается.

 

Теперь при каждом вхождении в скобки нужно проверять, не на прокси ли мы 
попали, и, если да, идти дальше. Одновременно спрямлять ссылки.

 

Вот такая сложность картины, плюс ее непредсказуемость для Рефал-программиста, 
и привели к тому, что эти идеи остались в истории.

Теперь я вспомнил, что отсутствие "идеальных" решений и есть главная причина, 
из-за которой идея не пошла в массы = в реализации Рефала.

Спасибо, вот сейчас мы нечаянно на них вышли и запротоколировали.

Может, где-то когда-то кому-то пригодится.

 

И по-прежнему, интересно узнать, использовалось ли такое коллапсирование или 
обсуждавшаяся табуляция в каких-нибудь системах.

Если кто наткнется или уже знает, напишите, пожалуйста.

 

Всего наилучшего,

Андрей

 

On Wed, Feb 13, 2019 at 1:08 PM Andrei Klimov andrei.klimov_AT_gmail.com 
<http://andrei.klimov_AT_gmail.com>  mailto:refal@botik.ru> > 
wrote:

Александр, тогда я видимо совсем вас не понял – ни псевдокод, ни объяснение 
словами в предыдущем письме:

 

ср, 13 февр. 2019 г., 0:18 Александр Коновалов a.v.konovalov87_AT_mail.ru 
<http://a.v.konovalov87_AT_mail.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. Тогда память не освобо

Re: Коллапсируюшее представление данных

[Anton Orlov orlovan_AT_gmail . com]

On Wed, Feb 13, 2019 at 6:13 AM Andrei Klimov andrei_AT_klimov.net <
refal@botik.ru> wrote:

> Александр, еще раз добрый день!
>
> Я понял, о чем вы писали и зачем требуется отношение порядка. Объясню
> своими словами на подвешенных скобках.
>
> Пусть (eX) и (eY) входят в два выражения e1(eX)e2 и e3(eY)e4, и при их
> сравнении выяснилось, что (eX) = (eY).
> И пусть на представления (eX) и (eY) есть еще ссылки из других выражений.
> Тогда замена ссылки на (eX) в первом выражении на ссылку на (eY) не
> освобождает память представления (eX).
> И наоборот, замена ссылки на (eY) во втором на ссылку на (eX) не
> освобождает память представления (eY).
> Более того, теряется информация про равенство (eX), или соответственно
> (eY), равным термам в других выражениях.
>
> Хотелось бы, чтобы был разумный способ выбрать, что на что заменять, чтобы
> какое-то из представлений равных термов лидировало и затягивало бы в себя
> ссылки с других.
> Например, в реализации со счетчиками ссылок на скобочный терм, можно
> переносить на представление с большим счетчиком.
>

В Рефале+ (в рантайме Андрея Слепухина) именно так и сделано.
Чтобы ответить на вопрос, много ли это даёт, хорошо было бы прогнать на
представительном наборе программ на Рефале+, которого, однако, не
наблюдается :).

Антон

А если есть отношение порядка между представлениями, то можно выбирать
> наименьшее.
> Если сборка мусора не меняет расположение представлений в памяти (что, как
> правило, имеет место быть), то подходящий порядок задают адреса.
> Но все равно процесс "затягивания" ссылок на самое "тяжелое" представление
> будет медленным и плохо предсказуемым.
>
> Чтобы не терять информацию об уже обнаруженных равенствах термов, лучший
> (как мне помнится) вариант, который был придуман такой:
> Головная ячейка представления скобочного терма может быть прокси, то есть
> ссылкой на окончательное представление или снова на прокси.
> Тогда при выяснении равенства (eX) и (eY) в вышеприведенном примере
> головная ячейка, скажем, (eY) становится прокси, ссылающимся на головную
> ячейку (eX). Подмена ссылки в выражении тоже делается.
>
> Теперь при каждом вхождении в скобки нужно проверять, не на прокси ли мы
> попали, и, если да, идти дальше. Одновременно спрямлять ссылки.
>
> Вот такая сложность картины, плюс ее непредсказуемость для
> Рефал-программиста, и привели к тому, что эти идеи остались в истории.
> Теперь я вспомнил, что отсутствие "идеальных" решений и есть главная
> причина, из-за которой идея не пошла в массы = в реализации Рефала.
> Спасибо, вот сейчас мы нечаянно на них вышли и запротоколировали.
> Может, где-то когда-то кому-то пригодится.
>
> И по-прежнему, интересно узнать, использовалось ли такое коллапсирование
> или обсуждавшаяся табуляция в каких-нибудь системах.
> Если кто наткнется или уже знает, напишите, пожалуйста.
>
> Всего наилучшего,
> Андрей
>
> On Wed, Feb 13, 2019 at 1:08 PM Andrei Klimov andrei.klimov_AT_gmail.com <
> refal@botik.ru> wrote:
>
>> Александр, тогда я видимо совсем вас не понял – ни псевдокод, ни
>> объяснение словами в предыдущем письме:
>>
>> ср, 13 февр. 2019 г., 0:18 Александр Коновалов a.v.konovalov87_AT_mail.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) может
>> освободиться (сборкой мусора или по счетчику ссылок).
>>
>> Александр, тонкость, о которой вы пишите, присутствует в таком
>> представлении с такой операцией сравнения?
>>
>> Если речь о том, что отнюдь не все равные термы будут сколлапсированы, а
>> только те, что когда-то пройдут через операцию сравне

Re: Коллапсируюшее представление данных

[Andrei Klimov andrei_AT_klimov . net]

Переношу реплику Аркадия под этот сабж.
А то мысли про джунгли окажутся потерянными в нескольких тредах.
Андрей

On Wed, Feb 13, 2019 at 6:26 PM Arkady Klimov arkady.klimov_AT_gmail.com <
refal@botik.ru> wrote:

> То, о чем написал Сергей действительно полезно на практике. У меня
> написана некая система работы с полиномами, и там обрабатываются
> неравенства вида P(x,y,...) < K, где K - целое число, а P не содержит
> свободного члена. В списке таких неравенств часто надо находить неравенства
> с общей левой частью (подобные). Конечно, полиномы должны иметь
> канонизированное представление. Тогда, джунгли очень даже полезны будут при
> поиске пар подобных неравенств посредством образца
>e1 (tA e) e2 (tA e) e3
> Ну и память экономится, если таких пар много.
>
> А насчет сборки мусора - так Антон и написал же, что ее нет, а есть
> счетчики ссылок. А нужна она только чтобы зависшие ящики подчищать. Но мне
> кажется, что это особо и не нужно - всегда можно руками вовремя обнулить.
> А если и вводить, то надо и "слабые" ссылки вводить.
>
> Другое дело, что возможно счетчики ссылок будут мешать распараллеливанию
> "над общей памятью". Даже если функции чистые и формально независимые, при
> параллельном выполнении придется корректировки ссылок делать защищенно,
> скажем atomic. Вопрос к залу: это не очень тормозить будет? Не потеряется
> ли эффект от распараллеливания? Надо б проверить.
> Аркадий К.
>
>
> вт, 12 февр. 2019 г. в 17:22, Eisymont Leonid verger-lk_AT_yandex.ru <
> refal@botik.ru>:
>
>> Так это массивное представление оправдало себя или нет? В сухом остатке
>> ведь - сборка мусора на ровном месте(раньше не было), какие-то переполнения
>> стеков. А в программах копирования списков не так уж и много, откуда этот
>> миф? Ради чего?
>> Наукообразия? Кто в больших программах про эти "джунгли" думать будет?
>> Имеются несколько недоработанных реализаций? Какая лучше всех, чем
>> пользоваться можно? Бенчмарки были или нет? М.б. просто рефал-2 взять и все
>> дела. Восстановить распараллеливание там хотя бы через машинные операции и
>> все. Прирост скорости будет в сотни раз на современных системах, а не
>> проценты или разы. Как быть?
>> Л.Эйсымонт
>>
>>
>> 12.02.2019, 15:53, "Sergei M. Abramov abram_AT_botik.ru" > >:
>>
>> День добрый, всем!
>>
>> Антон, спасибо за детали. Думаю снято много обвинений в сторону
>> массивного представления ;-)
>>
>> Коллеги, и это не все фенечки еще описаны. Как мелкий пример: как мне
>> помнится (Антон поправит), были еще реализованы "коллапсирующие
>> джунгли" или "табулирование сравнения термов-скобок".
>>
>> Суть простая:
>>
>> 0. Терм-скобка это поинтер на первое звено p и длина L.
>>
>> 1. У сравнения двух термов-скобок на равенство есть масса быстрых слуюаев:
>> 1.0 Если L1 == 0 && L2==0, то термы равны
>> 1.1 Если L1 /= L2, то термы не равны,
>> 1.2 Если p1==p2 && L1==L2, то термы равны
>>
>> 2. Наконец, если нам пришлось делать длинное сравнение и в конце
>> выяснилось, что термы таки равны, то мы делаем "коллапсирующие
>> джунгли" -- делаем присваивание: p2 = p1, L2=L1 (второе лишнее, но
>> пусть будет). Тут и память освободилась и следующий раз сравнение на
>> равенство пройдет быстрее ;-)
>>
>> О! Ран-тайм рефала плюс полировался с любовью ;-)
>>
>> Всего доброго,
>>
>> Сергей Абрамов
>>
>>
>> Anton Orlov orlovan_AT_gmail.com.
>>
>> Вы писали 11 февраля 2019 г., 21:39:24:
>>
>>  Добрый день!
>>
>>  On Mon, Feb 11, 2019 at 12:50 PM Arkady Klimov
>>  arkady.klimov_AT_gmail.com  <
>> refal@botik.ru> wrote:
>>
>>  Может ли кто ответить на такие вопросы по реализации Рефал+ на C++
>>  (в статье они не обсуждается - не тот уровень абстракции):
>>
>>  1.Какая организована работа с памятью? Какой менеджер памяти
>>  используется? Свой или каждый новый чанк через malloc запрашивается?
>>
>>  Сделан свой аллокатор по алгоритму близнецов, описанному Кнутом
>>  (https://en.wikipedia.org/wiki/Buddy_memory_allocation). Это делал
>> Андрей Слепухин.
>>
>>  2.Используются ли счетчики ссылок? Или полная сборка мусора время от
>> времени? Какой сборщик мусора?
>>
>>  Используются счётчики ссылок. Полной сборки мусора нет, поэтому
>>  память может течь (например, возможны циклы через ящики). Сборка
>>  мусора была в планах, но так и не была реализована (на практике
>> надобность в ней не ощущалась).
>>
>>  3.Есть ли версия конкатенации inplace (когда память для выражения
>>  взята "с запасом")? Андрей уже ответил частично.
>>
>>  В алгоритме близнецов все выделяемые куски имеют размер 2^n.
>>  Выражение помещается посередине нового куска, а справа и слева
>>  естественным образом получается запас по месту. При конкатенации,
>>  если этой дырки рядом с одним из выражений достаточно, то копируется
>>  только одно из выражений, а новая память не выделяется.
>>
>>  Например, если выражение длины N строится дописыванием в
>>  конец/начало по одному терму, то это требует O(log N) аллокаций
>>  (амортизированная стоимость O(1)).
>>
>>  Ант

Re: Коллапсируюшее представление данных

[Andrei Klimov andrei_AT_klimov . net]

On Wed, Feb 13, 2019 at 9:55 PM Александр Коновалов
a.v.konovalov87_AT_mail.ru  wrote:

> Прокси может ссылаться на прокси.
>
> Допустим, у нас есть три равных терма: A, B и C.
>
> Сравнивая A и B, мы превращаем A в прокси, который ссылается на B: A → B.
>
> Сравнивая затем B и C, делаем прокси B: B → C.
>
> Получается цепочка прокси: A → B → C.
>
> Конечно, при следующем обращении к A цепочка коллапсирует до A → C.
>

Да, верно. Ну это я пытался пооптимизировать сверх основного утверждения и
проврался.🤕
Главное – каждое обращение спрямляет ссылку. Остальное – мелочи.

Андрей


> Александр Коновалов
>
>
>
> *From:* Andrei Klimov andrei_AT_klimov.net 
> *Sent:* Wednesday, February 13, 2019 9:42 PM
> *To:* refal@botik.ru
> *Subject:* Re: Коллапсируюшее представление данных
>
>
>
> On Wed, Feb 13, 2019 at 2:42 PM Александр Коновалов
> a.v.konovalov87_AT_mail.ru  wrote:
>
> Андрей!
>
>
> *«Головная ячейка представления скобочного терма может быть прокси,
> то есть ссылкой на окончательное представление или снова
> на прокси.»«Одновременно спрямлять ссылки.»*
>
> Получаем лес непересекающихся множеств:
>
> https://ru.wikipedia.org/wiki/Лес_непересекающихся_множеств
>
> У этого метода самая лучшая временна́я сложность после константы —
> обратная функция Аккермана. Недостаток — требуется дополнительное поле
> ранга для выбора чего чему присваивать. Но ранг вроде тоже небольшой
> (в книжке Кормена, Лейзерсона и др. вроде про это есть), скорее всего байта
> хватит.
>
>
>
> Я не вижу смысла делать операцию объединения множеств, представленных
> таким "лесом", для которой в этой статье обсуждают сложность и нужен ранг.
> Каждая ссылка на прокси, спрямляются один раз в жизни, когда по ней
> произойдет доступ, проходом от прокси к реальному представлению. И прокси
> надо сразу устанавливать на представление терма. Я зря написал, что прокси
> может ссылаться на прокси. Это я недодумал.
>
>
>
> Других операций над прокси не выполняется. Тут вроде бы нечего
> оптимизировать.
>
>
>
> Всего наилучшего,
>
> Андрей
>
>
>
>  С уважением,
>
> Александр Коновалов
>
>
>
> *From:* Andrei Klimov andrei_AT_klimov.net 
> *Sent:* Wednesday, February 13, 2019 2:11 PM
> *To:* refal@botik.ru
> *Subject:* Re: Коллапсируюшее представление данных
>
>
>
> Александр, еще раз добрый день!
>
>
>
> Я понял, о чем вы писали и зачем требуется отношение порядка. Объясню
> своими словами на подвешенных скобках.
>
>
>
> Пусть (eX) и (eY) входят в два выражения e1(eX)e2 и e3(eY)e4, и при их
> сравнении выяснилось, что (eX) = (eY).
>
> И пусть на представления (eX) и (eY) есть еще ссылки из других выражений.
>
> Тогда замена ссылки на (eX) в первом выражении на ссылку на (eY) не
> освобождает память представления (eX).
>
> И наоборот, замена ссылки на (eY) во втором на ссылку на (eX) не
> освобождает память представления (eY).
>
> Более того, теряется информация про равенство (eX), или соответственно
> (eY), равным термам в других выражениях.
>
>
>
> Хотелось бы, чтобы был разумный способ выбрать, что на что заменять, чтобы
> какое-то из представлений равных термов лидировало и затягивало бы в себя
> ссылки с других.
>
> Например, в реализации со счетчиками ссылок на скобочный терм, можно
> переносить на представление с большим счетчиком.
>
> А если есть отношение порядка между представлениями, то можно выбирать
> наименьшее.
>
> Если сборка мусора не меняет расположение представлений в памяти (что, как
> правило, имеет место быть), то подходящий порядок задают адреса.
>
> Но все равно процесс "затягивания" ссылок на самое "тяжелое" представление
> будет медленным и плохо предсказуемым.
>
>
>
> Чтобы не терять информацию об уже обнаруженных равенствах термов, лучший
> (как мне помнится) вариант, который был придуман такой:
>
> Головная ячейка представления скобочного терма может быть прокси, то есть
> ссылкой на окончательное представление или снова на прокси.
>
> Тогда при выяснении равенства (eX) и (eY) в вышеприведенном примере
> головная ячейка, скажем, (eY) становится прокси, ссылающимся на головную
> ячейку (eX). Подмена ссылки в выражении тоже делается.
>
>
>
> Теперь при каждом вхождении в скобки нужно проверять, не на прокси ли мы
> попали, и, если да, идти дальше. Одновременно спрямлять ссылки.
>
>
>
> Вот такая сложность картины, плюс ее непредсказуемость для
> Рефал-программиста, и привели к тому, что эти идеи остались в истории.
>
> Теперь я вспомнил, что отсутствие "идеальных" решений и есть главная
> причина, из-за которой идея не пошла в массы = в реализации Рефала.
&g

RE: Коллапсируюшее представление данных

[Александр Коновалов a . v . konovalov87_AT_mail . ru]

Прокси может ссылаться на прокси.

Допустим, у нас есть три равных терма: A, B и C.

Сравнивая A и B, мы превращаем A в прокси, который ссылается на B: A → B.

Сравнивая затем B и C, делаем прокси B: B → C.

Получается цепочка прокси: A → B → C.

Конечно, при следующем обращении к A цепочка коллапсирует до A → C.

 

Александр Коновалов

 

From: Andrei Klimov andrei_AT_klimov.net  
Sent: Wednesday, February 13, 2019 9:42 PM
To: refal@botik.ru
Subject: Re: Коллапсируюшее представление данных

 

On Wed, Feb 13, 2019 at 2:42 PM Александр Коновалов a.v.konovalov87_AT_mail.ru 
<http://a.v.konovalov87_AT_mail.ru>  mailto:refal@botik.ru> > 
wrote:

Андрей!

«Головная ячейка представления скобочного терма может быть прокси, то есть 
ссылкой на окончательное представление или снова на прокси.»
«Одновременно спрямлять ссылки.»

Получаем лес непересекающихся множеств:

https://ru.wikipedia.org/wiki/Лес_непересекающихся_множеств

У этого метода самая лучшая временна́я сложность после константы — обратная 
функция Аккермана. Недостаток — требуется дополнительное поле ранга для выбора 
чего чему присваивать. Но ранг вроде тоже небольшой (в книжке Кормена, 
Лейзерсона и др. вроде про это есть), скорее всего байта хватит.

 

Я не вижу смысла делать операцию объединения множеств, представленных таким 
"лесом", для которой в этой статье обсуждают сложность и нужен ранг. Каждая 
ссылка на прокси, спрямляются один раз в жизни, когда по ней произойдет доступ, 
проходом от прокси к реальному представлению. И прокси надо сразу устанавливать 
на представление терма. Я зря написал, что прокси может ссылаться на прокси. 
Это я недодумал. 

 

Других операций над прокси не выполняется. Тут вроде бы нечего оптимизировать.

 

Всего наилучшего,

Андрей

 

 С уважением,

Александр Коновалов 

 

From: Andrei Klimov andrei_AT_klimov.net mailto:refal@botik.ru> > 
Sent: Wednesday, February 13, 2019 2:11 PM
To: refal@botik.ru <http://ik.ru> 
Subject: Re: Коллапсируюшее представление данных

 

Александр, еще раз добрый день!

 

Я понял, о чем вы писали и зачем требуется отношение порядка. Объясню своими 
словами на подвешенных скобках.

 

Пусть (eX) и (eY) входят в два выражения e1(eX)e2 и e3(eY)e4, и при их 
сравнении выяснилось, что (eX) = (eY).

И пусть на представления (eX) и (eY) есть еще ссылки из других выражений.

Тогда замена ссылки на (eX) в первом выражении на ссылку на (eY) не освобождает 
память представления (eX).

И наоборот, замена ссылки на (eY) во втором на ссылку на (eX) не освобождает 
память представления (eY).

Более того, теряется информация про равенство (eX), или соответственно (eY), 
равным термам в других выражениях.

 

Хотелось бы, чтобы был разумный способ выбрать, что на что заменять, чтобы 
какое-то из представлений равных термов лидировало и затягивало бы в себя 
ссылки с других.

Например, в реализации со счетчиками ссылок на скобочный терм, можно переносить 
на представление с большим счетчиком.

А если есть отношение порядка между представлениями, то можно выбирать 
наименьшее.

Если сборка мусора не меняет расположение представлений в памяти (что, как 
правило, имеет место быть), то подходящий порядок задают адреса.

Но все равно процесс "затягивания" ссылок на самое "тяжелое" представление 
будет медленным и плохо предсказуемым.

 

Чтобы не терять информацию об уже обнаруженных равенствах термов, лучший (как 
мне помнится) вариант, который был придуман такой:

Головная ячейка представления скобочного терма может быть прокси, то есть 
ссылкой на окончательное представление или снова на прокси.

Тогда при выяснении равенства (eX) и (eY) в вышеприведенном примере головная 
ячейка, скажем, (eY) становится прокси, ссылающимся на головную ячейку (eX). 
Подмена ссылки в выражении тоже делается.

 

Теперь при каждом вхождении в скобки нужно проверять, не на прокси ли мы 
попали, и, если да, идти дальше. Одновременно спрямлять ссылки.

 

Вот такая сложность картины, плюс ее непредсказуемость для Рефал-программиста, 
и привели к тому, что эти идеи остались в истории.

Теперь я вспомнил, что отсутствие "идеальных" решений и есть главная причина, 
из-за которой идея не пошла в массы = в реализации Рефала.

Спасибо, вот сейчас мы нечаянно на них вышли и запротоколировали.

Может, где-то когда-то кому-то пригодится.

 

И по-прежнему, интересно узнать, использовалось ли такое коллапсирование или 
обсуждавшаяся табуляция в каких-нибудь системах.

Если кто наткнется или уже знает, напишите, пожалуйста.

 

Всего наилучшего,

Андрей

 

On Wed, Feb 13, 2019 at 1:08 PM Andrei Klimov andrei.klimov_AT_gmail.com 
<http://andrei.klimov_AT_gmail.com>  mailto:refal@botik.ru> > 
wrote:

Александр, тогда я видимо совсем вас не понял – ни псевдокод, ни объяснение 
словами в предыдущем письме:

 

ср, 13 февр. 2019 г., 0:18 Александр Коновалов a.v.konovalov87_AT_mail.ru 
<http://a.v.konovalov87_AT_mail.ru>  mailto:refal@botik.ru> &

Re: Коллапсируюшее представление данных

[Andrei Klimov andrei_AT_klimov . net]

On Wed, Feb 13, 2019 at 2:42 PM Александр Коновалов
a.v.konovalov87_AT_mail.ru  wrote:

> Андрей!
>
>
> *«Головная ячейка представления скобочного терма может быть прокси,
> то есть ссылкой на окончательное представление или снова
> на прокси.»«Одновременно спрямлять ссылки.»*
>
> Получаем лес непересекающихся множеств:
>
> https://ru.wikipedia.org/wiki/Лес_непересекающихся_множеств
>
> У этого метода самая лучшая временна́я сложность после константы —
> обратная функция Аккермана. Недостаток — требуется дополнительное поле
> ранга для выбора чего чему присваивать. Но ранг вроде тоже небольшой
> (в книжке Кормена, Лейзерсона и др. вроде про это есть), скорее всего байта
> хватит.
>

Я не вижу смысла делать операцию объединения множеств, представленных таким
"лесом", для которой в этой статье обсуждают сложность и нужен ранг. Каждая
ссылка на прокси, спрямляются один раз в жизни, когда по ней произойдет
доступ, проходом от прокси к реальному представлению. И прокси надо сразу
устанавливать на представление терма. Я зря написал, что прокси может
ссылаться на прокси. Это я недодумал.

Других операций над прокси не выполняется. Тут вроде бы нечего
оптимизировать.

Всего наилучшего,
Андрей


>  С уважением,
>
> Александр Коновалов
>
>
>
> *From:* Andrei Klimov andrei_AT_klimov.net 
> *Sent:* Wednesday, February 13, 2019 2:11 PM
> *To:* refal@botik.ru
> *Subject:* Re: Коллапсируюшее представление данных
>
>
>
> Александр, еще раз добрый день!
>
>
>
> Я понял, о чем вы писали и зачем требуется отношение порядка. Объясню
> своими словами на подвешенных скобках.
>
>
>
> Пусть (eX) и (eY) входят в два выражения e1(eX)e2 и e3(eY)e4, и при их
> сравнении выяснилось, что (eX) = (eY).
>
> И пусть на представления (eX) и (eY) есть еще ссылки из других выражений.
>
> Тогда замена ссылки на (eX) в первом выражении на ссылку на (eY) не
> освобождает память представления (eX).
>
> И наоборот, замена ссылки на (eY) во втором на ссылку на (eX) не
> освобождает память представления (eY).
>
> Более того, теряется информация про равенство (eX), или соответственно
> (eY), равным термам в других выражениях.
>
>
>
> Хотелось бы, чтобы был разумный способ выбрать, что на что заменять, чтобы
> какое-то из представлений равных термов лидировало и затягивало бы в себя
> ссылки с других.
>
> Например, в реализации со счетчиками ссылок на скобочный терм, можно
> переносить на представление с большим счетчиком.
>
> А если есть отношение порядка между представлениями, то можно выбирать
> наименьшее.
>
> Если сборка мусора не меняет расположение представлений в памяти (что, как
> правило, имеет место быть), то подходящий порядок задают адреса.
>
> Но все равно процесс "затягивания" ссылок на самое "тяжелое" представление
> будет медленным и плохо предсказуемым.
>
>
>
> Чтобы не терять информацию об уже обнаруженных равенствах термов, лучший
> (как мне помнится) вариант, который был придуман такой:
>
> Головная ячейка представления скобочного терма может быть прокси, то есть
> ссылкой на окончательное представление или снова на прокси.
>
> Тогда при выяснении равенства (eX) и (eY) в вышеприведенном примере
> головная ячейка, скажем, (eY) становится прокси, ссылающимся на головную
> ячейку (eX). Подмена ссылки в выражении тоже делается.
>
>
>
> Теперь при каждом вхождении в скобки нужно проверять, не на прокси ли мы
> попали, и, если да, идти дальше. Одновременно спрямлять ссылки.
>
>
>
> Вот такая сложность картины, плюс ее непредсказуемость для
> Рефал-программиста, и привели к тому, что эти идеи остались в истории.
>
> Теперь я вспомнил, что отсутствие "идеальных" решений и есть главная
> причина, из-за которой идея не пошла в массы = в реализации Рефала.
>
> Спасибо, вот сейчас мы нечаянно на них вышли и запротоколировали.
>
> Может, где-то когда-то кому-то пригодится.
>
>
>
> И по-прежнему, интересно узнать, использовалось ли такое коллапсирование
> или обсуждавшаяся табуляция в каких-нибудь системах.
>
> Если кто наткнется или уже знает, напишите, пожалуйста.
>
>
>
> Всего наилучшего,
>
> Андрей
>
>
>
> On Wed, Feb 13, 2019 at 1:08 PM Andrei Klimov andrei.klimov_AT_gmail.com <
> refal@botik.ru> wrote:
>
> Александр, тогда я видимо совсем вас не понял – ни псевдокод, ни
> объяснение словами в предыдущем письме:
>
>
>
> ср, 13 февр. 2019 г., 0:18 Александр Коновалов a.v.konovalov87_AT_mail.ru
> :
> Добрый вечер, Сергей!
> > 2.  Наконец, если нам пришлось делать длинное сравнение и в конце
> выяснилось, что термы таки равны, то мы делаем "коллапсирующие джунгли" --
> делаем присваивание: p2 = p1, L2=L1

RE: Коллапсируюшее представление данных

[Александр Коновалов a . v . konovalov87_AT_mail . ru]

Добрый день, Сергей!

Индексация этого представления, как сказано, имеет сложность log(P, N), где 
P=32 — местность дерева. Операции очереди (вставка/удаление в начале/конце) — 
P×log(P, N), выбор префикса или суффикса — тоже P×log(P, N). Операция 
обновления i-го элемента (построения вектора с новым i-м элементом) тоже 
требует P×log(P, N) копирований.

Если узлам разрешить быть заполненными не полностью, как в Б-деревьях (от P/2 
до P), то можно обеспечить сравнительно эффективную конкатенацию двух векторов. 
Для этого потребуется выполнить P×|log(P, N1) − log(P, N2)| копирований, где 
N1, N2 — длины векторов. Но вот индексация из-за этого просядет от log(P, N) до 
P×log(P, N) или log(2, P)×log(P, N) = log(2, N), если использовать метод 
деления пополам.

Но для Рефала индексация нужна редко (открытые переменные можно реализовать 
последовательным удлинением на 1), а вот конкатенация — базовая операция. Так 
что такое дерево с неполными узлами тоже можно рассматривать как возможный 
способ представления выражений.

Вообще, есть похожая структура данных — rope. Это строка, построенная поверх 
двоичного дерева. Описанное выше можно рассматривать как вариант rope, но с 
основой Б-дерева.

 

С уважением,
Александр Коновалов

 

From: Sergei Romanenko sergei.romanenko_AT_supercompilers.ru  
Sent: Wednesday, February 13, 2019 1:47 PM
To: Refal Botik 
Subject: Re: Коллапсируюшее представление данных

 

Имеет смысл ознакомиться с тем, как реализованы/представлены "немутабельные" 
векторы в библиотеке Скалы:

 

Scala High Performance Programming
Vincent Theron, Michael Diamant
May 2016

 

https://www.packtpub.com/application-development/scala-high-performance-programming

 

Not only does Vector yield significantly better performance, it delivers the 
same throughput regardless of the size of the rollup. As a general rule, it is 
better to use Vector as a default implementation for immutable indexed 
sequences. Vector effectively provides constant time complexity not only for 
element random access but also for head and tail operations, as well as to 
append and prepend elements to an existing Vector.

 

The implementation of Vector is a tree structure of parity 32. Each node is 
implemented as an array of size 32, and it can store either up to 32 references 
to child nodes or up to 32 values. This 32-ary tree structure explains why the 
complexity of Vector is “effectively constant” instead of “constant”. The real 
complexity of the implementation is log(32, N), where N is the size of the 
vector. This is considered close enough to actual constant time. This 
collection is a good choice to store very large sequences because the memory is 
allocated in chunks of 32 elements. These chunks are not preallocated for all 
levels of the tree, but only allocated as needed.

 

Until Scala 2.10, one downside of Vector as compared to List was the lack of 
pattern matching support. This is now fixed and you can pattern-match an 
instance of Vector in the same way you pattern match a List.

 

СР

 

RE: Коллапсируюшее представление данных

[Александр Коновалов a . v . konovalov87_AT_mail . ru]

Андрей!

«Головная ячейка представления скобочного терма может быть прокси, то есть 
ссылкой на окончательное представление или снова на прокси.»
«Одновременно спрямлять ссылки.»

Получаем лес непересекающихся множеств:

https://ru.wikipedia.org/wiki/Лес_непересекающихся_множеств

У этого метода самая лучшая временна́я сложность после константы — обратная 
функция Аккермана. Недостаток — требуется дополнительное поле ранга для выбора 
чего чему присваивать. Но ранг вроде тоже небольшой (в книжке Кормена, 
Лейзерсона и др. вроде про это есть), скорее всего байта хватит.

 

С уважением,
Александр Коновалов 

 

From: Andrei Klimov andrei_AT_klimov.net  
Sent: Wednesday, February 13, 2019 2:11 PM
To: refal@botik.ru
Subject: Re: Коллапсируюшее представление данных

 

Александр, еще раз добрый день!

 

Я понял, о чем вы писали и зачем требуется отношение порядка. Объясню своими 
словами на подвешенных скобках.

 

Пусть (eX) и (eY) входят в два выражения e1(eX)e2 и e3(eY)e4, и при их 
сравнении выяснилось, что (eX) = (eY).

И пусть на представления (eX) и (eY) есть еще ссылки из других выражений.

Тогда замена ссылки на (eX) в первом выражении на ссылку на (eY) не освобождает 
память представления (eX).

И наоборот, замена ссылки на (eY) во втором на ссылку на (eX) не освобождает 
память представления (eY).

Более того, теряется информация про равенство (eX), или соответственно (eY), 
равным термам в других выражениях.

 

Хотелось бы, чтобы был разумный способ выбрать, что на что заменять, чтобы 
какое-то из представлений равных термов лидировало и затягивало бы в себя 
ссылки с других.

Например, в реализации со счетчиками ссылок на скобочный терм, можно переносить 
на представление с большим счетчиком.

А если есть отношение порядка между представлениями, то можно выбирать 
наименьшее.

Если сборка мусора не меняет расположение представлений в памяти (что, как 
правило, имеет место быть), то подходящий порядок задают адреса.

Но все равно процесс "затягивания" ссылок на самое "тяжелое" представление 
будет медленным и плохо предсказуемым.

 

Чтобы не терять информацию об уже обнаруженных равенствах термов, лучший (как 
мне помнится) вариант, который был придуман такой:

Головная ячейка представления скобочного терма может быть прокси, то есть 
ссылкой на окончательное представление или снова на прокси.

Тогда при выяснении равенства (eX) и (eY) в вышеприведенном примере головная 
ячейка, скажем, (eY) становится прокси, ссылающимся на головную ячейку (eX). 
Подмена ссылки в выражении тоже делается.

 

Теперь при каждом вхождении в скобки нужно проверять, не на прокси ли мы 
попали, и, если да, идти дальше. Одновременно спрямлять ссылки.

 

Вот такая сложность картины, плюс ее непредсказуемость для Рефал-программиста, 
и привели к тому, что эти идеи остались в истории.

Теперь я вспомнил, что отсутствие "идеальных" решений и есть главная причина, 
из-за которой идея не пошла в массы = в реализации Рефала.

Спасибо, вот сейчас мы нечаянно на них вышли и запротоколировали.

Может, где-то когда-то кому-то пригодится.

 

И по-прежнему, интересно узнать, использовалось ли такое коллапсирование или 
обсуждавшаяся табуляция в каких-нибудь системах.

Если кто наткнется или уже знает, напишите, пожалуйста.

 

Всего наилучшего,

Андрей

 

On Wed, Feb 13, 2019 at 1:08 PM Andrei Klimov andrei.klimov_AT_gmail.com 
<http://andrei.klimov_AT_gmail.com>  mailto:refal@botik.ru> > 
wrote:

Александр, тогда я видимо совсем вас не понял – ни псевдокод, ни объяснение 
словами в предыдущем письме:

 

ср, 13 февр. 2019 г., 0:18 Александр Коновалов a.v.konovalov87_AT_mail.ru 
<http://a.v.konovalov87_AT_mail.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>

Заметим, что это рассуждение не зависит от того, массивное представление 
выражений ил

Re: Коллапсируюшее представление данных

[Andrei Klimov andrei_AT_klimov . net]

Александр, да, теперь я понял.
Получилось так, что мы писали навстречу друг другу.
Я только что послал письмо, где обрисовал картину более подробно с
возможными решениями, но, к сожалению, неидеальными.
Андрей

On Wed, Feb 13, 2019 at 2:10 PM Александр Коновалов
a.v.konovalov87_AT_mail.ru  wrote:

> Андрей!
>
> Описываю, что я имел ввиду, на Рефале. Будем предполагать, что в этой
> реализации используются подвешенные скобки.
>
> F {
>   = ;
> }
>
> G {
>   t.1 t.2 = ;
> }
>
> 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 
> *Sent:* Wednesday, February 13, 2019 1:08 PM
> *To:* refal@botik.ru
> *Subject:* Re: Коллапсируюшее представление данных
>
>
>
> Александр, тогда я видимо совсем вас не понял – ни псевдокод, ни
> объяснение словами в предыдущем письме:
>
>
>
> ср, 13 февр. 2019 г., 0:18 Александр Коновалов a.v.konovalov87_AT_mail.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  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. Т.е. память не освободится. Просто переменные поменяются
> ссылками. Поэтому и нужно дополнительное ранжирование. Вроде вот этого:
>
> *«То есть в ящиках поддерживаются индексы в некотором отношении линейного

Re: Коллапсируюшее представление данных

[Andrei Klimov andrei_AT_klimov . net]

Александр, еще раз добрый день!

Я понял, о чем вы писали и зачем требуется отношение порядка. Объясню
своими словами на подвешенных скобках.

Пусть (eX) и (eY) входят в два выражения e1(eX)e2 и e3(eY)e4, и при их
сравнении выяснилось, что (eX) = (eY).
И пусть на представления (eX) и (eY) есть еще ссылки из других выражений.
Тогда замена ссылки на (eX) в первом выражении на ссылку на (eY) не
освобождает память представления (eX).
И наоборот, замена ссылки на (eY) во втором на ссылку на (eX) не
освобождает память представления (eY).
Более того, теряется информация про равенство (eX), или соответственно
(eY), равным термам в других выражениях.

Хотелось бы, чтобы был разумный способ выбрать, что на что заменять, чтобы
какое-то из представлений равных термов лидировало и затягивало бы в себя
ссылки с других.
Например, в реализации со счетчиками ссылок на скобочный терм, можно
переносить на представление с большим счетчиком.
А если есть отношение порядка между представлениями, то можно выбирать
наименьшее.
Если сборка мусора не меняет расположение представлений в памяти (что, как
правило, имеет место быть), то подходящий порядок задают адреса.
Но все равно процесс "затягивания" ссылок на самое "тяжелое" представление
будет медленным и плохо предсказуемым.

Чтобы не терять информацию об уже обнаруженных равенствах термов, лучший
(как мне помнится) вариант, который был придуман такой:
Головная ячейка представления скобочного терма может быть прокси, то есть
ссылкой на окончательное представление или снова на прокси.
Тогда при выяснении равенства (eX) и (eY) в вышеприведенном примере
головная ячейка, скажем, (eY) становится прокси, ссылающимся на головную
ячейку (eX). Подмена ссылки в выражении тоже делается.

Теперь при каждом вхождении в скобки нужно проверять, не на прокси ли мы
попали, и, если да, идти дальше. Одновременно спрямлять ссылки.

Вот такая сложность картины, плюс ее непредсказуемость для
Рефал-программиста, и привели к тому, что эти идеи остались в истории.
Теперь я вспомнил, что отсутствие "идеальных" решений и есть главная
причина, из-за которой идея не пошла в массы = в реализации Рефала.
Спасибо, вот сейчас мы нечаянно на них вышли и запротоколировали.
Может, где-то когда-то кому-то пригодится.

И по-прежнему, интересно узнать, использовалось ли такое коллапсирование
или обсуждавшаяся табуляция в каких-нибудь системах.
Если кто наткнется или уже знает, напишите, пожалуйста.

Всего наилучшего,
Андрей

On Wed, Feb 13, 2019 at 1:08 PM Andrei Klimov andrei.klimov_AT_gmail.com <
refal@botik.ru> wrote:

> Александр, тогда я видимо совсем вас не понял – ни псевдокод, ни
> объяснение словами в предыдущем письме:
>
> ср, 13 февр. 2019 г., 0:18 Александр Коновалов a.v.konovalov87_AT_mail.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  wrote:
>
>> Доброе утро, Андрей!
>>
>> Спасибо за интересное письмо!
>>
>> *«Память освободится, но отдельно в первой паре и во второй, а чт

RE: Коллапсируюшее представление данных

[Александр Коновалов a . v . konovalov87_AT_mail . ru]

Андрей!

Описываю, что я имел ввиду, на Рефале. Будем предполагать, что в этой 
реализации используются подвешенные скобки.

F {
  = ;
}

G {
  t.1 t.2 = ;
}

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  
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>  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>  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) для „коллапсирования рефал-выражений в ящики“ (выдаётся ссылка на 
тот же ящик, если уже формировался ящик с таким же содержимым) и табуляции их 
отношения порядка.»

Когда-то я подумывал о похожей системе для Рефала с массивным представлением. 
Поддерживается глобальное хеш-множество для всех скобочных термов в поле 
зрения, и, когда надо построить новый ск

Re: Коллапсируюшее представление данных

[Sergei Romanenko sergei . romanenko_AT_supercompilers . ru]

Имеет смысл ознакомиться с тем, как реализованы/представлены
"немутабельные" векторы в библиотеке Скалы:

*Scala High Performance Programming*
Vincent Theron, Michael Diamant
May 2016

https://www.packtpub.com/application-development/scala-high-performance-programming

Not only does Vector yield significantly better performance, it delivers
the same throughput regardless of the size of the rollup. As a general
rule, it is better to use Vector as a default implementation for immutable
indexed sequences. Vector effectively provides constant time complexity not
only for element random access but also for head and tail operations, as
well as to append and prepend elements to an existing Vector.

The implementation of Vector is a tree structure of parity 32. Each node is
implemented as an array of size 32, and it can store either up to 32
references to child nodes or up to 32 values. This 32-ary tree structure
explains why the complexity of Vector is “effectively constant” instead of
“constant”. The real complexity of the implementation is log(32, N), where
N is the size of the vector. This is considered close enough to actual
constant time. This collection is a good choice to store very large
sequences because the memory is allocated in chunks of 32 elements. These
chunks are not preallocated for all levels of the tree, but only allocated
as needed.

Until Scala 2.10, one downside of Vector as compared to List was the lack
of pattern matching support. This is now fixed and you can pattern-match an
instance of Vector in the same way you pattern match a List.

СР

Re: Коллапсируюшее представление данных

[Andrei Klimov andrei . klimov_AT_gmail . com]

Александр, тогда я видимо совсем вас не понял – ни псевдокод, ни объяснение
словами в предыдущем письме:

ср, 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  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
> ), поскольку они
> образуют группу. Это значит, что если известны хеши двух строк, хеш
> конкатенации вычисляется за константу. Если известен хеш строки и хеш её
> префикса, то хеш суффикса тоже вычисляется за константу (для известного
> хеша суффикса — аналогично). Вообще, я ещё летом поминал в рассылке
> кольцевые хеши.
>
> Но это были пустые размышления, поскольку тогда у меня не было своей
> нормальной реализации с векторами (нет и сейчас), а также понимал, что
> оверхед на всё это будет больше, чем потенциальная выгода.
>

Да, интересная идея с кольцевыми хешами (хотя не могу сказать, что я ее
полностью ухватил), но, действительно, неясно, есть ли овчинка выделки и не
будет ли только хуже. Всё зависит от задач, и как универсальное
представление вряд ли годится. Пример класса задач, где, в принципе, могла
бы быть польза – это упо

Re: Коллапсируюшее представление данных

[Andrei Klimov andrei_AT_klimov . net]

On Wed, Feb 13, 2019 at 11:04 AM Andrei Klimov  wrote:

> Я сменил сабж, так как тема шире, чем лишь для Рефала Плюс.
>
> ср, 13 февр. 2019 г., 0:18 Александр Коновалов a.v.konovalov87_AT_mail.ru
> :
>
>> Добрый вечер, Сергей!
>>
>> > 2.  Наконец, если нам пришлось делать длинное сравнение и в конце
>> выяснилось, что термы таки равны, то мы делаем "коллапсирующие джунгли" --
>> делаем присваивание: p2 = p1, L2=L1 (второе лишнее, но пусть будет).  Тут и
>> память освободилась и следующий раз сравнение на равенство пройдет быстрее
>> ;-)
>>
>> А если у нас в поле зрения есть несколько экземпляров одинаковых пар (p1,
>> L1), (p2, L2). В первый раз сравниваются пары в порядке (p1, L1) == (p2,
>> L2) и мы присвоили p1 := p2. В другой раз (другие экземпляры) сравнились в
>> порядке (p2, L2) == (p1, L1) и коллапсировались уже p2 := p1. Тогда память
>> не освободится. Такое может быть?
>>
>
> Отвечу за Сергея:😊
>
> Память освободится, но отдельно в первой паре и во второй, а чтобы остался
> один экземпляр из четырёх, нужно ещё одно сравнение. То есть, для склейки N
> (ещё несклеенных) термов нужно как минимум N-1 сравнений.
>
> Сергей, а я не помню, чтобы была такая реализация. Мне кажется, много раз
> обсуждали, что интересно было бы попробовать и измерить полезность на
> задачах типа компьютерной алгебры, но так и осталось в теории. Или кто-то
> сделал?
>
> Чтобы экономить память (и надеялись - и время), для системы Сантра Игоря
> Шенкова я ещё в 80-е годы разработал библиотечку ROTAB (References for
> Order Tabulation) для "коллапсирования рефал-выражений в ящики" (выдаётся
> ссылка на тот же ящик, если уже формировался ящик с таким же содержимым) и
> табуляции их отношения порядка. То есть в ящиках поддерживаются индексы в
> некотором отношении линейного порядка для последующего быстрого сравнения
> (для сортировки термов в представлении полиномов).
>
> ROTAB была реализована на Рефале-2 как прототип предполагавшейся
> реализации на PLI (на ЕС ЭВМ = IBM/370) или потом на С. Но за 30 лет у меня
> так и не дошли руки (самому или попросить кого-нибудь из молодежи)
> реализовать на низком уровне, а Игорь так и пользуется прототипом и сам
> перенёс ROTAB с Рефала-2 на Рефал-6.
>
> К сожалению, потенциальная польза от ROTAB  так и не исследована, и в
> Сантре неизвестная потеря памяти и времени заменена на линейное замедление
> - весьма большое из-за не эффективности прототипа реализации на Рефале.
>
> Кстати, сейчас на ящики в ROTAB не распространяется сборка мусора (которая
> есть в реализациях Рефала-2, но нет в основной реализации Рефала-6), а
> предполагалось сделать её в низкоуровневого реализации ROTAB.
>

Если кто заинтересуется, пользовательский интерфейс к ROTAB был описан в
препринте на стр. 29–35:

   - Анд.В. Климов, С.А. Романенко. Система программирования Рефал-2 для ЕС
   ЭВМ. Описание библиотеки функций. М.: ИПМ им. М.В. Келдыша АН СССР, 1986,
   препринт № 200. - 38 с. PDF
   

DJVU
   


Вообще интересно, в каких-нибудь системах компьютерной алгебры и прочей
> символьной обработки используются ли подобные механизмы? Они могли быть
> опробованы в стародавние времена, когда памяти было мало, а, подозреваю, в
> нынешнее время никто не стал бы возиться с исследованиями такого вопроса.
> Но все-таки, может, были эксперименты? Никто не знает?
>
> Андрей
>

RE: Коллапсируюшее представление данных

[Александр Коновалов a . v . konovalov87_AT_mail . ru]

Доброе утро, Андрей!

Спасибо за интересное письмо!

«Память освободится, но отдельно в первой паре и во второй, а чтобы остался 
один экземпляр из четырёх, нужно ещё одно сравнение.»

Я имел ввиду другое. Поясню псевдокодом:

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  ), 
поскольку они образуют группу. Это значит, что если известны хеши двух строк, 
хеш конкатенации вычисляется за константу. Если известен хеш строки и хеш её 
префикса, то хеш суффикса тоже вычисляется за константу (для известного хеша 
суффикса — аналогично). Вообще, я ещё летом поминал в рассылке кольцевые хеши.

Но это были пустые размышления, поскольку тогда у меня не было своей нормальной 
реализации с векторами (нет и сейчас), а также понимал, что оверхед на всё это 
будет больше, чем потенциальная выгода.

 

Спасибо,
Александр Коновалов

 

From: Andrei Klimov andrei_AT_klimov.net  
Sent: Wednesday, February 13, 2019 11:04 AM
To: refal@botik.ru
Subject: Коллапсируюшее представление данных

 

Я сменил сабж, так как тема шире, чем лишь для Рефала Плюс. 

 

ср, 13 февр. 2019 г., 0:18 Александр Коновалов a.v.konovalov87_AT_mail.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. Тогда память не освободится. 
Такое может быть?

 

Отвечу за Сергея:😊

 

Память освободится, но отдельно в первой паре и во второй, а чтобы остался один 
экземпляр из четырёх, нужно ещё одно сравнение. То есть, для склейки N (ещё 
несклеенных) термов нужно как минимум N-1 сравнений. 

 

Сергей, а я не помню, чтобы была такая реализация. Мне кажется, много раз 
обсуждали, что интересно было бы попробовать и измерить полезность на задачах 
типа компьютерной алгебры, но так и осталось в теории. Или кто-то сделал? 

 

Чтобы экономить память (и надеялись - и время), для системы Сантра Игоря 
Шенкова я ещё в 80-е годы разработал библиотечку ROTAB (References for Order 
Tabulation) для "коллапсирования рефал-выражений в ящики" (выдаётся ссылка на 
тот же ящик, если уже формировался ящик с таким же содержимым) и табуляции их 
отношения порядка. То есть в ящиках поддерживаются индексы в некотором 
отношении линейного порядка для последующего быстрого сравнения (для сортировки 
термов в представлении полиномов). 

 

ROTAB была реализована на Рефале-2 как прототип предполагавшейся реализации на 
PLI (на ЕС ЭВМ = IBM/370) или потом на С. Но за 30 лет у меня так и не дошли 
руки (самому или попросить кого-нибудь из молодежи) реализовать на низком 
уровне, а Игорь так и пользуется прототипом и сам перенёс ROTAB с Рефала-2 на 
Рефал-6.

 

К сожалению, потенциальная польза от ROTAB  так и не исследована, и в Сантре 
неизвестная потеря памяти и времени заменена на линейное замедление - весьма 
большое из-за не эффективности прототипа реализации на Рефале. 

 

Кстати, сейчас на ящики в ROTAB не распространяется сборка мусора (которая есть 
в реализациях Рефала-2, но нет в основной реализации Рефала-6),