16 марта: Доказательство свойств функциональных программ методом насыщения равенствами

Сергей Гречаник

Сергей Гречаник

Гречаник Сергей Александрович — сотрудник Института прикладной математики РАН имени М.В. Келдыша. В 2011 году окончил факультет вычислительной математики и кибернетики МГУ имени М.В. Ломоносова.

В докладе рассматривается метод преобразования программ на нестрогом функциональном языке первого порядка, основанный на комбинации методов насыщения равенствами и суперкомпиляции. Общая идея метода совпадает с идеей насыщения равенствами (предложенного в работе «Equality Saturation: A New Approach to Optimization» Тейта и др. для преобразования императивных программ) и заключается в преобразовании структуры данных, описывающей целое множество программ, а не одну программу. Используемые преобразования, однако, в основном взяты из суперкомпиляции. В рамках метода также предложено преобразование, названное слиянием по бисимуляции, соответствующее доказательству эквивалентности функций по индукции или коиндукции. Показано, что метод применим для индуктивного доказательства эквивалентности программ. Изложение основных идей метода можно найти в препринте «Полипрограммы как представление множеств функциональных программ и преобразования над ними».

Доклад состоится 16 марта 2017 года в 17:00 в Институте системного программирования РАН. Институт располагается в здании по адресу: улица Александра Солженицына, дом 25. Аудитория 110.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

*

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>