Mazdaywik
commented
3 years ago Более детальное обобщение
Функция gen__, как описано выше, обобщает до ближайшей переменной или пустоты, если аргумент пустой. Но может понадобиться обобщать не до ближайшей, а до конкретной переменной. Поэтому предлагается добавить функции gen_s__, gen_t__ и gen_e__ (можно допустить писать через дефис: gen-s__, gen-t__, gen-e__), которые обобщают аргумент до конкретной переменной.
Но что делать, если аргумент не совпадает с типом переменной, например, <gen_t__ 'hello'> или <gen_s__ ()>? Можно контролировать тип статически — требовать, чтобы формат аргумента соответствовал типу. Но это жёсткое ограничение, т.к. для корректной проверки форматов во время компиляции у Рефала-5λ мало данных. Например, если заведомо известно, что функция <MakeTerm> формирует скобочный терм, то вызов <gen_t__ <MakeTerm>> будет корректен, но компилятор проверить это не сможет.
Поэтому предлагается делать проверку во время оптимизации, иначе говоря, онлайн-проверку. Функции обобщения должны быть определены как
gen_s__ { e.X = e.X }
gen_t__ { e.X = e.X }
gen_e__ { e.X = e.X }а тип переменной, указанный в их имени, означает минимально допустимую нижнюю границу. Т.е. gen_s__ может обобщаться либо до s-, либо до t- и либо до e-переменной, gen_t__ — до t- или e-переменной, gen_e__ — только до e-переменной.
При наличии упомянутых трёх функций можно рассмотреть более «мягкую» семантику функции gen__. Выше сказано, что пустую строку она не обобщает. Можно пойти ещё дальше, и точно также, как предложено в #165, обобщать функцией gen__ до выражения длиной не более одного токена. Т.е. пустая строка обобщается до пустой строки, константный символ до самого себя (т.е. они оба не обобщаются), остальные значения — до соответствующей минимальной переменной. В частности, замыкания обобщаются до s-переменных, т.к. их запись требует не менее трёх токенов (скобки и обязательное имя).
Выше предлагается частичное решение — неточную реализацию семантики функции gen__. Как можно видеть из вышеизложенного — частичное решение есть точное выражение семантики функции gen_e__. Поэтому предлагается начать с реализации функции gen_e__.
Мотивация
Компилятор выполняет лишние специализации по аккумуляторам. Достаточно много примеров описано в #319 (смотреть в свёрнутых комментариях). Там же (https://github.com/bmstu-iu9/refal-5-lambda/issues/319#issuecomment-727816888, комментарий свёрнут) предложено оборачивать выражения в вызов функции, который не должен оптимизироваться.
Предложено было два варианта: «костыльный» средствами самого языка и расширение компилятора. Костыльный вариант уже реализован и используется в компиляторе:
Код получен копипастом. Определять entry-функцию в одном из файлов и импортировать в другом некрасиво — возникает странная связь, а создавать новый файл для костыля ИМХО избыточно.
Надо сделать не костыльно. Хотя, сама идея функции
gen__может рассматриваться как костыль…Что сделать
Нужно реализовать поддержку в компиляторе функции
gen__, вызов которой обобщается до ближайшей переменной (или пустоты, если аргумент пустой). Т.е. специализатор при анализе результатного выражения этот вызов может обобщить не доe.Call, а доt.Callилиs.Call. Когда прогонщик будет корректно обрабатывать функции с активными аргументами (#230), он аналогично должен интерпретироватьgen__. При этом, в идеале он должен считать этот вызов пассивным, если аргументgen__пассивный, т.е. разрешать его переупорядочивать, дублировать или стирать.Имя функции
gen__выбрано по аналогии с именами особых функций для SCP4:Const__,UnConst__и др.Функция
gen__не встроенная, она должна быть определена пользователем как тождественная локальная функция видаЕсли функция
gen__определена как-то иначе (entry, drive, inline, spec или с другим телом), должно выдаваться предупреждение и такая функция не должна оптимизироваться. Впрочем, на директивы$DRIVE gen__;,$INLINE gen__;,$SPEC gen__;лучше выдавать ошибки — проще будет на последующих стадиях анализа. Обоснование: функцияgen__может встречаться и в исходниках на классическом Рефале-5. Даже если она «неправильная», программа должна компилироваться и работать. Директивы$DRIVE,$INLINEи$SPECесть только в Рефале-5λ, поэтому на них можно накладывать жёсткие семантические ограничения.Детали реализации
Можно эту функцию распознавать на стадии синтаксического анализа и заменять на
Тогда при прогонке она заменится на некоторую встроенную функцию
$gen, которая распознаётся оптимизатором и реализует требуемое поведение.Но это плохая идея — функция
gen__должна работать и при специализации без прогонки.Просто распознавать имя
gen__прогонщиком и специализатором нельзя — нет гарантии, что она определена тождественной. Можно искать её тело при подготовке дерева к специализации и каким-то образом факт её наличия запоминать в промежуточной структуре данных(DriveInfo e._)или(SpecInfo e._). Но тоже некрасиво, усложняется внутренняя структура данных.Поэтому есть предложение сделать отдельный проход, распознающий наличие правильной функции
gen__(тождественная и локальная) и заменяющий её вызовы на<$gen …>, которую уже заведомо знают оптимизаторы. Проход может выполняться во время древесной оптимизации до неё или даже во время рассахаривания. Также нужен будет симметричный проход в конце, заменяющий<$gen …>на тождественную функцию.Ситуация осложняется тем, что у нас есть режим глобальной оптимизации: функций
gen__может быть много и они будут иметь суффиксыgen__~N. Такие имена тоже нужно будет распознавать.Частичное решение
На данном этапе пока достаточно обобщать вызовы до e-переменных, с чем прекрасно справляется специализатор сам. И обобщать их достаточно только в специализаторе.
Поэтому достаточно для корректной работы просто не прогонять эту функцию. Явно назначить ей метку
$DRIVEи$INLINEнельзя (должна быть синтаксическая ошибка, см. выше), а неявно ей не должна назначать метку авторазметка. Впрочем, компилятор может специализировать её вgen__@N, но это не страшно — всё равно произойдёт обобщение до e-переменной. А дополнительный проход прогонки экземпляров эти вызовы успешно уберёт с их накладными расходами.Частичное решение предлагается в первую очередь взамен костылей (399a6a037cc062ccf3ea1fc6d1ce9aad469cca62, b24582ea43931634c5f22db3f06c272095f31b3a).