День добрый, всем! >> Но есть один нюанс. Рефал Плюс использует массивное представление >> данных с дорогой конкатенацией. >> ... >> Эту проблему создатели языка решили жёстко: форматы функций >> (которые, вообще-то, идиома, рекомендация) сделали частью языка.
> Мне видится, что было немного не так. Не "язык Рефал Плюс такой, > потому что он использует массивное представление", а наоборот: "он > использует массивное представление, как наиболее подходящее (с точки > зрения авторов в тот момент времени) для реализации возможностей > языка Рефала Плюс". А возможности и особенности языка проистекают из > цели: сделать язык, замкнутым относительно суперкомпиляции. Последнее предложение самое важное и наиболее часто забываемое во всех обсозрных материалах про историю рефала. У С.А.Романенко перед Рефалом Плюс был препринт, про диалект Рефала, в котором выразимы результаты разных оптимизаций (например, отсечения удлинений, КУД-ы), включая суперкомпиляцию. Мне нестерпимо горько, что массово так и не понято, что любая разумная суперкомпиляция из любого диалекта Рефала, в котором арнострь и коарность равна единички, строит результат, в котором арности и коарности базовых функций (конфигураций) остаточной программы оказываются любыми, не обязательно единицами. Это и только это и есть форматы фуннкций. Арности и коарности. И для меня было знаково, что Рефал Плюс был (как мне известно) первым (а на мой вкус -- и единственным) функциональным языком, с внятной реализацией не только арности, но и коарности. Как результат, в рамках Обнинского семинара мною и Рутиком была написана программка "глюкало", которая брала вывод тогдашнего суперкомпилятора Турчина (это был S-граф) и преобразовывала его в Рефал Плюс програму. С арностью и коарностью. Вот так. На входе в Турчинский суперкомпилятор Рефял-5, на выходе S-граф и по нему Рефал Плюс, нашей "глюкалой". А до того, сам Турчин как-то и не брался откинуть S-граф обратно в Рефал-5. Ну, мол рук не хватало. Вот он рефал-мальчиков и просил поучаствовать... ;-) Но, на мой вкус, не рук не хватало, а проблемы были с тем, что Рефал-5 не совсем пригоден для изображемия результата своей суперкомпиляции... В силу ровно указанных сложностей. >> На сколько я знаю, когда-то были планы реализации front-end’а >> Рефала-5 в компиляторе Рефала Плюс. > Да, планы были, но, как я помню, в прямом виде осуществлены не были > (Сергей Михайлович, Антон, поправьте, если ошибаюсь). Планов было много, увы, не все сделано... > Однако, в 2000г. был другой проект. У SCP4 результат > суперкомпиляции сначала строится в виде графа, а затем уже > транслируется к Рефал 5. Был проект поменять backend SCP4 и > генерировать из графа не Рефал 5, а Рефал Плюс. Этот проект > назывался CGRp (http://rfp.botik.ru/cgrp) и был выполнен Антоном > Орловым и мной (в нашем студенчестве). Тут многие возможности > Рефала Плюс и пригодились, т.к. в этом графе есть и форматы > функций, и другие особенности. Это уже была взрослая и зрелая реинкарнация "глюкалы". Да, про имя: наша первая программка была названа в честь Роберта Глюка, который написал перед этим рабпту "В нутре суперкомпилятора" и изложил некие технические детали, которые помогали понимать, что же там происходят. Читать S-граф было не легко. И перевод из него в человеческий язык -- это была работа того же плана, который сделал Роберт в своей публикации... > Поэтому компилировать (вернее суперкомпилировать) Рефал 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 > были приемлемо эффективны, будучи скомпилированы Рефалом Плюс? > > В соседней ветке мы обсуждаем плохие приёмы программирования, и > одна из мыслей была — борьба с недостатком представления данных > протекает в стиль программирования. Так вот, в Рефале Плюс борьба с > недостатком представления данных протекла аж в дизайн языка. > > С уважением, > Александр Коновалов > > -- С уважением, Абрамов С.М. mailto:ab...@botik.ru
