Доброе утро, Антон! «Рекурсивный вызов Reverse хвостовой или нет?»
В конце нулевых Сергей Скоробогатов разрабатывал т.н. векторно-списковое представление объектных выражений — массивное с отложенной конкатенацией. В нём этот вызов Reverse будет хвостовым и функция будет выполняться за линейное время. К сожалению, публикаций на эту тему нет, есть только черновик статьи, который без разрешения Сергея я выслать не могу. Я исследовал это представление на курсовом проекте — студентка написала соответствующую реализацию Простого Рефала. При достаточном объёме кучи векторно-списковое представление оказывалось быстрее обычного спискового. С уважением, Александр Коновалов From: Anton Orlov orlovan_AT_gmail.com <refal@botik.ru> Sent: Tuesday, February 12, 2019 9:20 AM To: refal@botik.ru Subject: Re: Рефал Плюс – Was: Синтаксический анализ в Рефале On Mon, Feb 11, 2019 at 4:16 PM Yuri Klimov yuri_AT_klimov.net < <mailto:refal@botik.ru> refal@botik.ru> wrote: Добрый вечер! Антон, поправь меня, если я ошибусь. 2. Антон Орлов ответил на вопросы Аркадия про другую – вторую реализацию. Из письма Антона выписываю, как я понял: ... 3. Реализация на JVM в среде Eclipse Антона Орлова и Юры Климова: ... Это одна и та же реализация. У нее один компилятор, написанный на Рефале+. Отличаются только backend'ом: кодогенератом с абстрактного императивного представления и, разумеется, runtime'ом. Причем есть генерация как Java byte code, так и просто в Java. А также есть backend'ы в C++ и Т-систему. Она доступна по ссылкам с http://rfp.botik.ru/. Для истории, эта версия начиналась с рантайма на С++, который Андрей Слепухин начал делать в 2000-2001 годах. С конца 2002 года у меня есть ChangeLog (наверное тогда исходники переехали из RCS в CVS. Думаю, более раннюю историю тоже можно найти, но это надо копаться), и оттуда видно, что в 2003 шла активная работа над рантаймом (в основном Андрей), стандартной библиотекой (в основном Люба Позлевич) и компилятором (в основном я), и в первой половине 2004 компилятор (написанный на Рефале+) забутстрапился, и ещё через какое-то время предыдущей реализацией Рефала+ (Гурина-Романенко) мы пользоваться совсем перестали. В среде Eclipse дополнительно к этому компилятору был реализован парсер во AST для Eclipse, которое используется в плагине (для подсветки, навигации и других фич IDE). А для компиляции в байт-код вызывается обычный компилятор, которому на вход подается сразу абстрактное рефальское представление, построенное из AST. См. схемки на странице http://wiki.botik.ru/Refaldevel/ . На счет деталей реализаций уже смутно помню, но на Яве так же были реализованы "дырки". Соответственно выражение - это объект класса Expr, который содержит массив термов и индексы начала и конца. Терм - любой объект (обертки для термов нет), например символ-число - объект класса BigInteger. Экспериментировали и с реализацией без "дырок" - лежит в отдельной ветке. Вроде хотели и чисто массивную реализацию попробовать (без обертки Expr), но уже забыл чем дело кончилось. Еще отличие runtime'а C++ от Java/JBC является то, что в Java/JBC не используется свой стек - используется явовский стек. А если я правильно помню (Антон, так?) в реализации C++ использовался батутный стек, чтобы исключить переполнение стека. Поэтому интерфейс между Рефалом и Java вышел проще, и он доступен программисту: для рефальских функций можно описывать явовские прототипы и вызывать их из Явы, и для явовских функций можно описывать рефальские прототипы и вызывать их из Рефала. В С++ сделан не совсем батут -- используется Сишный стек вызовов функций, но для аргументов и результатов функций сделан свой стек в куче (heap). За счёт этого становится просто сделать оптимизацию (подмену верхушки стека вызовов) для хвостовых вызовов, и для них стек не растёт. Но переполнение стека всё-таки возможно. Казалось бы, разница невелика -- кончится память в куче или же на стеке, однако на практике для серьёзных программ разница есть: нехватку памяти в куче обычно можно обработать, а вот переполнение стека скорее всего ведёт к segmentation fault. Кстати, это ещё один момент, где играет представление выражения -- из него следует, что именно считается хвостовым вызовом. Например: Reverse { = ; t.1 e.2 = <Reverse e.2> t.1; } Рекурсивный вызов Reverse хвостовой или нет? Если представление списковое, то очень легко делается реализация, где этот вызов хвостовой (и вообще можно вернуть результатное выражение с любым количеством невычисленных функций в любых местах -- потом посчитать их на батуте, или, например, быть ленивым и вообще не считать, пока не понадобятся). С обычным векторным представлением так просто не получится, и этот вызов не хвостовой (откуда и растёт $iter). Антон С уважением, Юрий Климов On Mon, 11 Feb 2019 at 23:46, Andrei Klimov andrei_AT_klimov.net < <mailto:refal@botik.ru> refal@botik.ru> wrote: Добрый вечер! Я занудно меняю сабж, приписывая "Рефал Плюс", а то тред "Синтаксический анализ в Рефале" уже перегружен и обсуждение ушло с основной темы. Архивируемая рассылка ценна тем, что потом в ней можно находить ценную информацию. Для этого треды должны быть короткими, а сабжи – называть основную тему. Пусть ответ Антона на вопросы Аркадия перейдет под этот сабж (внизу привожу его текст). Давайте проясним, сколько у нас реализаций Рефала Плюс, и, говоря он них, будем указывать, о какой речь, а то, мне кажется, уже начала возникать путаница. Эта переписка напомнила мне о трех реализациях: 1. Я писал в предыдущем письме про исходную реализацию на С от Рутена Гурина и Сергея Романенко, прошедшую потом через руки сотрудников ИПС и в конце концов – Андрея Слепухина. Я не заглядывал в ее внутренности, а только был ее пользователем, поэтому могу ошибаться, говоря о ее свойствах. То, что я наивно думал, я написал в предыдущем письме. Резюмирую здесь: * массивное представление * чанки памяти под выражения выделяются из памяти, захваченной при старте; кажется, там был параметр – сколько памяти взять * сборка мусора была изначально * это ее алгоритм разработал Сергей Абрамов со Светланой Трубициной? * дырки были добавлены потом (точно не знаю, кто именно их реализовывал) * есть параметр – размер дырок * язык реализации – С (не С++) * погружение в IDE: нет * годы разработки от первой до последней версий: ~1990 – ~2000 * хорошо бы для истории восстановить даты поточнее Авторы, я не проврался? 2. Антон Орлов ответил на вопросы Аркадия про другую – вторую реализацию. Из письма Антона выписываю, как я понял: * массивное представление * аллокатор по алгоритму близнецов, умеющий склеивать чанки при возврате памяти * сборки мусора нет, есть счетчики ссылок * начальные дырки есть по сущности аллокатора (до степени двойки) * язык реализации: С++ * погружение в IDE: нет ? * годы разработки: начало 2000 ? Авторы, пожалуйста, поправьте меня или добавьте интересную информацию. 3. Реализация на JVM в среде Eclipse Антона Орлова и Юры Климова: * массивное представление: * выражение = Java-массив из термов * терм = объект специального класса * символы обернуты в терм или унаследованы от терма ? * например, как реализован символ-число? * выражение в скобках – массив, обернутый в объект-терм, да? * вопрос: есть ли "лишний" ссылочный уровень для скобок или массив-содержимое является элементом объемлющего массива-выражения? * аллокатор выражения: JVM'овский new array * сборка мусора: JVM'овская * дырок нет * язык реализации: Java и Рефал; исполняется на JVM * погружение в IDE (подсветки, подсказки и т.п.): Eclipse * годы разработки: 2006-2008 ? * спонсор: ИПС им. А.К. Айламазяна РАН Антон и Юра, правильно выписаны характеристики? О других реализациях Рефала Плюс я не слышал (или забыл). Еще есть? *. Для информации приведу еще одну реализацию на JVM, но не Рефала Плюс, а Рефала-6. Поэтому обозначаю ее в этом списке как *, а не 4. Ее сделал Аркадий Климов (а я был в роли "мы пахали") задолго до реализации Антона и Юры. Она называлась RefalJ: * массивное представление: * выражение = Java-массив из термов * терм = любой объект – не массив * символы: String, числа и т.п. – непосредственные элементы массива-выражения * выражение в скобках – содержимое-массив является элементом объемлющего выражения-массива * то есть "лишней" косвенной адресации нет * аллокатор выражения: JVM'овский new array * сборка мусора: JVM'овская * дырок нет * язык реализации: Java и Рефал-6; исполняется на JVM * погружение в IDE: нет * год разработки: 2003 (первое полугодие) * спонсор: Авикомп Сервисез <http://avicomp.ru/> * Предполагалось использовать эту реализацию, расширяя структуры данных и входной язык, для "семантических технологий <http://avicomp.ru/services/semantic> ", которые разрабатывались группой под руководством Владимира Хорошевского. (Но как-то не получилось.) Аркадий, поправь меня, пожалуйста, если я в чем-то ошибся. Замечание про реализации 3 и * на JVM: При конкатенации выражений, даже при приписывании одного терма к выражению, происходит копирование массивов. Оно выполняется библиотечным методом java.lang.System.arraycopy(), который в JVM выполняется одной Intel'овской командой, а не циклом. Такая операция в современных процессорах имеет хорошую локальность с пред-подкачкой в кеш. Мы с Аркадием были удивлены скоростью выполнения (сравнительные данные сейчас уже не могу привести). Думали, что копирование массивов будет большим тормозом. На это изначально шли, так как предполагалось, что впоследствии будут разрабатываться специальные структуры данных для семантических технологий Авикомпа, расширяя рефал-выражения. Поэтому было важно, чтобы базовое представление выражений было как можно проще и понятнее для пользователей и интерфейс с Java был максимально примитивным. И оказалось, что такое простое представление выражений с частыми копированиями вполне устраивает такой язык высокого уровня как Рефал. Выжимать эффективность для промышленных приложений нужно задним числом, переписывая на язык "низкого уровня" (Java, в данном случае) критические места программы (после их выявления путем тщательных измерений, а не по наитию). Преждевременная оптимизация — корень всех зол. Premature optimization is the root of all evil. Дональд Кнут. «Structured Programming with go to Statements», «Computing Surveys», Vol. 6, № 4, 1974 (стр. 268). <https://doi.org/10.1145/356580.356581> https://doi.org/10.1145/356580.356581 Всего наилучшего, Андрей On Mon, Feb 11, 2019 at 9:39 PM Anton Orlov orlovan_AT_gmail.com < <mailto:refal@botik.ru> refal@botik.ru> wrote: Добрый день! On Mon, Feb 11, 2019 at 12:50 PM Arkady Klimov <http://arkady.klimov_at_gmail.com/> arkady.klimov_AT_gmail.com < <mailto:refal@botik.ru> 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)). Антон P.S. Помимо списков и массивов есть ещё потенциально интересные структуры данных для представления выражений. Например, rope (https://en.wikipedia.org/wiki/Rope_(data_structure)) и Finger tree (https://en.wikipedia.org/wiki/Finger_tree), но серьёзно для рефальского применения их никто не исследовал, насколько я знаю. Буду благодарен за разъяснения. Аркадий
