refal-5-lambda
refal-5-lambda copied to clipboard
bmstu-iu9
Прогонка вызовов функций в условиях
Долго думал, к какой задаче: #248 или #249 написать комментарий, так и не придумал. В итоге решил вместо комментария создать заявку.
Размышления о прогонке функций в условиях
Сейчас компилятор не осуществляет ни прогонку, ни встраивание в функциях с условиями (хотя мог бы осуществлять встраивание).
Выше предлагается прогонять функции в первом условии и встраивать в остальных. Но прогонять функцию нужно не так, как в результатной части.
Рассмотрим пример:
$ENTRY Lookup {
s.Key t.Item e.Items, <Key t.Item> : s.Key = Found <Value t.Item>;
s.Key t.Item e.Items = <Lookup s.Key e.Items>;
s.Key /* пусто */ = /* пусто */;
}
$DRIVE Key, Value;
Key { (s.Key e.Value) = s.Key }
Value { (s.Key e.Value) = e.Value }
Если вызов Key прогнать так, как прогоняют в правой части, получится
$ENTRY Lookup {
s.Key (s.1 e.2) e.Items, s.1 : s.Key = Found <Value t.Item>;
s.Key t.Item e.Items, <Key*1 t.Item> : s.Key = Found <Value t.Item>;
s.Key t.Item e.Items = <Lookup s.Key e.Items>;
s.Key /* пусто */ = /* пусто */;
}
Key*1 { }
Получится явная фигня. Если условие не выполняется, то управление передаётся на следующее предложение с вызовом Key*1 в условии и программа падает. В правильном варианте если условие не выполняется, то нужно передавать управление последующим предложениям:
$ENTRY Lookup {
s.Key (s.1 e.2) e.Items, s.1 : s.Key = Found <Value (s.1 e.2)>;
s.Key (s.1 e.2) e.Items = <Lookup*1 s.Key (s.1 e.2) e.Items>;
s.Key t.Item e.Items, <Key*1 t.Item> : s.Key = Found <Value t.Item>;
s.Key t.Item e.Items = <Lookup s.Key e.Items>;
s.Key /* пусто */ = /* пусто */;
}
Lookup*1 {
s.Key t.Item e.Items = <Lookup s.Key e.Items>;
s.Key /* пусто */ = /* пусто */;
}
Key*1 { }
Можно «факторизовать» первое предложение:
$ENTRY Lookup {
s.Key (s.1 e.2) e.Items
= s.1
: {
s.Key = Found <Value (s.1 e.2)>;
e._ = <Lookup*1 s.Key (s.1 e.2) e.Items>;
};
s.Key t.Item e.Items, <Key*1 t.Item> : s.Key = Found <Value t.Item>;
s.Key t.Item e.Items = <Lookup s.Key e.Items>;
s.Key /* пусто */ = /* пусто */;
}
Если продолжить факторизацию и вынести вложенную функцию вовне, то получим программу, эквивалентную рассахариванию условий:
$ENTRY Lookup {
s.Key (s.1 e.2) e.Items
= <Lookup′ s.Key s.1 (e.2) (e.Items) s.1>;
s.Key t.Item e.Items, <Key*1 t.Item> : s.Key = Found <Value t.Item>;
s.Key t.Item e.Items = <Lookup s.Key e.Items>;
s.Key /* пусто */ = /* пусто */;
}
Lookup′ {
s.Key s.1 (e.2) (e.Items) s.Key = Found <Value (s.1 e.2)>;
s.Key s.1 (e.2) (e.Items) e._ = <Lookup*1 s.Key (s.1 e.2) e.Items>;
}
Программа эквивалентна программе с рассахаренными условиями с точностью до отсутствия прогонки вызова Key:
$ENTRY Lookup {
s.Key#1 t.Item#1 e.Items#1
= <Lookup$1?1?0 s.Key#1 t.Item#1 (e.Items#1) <Key t.Item#1>>;
e.Other#0 = <Lookup$1?1?1 e.Other#0>;
}
Lookup$1?1?0 {
s.Key#1 t.Item#1 (e.Items#1) s.Key#1 = Found <Value t.Item#1>;
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>;
}
Lookup$1?1?1 {
s.Key#1 t.Item#1 e.Items#1 = <Lookup s.Key#1 e.Items#1>;
s.Key#1 = /* empty */;
}
Функция Lookup$1?1?1 эквивалентна функции Lookup*1. Рассахариватель условий устраняет здесь дублирование кода — остаток функции Lookup записывает как вызов Lookup$1?1?1, хотя делать это в сгенерированном коде необязательно.
Но факторизацию выполнять не обязательно. Если исходный образец был L-выражением, то оба соседних предложения
s.Key (s.1 e.2) e.Items, s.1 : s.Key = Found <Value (s.1 e.2)>;
s.Key (s.1 e.2) e.Items = <Lookup*1 s.Key (s.1 e.2) e.Items>;
оптимизатор сопоставления с образом сопоставит один раз — факторизует неявно (за исключением случая наличия повторных s-переменных). А если образец не является L-выражением, то прогонять нельзя.
Ещё пример
$ENTRY F {
(e.X) e.Y, <Left e.X> <Right e.X> : 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 }
В условии у нас два прогоняемых вызова. Прогоним первый:
$ENTRY F {
(s.1 e.2) e.Y, s.1 <Right s.1 e.2> : s.Eq s.Eq = e.Y;
(s.1 e.2) e.Y = <F*1 (s.1 e.2) e.Y>;
(e.X) e.Y, <Left*1 e.X> <Right e.X> : 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 начинается на скобочный терм. Продолжаем прогонку:
$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 = <F*1 (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 = <F*1 (s.1) e.Y>;
(s.1 e.2) e.Y, s.1 <Right*1 s.1 e.2> : s.Eq s.Eq = e.Y;
(s.1 e.2) e.Y = <F*1 (s.1 e.2) e.Y>;
(e.X) e.Y, <Left*1 e.X> <Right e.X> : 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):
$ENTRY F {
(s.Eq e.3 s.Eq) e.Y = e.Y;
(s.1 e.3 s.4) e.Y = <F*1 (s.1 e.3 s.4) e.Y>;
(s.1) e.Y = e.Y;
(s.1) e.Y = <F*1 (s.1) e.Y>; /* № 1 */
(s.1 e.2) e.Y, s.1 <Right*1 s.1 e.2> : s.Eq s.Eq = e.Y;
(s.1 e.2) e.Y = <F*1 (s.1 e.2) e.Y>; /* № 2 */
(e.X) e.Y, <Left*1 e.X> <Right e.X> : 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. - Образцы функций
Доработать, как предложено, рассахариватель условий нужно. А вот делать точечное рассахаривание, скорее всего, не надо. Либо можно делать при не-L-образцах, что тоже сомнительно.
Кстати, интересно оценить соотношение по быстродействию в режимах «без оптимизаций», -OD+, -OC-, -OC- -OD+. В работе Анастасии Козловой @Anastasya34 выполнялось тестирование для нескольких программ кроме компилятора Рефала-5λ, поскольку в нём условия ещё не использовались. Интересно повторить замеры. Также интересно померить быстродействие MSCP-A (@TonitaN), в котором условия применяются очень широко — оптимизация _check-функций могла бы дать заметный прирост.
Если помечать _check-функции как прогоняемые, то пометка обеспечит прогонку при L-образцах. Однако, при открытых переменных _check-функции неизбежно пометятся как базисные, метки (Drive …) для них сотрутся. Без автоматической разметки прогонка только _check- и _forward-функций безопасна.
Да пускай будет на диплом! Пипец будет сливать правки по данной задаче и задаче #340, но к следующему семестру я что-нибудь придумаю.
Подозреваю, что по описанному принципу (добавление предложений с вызовом «хвоста») можно прогонять вызовы не только в первом условии, но и во всех остальных, а также в правой части. Ограничение только в том, что переменные, появившиеся в условиях, не могут сужаться. В такой постановке эта задача становится более общим случаем задачи #231 в части прогонки вызовов функций в предложениях с условиями.
~~Но пока мне этот тезис не полностью очевиден.~~ Не, должно работать.
Так что задача #231 прилипает к этой задаче как составная часть.
@torrentino555 ушёл к другому научному руководителю. Тема на ВКР не выбрана.