Прогонка и встраивание функций в Рефале-5λ

[Mazdaywik]

Эта задача — подзадача для #91. Подробнее о встраивании и прогонке см. в #91.

Основные расширения синтаксиса

1. Добавить синтаксис во front-end Простого Рефала, позволяющий отдельно задавать свойства функций в виде списка имён ($ENTRY, $INLINE и т.д.)

Foo {
  …
}

Bar {
  …
}

$ENTRY Foo, Bar;
$INLINE Bar;

2. Во front-end’е Простого Рефала добавить поддержку ключевого слова $INLINE перед именем функции (по аналогии с $ENTRY):

$INLINE Apply { … }

3. Во front-end’е Рефала-5λ добавить псевдокомментарий *$INLINE (уточнение: эту часть задачи делаю я, @Mazdaywik):

*$INLINE Foo, Bar;

4. Реализовать поддержку встраивания функций как один из проходов обессахаривателя. Семантика встраивания достаточно подробно описана в задаче Встраивание и специализация функций в Рефале-5λ #91.

Нюанс — встраивание и прогонка

В задаче #91 предлагается реализовать механизм прогонки с расщеплением предложений:

$INLINE Foo {
  s.X = s.X s.X
  ((e.Y)) = (((e.Y)));
}

Bar {
  t.X = #A;
  t.X t.Y t.Z = <Foo t.Y>;
  e.K = #B;
}

 ↓ ↓ ↓

Bar {
  t.X = #A;
  t.X s.X1 t.Z = s.X1 s.X1;
  t.X ((e.Y1)) t.Z = (((e.Y1)));
  t.X t.Y t.Z = <Foo1 t.Y>;
  e.K = #B;
}

$ENUM Foo1;

Достоинство данного механизма: повышается глубина оптимизации. Недостаток — для рекурсивных встраиваемых функций он будет зацикливаться. Поэтому предлагается ввести два ключевых слова: $INLINE для простого встраивания (не меняющего левую часть) и $DRIVE для прогонки (соответственно, *$INLINE и *$DRIVE для Рефала-5λ).

Список литературы

Теоретической основой данной задачи являются прежде всего две работы Турчина.

• В. Ф. Турчин. Эквивалентные преобразования рекурсивных функций, описанных на языке РЕФАЛ. В cб.: Труды симпозиума “Теория языков и методы построения систем программирования”, Киев-Алушта: 1972. Стр. 31-42. (djvu скан), (pdf скан), (djvu LaTeX), (pdf LaTeX)
• В. Ф. Турчин. Эквивалентные преобразования программ на РЕФАЛе. В cб.: Труды ЦНИПИАСС “Автоматизированная система управления строительством”, выпуск 6, М: 1974. Стр. 36-68. (djvu), (pdf).

Следует иметь ввиду, что в этих материалах рассматриваются L-выражения — жёсткие выражения без t-переменных. При реализации прогонки в Простом Рефале следует описанные алгоритмы аккуратно расширить на t-переменные.

[Mazdaywik]

Турчин формулировал свои эквивалентные преобразования (см. выше) для L-выражений, которые представляют собой жёсткие выражения, в которых разрешены повторные s-переменные и запрещены любые t-переменные.

Я сегодня спросил в рассылку [email protected], можно ли добавить в алгоритмы эквивалентных преобразований неодноимённые t-переменные:

https://www.mail-archive.com/[email protected]/msg00100.html

Андрей Климов мне ответил, что можно:

https://www.mail-archive.com/[email protected]/msg00101.html

Никаких теоретических ограничений на это нет, просто Турчин ради компактности и бритвы Оккама исключил и их тоже.

[Mazdaywik]

Ещё одна хорошая статья по нашей теме:

Ан. В. Климов, С. А. Романенко. Метавычислитель для языка Рефал. Основные понятия и примеры. М.:ИПМ им.М.В.Келдыша АН СССР, 1987, препринт N 71. - 32 с.
http://pat.keldysh.ru/~roman/doc/1987-Klimov_Romanenko--Metavychislitel%27_dlya_yazyka_Refal.pdf

В нашей терминологии Климов и Романенко в статье предлагали встраивание и прогонку единственных сужений (см. статью) для всех функций, неограниченную прогонку — для явно указанных пользователем.

Интересно то, что при встраивании (они это называют частичным вычислением) Климов и Романенко допускают обобщённое сопоставление с произвольным образцом (включая открытые e-переменные). Стоит подумать об этом.

Прогонка единственных сужений также нам может быть интересна.

[Mazdaywik]

@madnaaaaas, в работе

С. А. Романенко. Рефал-4 - расширение Рефала-2, обеспечивающее выразимость результатов прогонки. М.:ИПМ им.М.В.Келдыша АН СССР, 1987, препринт N 147. - 27 с.
http://pat.keldysh.ru/~roman/doc/1987-Romanenko--Refal-4_-_rasshirenie_Refala-2.pdf

важно прочитать и понять «Введение» и «1. Содержательная сущность прогонки».

Если кратко — базисный Рефал не замкнут относительно преобразования прогонки, т.е. результат прогонки не выразим средствами базисного Рефала. Поэтому Турчин перешёл к ограниченному Рефалу, в котором запрещены t-переменные и открытые и повторные e-переменные. Прогонка в этом подмножестве замкнута (хотя туда можно добавить неповторные t-переменные, см. выше).

Романенко предлагает другой вариант — расширение языка до надмножества, на котором прогонка тоже будет замкнута (ещё можно посмотреть вот сюда: http://pat.keldysh.ru/~roman/doc/1987-Romanenko--Progonka_dlya_programm_na_Refale-4.pdf, только введение и заключение).

В нашем случае на выходе обессахаривателя и на входе back-end’а мы имеем базисный Рефал с условиями (#17) и конструктором замыкания. Поэтому предлагается осуществлять встраивание и прогонку только для жёстких выражений с повторными s-переменными, они же L-выражения с неповторными t-переменными.

[Mazdaywik]

По поводу прогонки с t-переменными. Есть вот такая работа:

С.М. Абрамов. Обобщенный алгоритм отождествления для языка Рефал. - Курсовая работа, 1979. - 85 с. DJVU PDF

Правда, это больше похоже не на курсовую работу, а на черновик, что вполне логично — курсовая остаётся на кафедре, а черновик может отстаться у студента (или научрука).

В общем, в этой работе L-выражения пополняются неповторными t-переменными и v-переменными (непустыми e-переменными). Работу лучше не читать — в ней громоздкие математические доказательства, из которых строится математизированное описание алгоритма.

На самом деле, если чисто интуитивно добавить t-переменные в эквивалентные преобразования Турчина, получится не хуже.

Кроме того, Сергей Абрамов в работе также ставил задачу вычисления разности между классами, задаваемыми образцами и рестрикциями (неравенствами), что тоже сильно усложнило его алгоритм.

[Mazdaywik]

Задачу забрал себе, исключил веху study spring 2018, поскольку Дамир не восстановился.

[Mazdaywik]

Готово! Если вдруг всплывут ошибки, на них заведу отдельные заявки.

[Mazdaywik]

@InfiniteDisorder попросил открыть задачу.