Прогонка вызовов функций в условиях

Долго думал, к какой задаче: #248 или #249 написать комментарий, так и не придумал. В итоге решил вместо комментария создать заявку.

Размышления о прогонке функций в условиях
===============================
Сейчас компилятор не осуществляет ни прогонку, ни встраивание в функциях с условиями (хотя мог бы осуществлять встраивание).

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

Рассмотрим пример:
```Refal5
$ENTRY Lookup {
s.Key t.Item e.Items, : s.Key = Found ;
s.Key t.Item e.Items = ;
s.Key /* пусто */ = /* пусто */;
}

$DRIVE Key, Value;

Key { (s.Key e.Value) = s.Key }
Value { (s.Key e.Value) = e.Value }
```
Если вызов `Key` прогнать так, как прогоняют в правой части, получится
```Refal5
$ENTRY Lookup {
s.Key (s.1 e.2) e.Items, s.1 : s.Key = Found ;
s.Key t.Item e.Items, : s.Key = Found ;

s.Key t.Item e.Items = ;
s.Key /* пусто */ = /* пусто */;
}

Key*1 { }
```
Получится явная фигня. Если условие не выполняется, то управление передаётся на следующее предложение с вызовом `Key*1` в условии и программа падает. В правильном варианте если условие не выполняется, то нужно передавать управление последующим предложениям:
```Refal5
$ENTRY Lookup {
s.Key (s.1 e.2) e.Items, s.1 : s.Key = Found ;
s.Key (s.1 e.2) e.Items = ;
s.Key t.Item e.Items, : s.Key = Found ;

s.Key t.Item e.Items = ;
s.Key /* пусто */ = /* пусто */;
}

Lookup*1 {
s.Key t.Item e.Items = ;
s.Key /* пусто */ = /* пусто */;
}

Key*1 { }
```
Можно «факторизовать» первое предложение:
```Refal5
$ENTRY Lookup {
s.Key (s.1 e.2) e.Items
= s.1
: {
s.Key = Found ;
e._ = ;
};

s.Key t.Item e.Items, : s.Key = Found ;

s.Key t.Item e.Items = ;
s.Key /* пусто */ = /* пусто */;
}
```
Если продолжить факторизацию и вынести вложенную функцию вовне, то получим программу, эквивалентную рассахариванию условий:
```Refal5
$ENTRY Lookup {
s.Key (s.1 e.2) e.Items
= ;

s.Key t.Item e.Items, : s.Key = Found ;

s.Key t.Item e.Items = ;
s.Key /* пусто */ = /* пусто */;
}

Lookup′ {
s.Key s.1 (e.2) (e.Items) s.Key = Found ;
s.Key s.1 (e.2) (e.Items) e._ = ;
}
```
Программа эквивалентна программе с рассахаренными условиями с точностью до отсутствия прогонки вызова `Key`:
```Refal5
$ENTRY Lookup {
s.Key#1 t.Item#1 e.Items#1
= >;

e.Other#0 = ;
}

Lookup$1?1?0 {
s.Key#1 t.Item#1 (e.Items#1) s.Key#1 = Found ;

s.Key#1 t.Item#1 (e.Items#1) e.Other#0
= ;
}

Lookup$1?1?1 {
s.Key#1 t.Item#1 e.Items#1 = ;

s.Key#1 = /* empty */;
}
```
Функция `Lookup$1?1?1` эквивалентна функции `Lookup*1`. Рассахариватель условий устраняет здесь дублирование кода — остаток функции `Lookup` записывает как вызов `Lookup$1?1?1`, хотя делать это в сгенерированном коде необязательно.

Но факторизацию выполнять не обязательно. Если исходный образец был L-выражением, то оба соседних предложения
```Refal5
s.Key (s.1 e.2) e.Items, s.1 : s.Key = Found ;
s.Key (s.1 e.2) e.Items = ;
```
оптимизатор сопоставления с образом сопоставит один раз — факторизует неявно (за исключением случая наличия повторных s-переменных). А если образец не является L-выражением, то прогонять нельзя.

Ещё пример
--------------
```Refal5
$ENTRY F {
(e.X) e.Y, : s.Eq s.Eq = e.Y;

() e.Y = e.Y e.Y;
(e.X) e.Y = e.X;
}

$DRIVE Left, Right;

Left { s.1 e.2 = s.1 }
Right { e.2 s.2 = s.2 }
```
В условии у нас два прогоняемых вызова. Прогоним первый:
```Refal5
$ENTRY F {
(s.1 e.2) e.Y, s.1 : s.Eq s.Eq = e.Y;
(s.1 e.2) e.Y = ;
(e.X) e.Y, : s.Eq s.Eq = e.Y;

() e.Y = e.Y e.Y;
(e.X) e.Y = e.X;
}

F*1 {
() e.Y = e.Y e.Y;
(e.X) e.Y = e.X;
}

Left*1 { }
```
Вызов «аварийной функции» `Left*1` перехватит случай, когда, например, `e.X` начинается на скобочный терм. Продолжаем прогонку:
```Refal5
$ENTRY F {
(s.1 e.3 s.4) e.Y, s.1 s.4 : s.Eq s.Eq = e.Y;
(s.1 e.3 s.4) e.Y = ;
(s.1) e.Y, s.1 s.1 : s.Eq s.Eq = e.Y;
(s.1) e.Y = ;
(s.1 e.2) e.Y, s.1 : s.Eq s.Eq = e.Y;
(s.1 e.2) e.Y = ;
(e.X) e.Y, : s.Eq s.Eq = e.Y;

() e.Y = e.Y e.Y;
(e.X) e.Y = e.X;
}

F*1 {
() e.Y = e.Y e.Y;
(e.X) e.Y = e.X;
}

Left*1 { }
Right*1 { }
```
Не смотря на то, что после первой прогонки у нас после предложения с условием появились новые предложения, мы вызываем ту же функцию `F*1`. Вроде это правильно.

Теперь прогоним сами условия (#248):
```Refal5
$ENTRY F {
(s.Eq e.3 s.Eq) e.Y = e.Y;
(s.1 e.3 s.4) e.Y = ;
(s.1) e.Y = e.Y;
(s.1) e.Y = ; /* № 1 */
(s.1 e.2) e.Y, s.1 : s.Eq s.Eq = e.Y;
(s.1 e.2) e.Y = ; /* № 2 */
(e.X) e.Y, : s.Eq s.Eq = e.Y;

() e.Y = e.Y e.Y;
(e.X) e.Y = e.X;
}
```
Получаем несколько тонко экранированных предложений. Предложение, помеченное как № 1, скрывается из-за того, что предшествующее условие всегда истинное. Предложение № 2 скрывается из-за того, что в условии предыдущего находится вызов аварийной функции.

Случай № 1 экранирования возникает, если разрешение условия не даёт сужений. Но ведь тогда образцы двух соседних предложений будут просто совпадать дословно. Такой случай экранирования элементарно распознаётся автоматически.

Случай № 2 в общем случае распознать труднее. Нужно, во-первых, распознавать вызовы функций-enum’ов, во-вторых, ситуации, когда два соседних предложения имеют одинаковые образцы. Технически распознать можно, но возни больше.

Промежуточные выводы
-----------------------------
* Таким образом, прогонка (с сужениями) функций в условиях не так проста, как кажется. Образец должен быть L-выражением, при прогонке формируются два предложения, а не одно, нужно вызывать остаточную функцию.
* Рассахариватель условий позволяет осуществлять прогонку в условиях, код будет близок к тому, что должно происходить в конечном результате.
* Возможно появление экранированных предложений. Некоторые случаи экранирования распознаются тривиально.

Доработка рассахаривателя условий
=========================
Выше показано, что правильная реализация прогонки в условиях напоминает результат рассахаривания условий. Поэтому можно рассмотреть два варианта реализации такой прогонки:
* непосредственная реализация с удвоением предложений,
* точечное рассахаривание условия с прогоняемой функцией.

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

Во-первых, нужно будет рассахаривать первое условие в одном предложении. Если другие предложения содержат условия, но в них ничего интересного (прогонки с сужениями) нет, то их трогать не надо. Т.е. нужна отдельная входная точка, принимающая функцию и номер предложения (или просто само предложение).

Во-вторых, даже для обычного режима рассахаривания условий имеет смысл сделать поправки.
* В исходной функции сворачивать остальные предложения в одно с вызовом функции-«континуации» не надо. Исходно так было сделано для упрощения чтения сгенерированного кода — преобразователь Рефала-5 в базисный Рефал был экспериментальным проектом. Сейчас в этом нет необходимости.

А вот повлиять на быстродействие такое решение может. Во-первых, если образец предложения с условием не подошёл, требуется лишний шаг рефал-машины. Накладные расходы крошечные, но они есть. Во-вторых, оптимизация #252 таким функциям не сможет назначить шаблон специализации, т.к. будет выводить его как ГСО образцов, а последний образец — e-переменная.
* Функции-«континуации» нужно называть не `Func$x?y?z`, а `Func*x` для единообразия.
* Вспомогательные функции можно оптимизировать. В отличие от огульной прогонки всех встроенных функций, здесь это безопасно (#278).
- Образцы функций `_forward` часто могут быть L-выражениями, поэтому их имеет смысл прогонять.
- Функции `_next` ~~прогонять нельзя — они являются «базисными»~~ (https://github.com/bmstu-iu9/refal-5-lambda/issues/252#issuecomment-626916355).
**UPD:** нет, они не являются базисными. Базисной здесь является только функция `_check`.
Возможно, стоит добавить узел дерева `(Basic e.Name)` или даже директиву `$BASIC`, принудительно помечающую базисные функции. При обходе графа явные базисные функции являются корнями, при их обнаружении вниз не спускаемся.
В контексте этой задачи базисными логично помечать функции `_next`: в них удлиняются открытые переменные.
- Функцию `_check` прогонять можно — это обеспечит возможность прогонки условий (#248).
- Также функцию `_check` можно специализировать по переменным контекста — это обеспечит передачу информации при прогонке функций из условия в правую часть.
- Как строить шаблон специализации для остальных функций — мне пока не очевидно. Да и не нужно — прогонка в предложениях с не-L-образцами редко когда возможна.

Про функции `_forward`, `_next` и `_check`: [Подход%20к%20преобразованию%20условий.md](https://github.com/bmstu-iu9/refal-5-lambda/blob/master/doc/5-to-basis/Подход%20к%20преобразованию%20условий.md).

Доработать, как предложено, рассахариватель условий нужно. А вот делать точечное рассахаривание, скорее всего, не надо. Либо можно делать при не-L-образцах, что тоже сомнительно.

Кстати, интересно оценить соотношение по быстродействию в режимах «без оптимизаций», `-OD+`, `-OC-`, `-OC- -OD+`. В работе Анастасии Козловой @Anastasya34 выполнялось тестирование для нескольких программ кроме компилятора Рефала-5λ, поскольку в нём условия ещё не использовались. Интересно повторить замеры. Также интересно померить быстродействие MSCP-A (@TonitaN), в котором условия применяются очень широко — оптимизация `_check`-функций могла бы дать заметный прирост.