Разметка неразменных аргументов для прогонки

[Mazdaywik]

ВНИМАНИЕ! Исходная постановка задачи со временем потеряла актуальность на 60 %. Неактуальный кусок я завернул в складку. Наиболее точная постановка задачи сейчас — в комментарии https://github.com/bmstu-iu9/refal-5-lambda/issues/231#issuecomment-746839544.

Неактуальный кусок свёрнут

Цель === Размечать сужаемые и несужаемые аргументы для прогоняемых функций шаблоном, аналогичным шаблону `$SPEC`. Мотивация ======== Я переписывался по почте с @ArkadyKlimov и в ходе переписки у нас сформировалась идея о более тонком управлении прогонкой и встраиванием. Ключевое слово `$DRIVE` при прогонке разрешает сужения переменных в аргументе, т.е. при наличии нескольких решений с сужениями предложение с вызовом размножается, а полученные сужения подставляются в левые его части. Ключевое слово `$INLINE` разрешает только прогонку без сужений, т.е. замену вызова встраиваемой функции на её спекулятивно вычисленный результат без какой-либо другой модификации вызывающей функции. Прогонку с расщеплением от встраивания пришлось отделить ради оптимизации тех функций, прогонка с расщеплением которых будет выполняться бесконечно. Например, библиотечная функция `Apply`: https://github.com/bmstu-iu9/refal-5-lambda/blob/4ed95a0af96abfda5654ba8e4c7bf9ad680c4427/src/srlib/common/LibraryEx.refi#L4-L17 Прогонка с расщеплениями `Apply` будет выполняться бесконечно, причём там, где это совершенно избыточно. Например, в функции `Map`, где она вызывается с термом общего вида. Там её вообще не надо оптимизировать. Но есть интересные функции, которые не ложатся в это прокрустово ложе. Например, `OneOf`: ``` OneOf { t.SearchFor t.SearchFor e.Set = True; t.SearchFor t.Other e.Set = ; t.SearchFor /* пусто */ = False; } ``` Если эту функцию пометить как `$DRIVE`, то вызов `` прогонится замечательно. Но с другой стороны, вызов `` приведёт к зацикливанию. Что делать? Формат функции `OneOf` такой: Рекурсивный вызов во втором предложении применяется к части аргумента `e.Set` из-за чего происходит зацикливание. Следовательно, для (e-)переменных, попадающих в аргумент `e.Set`, сужение разумно запретить. Аргумент `t.SearchFor` сужается только в точке выхода из рекурсии (повторная переменная), на остальных он передаётся как есть. А для нерекурсивных вызовов сужение безопасно. Таким образом, для параметра `e.Set` прогонка должна вести себя как `$INLINE`, для `t.SearchFor` — как `$DRIVE`. Есть случай, когда прогонка некоторых переменных запрещена, поскольку физически невозможна — для «неразменных» переменных, которыми заменяют вызовы функций при попытке прогонки вызова с активным аргументом (#230). Здесь (e-)переменные в `e.Set` прогонять нельзя, поскольку это небезопасно — приведёт к зацикливанию. Таким образом, приходим к тому, что для обеспечения безопасности (терминируемости) прогонки нужно размечать переменные в аргументах как разменные и неразменные. Если прогонка требует сужения неразменной переменной, данный вызов просто считается не подлежащим оптимизации. Функции, помеченные как `$DRIVE` и `$INLINE` становятся просто частными случаями: у первых все переменные разменные, у вторых — все неразменные. Реализация ======== Предлагается добавить шаблоны следующего вида ``` $DRIVE FuncName шаблон; ``` где `шаблон` — жёсткое выражение. Индексы переменных в шаблоне роли не играют, за исключением первого знака их индекса. Если он является заглавной буквой, то параметр считается «разменным», если со строчной буквы, прочерка, дефиса или цифры — «неразменным». Семантика следующая. Для вызова прогоняемой функции выполняется сопоставление аргумента с шаблоном. Если оно чистое, то переменные, попавшие в неразменные параметры, становятся неразменными, т.е. сужения по ним запрещаются. Если сопоставление не удалось, то либо вызов не оптимизируется, либо просто все переменные считаются неразменными. В отличие от специализации, соответствия предложений прогоняемой функции шаблону не требуется. Побочный эффект и связи с другими задачами ================================ Во-первых, механизм пометки переменных как неразменных необходим в задаче #230. Поэтому достаточно просто строить множество неразменных переменных, которое является объединением переменных для вложенных вызовов и переменных, попавших под маску.

Во-вторых, неразменные переменные возникают в предложениях с условиями (они сейчас не оптимизируются). Если в вызове функции участвуют переменные как из образца предложения, так и из образца предшествующего условия, то первые переменные сужать можно (если они, конечно, из жёсткого образца образца-L-выражения), а вторые — нельзя. Реализация: в «мешок неразменных переменных» добавляются переменные из условий.

В-третьих, можно ограниченно разрешать прогонку с расщеплениями даже для не-L-образцов. Например:

$DRIVE F;

F {
  A = 1; B = 2; C = 3;
}

G {
  e.B s.A e.D = e.B <F s.A> e.D;
}

H {
  s.A e.B s.A e.D = e.B <F s.A> e.D;
}

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

G′ {
  e.B A e.D = e.B 1 e.D;
  e.B B e.D = e.B 2 e.D;
  e.B C e.D = e.B 3 e.D;
}

Вызов <G (()) (Z) B (Y) A ((X))> даст (()) (Z) 2 (Y) A ((X)), вызов G′ от того же аргумента — (()) (Z) B (Y) 1 ((X)), а оптимизация должна сохранять семантику.

Напротив, прогонка функции H будет полностью безопасной:

H′ {
  A e.B A e.D = e.B 1 e.D;
  B e.B B e.D = e.B 2 e.D;
  C e.B C e.D = e.B 3 e.D;
}

Не существует такого аргумента, где функции H и H′ давали бы разный результат.

Почему? Потому что в G переменная s.A получает своё значение внутри цикла удлинения открытой переменной, в функции H — до цикла.

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

Очевидно, в случаях не-L-образцов точно также из образца извлекается набор переменных, по которым сужения делать нельзя — «неразменных» переменных.

БОЛЬШЕ AD HOC’А ДЛЯ БОГА AD HOC’А!

[Mazdaywik]

@TonitaN, ты хорошо разбираешься в прогонке с образцами общего вида. Тебе есть чего-нибудь добавить интересного к приведённым выше рассуждениям?

[Mazdaywik]

Задача вполне пригодна для курсовой работы по компиляторам. Причём целиком — не только шаблон, но и описанное в разделе «Побочный эффект…».

[Mazdaywik]

Задача #230 — естественная подзадача этой задачи.

[Mazdaywik]

Задача не была выбрана в качестве курсовой.

[Mazdaywik]

Задача не была выбрана в качестве ВКР.

[Mazdaywik]

Неразменные переменные и не-L-образцы

С прогонкой для не-L-образцов тоже всё непросто. В примере из постановки задачи всё красиво:

$DRIVE F;

F {
  A = 1; B = 2; C = 3;
}

…

H {
  s.A e.B s.A e.D = e.B <F s.A> e.D;
}
  ↓   ↓   ↓   ↓   ↓   ↓   ↓

H′ {
  A e.B A e.D = e.B 1 e.D;
  B e.B B e.D = e.B 2 e.D;
  C e.B C e.D = e.B 3 e.D;
}

А вот пример, где всё некрасиво:

$DRIVE Fa;

Fa {
  A = AA;
  s.X = (s.X);
}

Test {
  s.P  e._ s.P e._ = Found <Fa s.P>;
  s.P e._ = NotFound;
}

Прогонка нам даст

Test {
  A e._ A e._ = Found AA;
  s.P e._ s.P e._ = Found (s.P);
  s.P e._ = NotFound;
}

Что получится для вызова <Test A 1 2 3 4 5 6 … 97 98 99 100>? Получится два по открытой переменной. Сначала не сопоставится образец с первым предложением. Потом со вторым.

Можно привести пример, что для однозначных образцов с повторными t-, e-переменными прогонка тоже приведёт к потере производительности.

Поэтому неразменные переменные сами по себе никак не помогают прогонке с не-L-образцами.

[Mazdaywik]

Задача #314 подразумевает отказ от точной разметки $DRIVE/$INLINE, в том числе и отказ от шаблона неразменных аргументов. Поэтому синтаксис

$DRIVE 〈имя〉 〈шаблон〉;

уходит в утиль. Прогоняемая функция с шаблоном есть вариант встраиваемой функции.

Если функция пригодна для встраивания (в том числе и «смешанного» с шаблоном неразменных переменных), то её расширенная специализация (#251) построит конечный набор экземпляров, часть из которых можно будет затем прогнать. Поэтому при решении #314 и #251 шаблон неразменных переменных становится избыточен.

Остальные соображения про неразменные переменные в топике и комментариях выше остаются актуальными.

[Mazdaywik]

Задача пригодна для курсовой работы.

[Mazdaywik]

На самом деле, здесь всё не так просто. И, если разобраться, эта задача — частный случай задачи #283.

Если имеем L-образец с условиями, то прогонять нужно как в #283 — между новыми предложениями нужно будет добавлять предложения перехода на хвост. «Разменными» переменными будут только предложения из образца, но не предложения из условий.

Если мы имеем не-L-образец, но образец мы можем представить как пару наиболее сложного L-образца и набора сужений, переводящих его в исходный образец. Можем заменить исходный образец на L-образец, а сужения представить как условия-сужения при нём. Задача сводится к предыдущей (L-образец с условиями). В актуальной реализации преобразование сужений в условия не оптимально, т.к. требуется копировать значения. Но с оптимизацией #257 это проблемой не будет. К тому же такое преобразование можно делать виртуальные.

В примере выше получится так:

$DRIVE Fa;

Fa {
  A = AA;
  s.X = (s.X);
}

Test {
  s.P e._ s.P e._ = Found <Fa s.P>;
  s.P e._ = NotFound;
}

Преобразуем Test в L-образец с условием:

Test {
  s.P e.1, e.1 : e._ s.P e._ = Found <Fa s.P>;
  s.P e._ = NotFound;
}

Прогоняем:

Test {
  A e.1, e.1 : e._ A e._ = Found AA;
  A e.1 = <Test*1 A e.1>;
  s.X e.1, e.1 : e._ s.X e._ = Found (s.X);
  s.X e.1 = <Test*1 s.X e.1>;
  s.P e._ = NotFound;
}

Test*1 {
  s.P e._ = NotFound;
}

(очевидно, предложение-переход перед последней функцией добавлять не обязательно)

Поскольку преобразования виртуальные, результат будет такой:

Test {
  A e._ A e._ = Found AA;
  A e.1 = <Test*1 A e.1>;
  s.X e._ s.X e._ = Found (s.X);
  s.X e.1 = <Test*1 s.X e.1>;
  s.P e._ = NotFound;
}

Результат эффективный. Но вообще, эта задача должна быть частью #283.

[Mazdaywik]

В свете вышеизложенного + https://github.com/bmstu-iu9/refal-5-lambda/issues/283#issuecomment-746885017 задача уходит на ВКР как существенно перекрывающаяся с #283.

[Mazdaywik]

@torrentino555 ушёл к другому научному руководителю, тема на ВКР не выбрана.