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 >>> <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 и x >>> 3.p ≡ x4.p ≡ p1. Т.е. память не освободится. Просто переменные >>> поменяются ссылками. Поэтому и нужно дополнительное ранжирование. Вроде вот >>> этого: >>> >>> *«То есть в ящиках поддерживаются индексы в некотором отношении >>> линейного порядка для последующего быстрого сравнения»* >>> >>> Либо можно сравнивать указатели как числа и присваивать большему меньшее. >>> >> >> Я не понял, зачем может понадобится отношение порядка для коллапсирования. >> >> >>> *«Чтобы экономить память (и надеялись — и время), для системы Сантра >>> Игоря Шенкова я ещё в 80-е годы разработал библиотечку ROTAB (References >>> for Order Tabulation) для „коллапсирования рефал-выражений в ящики“ >>> (выдаётся ссылка на тот же ящик, если уже формировался ящик с таким же >>> содержимым) и табуляции их отношения порядка.»* >>> >>> Когда-то я подумывал о похожей системе для Рефала с массивным >>> представлением. Поддерживается глобальное хеш-множество для всех скобочных >>> термов в поле зрения, и, когда надо построить новый скобочный терм, вместо >>> нового выбирается уже существующий. Нашёл, что для этой цели нужно >>> использовать кольцевые хеши (rolling hash >>> <https://www.google.ru/search?q=rolling+hash&tbm=isch>), поскольку они >>> образуют группу. Это значит, что если известны хеши двух строк, хеш >>> конкатенации вычисляется за константу. Если известен хеш строки и хеш её >>> префикса, то хеш суффикса тоже вычисляется за константу (для известного >>> хеша суффикса — аналогично). Вообще, я ещё летом поминал в рассылке >>> кольцевые хеши. >>> >>> Но это были пустые размышления, поскольку тогда у меня не было своей >>> нормальной реализации с векторами (нет и сейчас), а также понимал, что >>> оверхед на всё это будет больше, чем потенциальная выгода. >>> >> >> Да, интересная идея с кольцевыми хешами (хотя не могу сказать, что я ее >> полностью ухватил), но, действительно, неясно, есть ли овчинка выделки и не >> будет ли только хуже. Всё зависит от задач, и как универсальное >> представление вряд ли годится. Пример класса задач, где, в принципе, могла >> бы быть польза – это упомянутая компьютерная алгебра. Поэтому я думал >> поискать по литературе, не использовались ли коллапсирующие (склеивающие >> часть подвыражений) или табулируемые (склеивающие все равные подтермы) в >> каких-нибудь системах компьютерной алгебры. Но так руки не дошли. >> >> Всего наилучшего, >> Андрей >> >
