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