Добрый вечер!
Я занудно меняю сабж, приписывая "Рефал Плюс", а то тред "Синтаксический
анализ в Рефале" уже перегружен и обсуждение ушло с основной темы.
Архивируемая рассылка ценна тем, что потом в ней можно находить ценную
информацию. Для этого треды должны быть короткими, а сабжи – называть
основную тему. Пусть ответ Антона на вопросы Аркадия перейдет под этот сабж
(внизу привожу его текст).
Давайте проясним, сколько у нас реализаций Рефала Плюс, и, говоря он них,
будем указывать, о какой речь, а то, мне кажется, уже начала возникать
путаница. Эта переписка напомнила мне о трех реализациях:
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
Всего наилучшего,
Андрей
On Mon, Feb 11, 2019 at 9:39 PM Anton Orlov orlovan_AT_gmail.com <
refal@botik.ru> wrote:
> Добрый день!
>
> On Mon, Feb 11, 2019 at 12:50 PM Arkady Klimov arkady.klimov_AT_gmail.com
> <http://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)).
>
> Антон
>
> P.S. Помимо списков и массивов есть ещё потенциально интересные структуры
> данных для представления выражений. Например, rope (
> https://en.wikipedia.org/wiki/Rope_(data_structure)) и Finger tree (
> https://en.wikipedia.org/wiki/Finger_tree), но серьёзно для рефальского
> применения их никто не исследовал, насколько я знаю.
>
> Буду благодарен за разъяснения.
>> Аркадий
>>
>
