Re[2]: Об остановке суперкомпилятора Рефала
Квадрат - просто чтобы подчеркнуть, что вес числа констант и конструкторов больше, чем минус числа е-параметров. Имеют право и повторные быть, конечно, и смежные. Но для них я не знаю обоснования завершаемости суперкомпиляции. Может быть, можно как-то про строго непустые подстановки попробовать (т.е. накладывать ограничения не на обобщенное выражение, а на подстановки в него). Антонина Непейвода >Четверг, 20 декабря 2018, 14:37 +03:00 от Александр Коновалов >: > >Добрый день, Антонина! >Рад видеть тебя в рассылке! И, наверное, не только я. >«При каждом обобщении величина (3*K)^2+(3*K − E) может только уменьшаться.» >Я, наверное, туплю сегодня, но откуда там квадрат? Он связан с наличием >повторных переменных, которые при обобщении могут перестать быть повторными? > >Кстати, о повторных переменных. Мне кажется, что такая конфигурация имеет >право существовать: >< F ( e .1) e .1 e .2 ( e .2)> >и если её обобщить с >< F ( e .1) e .1 X e .2 ( e .2)> >то может получиться > >Но анализировать такие вещи будет сложнее. > >Спасибо, >Александр Коновалов >P . S . Андрей К., проверьте, пожалуйста, отлупы. Письмо Антонины мне не >пришло на ящик @ mail . ru . > >From: А Н < a_ne...@mail.ru > >Sent: Thursday, December 20, 2018 1:28 PM >To: refal@botik.ru >Subject: Re: Об остановке суперкомпилятора Рефала > >Добрый день, Александр! > >Насколько я знаю, в SCP4 используется стратегия, запрещающая построение >обобщений, в которых два е-параметра стоят подряд. Каждые такие два >е-параметра сливаются в один. И это гарантирует конечную длину цепочки >обобщений у выражения. Что можно попробовать доказать, построив оценку >"обобщаемости" выражения. Например, такую (грубую): пусть K - суммарное >количество термов (на любом скобочном уровне), вызовов функций, скобочных >конструкторов в выражении, E - суммарное количество е-параметров. Оно не может >превысить 3*K, поскольку каждый терм (конструктор, вызов) разбивает выражение >максимум на три области. Если количество е-параметров станет больше, чем 3*K, >какие-то два из них окажутся рядом (принцип Дирихле). > >И всё. При каждом обобщении величина (3*K)^2+(3*K - E) может только >уменьшаться. > >Наверное, и другие стратегии, запрещающие бесконечное обобщение, можно >придумать. А может, они даже где-то описаны. > >>Четверг, 20 декабря 2018, 12:33 +03:00 от Александр Коновалов < >>a.v.konovalo...@mail.ru >: >>Добрый день всем! >>Пишу в две рассылки, поскольку вопрос и про суперкомпиляцию, и про Рефал. >>В рассылке metacomputation - ru @… я встретил ссылку на препринт Сергея >>Романенко: >>С.А. Романенко. Суперкомпиляция: гомеоморфное вложение, вызов по имени, >>частичные вычисления // Препринты ИПМ им. М.В.Келдыша. 2018. № 209. С. 1-32. >>doi:10.20948/prepr-2018-209 link PDF >>В нём неформально обосновывается остановка суперкомпилятора SCPS , который >>работает с модельным языком SLL . Один из ключевых моментов — обобщение не >>может выполняться бесконечное количество раз: >>Таким образом, вместо поступательного построения дерева получается некоторая >>последовательность попыток: строим поддерево, «разочаровываемся» в нём, >>уничтожаем его, обобщаем конфигурацию, из которой оно выросло, строим >>поддерево заново, и т.д. >>Возникает вопрос: а не будет ли этот процесс продолжаться бесконечно? К >>счастью, как показал Сёренсен [16], в случае языка SLL, с которым работает >>суперкомпилятор SPSC [14], этот процесс рано или поздно завершается. Дело в >>том, что в случае SLL для любой конфигурации существует только конечное число >>обобщений (с точностью до переименования переменных). Таким образом, >>«верхняя» конфигурация может подвергнуться обобщению только конечное число >>раз. >> >>В случае с Рефалом всё не очевидно. На первый взгляд, для произвольной >>конфигурации — выражения с переменными и вызовами функций — можно построить >>бесконечное число обобщений, натыкивая в разные места e -переменные. Так ли >>это на практике? Можно ли бесконтрольно вставлять в выражение e- переменные? >> >>С уважением, >>Александр Коновалов >> >> > > >-- >А Н -- А Н
Re: Об остановке суперкомпилятора Рефала
Добрый день, Александр! Насколько я знаю, в SCP4 используется стратегия, запрещающая построение обобщений, в которых два е-параметра стоят подряд. Каждые такие два е-параметра сливаются в один. И это гарантирует конечную длину цепочки обобщений у выражения. Что можно попробовать доказать, построив оценку "обобщаемости" выражения. Например, такую (грубую): пусть K - суммарное количество термов (на любом скобочном уровне), вызовов функций, скобочных конструкторов в выражении, E - суммарное количество е-параметров. Оно не может превысить 3*K, поскольку каждый терм (конструктор, вызов) разбивает выражение максимум на три области. Если количество е-параметров станет больше, чем 3*K, какие-то два из них окажутся рядом (принцип Дирихле). И всё. При каждом обобщении величина (3*K)^2+(3*K - E) может только уменьшаться. Наверное, и другие стратегии, запрещающие бесконечное обобщение, можно придумать. А может, они даже где-то описаны. >Четверг, 20 декабря 2018, 12:33 +03:00 от Александр Коновалов >: > >Добрый день всем! >Пишу в две рассылки, поскольку вопрос и про суперкомпиляцию, и про Рефал. >В рассылке metacomputation - ru @… я встретил ссылку на препринт Сергея >Романенко: >С.А. Романенко. Суперкомпиляция: гомеоморфное вложение, вызов по имени, >частичные вычисления // Препринты ИПМ им. М.В.Келдыша. 2018. № 209. С. 1-32. >doi:10.20948/prepr-2018-209 link PDF >В нём неформально обосновывается остановка суперкомпилятора SCPS , который >работает с модельным языком SLL . Один из ключевых моментов — обобщение не >может выполняться бесконечное количество раз: >Таким образом, вместо поступательного построения дерева получается некоторая >последовательность попыток: строим поддерево, «разочаровываемся» в нём, >уничтожаем его, обобщаем конфигурацию, из которой оно выросло, строим >поддерево заново, и т.д. >Возникает вопрос: а не будет ли этот процесс продолжаться бесконечно? К >счастью, как показал Сёренсен [16], в случае языка SLL, с которым работает >суперкомпилятор SPSC [14], этот процесс рано или поздно завершается. Дело в >том, что в случае SLL для любой конфигурации существует только конечное число >обобщений (с точностью до переименования переменных). Таким образом, «верхняя» >конфигурация может подвергнуться обобщению только конечное число раз. > >В случае с Рефалом всё не очевидно. На первый взгляд, для произвольной >конфигурации — выражения с переменными и вызовами функций — можно построить >бесконечное число обобщений, натыкивая в разные места e -переменные. Так ли >это на практике? Можно ли бесконтрольно вставлять в выражение e- переменные? > >С уважением, >Александр Коновалов > > -- А Н
Re[4]: Рабочее совещание ИПС РАН и МГТУ имени Баумана по Рефалу
Во имя консистентности хочу добавить, что если нет s-переменных и повторных
e-переменных, то не всякие регулярные языки так можно описать, даже в конечном
алфавите. В частности, язык (AA)+ описать не получится. Но да, все описываемые
такими функциями (без повторных e- и s-) языки - регулярны.
>Воскресенье, 10 июня 2018, 16:05 +03:00 от Александр Коновалов
>:
>
>Добрый день, Бойко!
>
>«Прошу прощения, что вмешиваюсь, но нельзя ли вкратце описать, примером чего
>является данная функция?
>Или какую задачу она решает?»
>
>Прощу прощения. Антонина на семинаре рассматривала функции вида
>
>F {
> P1 = True;
> P2 = False;
> . . .
> PN = False;
>}
>
>Каждое предложение имеет вид «образец = символ;», где «образец» — выражение
>без скобок, а «символ» — True или False. Пусть L — язык, множество цепочек S,
>таких, что == True. Антонина анализировала, какой класс языков так можно
>описать, налагая разные ограничения на вид образцов Pi.
>
>В частности, если нет s-переменных и повторных e-переменных, то таким образом
>можно описывать регулярные языки.
>
>В случае, если образцы никак не ограничивать и добавить условия вида E1 : E2,
>где оба выражения пассивные и без скобок, то можно анализировать очень хитрые
>языки. Вот этот пример:
>
>LangPlay {
> e.WWW
>, e.WWW e.WWW: e.W e.WWW e.0
>, e.W : s.1 e.2 /* e.W не пустое */
>, e.WWW : e.W e.3
>= True;
>
> e.X = False;
>}
>
>возвращает True только на строках вида Q*, где Q — непустая строка. Например,
>, ABABAB и т.д.
>
>После выходных мы вывесим презентации докладов и всё станет понятнее.
>
>
>На слайде там была опечатка в этом примере, Антонина написала в рассылку
>исправленный вариант (в слайдах, которые мы вывесим, опечатки не будет, мы
>правим историю, да).
>
>
>С уважением,
>Александр Коновалов
Re[2]: Рабочее совещание ИПС РАН и МГТУ имени Баумана по Рефалу
Доброй ночи всем участникам совещания!
В функции для непростого слова из моей презентации была ошибка.
Хочу поделиться нормально работающим вариантом этой функции.
LangPlay {
e.x, e.x e.x : s.1 e.y e.x e.z, e.x : s.1 e.y s.2 e.xx = True;
e.x = False;
}
Надеюсь, что это только первое совещание в ряду совещаний по Рефалу! А.Непейвода
>Четверг, 7 июня 2018, 15:02 +03:00 от Александр Коновалов (офис)
>:
>
>Добрый день всем!
>Мероприятие прошло неплохо, хоть и затянулось более чем в два раза. Каждый
>доклад, вместо отведённых 30 минут, занял около часа.
>Хочу поблагодарить тех, кто мне помог в организации этого рефал-семинара.
>Андрей Петрович и Сергей Юрьевич, Спасибо Вам Большое!
>Слайды будут вывешены на сайте Института Рефала ( refal . botik . ru )
>примерно через неделю, я об этом напишу в рассылку.
>Хочу сказать несколько дополнений к своему докладу (временно доступен здесь:
>https://mazdaywik.github.io/direct-link/Язык%20и%20компилятор%20Рефал-5λ.pdf ).
>Репозиторий компилятора находится здесь:
>https://github.com/bmstu-iu9/simple-refal/ .
>В слайдах есть скриншот задачи из таск-трекера, посвящённой встроенным
>функциям Рефала-5. Вот эта задача:
>http://github.com/bmstu-iu9/simple-refal/issues/102
>В докладе я упоминал две оптимизации. Оптимизация совместного сопоставления с
>образцом (диплом Евгения Копьёва):
>https://github.com/bmstu-iu9/simple-refal/blob/master/doc/Презентация_Копьев_2016.pdf
>https://github.com/bmstu-iu9/simple-refal/blob/master/doc/РПЗ_Копьев_2016.pdf
>Оптимизация построения результатных выражений (диплом Ивана Скрыпникова):
>https://github.com/bmstu-iu9/simple-refal/blob/master/doc/OptPattern/Скрыпников%20Презентация%202016.pdf
>https://github.com/bmstu-iu9/simple-refal/blob/master/doc/OptPattern/Скрыпников%20Записка%202016.pdf
>Встроенные функции Рефала-5λ написаны на Рефале. Можно в этом убедиться:
>https://github.com/bmstu-iu9/simple-refal/blob/master/src/srlib/Library.sref
>https://github.com/bmstu-iu9/simple-refal/blob/master/src/srlib/common/refal5-builtins.srefi
>
>С уважением,
>Александр Коновалов
>
>From : Александр Коновалов < a . v . konovalov 87@ mail . ru >
>Sent : Friday , June 1, 2018 1:10 AM
>To : refal @ botik . ru
>Subject : FW : Рабочее совещание ИПС РАН и МГТУ имени Баумана по Рефалу
>
>Прошу прощения, забыл прикрепить вложение.
>
>From: mazday...@hotmail.com
>Sent: Friday, June 1, 2018 12:33 AM
>To: refal@botik.ru
>Subject: RE: Рабочее совещание ИПС РАН и МГТУ имени Баумана по Рефалу
>
>Добрый вечер всем!
>Есть уточнённая программа мероприятия (во вложении к письму). К сожалению, два
>докладчика отвалились в процессе, но остальные доклады тоже будут интересными.
>По времени советую ориентироваться на диапазон 10:00—15:00. Поскольку
>обсуждение может затянуться, либо не все участники смогут подъехать к 10 утра.
>Чтобы посетить конференцию, отправьте мне до завтрашнего вечера (до 17 часов
>01.06) фамилию, имя и отчество. Потому что надо успеть заказать пропуск
>(потом уже поздно будет). Не забудьте взять паспорт.
>Напоминаю, проходить рабочее совещание будет в главном корпусе МГТУ имени Н.
>Э. Баумана, по адресу ул. 2-я Бауманская, дом 5. Вход через проходную со
>львами.
>
>С уважением,
>Александр Коновалов
>P . S . Шлю с другой почты, поскольку с mail . ru есть некоторые проблемы.
>
>From: Александр Коновалов [ mailto:a.v.konovalo...@mail.ru ]
>Sent: Thursday, May 31, 2018 3:42 PM
>To: refal@botik.ru
>Subject: Рабочее совещание ИПС РАН и МГТУ имени Баумана по Рефалу
>
>Добрый день всем!
>5 июня 2018 года в МГТУ имени Н. Э. Баумана пройдёт
>Совместное рабочее совещание ИПС имени А. К. Айламазяна РАН
>и
>МГТУ имени Н. Э. Баумана
>по функциональному языку программирования Рефал
>Предварительная программа доступна здесь:
>http://refal.botik.ru/events/events.htm (программу уточню сегодня-завтра).
>На мероприятии выступят с докладами сотрудники ИПС РАН и студенты МГТУ,
>занимающиеся исследованиями, связанными с Рефалом и суперкомпиляцией.
>Если хотите посетить семинар , напишите мне письмо сегодня или завтра ,
>чтобы я мог Вам выписать пропуск ( фамилия, имя и отчество ). На проходной
>необходимо будет показать паспорт .
>Адрес: ул. 2-я Бауманская, дом 5 (главный корпус). Время с 10:00 до 17:00 ,
>аудитория 330аю .
>
>С уважением,
>Александр Коновалов
>
