IV совместное совещание ИПС РАН — МГТУ по Рефалу

[Александр Коновалов]

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

Во вторник, 8 июня в МГТУ имени Н. Э. Баумана пройдёт традиционное

IV совместное рабочее совещание
ИПС имени А.К. Айламазяна РАН
и
МГТУ имени Н.Э. Баумана
по функциональному языку Рефал

С докладами выступят сотрудники ИПС и преподаватели и студенты МГТУ. Совещание посвящено языку программирования Рефал и метавычислениям над ним.

Адрес: ул. 2-я Бауманская, дом 5 (главный корпус). Время с 11:00 до 17:30, аудитория 330аю.

Если хотите посетить совещание — пришлите мне ФИО до понедельника 7 июня, чтобы я смог выписать разовые пропуска. Вход на проходной по паспорту.

 

Программа мероприятия

11:00–11:05 — открытие

Первая сессия, председатель Александр Коновалов

11:05–11:45 — Андрей Немытых «О языке описания свойств параметризованных конфигураций (уравнение Хмелевского в словах)»
11:45–11:50 — перерыв
11:50–12:15 — Александра Спиридонова «Построение решателя уравнений в словах методом развёртки/свёртки графа решений»
12:15–12:20 — перерыв
12:20–13:00 — Антонина Непейвода «Суперкомпиляция как основа для построения алгоритмов решения уравнений в словах»

13:00–13:30 — обед

Вторая сессия, председатель Антонина Непейвода

13:30–13:55 — Владислав Пичугин «Расширенный алгоритм обобщённого сопоставления в компиляторе Рефала-5λ»
13:55–14:00 — перерыв
14:00–14:25 — Михаил Апахов «Алгоритм прогонки вызовов рекурсивных функций, не приводящий к зацикливанию в компиляторе Рефала-5λ»
14:25–14:30 — перерыв
14:30–15:10 — Александр Коновалов «Декомпозиция вызовов функций во время суперкомпиляции путём построения выходных форматов»

15:10–15:30 — кофе

Третья сессия, председатель Андрей Немытых

15:30–15:55 — Дмитрий Сырбу «Типизация функций для Рефала-5»
15:55–16:00 — перерыв
16:00–16:25 — Евгений Шевляков «О переборных алгоритмах проверки вложения конечнозначных структур»
16:25–16:30 — перерыв
16:30–17:10 — Дмитрий Костин «Проект Aleph0 — постановка задачи для создания платформонезависимой системы управления знаниями на базе языка Refal»

17:10–17:25 — обсуждение
17:25–17:30 — закрытие

Рядом с аудиторией есть столовая и кафетерий, где можно перекусить во время перерывов.

 

Аннотации докладов

1. Андрей Немытых «О языке описания свойств параметризованных конфигураций (уравнение Хмелевского в словах)»

В суперкомпиляторе MSCP-A реализован язык описания свойств параметризованных конфигураций L специализируемой программы, основанный на языке уравнений в свободном моноиде. Необходимость в использовании языка L следует из ассоциативности операции приписывания в языке Рефал. В докладе будут обсуждаться некоторые выразительные свойства языка L.

 

2. Александра Спиридонова «Построение решателя уравнений в словах методом развёртки/свёртки графа решений»

При суперкомпиляции программ возникает задача решения уравнений в словах.

A — алфавит констант; X — алфавит строковых переменных; T₁ = T₂ — уравнение в словах, где (T₁, T₂) ∊ (A ∪ X)*×(A ∪ X)*.

Основная трудность, возникающая при их решении — отсутствие эффективного и полного алгоритма, который бы находил все решения уравнения. Реализованный алгоритм Матиясевича определяет, имеет ли уравнение в словах решение. Он основан на свёртке и развёртке дерева всех возможных решений, которое порождается некоторым «шагом прогонки», т. е. способом преобразования уравнения в множество уравнений — частных случаев исходного. Алгоритм использует для построения графа развёртки преобразования Нильсена.

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

 

3. Антонина Непейвода «Суперкомпиляция как основа для построения алгоритмов решения уравнений в словах»

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

 

4. Владислав Пичугин «Расширенный алгоритм обобщённого сопоставления в компиляторе Рефала-5λ»

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

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

 

5. Михаил Апахов «Алгоритм прогонки вызовов рекурсивных функций, не приводящий к зацикливанию в компиляторе Рефала-5λ»

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

Будет рассказано о реализации данного алгоритма в Рефале-5λ. Такой подход позволит прогонять все функции, даже рекурсивные, при этом вызовы обычных функций должны прогоняться быстрее за счёт выполнения всех прогонок за один раз.

 

6. Александр Коновалов «Декомпозиция вызовов функций во время суперкомпиляции путём построения выходных форматов»

Как известно, суперкомпиляция неплохо справляется с задачей вычисления композиции функций: вызов <F <G e.X>> в остаточной программе преобразуется в вызов одной функции <Fg e.X>, выражающей результат композиции исходных функций. Однако, простые методы суперкомпиляции не могут сделать обратное преобразование: преобразовать вызов функции исходной программы <F e.X> в композицию двух вызовов остаточной программы <F″ <F′ e.X>>.

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

 

7. Дмитрий Сырбу «Типизация функций для Рефала-5»

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

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

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

 

8. Евгений Шевляков «О переборных алгоритмах проверки вложения конечнозначных структур»

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

 

9. Дмитрий Костин «Проект Aleph0 — постановка задачи для создания платформонезависимой системы управления знаниями на базе языка Refal»

На социальном, некоммерческом подходе планируется создать прототип программного модуля, аналога даймона в Unix-подобных ОС со способом управления на основе передачи сигналов по гибридной схеме, технологии блокчейн и клиент-сервер. Вводится понятие пространства имен, в котором используются модели «владелец», «роль владельца», «время жизни программы».

В качестве базы предполагается использовать язык Refal-05, суперкомпилятор SCP-4. Операционные системы Plan9Front, OpenBSD, FreeBSD, Debian. Для Windows будет задействован эмулятор Qemu.

 

До встречи!
Александр Коновалов

[Александр Коновалов]

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

Вывешены слайды с IV совместного совещания:

http://refal.botik.ru/events/events.htm
http://refal.botik.ru/events/IPSRAN-MGTU-seminar-08-06-2021.pdf

Дмитрий Иванович Костин читал доклад без слайдов (рассказывал и писал на доске), поэтому слайдов нет. Возможно, он со временем предоставит конспект своего доклада.

 

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