Новая реализация метафункций (Mu, Residue, Up, Ev-met)

[Mazdaywik]

Эта задача блокирует #260.

Актуальная реализация функции Mu затрудняет решение задачи #181.

Во-первых, сама функция Mu медленная — написана на Рефале и обращается к функции динамической загрузки Module-LookupFunction. А использование Map, MapAccum и Reduce есть краеугольный камень программирования на Рефале-5λ. Вероятно, из-за медленной Mu и получены столь плачевные результаты, описанные в #185.

Во-вторых, функция Mu сложна для автоматического анализа, о чём кратко написано в #181. Она содержит условие с вызовом нативной функции, функция Mu-Aux вызывает Type и __FindMuPtr, обе для оптимизации должны быть интринсиками.

Соответственно, нужен механизм более быстрый и более удобный для анализа.

[Mazdaywik]

Возможная реализация

Есть такое соображение: передавать в метафункции таблицу функций. Таблица представляет собой набор пар «идентификатор-имя функции» по одной паре для каждой функции, определённой в данной единице трансляции (и не имеющей суффикса). В метафункцию таблица передаётся неявным аргументом.

Метафункция определяется при помощи ключевого слова $META:

$META FuncName;

Такое определение является синтаксическим сахаром для

$EXTERN __Meta_FuncName;
$INLINE FuncName;
FuncName {
  e.Arg = <__Meta_FuncName e.Arg $table>;
}

где $table — та самая ссылка на таблицу.

В RASL’е таблица функций представляется как особая функция, локальная для модуля. При попытке её вызвать как обычную функцию, она падает как $ENUM. Функция-таблица может иметь имя вида $table + cookies. Будет ли она доступна по ключевому слову $table — пока не важно. В принципе, можно определить следующую метафункцию:

__Meta_table { s.Table = s.Table }
$META table;

которая будет допускать лишь пустой аргумент и возвращать ссылку на таблицу.

Здесь наиболее интересна связь с другими задачами.

Связь с другими задачами

При глобальной оптимизации (#255) предлагается переименовывать локальные функции в имена вида Func~1 и конкатенировать несколько отдельных деревьев. Предложенная реализация прекрасно согласуется с этим механизмом: метафункции как локальные функции точно также переименовываются, таблицы как локальные функции тоже переименовываются в $table~1, указатели на функцию в них тоже переименовываются. В сгенерированном коде будет несколько таблиц-функций с разными именами, но они все будут отображать те же идентификаторы в уже переименованные локальные функции. Таким образом, семантика не изменяется.

Оптимизация прогонки может привести к тому, что в единице трансляции останутся функции, которые ниоткуда не вызываются. И есть задача на удаление таких функций (#228). Но сформулирована она как задача удаления неиспользуемых функций с суффиксами, поскольку удалять локальные функции без суффиксов просто так нельзя: они могут вызываться через Mu. Предложенная реализация метафункций позволяет упростить чистку программы: оставляются только entry-функции, функции инициализации/финализации и транзитивно доступные из них. В частности, если где-то вызывается метафункция, это означает, что таблица используется, а значит, используются все имена, в ней перечисленные. Если метафункции не вызывались, то локальные функции, не вызываемые непосредственно, также останутся недоступными.

Также упрощается реализация метафункций как интринсиков (#260). При преобразовании <__Meta_Mu Func arg $table> имеется таблица, которая отобразит слово Func на функцию &Func (или &Func~n при глобальной оптимизации).

[Mazdaywik]

Уточняем возможную реализацию. Встроенные функции должны выполняться за один шаг рефал-машины, например, вызов <Mu F arg> должен заменяться на <F arg>.

Если Mu неявно описывается как

Mu {
  e.Arg = <__Meta_Mu e.Arg $table>;
}

то функция __Meta_Mu помимо поиска в таблице должна корректировать счётчик шагов.

Можно развести эти два содержательно разных действия, компилируя

$META Func;

в

$EXTERN __Meta_Func, __Step-Drop;
$INLINE Func;
Func {
  e.Arg = <__Step-Drop> <__Meta_Func e.Arg $table>;
}

Функция __Step-Drop уменьшает счётчик шагов на два: исходный вызов Func + сам вызов __Step-Drop.

При инлайне предлагается имя функции __Step-Drop распознавать и вызовы __Step-Drop удалять, потому что она не нужна.

Низкоуровневые оптимизации (-OdPR) должны сохранять видимое число шагов и трассировку поля зрения. Высокоуровневые (-OD, -OI, -OS + #260 + куча других планируемых) могут устранять шаги рефал-машины, заменять одни функции на другие и делать другие преобразования, которые, однако, должны сохранять семантику на области определения исходной программы (также желательно сохранять саму область определения).

Поэтому выкинуть __Step-Drop во время встраивания не только можно, но и нужно (но не непосредственно из определения Func).

[Mazdaywik]

К предыдущему комментарию.

Поэтому выкинуть __Step-Drop во время встраивания не только можно, но и нужно (но не непосредственно из определения Func).

Довольно нетривиальная логика потребуется. Проще выкидывать и из определения Func тоже. Функция Func достаточно проста для встраивания и поэтому должна встроиться везде. Она не может встроиться только для случая активного аргумента, но этот вопрос будет решён (#230).

[Mazdaywik]

Влияние новой Mu на быстродействие я не мерял. В самом Рефале-5λ функция Mu вызывается редко, поэтому нужно тестировать на другой программе, например, Рефале-05 (#185). А это было лень.

Поэтому я замерил, на сколько изменилось число шагов при самоприменении после обновления библиотеки (859e4ea). До обновления компилятор делал 26 754 373 шага, после — 26 712 997 шагов. Разница — 41 376 шагов или 0,15 %. Но 41 тысяча — всё равно немало (хотя не очевидно, откуда они взялись).