Добрый день всем! В *понедельник 2 марта 2020 в 15 часов* соберемся в 416 комнате ИПМ им. М.В. Келдыша РАН на семинар, чтобы послушать два доклада, связанных с языком Рефал:
- *Станислав Санталов *(МГТУ им. Н.Э. Баумана) *Параллельное выполнение функций в Рефале-05* Основная идея — рассмотреть возможность вычисления функций в Рефале-05 независимо, в различных потоках. Предлагается способ распределения нагрузки между потоками, сохранения порядка вычисления функций и доступа к глобальному полю зрения. Для реализации поставленных задач вводится новая сущность — а-терм, экземпляры которой организуются в дерево с атомарными счетчиками и специальный глобальный потокобезопасный безблокировочный список. Также создается несколько очередей а-термов: общая глобальная и по одной локальной для каждого потока. В конце приводятся результаты тестирования и анализ полученной схемы. - *Александр Коновалов* (МГТУ им. Н.Э. Баумана) *Алгоритм вывода свёрточной формы для функций обработки строк* Под *свёрточной формой* мы будем подразумевать представление функции, потребляющей некоторую структуру данных с помощью операции, знакомой функциональным программистам под именем foldr для лисповских списков, а в общем случае для типизированных языков типа ML и Haskell как * катаморфизм <https://traditio.wiki/Катаморфизм>* этой структуры данных — термин из теории категорий. Для функций обработки строк (и выражений Рефала), где есть ассоциативная операция конкатенации, это будет катаморфизм для свободного моноида, который также можно рассматривать как гомоморфизм моноида конкатенации в некоторый другой моноид. Под строками в докладе будут пониматься однородные последовательности произвольных значений, которые могут быть пустыми и для которых определены конкатенация и итерация с обеих сторон. Для сравнения: в лисповских списках определено добавление одного элемента в начало (cons) и итерация только слева-направо. Представление функций, потребляющих строки, в свёрточной форме даёт некоторые преимущества: - Появляется возможность выполнять слияние (fusion) с функциями, порождающими строки — в результирующей функции промежуточная строка даже не будет создаваться. Это вообще верно для любого катаморфизма и является основой сокращённой дефорестации (shortcut deforestation). - Появляется возможность распараллеливать вычисление функции — строку можно разделить на части, свернуть независимо и результаты их свёрток скомбинировать в искомое значение. Это свойство верно только для свёрточной формы строковых функций. - Можно менять направление обработки строк — из свёрточной формы можно получить функцию, читающую строку как слева-направо, так и справа-налево. Например, это позволяет преобразовать наивную функцию, вычисляющую значение многочлена, в схему Горнера. На семинаре 29 октября 2019 года рассматривалась сокращённая дефорестация и способ её реализации для языка Рефал. На нём было введено понятие свёрточной формы для строковых функций в терминах Рефала и были рассмотрены некоторые примеры функций в этой форме. Способ построения свёрточной формы на том семинаре не давался. В докладе 2 марта 2020 года мы определим свёрточную форму уже без использования терминологии Рефала, а также рассмотрим алгоритм перевода функций в свёрточную форму. Входом алгоритма будет функция, анализирующая строку по одному элементу слева-направо (или справа-налево), выходом будет свёрточная форма либо сообщение о том, что алгоритм не может её вывести. Алгоритм применим для ограниченного класса функций, т.е. не для любой функции, представимой в свёрточной форме, эту форму можно вывести. Однако, этот класс достаточно широк, что будет продемонстрировано на нескольких примерах. Вывод свёрточной формы использует ограниченную суперкомпиляцию на некоторых этапах своей работы. Ограниченность выражается в допустимых вариантах обобщения похожих конфигураций. Если в процессе требуется выполнить недопустимое обобщение, то или преобразуемая функция не представима в свёрточной форме, или она слишком сложна для этого алгоритма. В отличие от доклада 29.10.2019 для понимания этого доклада знания Рефала не требуется. ------------------------------ Гости ИПМ, которым нужен разовый пропуск, напишите мне по email или пошлите смс-ку с ФИО и НОМЕРОМ ПАСПОРТА на моб. +7 985 364 3536 до 12 час в день семинара. Пропуск получите либо в бюро пропусков в окошке слева от вахтера в главной проходной ("стеклянной", со стороны Миусской площади), либо непосредственно у вахтера. Я вам сообщу, какой вид пропуска будет оформлен. С ноутбуком, не зарегистрированным в списке на вахте на пронос в ИПМ, лучше не приходить, чтобы не споткнуться о ситуацию, когда не пропустят, а соответствующего начальства, чтобы подписать материальный пропуск на внос-вынос, не окажется на месте. ------------------------------ До встречи! Андрей Климов >
