Мотивация

Задача #181 требует использования функции Mu в функции Apply библиотеки LibraryEx. Но реализованные оптимизации прогонки и специализации (#91) могут эффективно работать только когда в Apply осуществляется непосредственный вызов. Поэтому для сохранения возможностей этих оптимизаций на стадии компиляции вызовы <Mu &Func …> и <Mu {{ &Func … }} …> должны заменяться на непосредственные вызовы. Т.е. компилятор должен функцию Mu понимать как интринсик (intrinsic).

В текущей версии компилятора (c47b82f2c188a6dbb70937f005701ed74390c219) при глубокой оптимизации Generator-RASL.ref в сгенерированном дереве остаются вызовы вроде <Divmod 0 256>. Очевидно, их тоже разумно упрощать на стадии компиляции.

Реализация

Просто хардкодить имена не комильфо. Один из аспектов идеологии — отделение языка от библиотеки. Кроме того, по-прежнему поддерживается Простой Рефал, в котором прелюдия не подключается, а значит, можно определить свои функции, одноимённые встроенным. Оптимизация в этом случае будет искажать семантику.

Поэтому предлагается использовать следующую директиву:

$INTRINSIC Mu, Divmod;

разрешающую соответствующую оптимизацию. Более хитрый вариант:

$INTRINSIC Mu : Mu, Residue : Mu, Divmod : Divmod;

где до двоеточия записывается имя функции, после — её семантика. Предлагается реализовать более простой вариант, оставив хитрый на потом (если он потребуется).

Список интринсиков

`Mu`

Её нужно реализовывать для #181.

Внимание! Нужно оптимизировать не Mu, а __Meta_Mu (см. комментарии).

Базовый вариант: оптимизировать только случаи, когда первым аргументом является указатель на функцию или замыкание, такого варианта достаточно для #181.

Расширенный вариант — оптимизировать полностью. Если первым термом является идентификатор или последовательность литер в скобках, и в текущем файле определена функция с этим именем, вызов заменяется на вызов этой функции.

Оптимизировать ли случай вызова функции, описанной как $EXTERN — не очевидно. Замена <Mu ExternFunc …> на <ExternFunc …> тонко меняет семантику программы.

Если внешняя функция в исходном тексте нигде прямо не вызывается, то при компиляции её объявление отбрасывается. Ни .rsl’ка классического Рефала-5, ни .rasl Рефала-5λ не будут зависеть от этой функции. И, если одноимённой entry-функции в программе нет, программа при загрузке не упадёт.

Таким образом, если выполняются следующие условия:

функция ExternFunc описана как $EXTERN,
она нигде прямо (т.е. <ExternFunc …>) не вызывается,
в программе нет определения $ENTRY ExternFunc { … } или ExternFunc не является встроенной,

то программа успешно загрузится (в обоих реализациях Рефала-5: лямбда и PZ), но вызов <Mu ExternFunc …> упадёт во время выполнения. Более того, функция ExternFunc может загружаться динамически и тогда вызов <Mu ExternFunc …> успешно выполнится.

Если при оптимизации <Mu ExternFunc …> заменять на <ExternFunc …>, то программа будет падать при загрузке.

Однако, вызов <Mu BuiltinFunc …>, наверное, всё-таки стоит заменять на непосредственный вызов встроенной функции. Ведь когда программист пишет на Рефале-5, он полагает, что все встроенные функции ему доступны. В конце концов пользоваться Mu, когда недоступны остальные встроенные функции, немножко странно. Соответственно, вызовы <Mu '+' …> и <Mu "+" …> должны точно также, как и <Mu Add …> заменяться на вызов функции <Add …>. Аналогично с остальными короткими псевдонимами. Как интринсик Mu будет отличать встроенные функции от невстроенных — деталь реализации. Можно или захардкодить список, или добавить ещё одну директиву $BUILTIN Add, Arg….

Функцию __FindMuPtr я не рассматриваю, поскольку в #254 предлагается менять реализацию Mu.

Арифметические функции (`Add`, `Div`, `Divmod`, `Mod`, `Mul`, `Sub`, `Compare`)

Их, очевидно, надо делать интринсиками. Если они вызываются с константным корректным аргументом (два числа, возможно, длинных), то их нужно вычислять во время трансляции.

Расширенный вариант — учёт аксиом — не так очевиден, ибо может менять семантику и расширять область определения. Например, если <Add 0 e.X> заменить на e.X, то (а) если в e.X есть незначащие + или несколько нулей в начале, то они так и останутся, (б) если e.X не является числом, то исходная программа падала бы, а оптимизированная работала дальше (или падала бы в другом месте).

Однако, вызов <Add 0 <Mul (e.X) e.Y>> безопасно заменять на <Mul (e.X) e.Y>, потому что вторым аргументом сложения является результат функции умножения — заведомо корректное число в нормальной форме.

`Chr`, `Ord`, `Lower`, `Upper`

Их интересно оптимизировать статически. Общий принцип — символы в аргументе заменяем на результат преобразования, скобки оставляем как есть, переменные окружаем вызовом оптимизируемой функции.

Внимание! Эти функции не «залезают» в квадратные скобки (см. здесь).

`Explode`, `Implode`, `Numb`, `Symb`, `Implode_Ext`, `Explode_Ext`

Базовый вариант: вычисляем для константного аргумента. Расширенный вариант — можно учитывать их обработку хвоста, где он игнорируется.

`First`, `Last`, `Lenw`

Вычисляем, если аргумент на верхнем уровне не содержит e-переменных. Для First и Last, очевидно, длина должна быть константной.

`Type`

Вычисляем, если статически известно начало аргумента.

`Exit`

В отличие от других функций, эту вычислить невозможно, поскольку она значения не возвращает. Однако, её тоже можно учитывать при оптимизации. В частности, удалять все вызовы функций, которые выполняются после вызова <Exit …>, из предложения с вызовом Exit удалять все конструкторы данных верхнего уровня.

Таким образом, её обработка сложнее и не ложится в схему «заменить вызов на статически вычисленное значение». Её реализацию можно отложить.

`ListOfBuiltin`, `SizeOf`

Обе эти функции изначально предназначены для переносимого написания компилятора crefal — компилятор ничего не знает ни о размерности данных, ни о списке встроенных функций. Поэтому успешно создаёт .rsl’ки под ту платформу, на которой запускается интерпретатор.

ListOfBuiltin также полезна при написании других инструментальных средств, например, она используется в refal-5-framework в синтаксическом анализаторе Рефала. SizeOf — функция, специфическая именно для crefal’а.

ListOfBuiltin можно описать как $INLINE-функцию. А про SizeOf нужно думать даже шире текущей задачи. Роль интерпретатора для crefal’а сейчас играет front-end, декомпилирующий .rsl’ки, а он поддерживает только их 32-разрядную реализацию. Поэтому для сохранения семантики crefal’а, в ней, возможно, тоже надо будет захардкодить размеры типов для 32-разрядной платформы.

Что нужно будет сделать

[x] Синтаксис $INTRINSIC список-имён;. Можно посмотреть, как реализованы списки имён для $EXTERN, $SWAP, $DRIVE, $META и т.д. и сделать также. Достаточно сделать для Рефала-5λ. Простой Рефал можно не расширять, его всё равно выбрасывать (#201). Внимание! Функция подлежит оптимизации только если она помечена как $INTRINSIC. Иначе её вызовы не оптимизируются не смотря на «совпадающее» имя.
[x] __Meta_Mu, базовый вариант, она нужна для #181.
[x] __Meta_Mu, расширенный вариант.
[x] Арифметические функции Add, Div, Divmod, Mod, Mul, Sub, Compare
[x] Chr, Ord, Lower, Upper
[x] Explode, Implode, Implode_Ext, Explode_Ext
[x] Numb, Symb
[x] First, Last, Lenw
[x] Type

Функция Exit в список не вошла, поскольку непонятно, что с ней нужно делать. ListOfBuiltin и, наверное, SizeOf проще объявить как $INLINE в refal5-builtins.refi, чем делать для них особую оптимизацию.

Если не брать функцию Mu, которую надо перепроектировать в рамках #254, остальные пункты выглядят подходящими для курсовой работы. Причём, сравнительно простой.

Задача в некоторой степени пересекается с #174 (аксиомы для оптимизатора). Просто добавляю перекрёстную ссылку, дополнительных мыслей у меня нет.

`Residue`, `<? …>`

Эта функция — (пока) синоним Mu в Рефале-5λ и почти синоним в Рефале-5. При обычном выполнении программы функции Mu и Residue взаимозаменяемы. Но под метакодом (Ev-met) их поведение различается: функция Mu продолжает работать, функция Residue останавливает вычисление. Функция Residue имеет короткий псевдоним <? …>.

Откуда она взялась? Реализация SCP3 не умела отличать функции, которые можно выполнять во время суперкомпиляции, и функции, вызовы которых должны в неизменном виде упасть в остаточную (residual) программу. (Для сравнения: SCP4 знает свойства встроенных функций, для внешних можно задать разметку *$EXECUTABLE.) Чтобы пометить вызов как остаточный, программист заменял его косвенным вызовом через Residue с использованием синтаксического сараха: <?Func …> для SCP3 имело смысл как остаточный вызов, для Рефала — как короткий синоним для <Residue Func …>.

Надо ли её делать интринсиком? И должно ли её поведение отличаться от Mu? И вообще, зачем она может быть нужна в Рефале-5λ?

Во-первых, она может быть нужна для попытки запуска SCP3 под ним. Во-вторых, короткий синтаксис позволяет компактно описывать вызов функции, который разрешается во время выполнения. В частности, при помощи <?Func …> можно описывать вызовы функций из библиотек, которые явно загружаются во время работы. В-третьих, могут выполняться какие-то эксперименты с Ev-met, если в дальнейшем эта функциональность будет реализована.

Случай запуска SCP3 — особый, тут рассматривать не будем.

Запуск функций из библиотек, разрешаемый во время выполнения, сам по себе подразумевает невозможность статической оптимизации.

Функция Ev-met в языке не реализована, когда будет реализована и будет ли — неизвестно. Так что если она будет реализована — можно будет подумать и об особенностях Residue и отличиях от Mu.

Так что вывод: если сейчас оптимизировать Residue также, как и Mu — ничего страшного в этом не будет.

Задача не была выбрана в качестве курсовой.

Оптимизация интринсиков будет напоминать оптимизацию встраивания — нужно будет обнаруживать вызовы интринсиков, проверять их аргументы, и если аргумент допустимый, то вызов будет заменяться на результат выполнения. Оптимизация встраивания является разновидностью оптимизации прогонки, реализованной в src/compiler/OptTree-Drive.ref.

Скорее всего, обработка интринсиков будет выполняться в одном проходе с прогонкой. Либо, если не в одном проходе, то реализация прохода обработки интринсиков будет напоминать проход прогонки по описанной выше причине. Поэтому рекомендую изучить файлы src/compiler/{OptTree,OptTree-Drive}.ref, хотя они могут измениться при выполнении #254 и #263.

`__Step-Drop`

Как сказано в #254, вызовы функции <__Step-Drop> нужно удалять везде. Она используется для коррекции числа «видимых» шагов — шагов, которые показывает встроенная функция Step.

Для одной и той же программы значения, возвращаемые <Step> в классическом Рефале-5 и Рефале-5λ всегда должны совпадать, не смотря на то, что некоторые встроенные функции по факту написаны на Рефале и требуют нескольких шагов вычислений. Для того, чтобы встроенные функции выполнялись за один «видимый» шаг, их вычисления окружаются вызовами <__Step-Start>, <__Step-End>, либо добавляются <__Step-Drop> — примеры применений есть в исходнике src/lib/Library.ref.

Объявление метафункции

$META FuncName;

неявно преобразовывается в следующую конструкцию:

$EXTERN __Meta_FuncName, __Step-Drop;
$INLINE FuncName;

FuncName {
  e.Arg = <__Step-Drop> <__Meta_FuncName e.Arg $table>
}

где $table — таблица пар «имя-указатель на функцию». Без вызова __Step-Drop она требовала бы 2 шага вычислений: один на вызов FuncName, второй на __Meta_FuncName. Но встроенные метафункции Рефала-5 (Mu, Up, Ev-met, Residue) выполняются за один шаг. Поэтому лишний шаг нужно куда-то деть. Поэтому добавляется вызов __Step-Drop, уменьшающий счётчик шагов на 2 (один вызов метафункции + один вызов себя).

Но при встраивании вызова FuncName вызов <__Step-Drop> становится лишним. Поэтому его надо стирать.

TL;DR: вызовы функции <__Step-Drop e.any> должны заменяться на пустоту с любым пассивным аргументом.

`__Meta_Mu` и особенности метафункций

То, что сказано выше про функцию Mu, на самом деле касается __Meta_Mu. Функция Mu сама по себе не должна быть интринсиком, интринсиком должна быть __Meta_Mu. Её формат:

<__Meta_Mu t.Function e.Arg s.METATABLE> == e.Res
t.Function ::=
    s.RealFunction
  | s.WORD
  | (s.CHAR*)

s.RealFunction ::= s.FUNCTION | s.CLOSURE

Т.е. функция принимает «имя функции», аргумент, с которым функция должна быть вызвана и метатаблицу (подробности см. в #254).

Если именем функции является «настоящая функция» — указатель на функцию (&Func) или замыкание (вложенная функция), то её вызов просто заменяется на вызов функции или замыкания.
Если именем функции является идентификатор (символ-слово) или скобочный терм с цепочкой литер внутри, то функция вызывается по имени. Имя — соответственно идентификатор (<__Meta_Mu Func e.Arg $table>) или строка в скобках (<__Meta_Mu ('Func') e.Arg $table>).

Т.е. нужно найти в текущей области видимости функцию с данным именем и заменить вызов на неё. Область видимости описывается переданной метатаблицей. Тонкости:
- В текущей реализации функция-метатаблица может быть только одна в дереве, однако следует иметь ввиду задачу #255, подразумевающую объединение нескольких деревьев. Поэтому при оптимизации __Meta_Mu отображение «имя → функция» нужно извлекать из соответствующей функции-метатаблицы.
- Также в текущей реализации в метатаблице имена идентификаторов и соответствующих функций совпадают. Но согласно #255 локальные функции будут переименовываться, а значит, их имена станут разными.
В остальных случаях вызов не меняем.

Residue

О ней даже не надо задумываться. В актуальной реализации она просто вызывает Mu.

@Mazdaywik

Можно посмотреть, как реализованы списки имён для $EXTERN, $SWAP, $DRIVE, $META и т.д. и сделать также.

В каких файлах это можно посмотреть? Я нашёл в src/compiler/R5-Parser.ref место, связанное с парсингом $EXTERN.

@Cstyler, нужно посмотреть в R5-Lexer.ref разбор ключевого слова $SWAP, $META, $DRIVE или $INLINE, а потом посмотреть, как эти лексемы обрабатываются в R5-Parser.ref.

Также, по-хорошему, надо добавить проверку в Checker.ref, что функция с этим именем объявлена, но это не так важно.

После того, как Вы добавите новое объявление в синтаксическое дерево, сразу выяснится, что многие последующие проходы его не знают и на нём будут спотыкаться. Значит, потребуется добавить в них предложения, которые данное объявление просто передают дальше (как (Drive …) и (Inline …)). Поглощаться новый узел должен в прогонщике (как там поглощаются те же (Drive …) и (Inline …)).

По сути $INTRINSIC в одном ряду с $DRIVE и $INLINE. Для последних двух мы говорим о том, что их вызовы нужно раскрыть в соответствии с их определением (причём inline-функции можно раскрывать только без сужений), для intrinsic-функций мы говорим, что их надо раскрывать компилятор сам знает как.

@Mazdaywik Нужно ли реализовывать desugaring аналогично функции Pass-RemoveRedundantDriveInline в Desugaring.ref?

Спасибо, правильный вопрос!

Нужно в этот проход встроить удаление Intrinsic. Drive забарывает всех, Inline забарывает Intrinsic. Цель в том, чтобы на вход OptTree-Drive.ref падало дерево, где для каждой функции есть не более одной метки: либо (Drive …), либо (Inline …), либо (Intrinsic …), либо ничего нет.

Кстати, у Вашего коммита записан email, который не привязан к аккаунту GitHub (khanaga.agazade <khanaga.agazade@metahouse.ru>):

https://github.com/bmstu-iu9/refal-5-lambda/commit/5014ef06fe94e7036ecc9bf15aa641bca7be74f2.patch

Можно не менять глобальные настройки, а поменять email только для репозитория. Внутри папки репозитория нужно выполнить

git config user.email "тот-email-который-знает-github"

Посмотреть его можно на https://github.com/settings/emails. Если его не хочется светить, то на той же странице можно найти фиктивный email вида 1309859+Mazdaywik@users.noreply.github.com, который тоже будет привязывать коммиты к аккаунту.

@Cstyler, нужно добавить автотест. Предлагаю такой (назовём его intrinsic.ref):

* TREE

$INTRINSIC Add, __Meta_Mu;

$META Mu;

$ENTRY Go {
  /* empty */
    = <Add 1 2> : 3
    = <Mu &Rev 'abracadabra'> : 'arbadacarba'
    = <Mu Rev 'abracadabra'> : 'arbadacarba'
    = 'abra' : e.X
    = <Mu { e.A = e.X e.A e.X } 'cad'> : 'abracadabra'
    = /* empty */
}

Rev {
  t.First e.Middle t.Last = t.Last <Rev e.Middle> t.First;
  t.One = t.One;
  /* empty */ = /* empty */;
}

__Meta_Mu {
  Rev e.Arg s.Metatable = <Rev e.Arg>;
  s.Ptr e.Arg s.Metatable = <s.Ptr e.Arg>;
}

Add {
  1 2 = 3;
}

Автотест простой, проверяет мало: что компилятор не падает на ключевом слове $INTRINSIC и что прогонщик корректно обрабатывает три простых случая двух интринсиков. Комментарий * TREE распознаётся движком автотестов, тестирует работу компиляцию с ключами древесной оптимизации (включая -Oi).

Если компилятор видит вызов встроенной функции, но не может её оптимизировать (например, потому что функция ему незнакома, компилируем старой версией файл для новой версии), то он вызов оставляет «как есть», делая его холодным (ColdCall). На данный момент, когда реализована поддержка только на front-end’е, прогонщик должен просто потреблять и игнорировать узел дерева Intrinsic. Этот тест должен проходить.

Затем при разработке этот тест будет защищать от простых грубых ошибок.

На самом деле, тесты на все оптимизации собственно оптимизацию (т.е. что программа ускорилась) не проверяют. Они проверяют, что сам компилятор не падает, и что файл, скомпилированный с ключами оптимизации, при запуске не падает.

Тесты самопроверяемые, т.е. в функции Go вызывается некоторая функция и возвращаемый результат сверяется с известным. Предполагается, что во всех режимах оптимизации тест скомпилируется в корректный код, компиляция не исказит семантику функций. Если какая-то оптимизация что-то искажает, то вызываемая функция скомпилируется неправильно и выдаст не тот результат — тест упадёт.

На самом деле немалая часть тестов — регрессионные. Обнаруживалось, что код в режиме какой-то оптимизации компилировался неправильно (или компилятор падал). Писался маленький тест, воспроизводящий эту ошибку, коммитился, а ошибка исправлялась.

@Mazdaywik

$INTRINSIC Add, __Meta_Mu;

$META Mu;

Проверил на компиляторе с мастера, директива "$META Mu;" выдаёт ошибку "ERROR: Function Mu is already defined" (в компиляторе эта строчка печатается в Checker.ref), хотя с другими внутренними функциями работает нормально. На моей ветке без этой команды, с интринсиками, работает.

🤦‍♂️ Коммит должен быть единым законченным этапом работы. Коммитить недописанный, особенно, некомпилирующийся код не надо.

Правильнее было бы слить два последних коммита в один, даже не два, а три. А если учесть следующий коммит, который добавляет автотест и исправляет выявленные им ошибки (если будут), то и четыре.

Если правки существенные (не опечатка в документации, скажем), то я перед пушем выполняю все автотесты (вернее, clean.bat + bootstrap.bat). Если всё прошло гладко — пушу.

Проверил на компиляторе с мастера, директива $META Mu; выдаёт ошибку ERROR: Function Mu is already defined (в компиляторе эта строчка печатается в Checker.ref), хотя с другими внутренними функциями работает нормально. На моей ветке без этой команды, с интринсиками, работает.

Это потому что функция Mu определена в стандартном вступлении (src/lib/common/refal5-builtins.refi), которое неявно добавляется ко всем исходным файлам. Тесты запускаются без стандартного вступления, поэтому в папке autotests этот тест будет работать как положено.

Прокомментировал коммит https://github.com/bmstu-iu9/refal-5-lambda/commit/9e279de1a3b49e62ef56d940c801575ce3d1af32.

@Mazdaywik Про автотест выше. Там "$META Mu;" генерирует функцию Mu в которой используется Step-Drop вне вызова интринсика Meta_Mu, функция Step-Drop не определена и тест падает. Получается мне нужно будет убирать Step-Drop, если его вызовы находятся в одном результатном выражении с интринсиком?

Да, я забыл в автотесте объявить __Step-Drop. Её можно так добавить:

$INTRINSIC Add, __Meta_Mu, __Step-Drop;

__Step-Drop { = }

. . .

Напомню, один тест можно запустить так:

./run.sh intrinsic.ref

run.bat intrinsic.ref

По коммитам:

Старайтесь не перезаписывать те коммиты, которые уже запушены и имеют номер. Перед этим комментарием расположены 3 коммита, из них только 2 актуальные. Упоминание коммита d03b201 уже здесь никак не сотрёшь.

Первую строчку сообщения нужно стараться уместить в ≈70 символов, иначе она обрезается на полуслове:

Фикс ошибки в удалении ненужных меток, фикс в логировании AST, исправ…

Предыдущий коммит я бы прокомментировал так:

Мелкие багфиксы (#260)

* Исправление ошибки в удалении ненужных меток,
* улучшение форматирования в логе AST,
* исправление автотеста.

@Mazdaywik

$EXTERN __Meta_Mu, __Step-Drop;
$INLINE Mu;

Mu {
  e.Arg = <__Step-Drop> <__Meta_Mu e.Arg $table>
}

Здесь не вытягивается название функции, которую должна вызвать __Meta_Mu. Подойдёт ли такое решение: изменяем левую часть предложения, добавляя к e.Arg s.FuncPtr, а вызов __Meta_Mu заменяем на вызов s.FuncPtr? Второй вариант: вставляем в дерево функцию, которая выделяет первый аргумент, и используем её на e.Arg.

И я правильно понял, что значения функций(Add и т.д.) надо вычислять исходя из определения этих функций в AST дереве, а не исходя из внутреннего определения функций?

@Cstyler, функция Mu будет полностью оптимизироваться при использовании ключей -OiI и -OiD.

Она здесь помечена как $INLINE, значит, она встроится в точку вызова при использовании ключей -OI или -OD. Поэтому вызов

<Mu &Rev 'abracadabra'>

заменится на

<__Step-Drop> <__Meta_Mu &Rev 'abracadabra' $table>

На втором проходе прогонщика обнаружится вызов __Step-Drop, который Вы замените на пустоту. На третьем — __Meta_Mu.

Не знаю, обратили ли Вы внимание, когда изучали код OptTree-Drive.ref. На каждом проходе прогонки из каждого результатного выражения выбирается самый левый терм вызова оптимизируемой функции. И или он оптимизируется, или заменяется на «холодный вызов» (ColdCallBrackets), благодаря чему будет пропускаться на следующих проходах.

Так сделано намеренно для того, чтобы компилятор работал конечное время. Легко написать функцию, которая прогоняться может бесконечно:

Infinity {
  e.X = <Infinity e.X '*'>
>

На каждом шаге вызов будет заменяться на новый вызов, а к аргументу будет приписываться звёздочка.

Поэтому заменяется за проход в каждом результатном выражении один вызов, а число проходов, которые делает компилятор, конечно (по умолчанию 100). Даже при некорректной пометке (вроде $DRIVE Infinity;) компилятор рано или поздно завершит работу.

Вызов функции Mu, таким образом, оптимизируется за три прохода прогонки (при использовании ключей -OiI или -OiD). Если при раскрытии в скобках оказалась оптимизируемая функция, то её уже будет оптимизировать четвёртый проход.

Базовая реализация интринсика __Meta_Mu — раскрывать вызовы, когда первым аргументом является указатель на функцию (Symbol Name e.Name) или замыкание (ClosureBrackets t.Function e.Context). Продвинутая — когда первым аргументом является имя функции в виде идентификатора (Symbol Identifier e.Name) или цепочки char’ов в круглых скобках.

В базовой реализации мы откидываем метатаблицу — она нам не нужна, функция для вызова и так задана явным образом:

<__Meta_Mu &Func e.Arg s.Table> → <Func e.Arg>
<__Meta_Mu {{ &Func e.Context }} e.Arg s.Table> → <Func e.Context e.Arg>

В виде кода:

(CallBrackets
  (Symbol Name '__Meta_Mu')
  (Symbol Name e.Name) e.Arg (Symbol Name e.MetatableName)
)

заменяется на

(CallBrackets (Symbol Name e.Name) e.Arg)

Для второго случая аналогично.

В продвинутом варианте мы имеем косвенный вызов по имени:

<__Meta_Mu FuncName e.Arg s.Table>
<__Meta_Mu ('FuncName') e.Arg s.Table>

Тут уже нужно заглянуть в метатаблицу и достать оттуда указатель на функцию. Метатаблица — это функция, у которой в теле вместо Sentences e.Sentences находится Metatable e.Metatable, где e.Metatable — список пар «имя функции — указатель на функцию. Имя функции там записано как символ-идентификатор, указатель — как символ-указатель. Можете посмотреть в src/compiler/README.mdс описанием структуры данных и в src/compiler/Log-AST.ref` как она печатается.

Если в метатаблице такого указателя нет, этот вызов не оптимизируем, а заворачиваем в «холодные скобки» (чтобы он нам не попадался на следующих проходах).

При обычной компиляции в каждом файле только одна метатаблица (и она имеет имя $table), в ней имена идентификаторов совпадают с именами указателей. При использовании режима -OG все синтаксические деревья сливаются в одно, а локальные функции переименовываются (получают суффикс ~n). Метатаблиц получается несколько, как и функций Mu. Если в разных файлах были одноимённые локальные функции, то в разных метатаблицах одни и те же имена будут отображаться на разные указатели (раз функции переименовались).

Можете попробовать написать три файла: 1.ref, 2.ref и go.ref:

* 1.ref
$ENTRY Entry1 {
  = <Local> <Mu Local>;
}

Local {
  = '1.ref';
}

* 2.ref
$ENTRY Entry2 {
  = <Local> <Mu Local>;
}

Local {
  = '2.ref';
}

* go.ref
$EXTERN Entry1, Entry2;

$ENTRY Go {
  = <Prout <Entry1> <Entry2>>;
}

И скомпилировать программу из них два раза, следующими командами:

rlc go.ref 1.ref 2.ref --log=log-simple.log -o noG
rlc go.ref 1.ref 2.ref -OG --log=log-G.log -o withG

Программы noG (noG.exe) и withG (withG.exe) работают одинаково, ведь оптимизация не должна менять семантику.

Но лог разный. Настоятельно советую посмотреть лог и в нём разобраться.

В классическом Рефале-5 не было указателей на функции. Поэтому для косвенного вызова там использовалась функция Mu, которая принимала имя и вызывала функцию с данным именем из текущей области видимости (из того файла, где этот вызов записан). Поэтому в файле 1.ref функция Mu вызывает функцию Local первого файла, в 2.ref — Local из второго файла.

Чтобы обеспечить такое поведение, были придуманы метатаблицы — таблицы функций текущей области видимости. Функция __Meta_Mu глобальная, написана на C++ в файле Library.ref (длинная тоскливая реализация), она принимает имя функции, её аргумент и метатаблицу. Метатаблицу ей подсовывает локальная функция Mu.

Правки в коде

Нужно будет сделать несколько вещей, отдельными коммитами, чтобы не запутаться.

«Протягивание» режима интринсиков к точке его использования.
Расширение e.DriveInfo для хранения информации об интринсиках.
Собственно, логика оптимизации интринсиков.

«Протягивание» флага режима оптимизации интринсиков

Оптимизацию интринсиков нужно будет вызывать из OptSentence-MakeSubstitutions, поэтому там функция должна знать, включён ли режим -Oi или нет.

По цепочке вызовов от DriveInlineOptimizerTick до OptSentence-MakeSubstitutions нужно протянуть значение s.OptIntrinsic — заменить везде s.Mode на t.Mode, где

t.Mode ::= (s.DriveMode s.IntrinsicMode)
s.DriveMode ::= None | Inline | Drive
s.IntrinsicMode ::= None | Intrinsic

s.DriveMode соответствует старому s.Mode, s.IntrinsicMode — новый режим. При этом нужно быть внимательным, функции ожидают, что s.DriveMode может быть только Drive или Inline.

Например, образец во втором предложении OptSentence-MakeSubstitutions имеет вид

  s.Mode
  ((e.Left) (e.Expr)) (e.Args)
  (s.FuncMode s.ScopeClass (e.Name) Sentences e.Body)

само предложение ожидает, что s.Mode может быть только Drive или Inline. Его нужно поменять на

  (s.DriveMode s.IntrinsicMode)
  ((e.Left) (e.Expr)) (e.Args)
  (s.FuncMode s.ScopeClass (e.Name) Sentences e.Body)
    , <OneOf s.DriveMode Drive Inline> : True

А в конец добавить предложение, которое просто «остужает вызов»:

  t.Mode
  ((e.Left) (e.Expr)) (e.Args)
  t.Function
    = <MakeColdSolution t.Function e.Args>;

Такие правки, по моему опыту, могут иметь ошибки (т.к. меняется формат нескольких функций), поэтому прежде чем коммитить, нужно прогнать все автотесты, или хотя бы автотесты на opt-tree*.ref:

./run.sh opt-tree*.ref
run.bat opt-tree*.ref

В коде есть TODO: грязный костыль (здесь), нужно будет убрать это предложение, прежде чем делать всё вышеописанное.

Расширение `e.DriveInfo`

Для поддержки встроенных функций нужно расширить структуру данных e.DriveInfo. Сейчас она определена так:

https://github.com/bmstu-iu9/refal-5-lambda/blob/ad478a9944f6df28164ab3e9ab41776287f25a9b/src/compiler/OptTree-Drive.ref#L17-L26

Нужно будет расширить e.OptBody так, чтобы он мог хранить интринсики и метатаблицы.

  t.OptFunction ::= (s.Label s.ScopeClass (e.Name) e.OptBody)
  s.Label ::= Drive | Inline | Intrinsic | Metatable
  e.OptBody ::=
      Sentences e.Sentences
    | Intrinsic e.Name
    | Metatable e.Metatable

Эта структура заполняется в UpdateDriveInfo, в этой функции нужно будет разобраться и расширить её. Сейчас эта функция сначала находит все новые метки (Drive e.Name) и (Inline e.Name), потом к ним пришивает тела функций.

Почему новые? Потому что @Kaelena добавляет автоматическую разметку (#252), из-за которой оптимизация будет выполняться в несколько больших циклов, на каждом цикле дерево анализируется и функциям, которые можно прогнать, приписываются метки (Drive …). Проход разметки не знает, какие функции имели ранее эту метку, он смотрит только на граф вызовов. Поэтому эти лишние Drive нужно игнорировать.

Для интринсика e.Name просто дублирует само имя функции. Но это как бы заготовка на возможное расширение синтаксиса и семантики:

$INTRINSIC Mu = Mu;
$INTRINSIC Residue = Mu;

Логика оптимизации интринсиков

Случай вызова интринсика нужно обрабатывать в OptSentence-MakeSubstitutions. Там есть предложение

  (s.DriveMode s.IntrinsicMode)  /* см. пункт 1 */
  ((e.Left) (e.Expr)) (e.Args)
  (s.FuncMode s.ScopeClass (e.Name) Sentences e.Body)

Нужно будет добавить предложение

  (s.DriveMode Intrinsic)
  ((e.Left) (e.Expr)) (e.Args)
  (Intrinsic s.ScopeClass (e.Name) Intrinsic e.BehaviorName)
    = ...

Тип функции OptSentence-MakeSubstitutions не документирован в исходниках (моё упущение), он такой:

  <OptSentence-MakeSubstitutions
    t.Mode (e.OriginSentence) (e.CallArgs) t.OptFunction
  >
    == (e.SolutionsPack)*
  e.SolutionsPack ::= (e.ReplacedExpr) t.Solution* (e.NewFunctions)
  t.Solution ::= (e.Contractions) (e.Assignments)

🤦‍♂️ Пока писал тип, понял, что её нужно аццки рефакторить. Мне стыдно, что в исходниках я оставил такой путанный код, тип можно было сделать гораздо проще. Но, впрочем, и в такую функцию можно добавить поддержку интринсиков.

Отрефакторю летом, сейчас не буду, чтобы не создавать неразберихи.

Аргументы функции:

t.Mode — обговорено выше.
e.OriginSentence — предложение, в котором находится вызов оптимизируемой функции. На самом деле функции OptSentence-MakeSubstitutions нужно не предложение, а только переменные из него. Прогонка для сужений генерирует новые переменные, список известных переменных нужен для того, чтобы не возникало конфликтов.
e.CallArgs — аргументы оптимизируемой функции.
t.OptFunction — оптимизируемая функция, см. тип в e.DriveInfo:
```
t.OptFunction ::= (s.Label s.ScopeClass (e.Name) e.OptBody)
e.OptBody ::= см. выше
```
Результат — набор пакетов решений.
e.SolutionsPack — решение для одного из предложений прогоняемой функции.
e.ReplacedExpr — то, на что нужно заменить вызов оптимизируемой функции.
e.Contractions — сужения, применяемые к образцу.
e.Assignments — присваивания, применяемые к e.ReplacedExpr.
e.NewFunctions — новая функция, которая могла появиться во время прогонки/встраивания.

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

(
  (новое выражение)
  ((/* нет сужений */) (/* нет присваиваний *))
  (/* нет новых функций */)
)

В случае, когда оптимизация невозможна, вызов оптимизируемой функции заменяется на холодный вызов с тем же аргументом — он генерируется при помощи MakeColdSolution.

@Mazdaywik Для NoOpt нужно добавить NoMode тогда? Потому что есть же случаи когда Drive/Inline включены, а Intrinsic нет, и наоборот, а делать отдельное предложение в DriveInlineOptimizerTick будет дублировать много кода

UPD: вопрос исчерпан, невнимательно прочел, это значение None

Наоборот, в функции DriveInlineOptimizerTick должно остаться только одно предложение (первое с комментарием убрать). Нужно в OptFunction заменить s.Mode на t.Mode, в OptSentence и OptSentence-Aux тоже самое. Всё различие будет только в OptSentece-MakeSubstitutions.

UPD: не заметил сразу UPD 😀.

Добавил

$INTRINSIC Divmod;

в файл Generator-RASL.ref.

Почему-то вызовы не заоптимизировались:

    (CmdCreateElem Reinit s.ElemNumber#1 ElOpenCall)
      = <*
          &PutCommand$3:1 "s.OpCode#2:" 86 <* &Divmod 0 256*>
          <* &Divmod 2 256*> <* &Divmod s.ElemNumber#1 256*>
        *>;

$INTRINSIC Divmod;

$INLINE F2;

F1 {
    1 = <F2 0>
}

F2 {
    s.1 = <Divmod s.1 256>
}

$ENTRY Go {
  /* empty */
    = <F1 1> : e._
    = <Prout <Divmod 0 256>> : e._
    =
}

Divmod {
    0 256 = (0) 0
}

Создал такой пример, вызов оптимизируется, у меня похоже баг, что если не объявлена функция, то она не оптимизируется. В автотестах ведь всё нужно было объявлять.

@Mazdaywik баг пофиксил, проверил на примере выше. <Prout <Divmod 0 256>> заменяется на <Prout (0) 0>. Объявление Divmod убрал из примера.

Да, общее у $INTRINSIC с $DRIVE и $INLINE в том, что они обрабатываются в одном модуле и сходным образом. А различное, что у $INTRINSIC не нужно определения, т.к. семантика и так зашита в компилятор.

bmstu-iu9 / refal-5-lambda

Интринсики для встроенных функций #260

Мотивация

Реализация

Список интринсиков

`Mu`

Арифметические функции (`Add`, `Div`, `Divmod`, `Mod`, `Mul`, `Sub`, `Compare`)

`Chr`, `Ord`, `Lower`, `Upper`

`Explode`, `Implode`, `Numb`, `Symb`, `Implode_Ext`, `Explode_Ext`

`First`, `Last`, `Lenw`

`Type`

`Exit`

`ListOfBuiltin`, `SizeOf`

Что нужно будет сделать

`Residue`, `<? …>`

`__Step-Drop`

`__Meta_Mu` и особенности метафункций

Residue

Правки в коде

«Протягивание» флага режима оптимизации интринсиков

Расширение `e.DriveInfo`

Логика оптимизации интринсиков

bmstu-iu9 / refal-5-lambda

Интринсики для встроенных функций #260

Мотивация

Реализация

Список интринсиков

Mu

Арифметические функции (Add, Div, Divmod, Mod, Mul, Sub, Compare)

Chr, Ord, Lower, Upper

Explode, Implode, Numb, Symb, Implode_Ext, Explode_Ext

First, Last, Lenw

Type

Exit

ListOfBuiltin, SizeOf

Что нужно будет сделать

Residue, <? …>

__Step-Drop

__Meta_Mu и особенности метафункций

Residue

Правки в коде

«Протягивание» флага режима оптимизации интринсиков

Расширение e.DriveInfo

Логика оптимизации интринсиков

`Mu`

Арифметические функции (`Add`, `Div`, `Divmod`, `Mod`, `Mul`, `Sub`, `Compare`)

`Chr`, `Ord`, `Lower`, `Upper`

`Explode`, `Implode`, `Numb`, `Symb`, `Implode_Ext`, `Explode_Ext`

`First`, `Last`, `Lenw`

`Type`

`Exit`

`ListOfBuiltin`, `SizeOf`

`Residue`, `<? …>`

`__Step-Drop`

`__Meta_Mu` и особенности метафункций

Расширение `e.DriveInfo`