On Wed, Feb 13, 2019 at 11:04 AM Andrei Klimov <and...@klimov.net> wrote:
> Я сменил сабж, так как тема шире, чем лишь для Рефала Плюс. > > ср, 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. Тогда память >> не освободится. Такое может быть? >> > > Отвечу за Сергея:😊 > > Память освободится, но отдельно в первой паре и во второй, а чтобы остался > один экземпляр из четырёх, нужно ещё одно сравнение. То есть, для склейки 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 <https://pat.keldysh.ru/~roman/doc/1986-Klimov_Romanenko--Refal-2__Opisanie_biblioteki_funkcij.pdf> DJVU <https://pat.keldysh.ru/~roman/doc/1986-Klimov_Romanenko--Refal-2__Opisanie_biblioteki_funkcij.djvu> Вообще интересно, в каких-нибудь системах компьютерной алгебры и прочей > символьной обработки используются ли подобные механизмы? Они могли быть > опробованы в стародавние времена, когда памяти было мало, а, подозреваю, в > нынешнее время никто не стал бы возиться с исследованиями такого вопроса. > Но все-таки, может, были эксперименты? Никто не знает? > > Андрей >
