Обобщающая функция gen__

[Mazdaywik]

Мотивация

Компилятор выполняет лишние специализации по аккумуляторам. Достаточно много примеров описано в #319 (смотреть в свёрнутых комментариях). Там же (#319 (comment), комментарий свёрнут) предложено оборачивать выражения в вызов функции, который не должен оптимизироваться.

Предложено было два варианта: «костыльный» средствами самого языка и расширение компилятора. Костыльный вариант уже реализован и используется в компиляторе:

• 399a6a0
• b24582e

Код получен копипастом. Определять entry-функцию в одном из файлов и импортировать в другом некрасиво — возникает странная связь, а создавать новый файл для костыля ИМХО избыточно.

Надо сделать не костыльно. Хотя, сама идея функции gen__ может рассматриваться как костыль…

Что сделать

Нужно реализовать поддержку в компиляторе функции gen__, вызов которой обобщается до ближайшей переменной (или пустоты, если аргумент пустой). Т.е. специализатор при анализе результатного выражения этот вызов может обобщить не до e.Call, а до t.Call или s.Call. Когда прогонщик будет корректно обрабатывать функции с активными аргументами (#230), он аналогично должен интерпретировать gen__. При этом, в идеале он должен считать этот вызов пассивным, если аргумент gen__ пассивный, т.е. разрешать его переупорядочивать, дублировать или стирать.

Имя функции gen__ выбрано по аналогии с именами особых функций для SCP4: Const__, UnConst__ и др.

Функция gen__ не встроенная, она должна быть определена пользователем как тождественная локальная функция вида

gen__ { e.X = e.X }

Если функция gen__ определена как-то иначе (entry, drive, inline, spec или с другим телом), должно выдаваться предупреждение и такая функция не должна оптимизироваться. Впрочем, на директивы $DRIVE gen__;, $INLINE gen__;, $SPEC gen__; лучше выдавать ошибки — проще будет на последующих стадиях анализа. Обоснование: функция gen__ может встречаться и в исходниках на классическом Рефале-5. Даже если она «неправильная», программа должна компилироваться и работать. Директивы $DRIVE, $INLINE и $SPEC есть только в Рефале-5λ, поэтому на них можно накладывать жёсткие семантические ограничения.

Детали реализации

Можно эту функцию распознавать на стадии синтаксического анализа и заменять на

gen__ { e.X = <$gen e.X> }

Тогда при прогонке она заменится на некоторую встроенную функцию $gen, которая распознаётся оптимизатором и реализует требуемое поведение.

Но это плохая идея — функция gen__ должна работать и при специализации без прогонки.

Просто распознавать имя gen__ прогонщиком и специализатором нельзя — нет гарантии, что она определена тождественной. Можно искать её тело при подготовке дерева к специализации и каким-то образом факт её наличия запоминать в промежуточной структуре данных (DriveInfo e._) или (SpecInfo e._). Но тоже некрасиво, усложняется внутренняя структура данных.

Поэтому есть предложение сделать отдельный проход, распознающий наличие правильной функции gen__ (тождественная и локальная) и заменяющий её вызовы на <$gen …>, которую уже заведомо знают оптимизаторы. Проход может выполняться во время древесной оптимизации до неё или даже во время рассахаривания. Также нужен будет симметричный проход в конце, заменяющий <$gen …> на тождественную функцию.

Ситуация осложняется тем, что у нас есть режим глобальной оптимизации: функций gen__ может быть много и они будут иметь суффиксы gen__~N. Такие имена тоже нужно будет распознавать.

Частичное решение

На данном этапе пока достаточно обобщать вызовы до e-переменных, с чем прекрасно справляется специализатор сам. И обобщать их достаточно только в специализаторе.

Поэтому достаточно для корректной работы просто не прогонять эту функцию. Явно назначить ей метку $DRIVE и $INLINE нельзя (должна быть синтаксическая ошибка, см. выше), а неявно ей не должна назначать метку авторазметка. Впрочем, компилятор может специализировать её в gen__@N, но это не страшно — всё равно произойдёт обобщение до e-переменной. А дополнительный проход прогонки экземпляров эти вызовы успешно уберёт с их накладными расходами.

Частичное решение предлагается в первую очередь взамен костылей (399a6a0, b24582e).

[Mazdaywik]

Более детальное обобщение

Функция 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__.

[Mazdaywik]

Указатели на gen-функции?

А что делать с указателями на gen-функции? И можно ли их вызывать через Mu?

Ответ на второй вопрос: вызывать можно. С точки зрения классического Рефала-5, gen-функции — обычные функции и их можно вызывать через Mu. Но тут возникает новый вопрос: а как интерпретировать вызов <Mu gen__ …>?

---

С этим нет никаких проблем, на самом деле. И указатели, и вызов через Mu интерпретируются как обычно. Только если в процессе преобразований как-то возникает вызов псевдофункции, этот вызов интерпретируется особым образом.

Это можно обеспечить такой реализацией. Предварительный проход (можно даже в рассахаривателе) ищет в дереве псевдофункции по именам и телам (тождественное тело и имя вида gen__, gen_?__, gen__~n, gen_?__~n). Затем заменяет все ссылки на функции вида (Symbol Name e.Name) на (Symbol Name PF e.Name), где PF означает pseudofunction, включая метатаблицы. Затем оптимизаторы при обнаружении вызова таких псевдофункций, их обрабатывают особым образом. Просто указатели на них интерпретируются как просто указатели на функцию.

Заключительный проход обходит дерево и заменяет вызовы псевдофункций их аргументами (тут нужно правильно обработать <<!gen__ &!gen__> …> → …), после чего удаляет PF из имён функций (если они остались где-то).