Добрый вечер, коллеги! Но есть один нюанс. Рефал Плюс использует массивное представление данных с > дорогой конкатенацией. > ... > Эту проблему создатели языка решили жёстко: форматы функций (которые, > вообще-то, идиома, рекомендация) сделали частью языка.
Мне видится, что было немного не так. Не "язык Рефал Плюс такой, потому что он использует массивное представление", а наоборот: "он использует массивное представление, как наиболее подходящее (с точки зрения авторов в тот момент времени) для реализации возможностей языка Рефала Плюс". А возможности и особенности языка проистекают из цели: сделать язык, замкнутым относительно суперкомпиляции. На сколько я знаю, когда-то были планы реализации front-end’а Рефала-5 в > компиляторе Рефала Плюс. Да, планы были, но, как я помню, в прямом виде осуществлены не были (Сергей Михайлович, Антон, поправьте, если ошибаюсь). Однако, в 2000г. был другой проект. У SCP4 результат суперкомпиляции сначала строится в виде графа, а затем уже транслируется к Рефал 5. Был проект поменять backend SCP4 и генерировать из графа не Рефал 5, а Рефал Плюс. Этот проект назывался CGRp (http://rfp.botik.ru/cgrp) и был выполнен Антоном Орловым и мной (в нашем студенчестве). Тут многие возможности Рефала Плюс и пригодились, т.к. в этом графе есть и форматы функций, и другие особенности. Поэтому компилировать (вернее суперкомпилировать) Рефал 5 в Рефал Плюс можно с помощью SCP4 ;). Но есть один нюанс. Рефал Плюс использует массивное представление данных с > дорогой конкатенацией. Возвращаясь к конкатенации. В языке две основные операции с выражениями: разбор (взятие подвыражений, копирование) и сбор (контакетанция) . По сути следует рассматривать одну обобщенную операцию: разобрать выражение на части, а потом из частей собрать новое выражение (говорю в первую очередь про разбор-сбор на одном уровне выражения, без "спуска" в скобки). Если какая-то часть размножается или нужно сохранить исходное выражение (чтобы, например, использовать в другой ветке программы), то копирование той или иной части будет необходимо независимо от представления. Поэтому массивные представления Рефала Плюс или Рефала 6 показывают сравнимые результаты с другими представлениями (правда, не знаю глубоких исследований). И небольшой оффтоп о представлениях. Мне было бы интересно, если бы студенты поисследовали "необычные" представления данных: Rope и Finger Tree. Если я правильно помню, то на их основе разбор-сбор выражений будет по сложности всегда логарифмический. Мы узнали об этих представлениях на одном контесте. Каждый год проводится ICFP Programming Contest - соревнования при конференции по функциональному программированию. Это три дня (72 часа) на одну необычную Задачу (студентам рекомендую! там задачи очень необычные: из условия обычно совершенно непонятно, что же в итоге придется делать). В 2007 году была задача http://save-endo.cs.uu.nl/ - спасти инопланетянина, переписывая его ДНК. На поверхности этой задачи был язык для изменения ДНК, очень похожий на Рефал. Мы перепробовали несколько подходов, но в итоге скорости работы этой части программы оказалось недостаточно, чтобы продвинуться на уровне победителей. Как потом оказалось, если бы использовали представления данных Rope или Finger Tree, то скорость работы программы была бы существенно выше. Поэтому мне интересно посмотреть эти представления в Рефалах на больших задачах. С уважением, Юрий Климов On Sun, 27 Dec 2020 at 01:55, Александр Коновалов a.v.konovalov87_AT_mail.ru <refal@botik.ru> wrote: > Добрый вечер, Аркадий! Добрый вечер всем остальным! > > В письме я сначала отвечу на реплики Аркадия, а потом приведу свои > соображения по поводу вывода форматов. > > > > *«Александр, Вы же сами пишете, что частью языка Рефал Плюс являются > форматы, — это и есть то решение, которое и предполагалось, и осуществлено > в Рефале Плюс.»* > > Я пишу о том, что есть конфликт: > • (а) форматы являются частью языка Рефал Плюс, частью его промежуточного > представления и жизненно необходимы его массивному генератору кода, > • (б) у системы Рефал Плюс есть поддержка входных файлов на Рефале-5, где > этих форматов нет, > • (в) предполагается, что система Рефал Плюс со фронтендом Рефала-5 будет > применима для программ, написанных для Рефала-5 (например, SCP4), иначе > зачем её добавлять, > • (г) в исходных файлах программ для Рефала-5 форматов нет, более того, > для функций не всегда формат может быть записан. > > Конфликт в том, что системе Рефал Плюс форматы нужны для построения > эффективного кода, но в некоторых режимах компиляции во входных файлах этих > форматов нет. А значит, или форматы должны рождаться в системе, или должны > быть всё-таки как-то указаны пользователем. Иначе программы для Рефала-5 > будут выполняться неприемлемо медленно. > > (Внимательные читатели обратили внимание на предлог. Я пишу не > «на Рефале-5», а «для Рефала-5», подразумевая, что программист пишет код > для конкретной реализации. Этот код будет эффективен на данной реализации, > однако может быть медленен на альтернативных реализациях.) > > > > От Андрея Петровича в частной переписке я узнал, что реализованный > фронтэнд Рефала-5 в Рефале Плюс просто приписывает всем функциям формат e > = e. Т.е. описанная мною задача решена не была. > > > > *«Что касается компиляции Рефала-5 в бэкенд Рефала Плюс, то именно > предполагалось, что форматы будут по возможности выявляться динамически, > по крайней мере, так я себе это представлял.»* > > А я вообще не представлял, как изначально предполагалось, поэтому > и спросил. Вообще существует два варианта решения, а вернее три. Нулевое > решение — сунуть голову в песок и приписывать всем функциям формат e = e, > оно и было реализовано. Два других: выводить форматы автоматически или > требовать от пользователя псевдокомментариев с корректными форматами. > Впрочем, возможна комбинация этих подходов. > > > > *«А разве не вы с дипломниками эту проблему уже рассматривали и вроде даже > как бы решили в прошлом году? Или там было что-то другое? Тогда уточните.»* > > Это другое, как модно сейчас писать в интернете. Вернее, этот вывод > форматов решает другую задачу. > > > > *«В принципе, аналогичная работа производилась в рамках > полусуперкомпилятора Рефала-6 Н.Кондратьевым. А при отображении в С эти > форматы использовались (к сожалению, уже четверть века это лежит без > употребления).»* > > Любопытно узнать детали. > > > > > > А теперь про то, что я сам об этом думаю. А думаю вот что: > > · Для entry- и extern-функций формат задаёт сам пользователь, > используя, например, псевдокомментарии. Или пишет отдельный файл > с форматами всех entry-функций, который скармливается компилятору. Здесь > важно обеспечить консистентность для случаев раздельной трансляции, чтобы > форматы, указанные для entry-функции в одном файле и extern-функции > с тем же именем в другом совпадали. Но это технический вопрос. > > · Форматы не-entry-функций выводятся компилятором. А это уже > вопрос принципиальный. > > > > Дальше про вывод форматов. Для простоты я буду рассматривать базисный > Рефал. > > Но нужно сначала уточнить требования к форматам в Рефале Плюс, вернее те, > которые существенны для дальнейшего обсуждения. Требования следующие: > > 1. Аргумент каждого вызова функции должен соответствовать формату. > Т.е. если ARG — аргумент, а INFMT — входной формат вызываемой функции, > то сопоставление ARG : INFMT должно быть успешным и без сужений > (ограничений на переменные в ARG). > > 2. Правые части предложений каждой функции должны соответствовать > выходному формату. Т.е. если RES — выражение в правой части предложения, > а OUTFMT — выходной формат функции, то RES : OUTFMT должно быть успешным > и без сужений. > > 3. Левые части предложений каждой функции должны соответствовать > входному формату функции. Т.е. если PAT — выражение в левой части, а > INFMT — входной формат, то PAT : INFMT успешно и без сужений. > > Известно два алгоритма вывода форматов функций: > > · Алгоритм, разработанный Сергеем Анатольевичем Романенко для > повышения местности в самоприменимом «московском специализаторе» > в 1987 году. > http://dx.doi.org/10.1007/3-540-52592-0_73 > > · Алгоритм, предложенный автором письма и реализованный вместе > со студентом Георгием Ивановым в рамках выпускной квалификационной работы > в 2019 году. > https://github.com/bmstu-iu9/refal-5-arity-raiser-and-verifier > https://github.com/bmstu-iu9/refal-5-arity-raiser-and-verifier/blob/master > /report/diploma/ДипломЗапискаВКР.pdf > (надеюсь, когда-нибудь будет и здесь DOI) > > Целью *алгоритма Романенко* является повышение местности функций > в остаточных программах, построенных специализатором. Выходные форматы > функций выводятся на основе анализа определений функций, однако входные > форматы — только на основе аргументов всех вызовов данной функции. Т.е. > если аргументы всех вызовов функции F можно описать как список из трёх > термов, то таковым будет и входной формат функции F независимо от её > фактического определения в программе. Более того, формат выведенный для > функции может даже не пересекаться с объединением множеств левых частей > предложений функции, т.е. вызов такой функции всегда будет фатален. > > Применительно к задаче вывода форматов для массивного представления > алгоритм обеспечивает только выполнение *первых двух требований.* При > выводе входных форматов не учитываются левые части предложений, поэтому > входной формат может не соответствовать определению функции. > > Целью *алгоритма Коновалова-Иванова* (нескромно назовём его так) является > проверка корректности программы. Алгоритм выводит и входные, и выходные > форматы основываясь на определениях функций (причём анализ делается > довольно глубокий), вызовы проверяет только на допустимость. Если > существуют такие значения переменных, что все вызовы функций в правой части > могут быть выполнены на один шаг, значит, предложение корректное. Иначе > (нет таких значений переменных) — в предложении ошибка. > > Применительно к рассматриваемой задаче алгоритм обеспечивает только > выполнение *последних двух требований.* В размеченной программе могут > быть вызовы функций с аргументами, не вкладывающимися во входные форматы. > Например, входной формат функции F может иметь вид (e.1) e.2, в то время > как она будет вызываться с аргументом <F e.X s.Y>. Пересечение множеств (e.1) > e.2 и e.X s.Y непустое, поэтому верификатор форматов об ошибке > не сообщит. Однако, сопоставление e.X s.Y : (e.1) e.2 возможно только > с сужением e.X → (e.3) e.4, что нарушает требование 1. > > Так что *оба алгоритма не подходят* для повышения местности для > компиляции в массивное представление. *Нужна доработка напильником одного > из алгоритмов.* > > > > На этом письмо заканчиваю. В следующем письме я расскажу, какой алгоритм > нужно доработать напильником, чтобы удовлетворить все три требования > массивного представления. А пока можете делать ставки. > > На самом деле, доработать можно оба, но один из них предпочтительнее. > > > > С уважением, > Александр Коновалов > > > > > > *From:* Arkady Klimov arkady.klimov_AT_gmail.com [mailto:refal@botik.ru] > *Sent:* Friday, December 25, 2020 1:35 PM > *To:* refal@botik.ru > *Subject:* Re: Рефал-5, Рефал Плюс и форматы > > > > Александр, Вы же сами пишете, что частью языка Рефал Плюс являются > форматы, - это и есть то решение, которое и предполагалось, и осуществлено > в Рефале Плюс. > > Что касается компиляции Рефала-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* >
