Re: Семинар по метавычислениям в понедельник 2 марта 2020 в ИПМ

[Eisymont Leonid verger-lk_AT_yandex . ru]

Андрей, очень хотел попасть на семинар, но сижу дома со статьей по ЭКБ для ИИ. Очень тяжело идет, а завтра надо бы отдать коллегам на анализ. Жду презентацию, вопросов у меня уже сейчас много, ведь мы этим занимались 15 лет назад, еще в НИЦЭВТ-е, тогда не пошло, а потом не до этого было. Сейчас интерес есть, даже Рреализацию на односвязных списках Рефала-2 на сервере Модуля установили, она с машинными операциями под MPI, да и вообще испытанная и самая практически продвинутая. Вручную распараллеливать можно, даже пробовали еще в НИЦЭВТ-е. Это в НИР Вектор с Квантом - 2004 год.

Успехов, завидую вашему участию в работе такого семинара.

Л.Эйсымонт

 

02.03.2020, 08:03, "Andrei Klimov andrei_AT_klimov.net" <refal@botik.ru>:

Александр, доброе утро!

 

Жаль, но что ж делать...

Если параллелизм нас так не затянет, что первый доклад с обсуждением займет намного больше времени, чем думали, то есть такие соображения для полезных рефал-обсуждений после него:

• Новый участник семинара Максим Кривчиков может дать у доски аннотацию его статьи, а мы обсудим:
  • Vasenin, V.A., Krivchikov, M.A. Intermediate Representation of Programs with Type Specification Based on Pattern Matching. Program Comput Soft 46, 57–66 (2020). https://doi.org/10.1134/S0361768820010077
  • Это журнал "Программирование", но файл статьи на русском дают только за деньги (или у автора), а у Шпрингера можно взять бесплатно из академических институтов и, наверно, из части университетов. (А есть способы и не только из институтов.:-))

• У меня есть затравочные вопросы по (отсутствующему, но потенциальному) месту Рефала в мире и его (гипотетическому) развитию в соответствующем направлении, которых на доклад недостаточно, но дискуссию могу разжечь. Вот этот доклад и статья доклад Сергея Романенко в ту же сторону, но есть что добавить:
  • С.А. Романенко. Рефал и Агда как воплощения идеи “метаалгоритмического языка” // Научный сервис в сети Интернет: труды XIX Всероссийской научной конференции (18-23 сентября 2017 г., г. Новороссийск). — М.: ИПМ им. М.В.Келдыша, 2017. — С. 417-424 . — http://doi.org/10.20948/abrau-2017-63
  • Файл статьи доступен по этой ссылке.

До встречи!

 

Всего наилучшего,

Андрей Климов

 

 

On Sun, Mar 1, 2020 at 6:13 PM 'Александр Коновалов' via Метавычисления и специализация программ <metacomputation...@googlegroups.com> wrote:

Добрый вечер всем!

Я не успеваю подготовить доклад к завтрашнему семинару, поэтому снимаю завтрашнее выступление.

Поэтому слушать завтра будем только доклад Станислава.

Но я думаю, что мы найдём достаточно тем для обсуждения и без моего выступления.

Простите, что так выходит.

 

С уважением,
Александр Коновалов

 

 

From: Andrei Klimov [mailto:and...@klimov.net]
Sent: Friday, February 28, 2020 2:04 PM
To: metacomputation-ru <metacomputation...@googlegroups.com>; refal@botik.ru
Subject: Семинар по метавычислениям в понедельник 2 марта 2020 в ИПМ

 

Добрый день всем!

В понедельник 2 марта 2020 в 15 часов соберемся в 416 комнате ИПМ им. М.В. Келдыша РАН на семинар, чтобы послушать два доклада, связанных с языком Рефал:

• Станислав Санталов (МГТУ им. Н.Э. Баумана)
  Параллельное выполнение функций в Рефале-05

Основная идея — рассмотреть возможность вычисления функций в Рефале-05 независимо, в различных потоках. Предлагается способ распределения нагрузки между потоками, сохранения порядка вычисления функций и доступа к глобальному полю зрения. Для реализации поставленных задач вводится новая сущность — а-терм, экземпляры которой организуются в дерево с атомарными счетчиками и специальный глобальный потокобезопасный безблокировочный список. Также создается несколько очередей а-термов: общая глобальная и по одной локальной для каждого потока. В конце приводятся результаты тестирования и анализ полученной схемы.

• Александр Коновалов (МГТУ им. Н.Э. Баумана)
  Алгоритм вывода свёрточной формы для функций обработки строк

Под свёрточной формой мы будем подразумевать представление функции, потребляющей некоторую структуру данных с помощью операции, знакомой функциональным программистам под именем foldr для лисповских списков, а в общем случае для типизированных языков типа ML и Haskell как катаморфизм этой структуры данных — термин из теории категорий. Для функций обработки строк (и выражений Рефала), где есть ассоциативная операция конкатенации, это будет катаморфизм для свободного моноида, который также можно рассматривать как гомоморфизм моноида конкатенации в некоторый другой моноид.

Под строками в докладе будут пониматься однородные последовательности произвольных значений, которые могут быть пустыми и для которых определены конкатенация и итерация с обеих сторон. Для сравнения: в лисповских списках определено добавление одного элемента в начало (cons) и итерация только слева-направо.

Представление функций, потребляющих строки, в свёрточной форме даёт некоторые преимущества:

• Появляется возможность выполнять слияние (fusion) с функциями, порождающими строки — в результирующей функции промежуточная строка даже не будет создаваться. Это вообще верно для любого катаморфизма и является основой сокращённой дефорестации (shortcut deforestation).
• Появляется возможность распараллеливать вычисление функции — строку можно разделить на части, свернуть независимо и результаты их свёрток скомбинировать в искомое значение. Это свойство верно только для свёрточной формы строковых функций.
• Можно менять направление обработки строк — из свёрточной формы можно получить функцию, читающую строку как слева-направо, так и справа-налево. Например, это позволяет преобразовать наивную функцию, вычисляющую значение многочлена, в схему Горнера.

На семинаре 29 октября 2019 года рассматривалась сокращённая дефорестация и способ её реализации для языка Рефал. На нём было введено понятие свёрточной формы для строковых функций в терминах Рефала и были рассмотрены некоторые примеры функций в этой форме. Способ построения свёрточной формы на том семинаре не давался.

В докладе 2 марта 2020 года мы определим свёрточную форму уже без использования терминологии Рефала, а также рассмотрим алгоритм перевода функций в свёрточную форму. Входом алгоритма будет функция, анализирующая строку по одному элементу слева-направо (или справа-налево), выходом будет свёрточная форма либо сообщение о том, что алгоритм не может её вывести.

Алгоритм применим для ограниченного класса функций, т.е. не для любой функции, представимой в свёрточной форме, эту форму можно вывести. Однако, этот класс достаточно широк, что будет продемонстрировано на нескольких примерах.

Вывод свёрточной формы использует ограниченную суперкомпиляцию на некоторых этапах своей работы. Ограниченность выражается в допустимых вариантах обобщения похожих конфигураций. Если в процессе требуется выполнить недопустимое обобщение, то или преобразуемая функция не представима в свёрточной форме, или она слишком сложна для этого алгоритма.

В отличие от доклада 29.10.2019 для понимания этого доклада знания Рефала не требуется.

---

Гости ИПМ, которым нужен разовый пропуск, напишите мне по email или пошлите смс-ку с ФИО и НОМЕРОМ ПАСПОРТА на моб. +7 985 364 3536 до 12 час в день семинара. Пропуск получите либо в бюро пропусков в окошке слева от вахтера в главной проходной ("стеклянной", со стороны Миусской площади), либо непосредственно у вахтера. Я вам сообщу, какой вид пропуска будет оформлен.

С ноутбуком, не зарегистрированным в списке на вахте на пронос в ИПМ, лучше не приходить, чтобы не споткнуться о ситуацию, когда не пропустят, а соответствующего начальства, чтобы подписать материальный пропуск на внос-вынос, не окажется на месте.

---

До встречи!

Андрей Климов

--
Вы получили это сообщение, поскольку подписаны на группу "Метавычисления и специализация программ".
Чтобы отменить подписку на эту группу и больше не получать от нее сообщения, отправьте письмо на электронный адрес metacomputation-ru+unsubscr...@googlegroups.com.
Чтобы посмотреть обсуждение на веб-странице, перейдите по ссылке https://groups.google.com/d/msgid/metacomputation-ru/CAM7HiMnG8AfcNM%2BUG3ufHWeKX_0qs-Mbx_nWp7Eq2DWMVP-tSw%40mail.gmail.com.

 

--
Вы получили это сообщение, поскольку подписаны на группу "Метавычисления и специализация программ".
Чтобы отменить подписку на эту группу и больше не получать от нее сообщения, отправьте письмо на электронный адрес metacomputation-ru+unsubscr...@googlegroups.com.
Чтобы посмотреть обсуждение на веб-странице, перейдите по ссылке https://groups.google.com/d/msgid/metacomputation-ru/0af601d5efdc%240145e8a0%2403d1b9e0%24%40mail.ru.