JetBrains Research — наука, меняющая мир

​Семинар по суперкомпиляции

Суперкомпиляция - метод преобразования программ, который может использоваться как для оптимизации программ, так и для выявления и доказательства свойств программ. Составные части суперкомпиляции - прогонка, обобщение и зацикливание. Прогонка - это символическое исполнение программы, порождающее (вообще говоря - бесконечное) дерево, описывающее возможные состояние программы. Обобщение - замена описаний множеств состояний на более общее. Зацикливание - сведение множества состояний к более общему (которое уже встречалось раньше). Обобщение и зацикливание позволяют свернуть бесконечное дерево в конечный граф, из которого можно извлечь окончательный результат суперкомпиляции - остаточную программу.

В результате суперкомпиляции могут происходить такие полезные преобразования программы, как

1. устранение бесполезных частей программы

2. выполнение операций, исходные данные для которых (достаточно хорошо) известны

3. превращение многопроходных алгоритмов в однопроходные

4. устранение промежуточных структур данных.

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

Докладчик: Сергей Романенко, ИМП им. Келдыша РАН, г.Москва.

30.03.2018, 13:00.

Место: ауд. 3248, мат-мех. факультет СПбГУ, Старый Петергоф, Университетский пр-т, д. 28