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

**ВНИМАНИЕ!** Исходная постановка задачи со временем потеряла актуальность на 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 e.D;
}

H {
s.A e.B s.A e.D = e.B 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;
}
```
Вызов `` даст `(()) (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’А!