Добрый вечер всем!
На сколько я знаю, когда-то были планы реализации 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 были
приемлемо эффективны, будучи скомпилированы Рефалом Плюс?
В соседней ветке мы обсуждаем плохие приёмы программирования, и одна из мыслей
была — борьба с недостатком представления данных протекает в стиль
программирования. Так вот, в Рефале Плюс борьба с недостатком представления
данных протекла аж в дизайн языка.
С уважением,
Александр Коновалов
