Специализация без шаблона #251
Description
UPD 24.10.2020: название заявки обновлено, т.к. именно это требуется в комментариях.
Мотивация
Сейчас компилятор требует, чтобы в образцах предложений специализируемой функции статические параметры соответствовали переменным того же типа. Однако, это довольно жёсткое ограничение: для некоторых содержательных функций приходится писать довольно громоздкий и корявый код.
Например, в своём недавнем письме в рассылку refal@botik.ru я разбирал пример с интерпретатором диалекта Форта, где пришлось написать так:
$SPEC Loop e.stack (e.CODE) (e.DICT);
Loop {
e.Stack (e.Code_) (e.Dict)
, e.Code_
: {
/* empty */ = e.Stack;
DUP e.Code
= e.Stack : e.Stack^ t.Top
= <Loop e.Stack t.Top t.Top (e.Code) (e.Dict)>;
DROP e.Code
= e.Stack : e.Stack^ t.Top
= <Loop e.Stack (e.Code) (e.Dict)>;
…
}
}
Чтобы функцию можно было специализировать по e.CODE потребовалось написать одно предложение с блоком. Более естественный вариант выглядел бы так:
$SPEC Loop e.stack (e.CODE) (e.DICT);
Loop {
e.Stack (/* empty */) (e.Dict) = e.Stack;
e.Stack (DUP e.Code) (e.Dict)
= e.Stack : e.Stack^ t.Top
= <Loop e.Stack t.Top t.Top (e.Code) (e.Dict)>;
e.Stack (DROP e.Code) (e.Dict)
= e.Stack : e.Stack^ t.Top
= <Loop e.Stack (e.Code) (e.Dict)>;
…
}
Но нельзя, e.CODE здесь уточняется не в e-переменную, а в выражение.
Почему так сделано? Потому что функция, помеченная $SPEC, по сути является шаблоном, по которому строятся экземпляры, адаптированные к каждому конкретному вызову. И строятся они буквально шаблонной заменой значений статических параметров на их актуальные значения. А для шаблонной замены параметрам неизбежно должны соответствовать переменные того же типа в предложениях — на место этих переменных подставляется фактический аргумент.
Однако разумно разрешить статическим параметрам уточняться не в переменные, а в произвольные выражения того же типа. Как минимум, в L-выражения. В этом случае специализация получает возможности прогонки. При создании экземпляра функции для каждого предложения будет разрешаться система уравнений для статических параметров, предложения будут размножаться в соответствии с решениями системы.
Почему так не было сделано? Подход с возможностями прогонки требует наличия функции обобщённого сопоставления с образцом, которая может решить эту систему уравнений. Но на момент начала работ по обоим оптимизациям (прогонка #122, специализация #126) этой функциональности не было, был её ограниченный вариант, допускающий лишь успешные сопоставления. Прогонку делал Кирилл Ситников @InfiniteDisorder, специализацию — Дарья Сухомлинова @StrixSeloputo. Поскольку функция решения уравнений есть содержательная часть работы Кирилла, было решено ограничить Дарью базовым вариантом специализации.
Программа минимум: статические параметры не обязаны сужаться только в переменные
Собственно, нужно добавить элементы прогонки в специализацию, как описано в предыдущем абзаце. Сейчас в компиляторе есть и функция обобщённого сопоставления, и базовый вариант специализации.
Если статические параметры сужаются в L-выражения (которые в совокупности не содержат повторных t- и e-переменных), то специализация с элементами прогонки всегда будет успешной. Иначе возможен вариант Undefined, что в этом случае делать — не очевидно.
- Базовый вариант — отказываться от специализации этого вызова.
- Тонкий вариант — специализация только предшествующих предложений. Для предложений, начиная с первого
Undefined, генерируется как при прогонке остаточная функцияFunc*N, которая вызывается в неуспешном предложении. Побочный эффект: оптимизация будет увеличивать число шагов. - Другой, ещё более тонкий вариант — динамически обобщать аргумент. Поговорим о нём подробнее.
Что значит: сопоставление не удалось разрешить? Это значит, что при решении системы получилось уравнение вида E : Le, где E — фрагмент аргумента, а Le — фрагмент образца и с этим уравнением алгоритм решения справиться не может. (Частный случай E1 : E2, возникающий при наличии двух присваиваний E1 ← var и E2 ← var можно трактовать как уравнение 〈E1, E2〉 : 〈var, var〉, не будем его подробно рассматривать.)
Уравнение вида var : Le решить в каком-то смысле можно при любом Le (при соответствии типа переменной, конечно) — его решением можно назвать сужение var → Le (но есть тонкости с переменными). Решение для системы (var1) … (varN) : (Le1) … (LeN) вида var1 → Le1, …, varN → LeN можно подставить в L-образец, если порядок переменных var1 … varN тот же, что и в системе уравнений. В том смысле, что при подстановке не должен меняться порядок следования открытых e-переменных (см. #249).
Если решатель нашёл неразрешённое уравнение E : Le (или несколько таких уравнений), то в исходном аргументе можно заменить E на новую переменную и заново выполнить прогонку. Т.е., в каком-то смысле мы часть аргумента делаем динамической.
Базовый вариант должен быть реализован в первую очередь. Любая пометка оптимизации ($DRIVE, $INLINE, $SPEC) это всего лишь совет компилятору оптимизировать функцию. Если оптимизация возможна, то она выполняется. Если нет, остаётся как есть. Такое решение в духе Си++, где ключевые слова inline и register тоже являются исключительно советами. Если программист сам написал предложение, где статические параметры в совокупности отображаются в не-L-кортеж образцов, значит он готов к тому, что функция иногда специализироваться не сможет.
Программа максимум: специализация без шаблона
Здесь предлагается специализируемые функции просто помечать ключевым словом $SPEC, например в форме $SPEC Map { … }.
Если реализована программа-минимум, то описание
$SPEC Func;
должно считаться эквивалентным
$SPEC Func e.ALL-STATIC-ARG;
Вообще, зачем нужен был шаблон в исходной постановке задачи? Изначально для выделения статических (шаблонных) параметров одновременно с желанием сохранить привычный синтаксис функции. Альтернативной могло быть использование особого синтаксиса для шаблонных параметров. Например, такого:
Map [t.Func] {
t.Next e.Rest = <Apply t.Func t.Next> <Map [t.Func] e.Rest>;
/* empty */ = /* empty */;
}
А так (а) сохраняется привычный вид специализируемой функции, (б) при невозможности специализации вызов функции выполняется обычным образом.
Что даёт шаблон, если мы разрешим прогонку статических параметров? Во-первых, шаблон автоматически обобщает некоторые участки аргумента как незначимые. Во-вторых, он разрешает динамическим частям образцов иметь любой вид без ограничений.
Например, в функции
$SPEC Replace (e.FROM) (e.TO) e.text;
Replace {
(e.From) (e.To) e.Text-B e.From e.Text-E
= e.Text-B e.To <Replace (e.From) (e.To) e.Text-E>;
(e.From) (e.To) e.Text = e.Text;
}
есть открытые и повторные e-переменные и они ни сколько не мешают оптимизации. При специализации этой же функции без шаблона нужна нетривиальная поддержка образцов общего вида при прогонке и, по-видимому, механизм динамического обобщения аргумента. Например, в следующей гипотетической программе
$SPEC Replace {
(e.From) (e.To) e.Text-B e.From e.Text-E
= e.Text-B e.To <Replace (e.From) (e.To) e.Text-E>;,
(e.From) (e.To) e.Text = e.Text;
}
Test { (e.X) (e.Y) (e.Z) = <Replace ('Foo') ('Bar') e.X e.Y e.Z> }
возникнет нетривиальное уравнение e.X e.Y e.Z : e.Text-B 'Foo' e.Text-E, которое решить невозможно и придётся динамически обобщить e.X e.Y e.Z до одной переменной, скажем, e.0.
Т.е. специализацию без шаблона сделать можно, но она потребует сложный нетривиальный (и, по-видимому, медленный) анализ на стадии компиляции. Она может быть дополнением специализации с шаблоном, но не заменой ему.