Александр, Вы же сами пишете, что частью языка Рефал Плюс являются форматы,
- это и есть то решение, которое и предполагалось, и осуществлено в Рефале
Плюс.
Что касается компиляции Рефала-5 в бэкенд Рефала Плюс, то именно
предполагалось, что форматы будут по возможности выявляться динамически, по
крайней мере, так я себе это представлял. А разве не вы с дипломниками эту
проблему уже рассматривали и вроде даже как бы решили в прошлом году? Или
там было что-то другое? Тогда уточните.
В принципе, аналогичная работа производилась в рамках
полусуперкомпилятора Рефала-6 Н.Кондратьевым. А при отображении в С эти
форматы использовались (к сожалению, уже четверть века это лежит без
употребления).
Аркадий
чт, 24 дек. 2020 г. в 22:33, Александр Коновалов a.v.konovalov87_AT_mail.ru
<refal@botik.ru>:
> Доброй ночи всем!
>
> В принципе, я разобрался, как надо повышать местность и коместность при
> компиляции Рефала-5 в массивное представление. Могу изложить, как бы я это
> сделал (а может, когда-нибудь и сделаю, через год, через два). Но сначала я
> хотел бы узнать, как это предполагалось в Рефале Плюс.
>
>
>
> С уважением,
> Александр Коновалов
>
>
>
> *From:* Александр Коновалов a.v.konovalov87_AT_mail.ru [mailto:
> refal@botik.ru]
> *Sent:* Wednesday, December 16, 2020 12:07 AM
> *To:* refal@botik.ru
> *Subject:* Рефал-5, Рефал Плюс и форматы
>
>
>
> Добрый вечер всем!
>
> На сколько я знаю, когда-то были планы реализации front-end’а Рефала-5
> в компиляторе Рефала Плюс. Т.е. предполагалось использовать компилятор
> Рефала Плюс для компиляции исходных текстов Рефала-5.
>
> (Дальше пишу подробно, поскольку не все подписчики знакомы
> с рассматриваемой проблемой. Те, кто знакомы, могут сразу промотать письмо
> до конца.)
>
> Но есть один нюанс. Рефал Плюс использует массивное представление данных
> с дорогой конкатенацией. А это значит, что традиционный способ передавать
> параметры в функцию, используя N−1 скобок для N e-параметров будет
> приводить к избыточной конкатенации, а значит, и увеличению порядка
> сложности.
>
> Пример, замена символов A на B:
>
> Fab { e.X = <Loop () e.X> }
>
> Loop {
> (e.Acc) 'A' e.Rest = <Loop (e.Acc 'B') e.Rest>;
> (e.Acc) s.X e.Rest = <Loop (e.Acc s.X) e.Rest>;
> (e.Acc) /* пусто */ = e.Acc;
> }
>
> Здесь есть две конкатенации, с которыми столкнётся Рефал Плюс.
>
> Первая — конкатенация символа с аккумулятором e.Acc 'B' и e.Acc s.X. Если
> длина аккумулятора N, то потребуется создать новый массив длины N+1,
> скопировать в него содержимое e.Acc и дописать туда символ ('B' или s.X).
> На каждом шаге аккумулятор вырастает на единицу, а значит, затраты времени
> на копирования элементов будут N×(N+1)/2 = O(N²), где N — исходная длина
> строки.
>
> Вторая — конкатенация скобочного терма с остатком строки (…) e.Rest.
> В ней затраты те же: нужно создать массив длины N+1 (где N — длина e.Rest),
> скопировать туда e.Rest и скобочный терм. Тоже сложность будет O(N²).
>
> Первая проблема, проблема роста аккумулятора, решается пустым местом
> вокруг формируемого массива. На большинстве итераций новый символ будет
> дописан в пустое место, а сам массив копировать не потребуется. Затраты
> времени на формирование выражения в аккумуляторе будут амортизированными
> линейными. Детали пересказывать не буду (когда-то их уже обсуждали
> в рассылке). В общем, решение элегантное.
>
> А вот вторую конкатенацию дыры не спасут, т.к. их там нет.
> В массиве-аргументе слева от e.Rest уже находится символ, вписать на его
> место круглую скобку нельзя, т.к. участком массива 'A' e.Rest может
> пользоваться другая часть программы.
>
> Эту проблему создатели языка решили жёстко: форматы функций (которые,
> вообще-то, идиома, рекомендация) сделали частью языка.
>
> Теперь программист вынужден для каждой функции указывать формат, образцы
> всех предложений должны этот формат уточнять, результат работы функции
> в этот формат тоже обязан вкладываться. Аргументы функций также должны
> соответствовать входному формату.
>
> Для функций выше в программе должны быть написаны следующие строчки:
>
> $func Fab e.X = e.X;
> $func Loop (e.Acc) e.X = e.Acc;
>
> Для каждого вызова Loop компилятор проверит, что фактический аргумент
> вкладывается в формат, после чего аккумулятор и остаток строки передаст в
> виде двух отдельных параметров. Конкатенации не будет. Сложность функции
> будет амортизированно линейной.
>
> Теперь написать функцию с несколькими форматами или с необязательными
> параметрами нельзя. Вернее можно, но это будет неэффективно.
>
>
>
> Так вот, к чему я пишу. На Рефале-5 конкатенация дешёвая, форматов
> на уровне синтаксиса нет, встречаются функции с несколькими форматами. Как
> быть с такими программами? Если функциям неявно приписывать формат e.X = e
> .X, то программы для Рефала-5, скомпилированные Рефалом Плюс, будут
> работать заведомо медленно. Причём медленнее не на константу, а на порядок
> алгоритма.
>
> А что же тогда предполагалось делать, чтобы программы для Рефала-5 были
> приемлемо эффективны, будучи скомпилированы Рефалом Плюс?
>
>
>
> В соседней ветке мы обсуждаем плохие приёмы программирования, и одна
> из мыслей была — борьба с недостатком представления данных протекает
> в стиль программирования. Так вот, в Рефале Плюс борьба с недостатком
> представления данных протекла аж в дизайн языка.
>
>
>
> С уважением,
> Александр Коновалов
>
>
>
--
_______________
*С уважением, *
*Аркадий Климов,*
*с.н.с. ИППМ РАН,*
*+7(499)135-32-95*
*+7(916)072-81-48*
