search

bmstu-iu9 / refal-5-lambda

Компилятор Рефала-5λ
https://bmstu-iu9.github.io/refal-5-lambda
Other
79 stars 35 forks source link

Понятный аварийный дамп для специализированных функций #240

Closed Mazdaywik closed 4 years ago

Mazdaywik commented 5 years ago

Мотивация

Так получилось, что основным отладочным средством Рефала-5λ является аварийный дамп. По нему можно посмотреть, в каком именно состоянии программа была на момент падения, какая именно функция упала из-за неверного аргумента на входе.

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

Конечно, можно перекомпилировать программу с логом и попытаться разобраться по содержимому лога. Но это не эффективно — логирование заметно замедляет компиляцию, для поиска ошибки компиляцию и запуск придётся повторить.

Как сделано в прогонке?

Почему нет подобной задачи про оптимизацию прогонки? Потому что там с отладкой всё в порядке. Оптимизируемая (встраиваемая или прогоняемая) функция вида

F {
  Pat1 = Res1;
  Pat2 = Res2;
  Pat3 = Res3;
}

интерпретируется как

F {
  Pat1 = Res1;
  e.X = <F*1 e.X>;
}

F*1 {
  Pat2 = Res2;
  e.X = <F*2 e.X>;
}

F*2 {
  Pat3 = Res3;
  e.X = <F*3 e.X>;
}

F*3 { /* нет предложений */ }

и при этом функции F*1 и F*2 считаются оптимизируемыми также, как и исходная.

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

Самое интересное в контексте задачи: отладку обеспечивает функция F*3. Если функция полностью прогналась с сужениями, то в вызывающую функцию будет добавлено предложение совпадающее с исходным, но содержащее <F*3 …> вместо исходного <F …>. И, если ни одно из исходных предложений оказалось неприменимым, то точно также окажутся неприменимыми предложения, построенные прогонкой. И программа упадёт на <F*3 …>. Дамп аварийного вызова функции оптимизированной программы от неоптимизированной будет отличаться лишь именем F*3 вместо исходного F.

У Турчина, кстати, подобное предложение не вставлялось, поэтому аварийный останов исходной программы приводил бы к продолжению вычислений оптимизированной. Управление передавалось бы на предложение, следующее за оптимизированным предложением. И программа либо падала бы в другом месте, либо выдавала бы какой-то ответ (скорее всего, неверный).

Что делать со специализацией?

Сделать нужно примерно тоже самое. Чтобы в дампе первичное активное подвыражение со специализацией совпадало с ним же без специализации с точностью до имени функции.

Т.е. сейчас у нас так. Если падает функция Func, но после специализации может падать функция, скажем, Func@3 с перетасованным аргументом и неизвестным телом. Нужно обеспечить, чтобы в дампе отображалась функция Func… с тем же аргументом, что и в исходной программе. Тогда пользователь может сопоставить аргумент в дампе телу функции и понять, что же здесь не так.

Реализация

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

Нумерация специализируемых функций начинается с единицы: Map@1, Map@2, Map@3… Поэтому имя Map@0 свободно. Его можно использовать как пустую функцию для аварийного дампа.

Модификация тела функции не сложна. Для этого в конец нужно добавить предложение вида

шаблон = <Func@0 шаблон>;

где шаблон — шаблон, указанный в $SPEC.

Почему это будет работать? При специализации образцы перекраиваются, в остальные части предложений (условия и результатное выражение) вместо статических параметров подставляются соответствующие выражения из сигнатуры. Поэтому если выполнение в специализированной функции дойдёт до последнего предложения, аргументом функции Func@0 будет то самое выражение, на котором бы упала функция Func в исходной программе. А Func@0 пустая, на ней программа упадёт.

Пример:

$SPEC Select s.no t.FIRST t.SECOND;

Select {
  1 t.First t.Second = t.First;
  2 t.First t.Second = t.Second;
}

$ENTRY F { s.X (e.Y) (e.Z) = <Select s.X (e.Y e.Z) (e.Z e.Y)> }

При специализации её тело будет рассматриваться как

Select {
  1 t.First t.Second = t.First;
  2 t.First t.Second = t.Second;
  s.no t.FIRST t.SECOND = <Select@0 s.no t.FIRST t.SECOND>;
}

Select@0 { /* нет предложений */ }

Сигнатура вызова: e.Y e.Z ← t.FIRST, e.Z e.Y ← t.SECOND. После специи программа примет вид (примерно):

Select@1 {
  1 (e.Y) (e.Z) = (e.Y e.Z);
  2 (e.Y) (e.Z) = (e.Z e.Y);
  s.no (e.Y) (e.Z) = <Select@0 s.no (e.Y e.Z) (e.Z e.Y)>;
}

Select@0 { /* нет предложений */ }

$ENTRY F { s.X (e.Y) (e.Z) = <Select@1 s.X (e.Y) (e.Z)>;

Вызов <F 3 ('ab') ('cd')> в исходной программе приведёт к аварийному останову с выражением <Select 3 ('abcd') ('cdab')>. Нетрудно убедиться, что тот же вызов в оптимизированной программе будет выглядеть как <Select@0 3 ('abcd') ('cdab')>.

Т.е. если пользователь видит аварийный останов с функцией Func@0, то он игнорирует @0 и идёт в исходнике искать функцию Func. Точно также при прогонке он игнорирует суффиксы *1, *2 и т.д.

Деталь реализации: если функция специализируется несколько раз, аварийную функцию Func@0 нужно добавлять только один раз.

Mazdaywik commented 4 years ago

Реализовать описанную оптимизацию несложно, достаточно добавлять аварийное предложение и аварийную пустую функцию в OptTree-Spec-ExtractOptInfo.

Но! Есть другой способ достижения той же цели (понятный аварийный дамп) — это добавление разметки контекста. Если опция --markup-context включена (а в отладочном режиме её рекомендуется включать), то аргумент функции будет размечаться точно также, как размечаются параметры замыкания — имена параметров берутся из шаблона $SPEC.

И теперь мне непонятно, что предпочесть.

Преимущества и недостатки аварийного предложения:

Преимущества и недостатки разметки контекста:

Поэтому всё-таки лучше использовать аварийное предложение. А оптимизацию с -OS --markup-context убрать из автотестов.

Mazdaywik commented 4 years ago

Реализовано в простейшем варианте.

Можно было бы добавить проверку, что если последнее предложение совпадает с шаблоном с точностью до переименования переменных, то предохранительное предложение добавлять не нужно.

Но такой приём не гарантирует того, что аварийное предложение не будет лишним. Например, в функции Map проверяются все возможные образцы, поскольку сужения e → ε и e → t e являются разбиением для e: https://github.com/bmstu-iu9/refal-5-lambda/blob/96fb33e3a00ce84b16ed07498491a3d7208e1685/src/lib/common/LibraryEx.refi#L27-L31 Добавление аварийного предложения сделает его недостижимым. Но вычислить это не так-то просто. Аналогично и с функциями MapAccum и Reduce, а ведь именно ради них и придумана специализация.

Поэтому решено на счёт избыточности аварийного предложения не заморачиваться.

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