refal-5-lambda
refal-5-lambda copied to clipboard
bmstu-iu9
Разметка неразменных аргументов для прогонки
ВНИМАНИЕ! Исходная постановка задачи со временем потеряла актуальность на 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 = <OneOf t.SearchFor e.Set>;
t.SearchFor /* пусто */ = False;
}
Если эту функцию пометить как $DRIVE, то вызов <OneOf s.X Foo Bar Baz> прогонится замечательно. Но с другой стороны, вызов <OneOf s.X Foo e.Bar Baz> приведёт к зацикливанию.
Что делать?
Формат функции OneOf такой:
<OneOf t.SearchFor e.Set>
Рекурсивный вызов во втором предложении применяется к части аргумента 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 <F s.A> e.D;
}
H {
s.A e.B s.A e.D = e.B <F s.A> 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;
}
Вызов <G (()) (Z) B (Y) A ((X))> даст (()) (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’А!
@TonitaN, ты хорошо разбираешься в прогонке с образцами общего вида. Тебе есть чего-нибудь добавить интересного к приведённым выше рассуждениям?
Задача вполне пригодна для курсовой работы по компиляторам. Причём целиком — не только шаблон, но и описанное в разделе «Побочный эффект…».
Неразменные переменные и не-L-образцы
С прогонкой для не-L-образцов тоже всё непросто. В примере из постановки задачи всё красиво:
$DRIVE F;
F {
A = 1; B = 2; C = 3;
}
…
H {
s.A e.B s.A e.D = e.B <F s.A> e.D;
}
↓ ↓ ↓ ↓ ↓ ↓ ↓
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;
}
А вот пример, где всё некрасиво:
$DRIVE Fa;
Fa {
A = AA;
s.X = (s.X);
}
Test {
s.P e._ s.P e._ = Found <Fa s.P>;
s.P e._ = NotFound;
}
Прогонка нам даст
Test {
A e._ A e._ = Found AA;
s.P e._ s.P e._ = Found (s.P);
s.P e._ = NotFound;
}
Что получится для вызова <Test A 1 2 3 4 5 6 … 97 98 99 100>? Получится два по открытой переменной. Сначала не сопоставится образец с первым предложением. Потом со вторым.
Можно привести пример, что для однозначных образцов с повторными t-, e-переменными прогонка тоже приведёт к потере производительности.
Поэтому неразменные переменные сами по себе никак не помогают прогонке с не-L-образцами.
Задача #314 подразумевает отказ от точной разметки $DRIVE/$INLINE, в том числе и отказ от шаблона неразменных аргументов. Поэтому синтаксис
$DRIVE 〈имя〉 〈шаблон〉;
уходит в утиль. Прогоняемая функция с шаблоном есть вариант встраиваемой функции.
Если функция пригодна для встраивания (в том числе и «смешанного» с шаблоном неразменных переменных), то её расширенная специализация (#251) построит конечный набор экземпляров, часть из которых можно будет затем прогнать. Поэтому при решении #314 и #251 шаблон неразменных переменных становится избыточен.
Остальные соображения про неразменные переменные в топике и комментариях выше остаются актуальными.
На самом деле, здесь всё не так просто. И, если разобраться, эта задача — частный случай задачи #283.
Если имеем L-образец с условиями, то прогонять нужно как в #283 — между новыми предложениями нужно будет добавлять предложения перехода на хвост. «Разменными» переменными будут только предложения из образца, но не предложения из условий.
Если мы имеем не-L-образец, но образец мы можем представить как пару наиболее сложного L-образца и набора сужений, переводящих его в исходный образец. Можем заменить исходный образец на L-образец, а сужения представить как условия-сужения при нём. Задача сводится к предыдущей (L-образец с условиями). В актуальной реализации преобразование сужений в условия не оптимально, т.к. требуется копировать значения. Но с оптимизацией #257 это проблемой не будет. К тому же такое преобразование можно делать виртуальные.
В примере выше получится так:
$DRIVE Fa;
Fa {
A = AA;
s.X = (s.X);
}
Test {
s.P e._ s.P e._ = Found <Fa s.P>;
s.P e._ = NotFound;
}
Преобразуем Test в L-образец с условием:
Test {
s.P e.1, e.1 : e._ s.P e._ = Found <Fa s.P>;
s.P e._ = NotFound;
}
Прогоняем:
Test {
A e.1, e.1 : e._ A e._ = Found AA;
A e.1 = <Test*1 A e.1>;
s.X e.1, e.1 : e._ s.X e._ = Found (s.X);
s.X e.1 = <Test*1 s.X e.1>;
s.P e._ = NotFound;
}
Test*1 {
s.P e._ = NotFound;
}
(очевидно, предложение-переход перед последней функцией добавлять не обязательно)
Поскольку преобразования виртуальные, результат будет такой:
Test {
A e._ A e._ = Found AA;
A e.1 = <Test*1 A e.1>;
s.X e._ s.X e._ = Found (s.X);
s.X e.1 = <Test*1 s.X e.1>;
s.P e._ = NotFound;
}
Результат эффективный. Но вообще, эта задача должна быть частью #283.
В свете вышеизложенного + https://github.com/bmstu-iu9/refal-5-lambda/issues/283#issuecomment-746885017 задача уходит на ВКР как существенно перекрывающаяся с #283.
@torrentino555 ушёл к другому научному руководителю, тема на ВКР не выбрана.