Предупреждать об экранируемых предложениях #256
Description
Мотивация
Задача состоит в том, чтобы обнаруживать в функциях предложения, которые никогда не выполняются, и сообщать о них пользователю (выдавать предупреждения).
Предложение в программе может не выполняться, если его левая часть (образец+условия) описывает множество аргументов, являющихся подмножеством другого предложения, записанного выше. В таких случаях мы будем говорить что одно предложение экранирует другое.
Случай, когда не выполняется правая часть предложения с условием, сложен для автоматического анализа. Более того, такие предложения могут быть написаны намеренно ради побочного эффекта в условии и отката на последующие предложения.
Поэтому будем рассматривать случаи, когда экранирующие предложения условий не содержат. (Впрочем, условия вида , A : B тоже можно обнаруживать, но они к данной задаче не относятся.)
Экранирующие предложения такого вида могут быть написаны только по ошибке, и эта ошибка может быть достаточно коварной (не очевидной). Но при этом её вполне можно диагностировать автоматически и выдавать соответствующее предупреждение.
Для L-образцов всё довольно просто, для образцов общего вида проверить вложения — задача нетривиальная. И тут нам потребуется консультация Антонины Николаевны (@TonitaN), которая уже давно исследует этот вопрос в рамках написания модельного суперкомпилятора MSCP-A.
Старая мотивация ставила задачу оптимизации. Это сравнительно глупо (см. комментарии), поэтому она свёрнута.
Задача состоит в том, чтобы обнаруживать в функциях предложения, которые никогда не выполняются, и их удалять.
Конечно, программисты редко пишут функции с лишними предложениями, и, если пишут, то как правило по ошибке. Но всё становится интереснее, когда работает оптимизация, особенно, прогонка (для специализации мне это пока не очевидно).
Например:
Test {
e.X = <CheckAB <ReplaceAB e.X>>
}
$DRIVE CheckAB, ReplaceAB;
CheckAB {
A B e.X = FALSE;
e.X = TRUE;
}
ReplaceAB {
A B e.X = AB e.X;
e.X = e.X;
}
Функция CheckAB проверяет, начинается ли аргумент на символы A B, ReplaceAB заменяет пару символов A B в начале аргумента на один символ AB. В идеале, в оптимизированном дереве вообще не должно быть символа FALSE. Но он есть:
Test {
A B e.0#0 = TRUE;
A B e.0#0 = FALSE;
e.X#1 = TRUE;
}
Очевидно, второе предложение экранируется первым.
В чём преимущества исключения лишних предложений? Во-первых, уменьшается объём кода. Это ускоряет последующие проходы после оптимизации дерева и может ускорить весь процесс компиляции (поскольку чистка предложений сама требует времени). Это уменьшает объём исполнимого файла, а значит, он потенциально лучше будет влезать в кэш процессора. Во-вторых, оптимизатор совместного сопоставления с образцом может для таких случаев сгенерировать более эффективный код (ну, наверное, может).
Реализация
Нужна функция, которая принимает пару образцов и определяет, является ли первый подмножеством второго. На первом этапе можно использовать функцию обобщённого сопоставления — если сопоставление чистое, то образец точно вкладывается. Но вообще задача сложнее, @TonitaN не даст соврать.
Побочная задача
Задача неактуальна, обоснование в комментариях. Поэтому свёрнуто.
Оптимизатор при преобразованиях сохраняет область определения программы: если исходная функция падала на некотором аргументе, то и преобразованная функция будет падать. Например:
Test {
s.X = <F s.X>;
t.X = Term;
}
$DRIVE F;
F {
A = Symbol A;
B = Symbol B;
}
Если аргументом функции Test является один из двух символов A или B, то функция вернёт или Symbol A, или Symbol B, соответственно. Если любой другой символ — функция упадёт. Если не символ (круглые или квадратные скобки) — функция вернёт Term.
Прогонка функции F по Турчину (см. «Эквивалентные преобразования…», 197? год) расширит область определения — на любых символах, кроме A и B, функция будет выдавать Term.
Чтобы избежать такого искажения программы, компилятор добавляет вызов пустой функции:
Test {
A = Symbol A;
B = Symbol B;
s.X#1 = <F*2 s.X#1>;
t.X#1 = Term;
}
F*2 {
}
Компилятор добавил третье предложение, которое срабатывает, когда аргумент функции Test является любым символом, кроме A и B. В нём вызывается пустая функция F*2, которая падает на любом аргументе. Таким образом, область определения сохраняется.
Но есть случаи, когда такие предложения избыточны. Модифицируем функцию Test таким образом (функция F та же):
Test {
1 s.X = <F s.X>;
2 t.X = Term;
}
Оптимизированное дерево примет вид:
Test {
1 A = Symbol A;
1 B = Symbol B;
1 s.X#1 = <F*2 s.X#1>;
2 t.X#1 = Term;
}
F*2 {
}
Третье предложение можно смело исключить — область определения программы не изменится.
Избыточные «аварийные» предложения выявляются тем же механизмом. Если образец «аварийного» предложения вкладывается в один из последующих образцов, то «аварийное» предложение исключать нельзя. Иначе — можно.
Однако, следует иметь ввиду, что режекция аварийных предложений может затруднить отладку, т.к. оптимизируемая программа будет падать на один шаг раньше. Не «очищенная» программа падала на функции F*2, которая вызывалась с тем же аргументом, что и функция F в исходной программе. «Очищенная» программа будет падать сразу в функции Test. Поэтому, в отличие от устранения экранированных предложений, устранение аварийных предложений должно контролироваться пользователем.